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