On finding multi-constrained paths

Shigang Shigang Chen, Klara Nahrstedt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

New emerging distributed multimedia applications provide guaranteed end-to-end quality of service (QoS) and have stringent constraints on delay, delay-jitter, cost, etc. The task of QoS routing is to find a route in the network which has sufficient resources to satisfy the constraints. The delay-cost-constrained routing problem is NP-complete. We propose a heuristic algorithm for this problem. The idea is to first reduce the NP-complete problem to a simpler one which can be solved in polynomial time, and then solve the new problem by either an extended Dijkstra's algorithm or an extended Bellman-Ford algorithm. We prove the correctness of our algorithm by showing that a solution for the simpler problem must also be a solution for the original problem. The performance of the algorithm is studied by both theoretical analysis and simulation.

Original languageEnglish (US)
Title of host publicationICC 1998 - 1998 IEEE International Conference on Communications
Subtitle of host publicationNew Century Communications, Conference Record; Affiliated with SUPERCOMM 1998
Pages874-879
Number of pages6
DOIs
StatePublished - 1998
Event1998 IEEE International Conference on Communications: New Century Communications, ICC 1998 - Affiliated with SUPERCOMM 1998 - Atlanta, GA, United States
Duration: Jun 7 1998Jun 11 1998

Publication series

NameInternational Conference on Communications - Proceedings
Volume2

Other

Other1998 IEEE International Conference on Communications: New Century Communications, ICC 1998 - Affiliated with SUPERCOMM 1998
CountryUnited States
CityAtlanta, GA
Period6/7/986/11/98

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Engineering(all)

Fingerprint Dive into the research topics of 'On finding multi-constrained paths'. Together they form a unique fingerprint.

Cite this