Hop-by-hop routing algorithms for premium traffic

ABSTRACT

In Differentiated Service (DiffServ) networks, the routing algorithms used by the premium class traffic, due to the high priority afforded to that traffic, may have a significant impact not only on the premium class traffic itself, but on all other classes of traffic as well. The shortest hop-count routing scheme, used in current Internet, turns out to be no longer sufficient in DiffServ networks. This paper studies the problem of finding optimal routes for the premium-class traffic in a DiffServ domain, such that (1) no forwarding loop exists in the entire network in the context of hop-by-hop routing; and (2) the residual bandwidth on bottleneck links is maximized. This problem is called the Optimal Premium-class Routing (OPR) problem. We prove in this paper that the OPR problem is NP-hard.To handle the OPR problem, first, we analyze the strength and weaknesses of two existing algorithms (Widest-Shortest-Path algorithm and Bandwidth-inversion Shortest-Path algorithm). Second, we propose a novel heuristic algorithm, called the Enhanced Bandwidth-inversion Shortest-Path (EBSP) algorithm. We prove theoretically the correctness of the EBSP algorithm, i.e., we show that it is consistent and loop-free. Our extensive simulations in different network environments show clearly that the EBSP algorithm performs better when routing the premium traffic in complex, heterogeneous networks.

REFERENCES

• 1: G. Apostolopoulos, D. Williams, S. Kamat, R. Guerin, A. Orda, and T. Przygienda. QoS Routing Mechanisms and OSPF Extensions. RFC 2676, Aug. 1999.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: S. Chen and K. Nahrstedt. An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions. IEEE Network, Special Issue on Transmission and Distribution of Digital Video, Nov./Dec. 1998.
• 4: Distributed QoS Routing with Imprecise State Information, Proceedings of the International Conference on Computer Communications and Networks, p.614, October 12-15, 1998
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: S. et. al. An Architecture for Differentiated Services. RFC 2475, December 1998.
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: J. Jaffe. Bottleneck flow control. IEEE Transactions on Communication, 29:954--962, 1981.
• 9: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 10: Jon Kleinberg , Eva Tardos , Yuval Rabani, Fairness in Routing and Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.568, October 17-18, 1999
• 11: K.Nichols, V.Jacobson, and L.Zhang. A Two-bit Differentiated Services Architecture for the Internet. RFC 2638, July 1999.
• 12: M. Kodialam and T. Lakshman. Minimum Interference Routing with Applications to MPLS Traffic Engineering. In Proceedings of IEEE Infocom 2000, March 2000.
• 13: Stavros G. Kolliopoulos , Clifford Stein, Improved Approximation Algorithms for Unsplittable Flow Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.426, October 19-22, 1997
• 14: J. Lenstra, D. Shmoys, and E. Tardos. Approximation algorithms for scheduling unrelated parallel machines. In 28th IEEE FOCS, 1987.
• 15: Qingming Ma , P. Steenkiste, On path selection for traffic with bandwidth guarantees, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.191, October 28-31, 1997
• 16: Q. Ma and P. Steenkiste. Supporting Dynamic Inter-Class Resource Sharing: A Multi-class QoS Routing Algorithm. In IEEE Proceedings of INFOCOM '99, pages 649--660, 1999.
• 17: 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
• 18: I. Matta and A. U. Shankar. Type-of-Service Routing in Datagram Delivery Systems. IEEE Journal of Selected Areas in Communications, 13(8), October 1995.
• 19: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 20: Piet Van Mieghem , Hans De Neve , Fernando Kuipers, Hop-by-hop quality of service routing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.37 n.3-4, p.407-423, November 5, 2001 [doi>10.1016/S1389-1286(01)00222-5]
• 21: M.May, J.C.Bolot, C.Diot, and A.Jean-Marie. Simple Performance Models of Differentiated Services Schemes for the Internet. In Proceedings of IEEE Infocom 1999, March 1999.
• 22: Ariel Orda, Routing with end-to-end QoS guarantees in broadband networks, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.365-374, June 1999 [doi>10.1109/90.779205]
• 23: A. Orda and A. Sprintson. QoS Routing: the Precomputation Perspective. In Proceedings of IEEE Infocom 2000, March 2000.
• 24: 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
• 25: J. Sobrinho. Algebra and algorithms for QoS path computation and hop-by-hop routing in the Internet. In IEEE INFOCOM 2001, Anchorage, Alaska, pages 727 -- 735, April 2001.
• 26: J. Wang and K. Nahrstedt. Hop-by-Hop Routing Algorithms For Premium-class Traffic In DiffServ Networks. In Proceedings of IEEE Infocom 2002, June 2002.
• 27: Jun Wang , Ying Wang , Klara Nahrstedt, Quantitative Study of Differentiated Service Model Using UltraSAN, University of Illinois at Urbana-Champaign, Champaign, IL, 2001
• 28: L. Xiao, J. Wang, and K. Nahrstedt. The Enhanced Ticket-based Routing Algorithm. In Proceedings of IEEE ICC 2002, New York, NY USA, April 28 - May 2 2002.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)
      C.2.6 Internetworking
          Subjects: Routers
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Documentation, Performance, Reliability

Keywords:
differentiated service, hop-by-hop routing, premium class, saturate bandwidth