Title: Scheduling Flows with Unknown Sizes: Approximate Analysis

Author: Liang Guo and Ibrahim Matta

Date: March 21, 2002

Abstract:

Previous studies have shown that giving preferential treatment to
short jobs helps reduce the average system response time, especially
when the job size distribution possesses the heavy-tailed
property. Since it has been shown that the TCP flow length
distribution also has the same property, it is natural to let short
TCP flows enjoy better service inside the network.  Analyzing such
discriminatory system requires modification to traditional job
scheduling models since usually network traffic managers do not have
detailed knowledge about individual flows such as their lengths.  The
Multi-Level (ML) queue, proposed by Kleinrock, can be used to
characterize such system.  In an ML queueing system, the priority of a
flow is reduced as the flow stays longer.  We present an approximate
analysis of the ML queueing system to obtain a closed-form solution of
the average system response time function.  We show that the response
time of short flows can be significantly reduced without penalizing
long flows.