From braden@venera Mon Oct 5 08:43:44 1987
Return-Path: van@lbl-csam.arpa
Posted-Date: Mon, 05 Oct 87 04:48:45 PDT
Received-Date: Mon, 5 Oct 87 04:48:23 PDT
Received: from LBL-CSAM.ARPA by venera.isi.edu (5.54/5.51)
id AA14560; Mon, 5 Oct 87 04:48:23 PDT
Received: by lbl-csam.arpa (5.58/1.18)
id AA22943; Mon, 5 Oct 87 04:48:47 PDT
Message-Id: <8710051148.AA22943@lbl-csam.arpa>
To: braden
Cc: end2end-tf@venera.isi.edu
Subject: Re: Next meeting
In-Reply-To: Your message of Fri, 18 Sep 87 12:29:13 PDT.
Date: Mon, 05 Oct 87 04:48:45 PDT
From: Van Jacobson
Status: RO
Bob -
My apologies for the long silence. For the past several weeks
I've been out with a back problem. The doctor and I still don't
agree on the wisdom of a cross-country plane trip but I've been
looking forward to this meeting and have made the reservations
anyway.
I'm eager to hear any results from Jon or the BBN SATNET group
on the new TCP's behavior. I've been doing some multi-host,
multi-simultaneous-conversation tests to study the stability,
fairness, and range/rate of adaptation of the dynamic window
stuff. So far it looks pretty good, even when the sum of the
window sizes exceeds the intermediate gateway buffer capacity
by an order of magnitude. In fact, in the most recent test I
tried 8 simultaneous transfers between 8 different machines (2
conversations per machine pair) across the LBL-UCB uwave link
(a 230.4Kbs IP gateway connecting 10Mbps ethernets on each side).
All the transfers were using 32KB windows but the gateway allocates
only 25KB of buffer to the slow link. I.e., any single conversation
could exceed the gateway buffer capacity. All the transfers
worked perfectly, with an average drop rate of < 1% (as usual,
we use packet drops to drive the window adaptation). The
bandwidth distribution wasn't "fair" but I expected that: I don't
see any way to guarantee fairness at the tcp endpoints (but I
think I see easy, stateless, ways to guarantee it at the
intermediate IP gateways). Of course, I have no idea how these
tests relate to real network conditions. Thus some SATNET trace
data would be welcome.
I think I've also made some progress in understanding packet
clumping, both analytically and intuitively. I was having lunch
with one of our mathematicians and described some traces of
gateway queue length vs. time. When I complained that I hadn't
been able to find any analytic explanation for the behavior, she
looked at me as if I were retarded and asked ``Does the behavior
occur when rho is around .5?'' ``Yes.'' ``Does it occur when the
maximum node degree is 2?'' ``I've only observed it happening in
more complex networks.'' ``Then it's obvious: The large rho means
you're exceeding the sound-speed of the medium. At high
viscosity, the Fokker-Planck equation has no time-invariant
solutions when the system dimensionality is greater than one.
You're just seeing turbulence.''
It looks like she was right: Any textbook on turbulent flow
shows patterns that are similar to my gateway queue traces. What
was better (for me), the textbooks give a fairly intuitive description
of how the system topology and geometry generate the flow pattern.
Another piece that may have fallen into place has to do with Source
Quenches: A year ago when I was looking in gateway traces
for the effects of SQ, I was puzzled by the fact that an SQ was almost
always sent to the wrong guy. E.g., if you had one host hitting
the gateway with a 16KB window and a bunch of other hosts hitting it
with 2KB windows, gateway SQ's almost always went to the 2KB guys.
A couple of months ago there was an article in Phys. Rev. Letters
about why small pieces always sink to the bottom of the Potato Chip or
Cookie bag (a very important problem for today's physicists). It
turns out that the math that describes why this happens also predicts
that Source Quench will almost always be mis-directed to the good guys
(if tcp conversations are fairly long-lived).
At the last meeting I claimed that tcp timer backoff had to be
exponential, as opposed to constant or linear, to guarantee
stability of the network (where "stability" means that there is no
new-connection arrival rate and/or no mis-estimate of rtt that
will drive the network into congestive collapse). The claim was
based on the way you prove stability for a stochastic system
(Lyapunov's Indirect Method) and I though it would be easy to
prove. Prue & Postel's reply to my SQuID note spurred me to
complete the proof. Proving that constant backoff is unstable
is trivial. Linear backoff is stable under rtt mis-estimates
but goes unstable if the new-connection arrival rate is high
enough (several good proofs of this were done for ALOHA networks.
I just copied one of them, changing "ether" to "IP gateway" where
appropriate). I have (had?) a proof that exponential backoff is
stable under any conditions as long as the total, potential number
of connections is finite. Then I read "Ultimate Instability of
Exponential Back-Off Protocol for Acknowledgment-Based Transmission
Control of Random Access Communication Channels" by D.J.Aldous
in the March,'87 IEEE Transactions on Information Theory. Back
to the drawing board. I think Aldous is using an infinite user
population and my proof is valid for real networks but I'm not
sure yet. It may be that nothing works under all conditions.
(But exponential backoff works better than any of the alternatives).
I've put together an X-windows based graphing tool that's proved
to be very useful for looking at all this protocol trace data.
If there was any interest, and if there were a Sun or Microvax
running V10 of X handy, I could demo this on the multi-conversation
stability data (and I'd be glad to give a copy to anyone who wants it).
I'd also like to talk to Dave Clark, Lixia, Mark Lambert, or some
appropriate person about that frequency doubling scheme for adaptive
NETBLT that we talked about after the end2end teleconference. I
don't think it will work but it would be real interesting try it,
get a trace, and see exactly how it fails.
See you in Cambridge.
- Van