Optimal scheduling and routing for maximum network throughput

ABSTRACT

In this paper we consider packet networks loaded by admissible traffic patterns, i.e., by traffic patterns that, if optimally routed, do not overload network resources. We prove that simple distributed dynamic routing and scheduling algorithms based upon link state information can achieve the same network throughput as optimal centralized routing and scheduling algorithms with complete traffic information.

Our proofs apply the stochastic Lyapunov function methodology to a flow-level abstract model of the network, and consider elastic traffic, i.e., we assume that flows can adapt their transmission rates to network conditions, thus resembling traffic engineering and quality-of-service approaches being currently proposed for IP networks.

Although the paper mainly brings a theoretical contribution, such dynamic routing and scheduling algorithms can be implemented in a distributed way. Moreover we prove that maximum throughput is achieved also in case of temporary mismatches between the actual links state and the link state information used by the routing algorithm. This is a particularly relevant aspect, since any distributed implementation of a routing algorithm requires a periodic exchange of link state information among nodes, and this implies delays, and thus time periods in which the current link costs are not known.

REFERENCES

• 1: João Luís Sobrinho, Algebra and algorithms for QoS path computation and hop-by-hop routing in the internet, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.541-550, August 2002 [doi>10.1109/TNET.2002.801397]
• 2: João Luis Sobrinho, Network routing with path vector protocols: theory and applications, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863963]
• 3: George Apostolopoulos , Roch Guérin , Sanjay Kamat , Satish K. Tripathi, Quality of service based routing: a performance perspective, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.17-28, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 4: Anees Shaikh , Jennifer Rexford , Kang G. Shin, Load-sensitive routing of long-lived IP flows, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.215-226, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 5: G. Apostolopoulos , S. Kama , D. Williams , R. Guerin , A. Orda , T. Przygienda, QoS Routing Mechanisms and OSPF Extensions, RFC Editor, 1999
• 6: [6] L. Fratta, M. Gerla, and L. Kleinrock, "The flow deviation method--An approach to the store-and-forward communication network design," Networks, vol. 3, pp. 97-133, 1973.
• 7: [7] Z. Wang, Y. Wang, and L. Zhang, "Internet traffic engineering without full mesh overlaying," in Proc. IEEE INFOCOM 2001, Anchorage, AK, Apr. 2001, vol. 1, pp. 565-571.
• 8: 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]
• 9: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 10: [10] Z. Wang and J. Crowcroft, "QoS routing for supporting multimedia applications," IEEE J. Sel. Areas Commun., vol. 14, no. 7, pp. 1228-1234, Sep. 1996.
• 11: Qingming Ma , Peter Steenkiste , Hui Zhang, Routing high-bandwidth traffic in max-min fair share networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.206-217, August 28-30, 1996, Palo Alto, California, United States
• 12: C. Casetti , R. Lo Cigno , M. Mellia , M. Munafò , Z. Zsóka, A new class of QoS routing strategies based on network graph reduction, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.41 n.4, p.475-487, 15 March 2003 [doi>10.1016/S1389-1286(02)00414-0 ]
• 13: Anindya Basu , Alvin Lin , Sharad Ramanathan, Routing using potentials: a dynamic traffic-aware routing algorithm, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863962]
• 14: E. Rosen , A. Viswanathan , R. Callon, Multiprotocol Label Switching Architecture, RFC Editor, 2001
• 15: [15] S. P. Meyn and R. Tweedie, Markov Chain and Stochastic Stability. New York: Springer-Verlag, 1993.
• 16: [16] M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," in Proc. IEEE INFOCOM 2003, San Francisco, CA, Apr. 2003, pp. 745-755.
• 17: Srisankar Kunniyur , R. Srikant, End-to-end congestion control schemes: utility functions, random losses and ECN marks, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.689-702, October 2003 [doi>10.1109/TNET.2003.818183]
• 18: Dina Katabi , Mark Handley , Charlie Rohrs, Congestion control for high bandwidth-delay product networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 19: 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]
• 20: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 21: [21] M. Bramson, "Instability of FIFO queueing networks," Ann. Appl. Probab., vol. 4, pp. 414-431, 1994.
• 22: R. J. Williams, An invariance principle for semimartingale reflecting Brownian motions in an orthant, Queueing Systems: Theory and Applications, v.30 n.1-2, p.5-25, 1998
• 23: Maury Bramson, State space collapse with application to heavy traffic limits for multiclass queueing networks, Queueing Systems: Theory and Applications, v.30 n.1-2, p.89-148, 1998
• 24: [24] H. C. Gromoll, "Diffusion approximation for a processor sharing queue in heavy traffic," Ann. Appl. Prob., vol. 14, pp. 555-611, 2004.
• 25: [25] E. Leonardi, M. Mellia, M. Ajmone Marsan, and F. Neri, "Joint optimal scheduling and routing for maximum network throughput," in Proc. IEEE INFOCOM 2005, Miami, FL, Jun. 2005, pp. 819-830.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
Lyapunov methods, asymptotic stability, computer network performance