Free-Drop TCP

ABSTRACT

We introduce a new class of TCP congestion control algorithms that take a non-standard approach: instead of modifying AIMD parameters or exploiting traffic measurements, the new protocols modify the rule for deciding when to cut the congestion window. The class is defined by an additional window with a packet-count parameter w; the congestion window is reduced by half when a packet loss is detected, at time t say, if and only if there has been at least one dropped packet in the last w packet transmissions prior to time t. An algorithm in the class is called Free-Drop TCP, since dropped packets are "free" (they do not cause cuts in the window size) unless they are sufficiently bursty. We propose this new class as a means to achieve high utilizations in high bandwidth-delay product networks with small buffers. We analyze a fluid model which leads to explicit estimates of the average throughput for small loss probabilities. We then give the results of experiments, which show that, relative to TCP, a family of 'shifted' response functions of the form O(1/√p - ε) can be obtained over a wide range of p by suitably varying w. Potential costs of these increases in throughput are also examined in terms of coefficents of variation and Jain's fairness measure. The costs range from negligible to moderate.

REFERENCES

• 1: Y. Baryshnikov, E. Coffman, J. Feng, and P. Momcilovic. Asymptotic analysis of a nonlinear AIMD algorithm. Discrete Mathematics and Theoretical Computer Science, pages 27--38, 2005. In proceedings, 2005 International Conference on Analysis of Algorithms, Conrado Martinez (ed.).
• 2: Yu Gu, Don Towsley, Chris Hollot, and Honggang Zhang. Congestion control for small buffer high speed networks. Technical Report 06--14, UMass Amherst Computer Science Department, 2006.
• 3: S. Ha, Y. Kim, L. Le, I. Rhee, and L. Xu. A step toward realistic evaluation of high-speed tcp protocols.
• 4: R. Jain, A. Durresi, and G. Babic. Throughput fairness index: An explanation. ATM Forum/99--0045, Feb. 1999.
• 5: C. Jin, D. Wei, and S. Low. Fast tcp: Motivation, architecture, algorithms, performance. In Proceedings of IEEE INFOCOM, 2004. citeseer.ist.psu.edu/jin04fast.html.
• 6: D. Leith and R. Shorten. Analysis and design of synchronised communication networks. Automatica, 41:725--730, 2005.
• 7: V. Misra, W. B. Gong, and D. Towsley. Stochastic differential equation modeling and analysis of tcp windowsize behavior. In IFIP WG7.3 Performance, November 1999.
• 8: T. J. Ott, J. Kemperman, and M. Mathis. The stationary behavior of ideal TCP congestion avoidance. August 1996.
• 9: Jitendra Padhye , Victor Firoiu , Donald F. Towsley , James F. Kurose, Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.133-145, April 2000 [doi>10.1109/90.842137]