An efficient algorithm for finding a path subject to two additive constraints

ABSTRACT

One of the key issues in providing end-to-end quality-of-service guarantees in packet networks is how to determine a feasible route that satisfies a set of constraints while simultaneously maintaining high utilization of network resources. In general, finding a path subject to multiple additive constraints (e.g., delay, delay-jitter) is an NP-complete problem that cannot be exactly solved in polynomial time. Accordingly, heuristics and approximation algorithms are often used to address to this problem. Previously proposed algorithms suffer from either excessive computational cost or low performance. In this paper, we provide an efficient approximation algorithm for finding a path subject to two additive constraints. The worst-case computational complexity of this algorithm is within a logarithmic number of calls to Dijkstra's shortest path algorithm. Its average complexity is much lower than that, as demonstrated by simulation results. The performance of the proposed algorithm is justified via theoretical performance bounds. To achieve further performance improvement, several extensions to the basic algorithm are also provided at low extra computational cost. Extensive simulations are used to demonstrate the high performance of the proposed algorithm and to contrast it with other path selection algorithms.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: A. Alles. ATM internetworking. White Paper, Cisco Systems, Inc., May 1995.
• 3: Y. P. Anej~, V. Aggarwal, and K. P. K. Nair. Shortest chain subject to side constraints. NetworkS, 13:295-302, 1983.
• 4: G. Apostolopoulos et al. QoS routing mechanisms and OSPF extensions. Technical Report dr~t-guerin-qosrouting-ospf-05.txt, Internet Engineering Task Force, April 1998.
• 5: 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
• 6: David Blokh , Gregory Gutin, An Approximation Algorithm for Combinatorial Optimization Problems with Two Parameters, University of Southern Denmark, 1995
• 7: S. Chen and K. N~hrstedt. On finding multiconstrained paths. In Proceedings of the ICC '98 Conference, pages 874-879. IEEE, 1998.
• 8: S. Chen and K. Nahrstedt. An overview of qualityof-service routing for the next generation high-speed networks: Problems and solutions. 1EEE Network, 12(6):64-79, Nov-Dec 1998.
• 9: E. I. Chong, S. R. Sanjeev Rao Maddila, and S. T. Morley. On finding single-source single-destination k shortest paths. In the Seventh International Conference on Computing and Information (ICCI '95}, pages 40- 47, July 5-8, 1995.
• 10: David Clark , Joseph Pasquale, Strategic directions in networks and telecommunications, ACM Computing Surveys (CSUR), v.28 n.4, p.679-690, Dec. 1996 [doi>10.1145/242223.242273]
• 11: Douglas E. Comer, Internetworking with TCP/IP (2nd ed.), vol. I, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 12: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 13: E. Crawley et aJ. A framework for QoS-bazed routing in the Internet. Internet draft, IETF, July 10, 1998. (draft-ie t f-qosr-frame work- 06. txt ).
• 14: H. De Neve and P. Van Mieghem. A multiple quality of service routing algorithm for P NNI. In Proceedings of the ATM Workshop, pages 324- 328. IEEE, May 1998.
• 15: D. Eppstein. Finding the k shortest paths. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 154 - 165. IEEE, Nov. 1994.
• 16: 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
• 17: Roche A. Guérin , Ariel Orda, QoS routing in networks with inaccurate information: theory and algorithms, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.350-364, June 1999 [doi>10.1109/90.779203]
• 18: Search Space Reduction in QoS Routing, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.142, May 31-June 04, 1999
• 19: G. Y. Handler ~nd I. Zang. A dual algorithm for the constrained shortest path problem. Networks, 10:293- 310, 1980.
• 20: Refael Hassin, Approximation schemes for the restricted shortest path problem, Mathematics of Operations Research, v.17 n.1, p.36-42, Feb. 1992 [doi>10.1287/moor.17.1.36]
• 21: Kenji Ishida , Kitsutaro Amano , Naoki Kannari, A Delay-Constrained Least-Cost Path Routing Protocol and the Synthesis Method, Proceedings of the 5th International Conference on Real-Time Computing Systems and Applications, p.58, October 27-29, 1998
• 22: A. Iwata etal. ATM routing algorithms with multiple QOS requirements for multimedia internetworking. 1EICE Trans. Commun., E79-B(8):999-1006, August 1996.
• 23: J. M. Jaffe. Algorithms for finding paths with multiple constraints. Networks, 14:95-116, 1984.
• 24: K. Lee et al. QoS based routing for integrated multimedia services. In Proceedings of the GLOBECOM '97 Conference, volume II, pages 1047-1051. IEEE, 1997.
• 25: W. C. Lee, M. G. Hluchyi, ~nd P. A. ttumblet. Routing subject to quality of service constraints in integrated communication networks. IEEE Network, pages 46-55, July/August 1995.
• 26: 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
• 27: Q. Ma and P. Steenkiste. Routing traffic with qualityof-service guaraxttees in integrated services networks. In Proceedings of NOSSDA V '98, July 1998.
• 28: 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]
• 29: C. Pornavalai , G. Chakraborty , N Shiratori, QoS based routing algorithm in integrated services packet networks, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.167, October 28-31, 1997
• 30: Hussein F. Salama , Douglas S. Reeves , Yannis Viniotis, A Distributed Algorithm for Delay-Constrained Unicast Routing, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.84, April 09-11, 1997
• 31: C. C. Skiscim , B. L. Golden, Solving k-shortest and constrained shortest path problems efficiently, Annals of Operations Research, v.20 n.1-4, p.249-282, Aug. 1989 [doi>10.1007/BF02216932]
• 32: N. Taft-Plotkin, B. Bellur, and R. Ogler. Qualityof-service routing using maximally disjoint paths. In the Seventh International Workshop on Quality o.f Service (IWQoS '99), pages 119- 128, London, England, May/June 1999. IEEE.
• 33: R. Vogel et al. QoS-based routing of multimedia streams in computer networks. IEEE Journal on Selected Areas in Communications, 14(7):1235-1244, September 1996.
• 34: Zheng Wang, On the complexity of quality of service routing, Information Processing Letters, v.69 n.3, p.111-114, Feb. 12, 1999 [doi>10.1016/S0020-0190(98)00206-3]
• 35: Z. Wang and J. Crowcroft. Quality-of-service routing for supporting multimedia applications. IEEE Journal on Selected Areas in Communications, 14(7):1228- 1234, September 1996.
• 36: R. Widyono. The design and evaluation of routing algorithms for real-time channels. Technical Report TR- 94-024, University of California at Berkeley & International Computer Science Institute, June 1994.
• 37: X. Xiao and L. M. Ni. Internet QoS: a big picture. IEEE Network, 13(2):8-18, March-April 1999.
• 38: J. Zhou. A new distributed routing algorithm for supporting delay-sensitive applications. In Proceedings of ICCT '98, pages $37-06(1-7). IEEE, 22-24 Oct. 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
QoS routing, multiple constrained path selection, scalable routing