[e2e] [Fwd: RED-->ECN]

[Michael B Greenwald]

   Thu, 01 Feb 2001 16:39:44 -0800
   Fred Baker <fred at cisco.com>

   At 08:40 AM 2/1/01 -0500, Michael B Greenwald wrote:
   >If the input rate is less than the
   >output rate, then (independent of variations in inter-arrival time) the
   >queue length is 0 -- always empty.  For an arbitrarily low *average* input
   >rate, and a long enough interval, and an unbounded queue, I can construct
   >an arrival schedule that will cause an arbitrarily high *average* queue
   >length.
   
   who told you that?

No one; it is trivially true (and rather uninteresting, and irrelevant
except as a pedagogic example showing that avg qlen is not *purely* a
function of input and output rates; qlen is also a function of the
burstiness).  I think you may have misread what I wrote because (a) what
you write below doesn't contradict what I said --- it's just orthogonal to
it, and (b) I never said anything about a step function.  The fault may be
mine because I thought I was quickly dashing off an obvious point, and in
my haste I was probably unclear.

If the max input rate is lower than the *constant* output rate, then I
can't produce any queue size at all (because whenever a packet arrives, the
previous packet was already drained from the queue), so it is
uninteresting.  If the avg input rate is higher than the avg output rate,
the queue length grows without bound, so it is also uninteresting.  But,
assuming the max input burst rate exceeds the constant output rate, and the
avg input rate is less than the avg output rate, then no matter what
non-zero avg input and output rates you give me, I can produce a
*particular* schedule in which the average queue length can be any size Q
you desire (provided the queue was unbounded and I could look at the queue
over a long enough time interval).

Let the output process drain the queue at a constant rate O, and let the
input process deliver bursts at rate I, producing a burst every t time
units.  Burst size must = I*t.  Assume this results in an avg qlen of q.
Send a burst of size (Q/q)I*t every (Q/q)*t time units, this will result in
avg qlen of Q for input rate I and output rate O.

As I said, these are unrealistic examples, intended only to quibble with
the message that asserted that average queue length was purely a
function of input rates (actually, they said "utilization"). 
   
   I think you'll find that with any distribution, mean queue depth is not a 
   binary flip-flop between zero and infinity. With poisson distributions 
   (M/M/1) and a ratio if input rate to output rate of p and mean service 
   interval m, Kleinrock tells me that the average time in queue (which is to 
   say mean queue depth including the packet itself)
   
                 p/m
            W = -----
                1 - p
   
   and in the general case
   
                 average remaining service time
            W = --------------------------------
                            1 - p
   
   That's far from a step function.