Stability of end-to-end algorithms for joint routing and rate control

ABSTRACT

Dynamic multi-path routing has the potential to improve the reliability and performance of a communication network, but carries a risk. Routing needs to respond quickly to achieve the potential benefits, but not so quickly that the network is destabilized. This paper studies how rapidly routing can respond, without compromising stability.We present a sufficient condition for the local stability of end-to-end algorithms for joint routing and rate control. The network model considered allows an arbitrary interconnection of sources and resources, and heterogeneous propagation delays. The sufficient condition we present is decentralized: the responsiveness of each route is restricted by the round-trip time of that route alone, and not by the round-trip times of other routes. Our results suggest that stable, scalable load-sharing across paths, based on end-to-end measurements, can be achieved on the same rapid time-scale as rate control, namely the time-scale of round-trip times.

REFERENCES

• 1: M. Beckmann, C.B. McGuire and C.B. Winsten. Studies in the Economics of Transportation. Cowles Commission Monograph, Yale University Press, 1956.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 3: M. Chiang. Balancing transport and physical layers in wireless multihop networks: jointly optimal congestion control and power control. IEEE J. Sel. Areas Comm., 23:104--116, 2005.
• 4: Jon Crowcroft , Richard Gibbens , Frank Kelly , Sven Östring, Modelling incentives for collaboration in mobile ad hoc networks, Performance Evaluation, v.57 n.4, p.427-439, August 2004 [doi>10.1016/j.peva.2004.03.003]
• 5: C.A. Desoer and Y.T. Yang. On the generalized Nyquist stability criterion. IEEE Transactions on Automatic Control, 25:187--196, 1980.
• 6: S.J. Golestani. A Unified Theory of Flow Control and Routing in Data Communication Networks. PhD thesis, MIT, Dept. of Electrical Engineering and Computer Science, Cambridge, MA, 1980.
• 7: H. Han, S. Shakkottai, C. Hollot, R. Srikant, and D. Towsley. Overlay TCP for multi-path routing and congestion control. In ENS-INRIA ARC-TCP Workshop, Paris, France, 2003.
• 8: O.L.R. Jacobs. Introduction to Control Theory. Oxford University Press, Oxford, 1993.
• 9: V. Jacobson, Congestion avoidance and control, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.314-329, August 1988
• 10: Ramesh Johari , David Kim Hong Tan, End-to-end congestion control for the internet: delays and stability, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.818-832, December 2001 [doi>10.1109/90.974534]
• 11: D.B. Johnson and D.A. Maltz. Dynamic source routing in ad hoc wireless networks. In T. Imielinski and H. Korth, editors, Mobile Computing, 153--181. Kluwer, 1996.
• 12: F. Kelly. Fairness and stability of end-to-end congestion control. European Journal of Control, 9:159--176, 2003.
• 13: F.P. Kelly, A.K. Maulloo, and D.K.H. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.
• 14: Tom Kelly, Scalable TCP: improving performance in highspeed wide area networks, ACM SIGCOMM Computer Communication Review, v.33 n.2, April 2003 [doi>10.1145/956981.956989]
• 15: T. Kelly. Engineering Flow Controls for the Internet. PhD thesis, Department of Engineering, University of Cambridge, 2004. http://www-lce.eng.cam.ac.uk/~ctk21/papers/
• 16: L. Massoulié. Stability of distributed congestion control with heterogeneous feedback delays. IEEE Transactions on Automatic Control, 47:895--902, 2002.
• 17: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 18: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 19: Fernando Paganini , Zhikui Wang , John C. Doyle , Steven H. Low, Congestion control for high performance, stability, and fairness in general networks, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.43-56, February 2005 [doi>10.1109/TNET.2004.842216]
• 20: Antonis Papachristodoulou , Lun Li , John C. Doyle, Methodological frameworks for large-scale network analysis and design, ACM SIGCOMM Computer Communication Review, v.34 n.3, July 2004 [doi>10.1145/1031134.1031138]
• 21: Ashwin Sridharan , Roch Guérin , Christophe Diot, Achieving near-optimal traffic engineering solutions for current OSPF/IS-IS networks, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.234-247, April 2005 [doi>10.1109/TNET.2005.845549]
• 22: Rayadurgam Srikant, The Mathematics of Internet Congestion Control (Systems and Control: Foundations and Applications), SpringerVerlag, 2004
• 23: G. Vinnicombe. On the stability of networks operating TCP-like congestion control. Proc. IFAC World Congress, Barcelona, Spain 2002.
• 24: G. Vinnicombe. Robust congestion control for the Internet. 2002.
• 25: T. Voice. Delay stability results for congestion control algorithms with multi-path routing. 2004. http://www.statslab.cam.ac.uk/~tdv20
• 26: Zheng Wang , Jon Crowcroft, Analysis of shortest-path routing algorithms in a dynamic network environment, ACM SIGCOMM Computer Communication Review, v.22 n.2, p.63-71, April 1992 [doi>10.1145/141800.141805]
• 27: J.G. Wardrop. Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, 1:325--378, 1952.
• 28: S. Yilmaz and I. Matta. On the scalability-performance tradeoffs in MPLS and IP routing. In Proceedings of SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks, Boston, MA, 2002.
• 29: Dapeng Zhu , Mark Gritter , David R. Cheriton, Feedback based routing, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.71-76, January 2003 [doi>10.1145/774763.774774]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Theory

Keywords:
dynamic routing, internet, scalable TCP