Quality of service based routing: a performance perspective

ABSTRACT

Recent studies provide evidence that Quality of Service (QoS) routing can provide increased network utilization compared to routing that is not sensitive to QoS requirements of traffic. However, there are still strong concerns about the increased cost of QoS routing, both in terms of more complex and frequent computations and increased routing protocol overhead. The main goals of this paper are to study these two cost components, and propose solutions that achieve good routing performance with reduced processing cost. First, we identify the parameters that determine the protocol traffic overhead, namely (a) policy for triggering updates, (b) sensitivity of this policy, and (c) clamp down timers that limit the rate of updates. Using simulation, we study the relative significance of these factors and investigate the relationship between routing performance and the amount of update traffic. In addition, we explore a range of design options to reduce the processing cost of QoS routing algorithms, and study their effect on routing performance. Based on the conclusions of these studies, we develop extensions to the basic QoS routing, that can achieve good routing performance with limited update generation rates. The paper also addresses the impact on the results of a number of secondary factors such as topology, high level admission control, and characteristics of network traffic.

REFERENCES

• 1: R. S. Krupp, "Stabilization of Alternate Routing Networks," in IEEE International Communication Conference, Philadelphia, PA, 1982
• 2: R.J. Gibbens, F. P. Kelly, and P. B. Key, "Dynamic Alternate Routing- Modeling and Behaviour," in Teletrafic Science for New Cost-Effective Systems, Networks and Services, ITC-12, Elsevier Science Publishers, 1989
• 3: E. Crawley, R. Nair, B. Rajagopalan, and H. Sandick, "A Framework for QoS-based Routing in the Internet," Internet Draft, QoS Routing Working Group, Internet Engineering Task Force, expires October 1998
• 4: "Interim Inter-Switch Signalling Protocol Version 1," ATM Forum, af-pnni-O055.000, March 1996
• 5: R. Braden, Ed., L. Zhang, S. Berson, S. Herzog, S. Jamin, "Resource ReSerVation Protocol (RSVP) - Version 1 Functional Specification," Request For Comments 2205, Internet Engineering Task Force, September 1997
• 6: H. Ahmadi, J. S.-C. Chen, and R. Gu~rin, "Dynamic Routing and Call Control in High-Speed Integrated Networks", Proc. Proc. Workshop Sys. Eng. Traf. Eng., ITC'13, 1991
• 7: 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
• 8: Roch Guérin , Ariel Orda, QoS-based Routing in Networks with Inaccurate Information: Theory and Algorithms, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.75, April 09-11, 1997
• 9: Z. Wang, and J. Crowcroft, "Quality of Service Routing for Supporting Multimedia Applications," IEEE Journal Selected Areas in Communications, 14(7):1228- 1234, 1996
• 10: W. C. Lee, M. G. Hluchyj, and P. A. Humblet, "Routing Subject to Quality of Service Constraints in Integrated Communication Networks," IEEE Networks, pages 46- 55, July/August 1995
• 11: R. Widyonon, "The Design and Evaluation of Routing Algorithms for real-time Channels," Technical Report TR-94-024, University of California at Berkeley, June 1994
• 12: V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, "Two Distributed Algorithms for the Constrained Steiner Tree Problem," in proceedings of 2nd International Conference on Computer Communication and Networking, pages 343-349, 1993
• 13: R. Gu~rin, D. Williams, and A. Orda, "QoS Routing Mechanisms and QSPF extensions," in proceedings of GLOBECOM, 1997
• 14: A. Shaikh, J. Rex. ford, and K. Shin, "Dynamics of quality-of-service routing with inaccurate link-state information," University of Michigan Technical Report CSE-TR-350-97, November 1997
• 15: J. Moy, "OSPF Version 2,' Request For Comments 2178, Internet Engineering Task Force, July 1997
• 16: C. Alaettinoglu, A. U. Shankar K. Dussa-Zieger, and I. Matta. "Design and Implementation of MARS: A Routing Testbed," Journal of Internetworking Research and Experience, 5(1):17-41, 1994

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

General Terms:
Design, Measurement, Performance

Keywords:
QoS routing, link state routing, path pre-computation, performance evaluation