[e2e] VJ re: Why small pieces sink to the bottom of the bag

[Craig Partridge]

Here's the note I mentioned.  It turns out to be a private note to a
few folks in response to a question I asked Van.  But I believe the
note has been circulated more widely in the past, so I'll risk resending
it now.  (I owe Van some good brandy if he's displeased -- I still find
the note useful reading 18 years later).

Craig

E-mail: craig at aland.bbn.com or craig at bbn.com

------- Forwarded Message

To: Craig Partridge <craig at NNSC.NSF.NET> ...
Subject: Re: Why small pieces sink to the bottom of the bag 
In-Reply-To: Your message of Mon, 05 Oct 87 12:32:10 D.
Date: Tue, 06 Oct 87 02:54:30 PDT
From: Van Jacobson <van at lbl-csam.ARPA>

Craig -

I suspect I'd need to draw some pictures to come up with a convincing
explanation.  Maybe we can find some time at the task force meeting
to sit down together and sketch what I think is happening (preferably
with a bottle of brandy nearby to lubricate our intuition).  In the
interim, I'll try to confuse the issue with some words.

After looking at lots of trace data, I've started to picture time
at a gateway as being divided into fairly distinct buckets.  Those
sawtooth patterns of rtt vs. t say that a gateway operates by 
accumulating packets for a while, sending none of them, then suddenly
sends them as fast as it can, then goes back to accumulating.  (The
start of each accumulation cycle is just after the rtt takes its
big jump up.)  Both inspection and fourier analysis say that the
jumps up happen at approximately equal intervals so you can view
this as a constant, periodic structure and ask if there's any
fine structure in it.

The question is interesting because the "phase" of packet arrivals
with respect to the start of the accumulation cycle determines
the drop probability:  A packet that arrives early in the cycle has
a low probability of being dropped (since little has been accumulated
and the queues are empty) and a packet that arrives late in the 
cycle has a high drop probability (if the traffic intensity is on
the order of the available buffering).  One can now ask two questions:
1) Do clumps of packets from the same tcp conversation tend to stay
close together in time? (If the answer is yes, we will see clumps
of packets on the order of the conversation's window size in the
queue.  If no, packets from different conversations will be randomly
intermixed, per-conversation "phase" won't have any meaning, and
drop probability will simply increase with window size).  2) If
the answer to (1) is yes, is there any process that migrates clumps
based on their size?

>From experimental data, the answer to (1) is yes, packets from
the same conversation tend to stay together and gateway queues
are very stratified.  The "force" that drives this seems to be
that most protocol implementations are more efficient processing
bursts of packets than isolated packets (partly because of fewer
boundary crossings / context switches and partly because of
delayed acks).  This means that if the 2nd packet of a burst and
an isolated packet pop out of the receiver-side gateway at about
the same time, the ack for the burst packet makes it back first. 
This means that on the next round, the burst packet is ahead 
(earlier) in the gateway queue.  Thus bursts tend to move to the
front (empty queue) part of the cycle and isolated packets toward
the tail (full queue) part.  (I have actual data that shows this
happening: If the conversations go on long enough, the queue in
the gateway gets perfectly sorted into descending window size
order.)

So, getting back to cookies, necessary and sufficient conditions
for the stratification that Phys Rev talked about to occur are
 1) a well defined container (the cookie box; an accumulation cycle)
 2) different size pieces (whole and broken cookies; different window
    sizes)
 3) a "force" that defines "up" and "down" for the container (gravity;
    the "surface tension" that keeps packets of a burst together 
    combined with the exclusion principle that says two packets
    can't occupy the same slot in the queue).
All the conditions hold (if the conversations are long enough for
the relatively weak "clumping" force to have time to organize the
queue) so you end up with the small pieces at the bottom.  I.e.,
packets from the small-window conversations tend to arrive after
the big-window conversations have filled the queue.  Thus the
small window guys preferentially get SQ'd and dropped.

Hope that confuses things.

 - Van

------- End of Forwarded Message