TCP-Illinois: a loss and delay-based congestion control algorithm for high-speed networks

ABSTRACT

We introduce a new congestion control algorithm, called TCP-Illinois, which has many desirable properties for implementation in (very) high-speed networks. TCP-Illinois is a sender side protocol, which modifies the AIMD algorithm of the standard TCP (Reno, NewReno or SACK) by adjusting the increment/decrement amounts based on delay information. By using both loss and delay as congestion signals, TCP-Illinois achieves a better throughput than the standard TCP for high-speed networks. To study its fairness and stability properties, we extend recently developed stochastic matrix models of TCP to accommodate window size backoff probabilities that are proportional to arrival rates when the network is congested. Using this model, TCP-Illinois is shown to allocate the network resource fairly as in the standard TCP. In addition, TCP-Illinois is shown to be compatible with the standard TCP when implemented in today's networks, and is shown to provide the right incentive for transition to the new protocol. We finally perform ns-2 simulations to validate its properties and demonstrate its performance.

References

1. J. Ahn, P. Danzig, Z. Liu, and L. Yan. Experience with TCP vegas: Emulation and experiment. In Proceedings of ACM SIGCOMM, 1995.
2. F. Baccelli and D. Hong. The AIMD model for TCP sessions sharing a common router. In Proceedings of 39th Annual Allerton Conf. on Communication, Control and Computing, October 2001.
3. A. Berman and R. Plemmons. Nonnegative Matrices in the Mathematical Sciences. SIAM, 1979.
4. S. Biaz and N. Vaidya. Is the round-trip time correlated with the number of packets in flight. In Proceedings Internet Measurement Conference (IMC), October 2003.
5. L. Brakmo, S. O'Malley, and L. Peterson. TCP vegas: New techniques for congestion detection and avoidance. In Proceedings of ACM SIGCOMM Symposium, pages 24--35, August 1994.
6. S. Floyd. Highspeed TCP for large congestion windows. Internet draft, draft-floyd-tcp-highspeed-01.txt, December 2003, Available at http://www.icir.org/floyd/hstcp.html.
7. S. Floyd and T. Henderson. The new reno modification to TCPs fast recovery algorithm. RFC 2582, 1999.
8. A. Graham. Nonnegative Matrices and Applicable Topics in Linear Algebra. Ellis Horwood Limited, Chichester, England, 1987.
9. V. Jacobson. Congestion avoidance and control. ACM Computer Communication Review, 18:314--329, August 1988.
10. V. Jacobson. Berkeley TCP evolution from 4.3-tahoe to 4.3-reno. In Proceedings of the Eighteenth Internet Engineering Task Force, July 1990.
11. C. Jin, D. Wei, S. H. Low, G. Buhrmaster, J. Bunn, D. H. Choe, R. L. A. Cottrell, J. C. Doyle, W. Feng, O. Martin, H. Newman, F. Paganini, S. Ravot, and S. Singh. FAST TCP: From theory to experiments, April 2003.
12. D. Katabi, M. Handley, and C. Rohrs. Congestion control for high bandwidth-delay product networks. In Proceedings on ACM Sigcomm, 2002.
13. T. Kelly. On engineering a stable and scalable TCP variant. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.435, June 2002.
14. D. Leith and R. Shorten. Analysis and design of synchronised communication networks. Automatica, 41:725--730, 2005.
15. D. Leith, R. Shorten, and Y. Li. H-TCP: A framework for congestion control in high-speed and long-distance networks. HI Technical Report, August 2005. Available at http://www.hamilton.ie/net/htcp/.
16. S. Liu, T. Başar, and R. Srikant. TCP-illinois: A delay and loss-based congestion control algorithm for high-speed networks. Technical Report, UIUC, 2006. Available at http://www.ews.uiuc.edu/~shaoliu/tcpillinois_full.pdf.
17. J. Martin, A. A. Nilsson, and I. Rhee. Delay-based congestion avoidance for TCP. IEEE/ACM Transactions on Networking, pages 356--369, June 2003.
18. M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow. TCP selective acknowledgement options. RFC 2018, April 1996, available at http://www.icir.org/floyd/sacks.html.
19. J. Mo, R. J. La, V. Anantharam, and J. C. Walrand. Analysis and comparison of TCP reno and vegas. In Proceedings of IEEE INFOCOM, 1999.
20. J. Padhye, V. Firoiu, D. Towsley, and J. Kurose. Modeling TCP throughput: A simple model and its empirical validation. In Proceedings of ACM SIGCOMM, 1998.
21. R. S. Prasad, M. Jain, and C. Dovrolis. On the effectiveness of delay-based congestion avoidance. In Proceedings of Second International Workshop on Protocols for Fast Long-Distance Networks, 2004.
22. W. Stevens. TCP/IP Illustrated, Vol.1 The Protocols. Addison-Wesley, 1994.
23. K. Tan, J. Song, Q. Zhang, and M. Sridharan. A compound TCP approach for high-speed and long distance networks. In Proceedings of IEEE Infocom, April 2006.
24. A. Tang, J. Wang, S. Low, and M. Chiang. Equilibrium of heterogeneous congestion control protocols. In Proceedings of IEEE Infocom, Miami, FL, March 2005.
25. F. Wirth, R. Stanojevic, R. Shorten, and D. Leith. Stochastic equilibria of AIMD communication networks. Accepted by SIAM J. Matrix Analysis and its Applications, 2005. Available at http://www.hamilton.ie/chris/SIMAX_july28.pdf.
26. L. Xu, K. Harfoush, and I. Rhee. Binary increase congestion control for fast long-distance networks. In Proceedings of IEEE INFOCOM, 2004.
27. A. Zanella, G. Procissi, M. Gerla, and M. Y. Sanadidi. TCP westwood: Analytic model and performance evaluation. In Proceedings of IEEE Globecom, 2001.

Index Terms

• Networks

  • Network protocols