Rate-based Pacing Description

This web page attemptes to illustrate three TCP slow-start restart algorithms described in ``Improving Restart of Idle TCP Connections''. It is based on a nam animation (see the file ex/rbp_demo.nam in the nam distribution) derived from an ns simulation (see the file tcl/ex/rbp_demo.tcl in the ns distribution).

There are three groups of nodes. Each group has 10 clients (colored circles on the left) and one server (the black circle on the right) joined by two routers (hexagons) and a bottleneck link. The clients make web requests at random times (uniformly distributed around a central point), causing the server to send a burst of 10KB (=10 packets) of data. We do this twice, first at about 9.0s and then again at about 29s.

The point of the experiment is to illustrate TCP behavior after the connection goes idle. It does this by showing a different algorithm in each group of nodes.

The TOP group illustrates ``no slow-start restart'' (NSSR): after an idle period the TCP at node 112 does nothing special and so it sends a window-sized burst of data on the second request. NSSR is the policy implemented by SunOS for all connections and by all BSD-derived TCP's for web style traffic (due to an interaction between idle detection and HTTP-style traffic).

The BOTTOM group illustrates ``slow-start restart'' (SSR): are an idle period, TCP resets itself and does a full slow-start. This is the policy advocated in the appendix of the 1990 revision of Jacobson's paper ``Congestion Avoidance and Control'' (with Mike Karels). Although 4.4BSD implements this policy, it is not used for web traffic because of an interaction between idle detection and HTTP-style traffic.

The MIDDLE group illustrates ``rate-based pacing'' (RBP): a new algorithm proposed in the paper ``Improving Restart of Idle TCP Connections'' by Visweswaraiah and Heidemann.

The animation is broken down into three phases, 9-12s and 29-32s, and 49-54s.

First Phase

In the FIRST PHASE (9-12s), all algorithms should behave identically. They do, for the most part, but as an implementation artifact, RBP sends packets with a slightly different schedule than the other algorithsm. This difference is because RBP (shown here) is based on Vegas while the others are Reno. We plan to redo the simulation with a Reno-based RBP.

Second Phase

In the SECOND PHASE (29-32s), we see clear differences in the algorithms.

We illustrate this second phase with a several snapshots of the animation taken between 29 and 30 seconds.

The first image (time ~29.08s) shows NSSR just beginning to burst (the back-to-back magenta packets on the top set). By contrast, RBP and SSR are both transimitting slowly (compare the two single magenta packets on the bottom two sets).

The next image (time ~29.14s) shows several NSSR bursts (to the magenta, yelow, white, and green clients) that happend at about the same time. As a result, several packet drops can be seen (the two falling white and one green packet). We can also see RBP begin pacing---in the middle set of nodes, we see a second magenta packet before the ACK has returned.

The next image (time ~29.28s) shows the final (of 4) paced magenta packets in the middle set. We can also see the first magenta ACK returning in both of the bottom sets. This ACK will restart the ACK clock for RBP.

In the final iamge (time ~29.36s), the bottom two sets show packets sent in response to the ACKs just mentioned. In addition, we can see a second magenta ACK returning on the RBP section. Pacing not only fills the time between first transmission and ACK, but it primes the ACK clock at a rate closer to steady state than slow start. Finally, we observe some white ACKs returning in the top set. Because of the dropped white packets resulting from the momentary congestion associated with bursting, the NSSR white connection is actually slower than either the RBP or SSR cases. Sending all your data at once does not always improve performance!

We have put all these frames together an animated sequence. (The GIF is ~1.3MB.)

Third Phase

In the THIRD PHASE (59-54s) we have another round of the experiment. This time NSSR has fewer packet drops (4 instead of 12) because the loses in the second phase caused some flows to be less agressive.

Comments?

Comments or suggestions about rate-based pacing are encouraged; send mail to {johnh,visweswa}@isi.edu. These traces are from the RBP implementation in ns-2.0. The simulation is in post-ns-2.0 distributions as tcl/ex/rbp_demo.tcl, or at http://www.isi.edu.
Page maintainer: John Heidemann
Last modified: Wed Dec 17 13:21:05 1997