Removing Exponential Backoff from TCP

Amit Mondal and Aleksandar Kuzmanovic
Appears in: 
CCR October 2008

The well-accepted wisdom is that TCP’s exponential backoff mechanism, introduced by Jacobson 20 years ago, is essential for preserving the stability of the Internet. In this paper, we show that removing exponential backoff from TCP altogether can be done without inducing any stability sideeffects. We introduce the implicit packet conservation principle and show that as long as the endpoints uphold this principle, they can only improve their end-to-end performance relative to the exponential backoff case.

By conducting large-scale simulations, modeling, and network experiments in Emulab and the Internet using a kernellevel FreeBSD TCP implementation, realistic traffic distributions, and complex network topologies, we demonstrate that TCP’s binary exponential backoff mechanism can be safely removed. Moreover, we show that insuitability of TCP’s exponential backoff is fundamental, i.e., independent from the currently-dominant Internet traffic properties or bottleneck capacities. Surprisingly, our results indicate that a path to incrementally deploying the change does exist.

Public Review By: 
Jitendra Padhye

This paper poses an intriguing question: is the exponential backoff in TCP really necessary? The general perception is that the backoff is necessary to maintain the stability of the Internet under extremely heavy congestion. The authors, however, show that exponential backoff is not necessary for maintaining stability, as long as the packet conservation principle is followed.
The paper is well-written, and the evaluation is generally adequate. However, it is not clear to me that we should rush to remove exponential backoff from TCP implementations just yet. The reasons are as follows. First, as the authors themselves point out, their analysis breaks down when the RTT suddenly changes (perhaps due to a routing change) such that the new RTT is greater than the previously calculated RTO. It would be interesting to know how often this occurs.
Second, one of the downsides of removing exponential backoff is that it takes the network longer to recover from heavy congestion. The impact of this extra ``delay’’ should be evaluated carefully.
Third, it is not clear that the benefits of removing exponential backoff are significant. In some of the scenarios discussed in the paper, only a small fraction of the flows see any improvement in performance.
Fourth, the proposed plan for incremental deployment is not satisfactory. Since flows that do not use exponential backoff (TCP*(?)) hurt the performance of flows that use traditional TCP, the authors propose to go in two small steps wherein a less aggressive version (TCP*(3)) is deployed first. However, even this less aggressive version seems to reduce throughput of traditionalflows by 20% or more in some cases. Then, when TCP*(?) is deployed, it seems to affect the performance of TCP*(3) substantially as well! And there may still be some traditional TCP flows left in the network!
Finally, since this change will be perceived as 'drastic,' many more (and large scale) studies will be required to convince audiences such as the IETF to standardize TCP*(?).