article

Finding a path subject to many additive QoS constraints

Authors:

Krishnaiya ThulasiramanAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 15, Issue 1

Pages 201 - 211

https://doi.org/10.1109/TNET.2006.890089

Published: 01 February 2007 Publication History

Abstract

A fundamental problem in quality-of-service (QoS) routing is to find a path between a source-destination node pair that satisfies two or more end-to-end QoS constraints. We model this problem using a graph with n vertices and m edges with K additive QoS parameters associated with each edge, for any constant K ≥ 2. This problem is known to be NP-hard. Fully polynomial time approximation schemes (FPTAS) for the case of K = 2 have been reported in the literature. We concentrate on the general case and make the following contributions. 1) We present a very simple O(Km + nlogn) time K -approximation algorithm that can be used in hop-by-hop routing protocols. 2) We present an FPTAS for one optimization version of the QoS routing problem with a time complexity of O(m(n/ε)^K-1).3) We present an FPTAS for another optimization version of the QoS routing problem with a time complexity of O(n log n + m(H/ε)^K-1) when there exists an H-hop path satisfying all QoS constraints. When K is reduced to 2, our results compare favorably with existing algorithms. The results of this paper hold for both directed and undirected graphs. For ease of presentation, undirected graph is used.

References

[1]

{1} R. Andersen, F. Chung, A. Sen, and G. Xue, "On disjoint path pairs with wavelength continuity constraint in WDM networks," in Proc. IEEE INFOCOM'04, pp. 524-535.

[2]

{2} BRITE. {Online}. Available: http://www.cs.bu.edu/brite/

[3]

{3} S. Chen and K. Nahrstedt, "On finding multi-constrained paths," IEEE ICC'98, pp. 874-879.

[4]

{4} X. Chu and B. Li, "Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks," IEEE/ACM Trans. Netw., vol. 13, no. 3, pp. 704-715, Jun. 2005.

[5]

{5} T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. New York: McGraw-Hill, 2001.

[6]

{6} F. Ergun, R. Sinha, and L. Zhang, "An improved FPTAS for restricted shortest path," Inf. Process. Lett., vol. 83, pp. 287-291, 2002.

[7]

{7} A. Goel, K. G. Ramakrishnan, D. Kataria, and D. Logothetis, "Efficient computation of delay-sensitive routes from one source to all destinations," in Proc. IEEE INFOCOM 2001, pp. 854-858.

[8]

{8} R. Guerin and A. Orda, "QoS routing in networks with inaccurate information: theory and algorithms," IEEE/ACM Trans. Netw., vol. 7, no. 3, pp. 350-364, Jun. 1999.

[9]

{9} R. Hassin, "Approximation schemes for the restricted shortest path problem," Math. Oper. Res., vol. 17, pp. 36-42, 1992.

[10]

{10} C. Huitema, Routing in the Internet, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall PTR, 2000.

[11]

{11} O. H. Ibarra and C. E. Kim, "Fast approximation algorithms for the Knapsack and Sum of Subset problems," J. ACM, vol. 22, pp. 463-468, 1975.

[12]

{12} J. M. Jaffe, "Algorithms for finding paths with multiple constraints," Networks, vol. 14, pp. 95-116, 1984.

[13]

{13} A. Juttner, B. Szviatovszki, I. Mecs, and Z. Rajko, "Lagrange relaxation based method for the QoS routing problem," in Proc. IEEE INFOCOM 2001, pp. 859-868.

[14]

{14} T. Korkmaz and M. Krunz, "Mult-constrained optimal path selection," in Proc. IEEE INFOCOM 2001, pp. 834-843.

[15]

{15} D. H. Lorenz and D. Raz, "A simple efficient approximation scheme for the restricted shortest path problem," Oper. Res. Lett., vol. 28, pp. 213-219, 2001.

[16]

{16} Q. Ma and P. Steenkiste, "Quality-of-service routing for traffic with performance guarantees," Proc. IWQoS'97, pp. 115-126.

[17]

{17} Quality of Service in Multiservice IP Networks, Proc. QoS-IP 2003, ser. Lecture Notes in Computer Science, Vol. 2601, M. Ajmone Marsan, G. Corazza, M. Listanti, and A. Roveri, Eds. Berlin: Springer, 2003.

[18]

{18} A. Orda, "Routing with end-to-end QoS guarantees in broadband networks," IEEE/ACM Trans. Netw., vol. 7, no. 3, pp. 365-374, Jun. 1999.

[19]

{19} A. Orda and A. Sprintson, "Precomputation schemes for QoS routing," IEEE/ACM Trans. Netw., vol. 11, no. 4, pp. 578-591, Aug. 2003.

[20]

{20} A. Orda and A. Sprintson, "Efficient algorithms for computing disjoint QoS paths," in Proc. IEEE INFOCOM 2004, pp. 727-738.

[21]

{21} S. Sahni, "General techniques for combinatorial approximation," Oper. Res., vol. 25, pp. 920-936, 1977.

[22]

{22} Z. Wang and J. Crowcroft, "Quality-of-service routing for supporting multimedia applications," IEEE J. Sel. Areas Commun., vol. 14, no. 7, pp. 1228-1234, Sep. 1996.

[23]

{23} A. Warburton, "Approximation of Pareto optima in multiple-objective, shortest path problem," Oper. Res., vol. 35, pp. 70-79, 1987.

[24]

{24} B. M. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.

[25]

{25} G. Xue, "Primal-dual algorithms for computing weight-constrained shortest paths and weight-constrained minimum spanning trees," Proc. IEEE IPCCC'2000, pp. 271-277.

[26]

{26} G. Xue, "Minimum cost QoS multicast and unicast routing in communication networks," IEEE Trans. Commun., vol. 51, no. 5, pp. 817-824, May 2003.

[27]

{27} G. Xue, A. Sen, and R. Banka, "Routing with many additive QoS constraints," in Proc. IEEE ICC'2003, pp. 223-227.

[28]

{28} X. Yuan, "Heuristic algorithms for multiconstrained quality-of-service routing," IEEE/ACM Trans. Netw., vol. 10, no. 2, pp. 244-256, Apr. 2002.

Cited By

Awad Abdellatif AAbo-Eleneen AMohamed AErbad ANavkar NGuizani M(2023)Intelligent-Slicing: An AI-Assisted Network Slicing Framework for 5G-and-Beyond NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2023.327423620:2(1024-1039)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3274236
Abdellatif AMohamed AErbad AGuizani M(2022)Dynamic Network Slicing and Resource Allocation for 5G-and-Beyond Networks2022 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC51071.2022.9771877(262-267)Online publication date: 10-Apr-2022
https://dl.acm.org/doi/10.1109/WCNC51071.2022.9771877
Ding W(2021)Finding Cheapest Deadline PathsComputing and Combinatorics10.1007/978-3-030-89543-3_40(476-486)Online publication date: 24-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89543-3_40
Show More Cited By

Index Terms

Finding a path subject to many additive QoS constraints

Recommendations

Polynomial time approximation algorithms for multi-constrained QoS routing

We study the multi-constrained quality-ofservice (QoS) routing problem where one seeks to find a path from a source to a destination in the presence of K ≥ 2 additive end-to-end QoS constraints. This problem is NP-hard and is commonly modeled using a ...
An efficient algorithm for finding a path subject to two additive constraints
Special issue on proceedings of ACM SIGMETRICS 2000

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, ...
An efficient algorithm for finding a path subject to two additive constraints

One of the key issues in providing end-to-end quality-of-service (QoS) guarantees in packet networks is how to determine a feasible path that satisfies a number of QoS constraints. For two or more additive constraints, the problem of finding a feasible ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 15, Issue 1

February 2007

245 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2007

Published in TON Volume 15, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
589
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Awad Abdellatif AAbo-Eleneen AMohamed AErbad ANavkar NGuizani M(2023)Intelligent-Slicing: An AI-Assisted Network Slicing Framework for 5G-and-Beyond NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2023.327423620:2(1024-1039)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TNSM.2023.3274236
Abdellatif AMohamed AErbad AGuizani M(2022)Dynamic Network Slicing and Resource Allocation for 5G-and-Beyond Networks2022 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC51071.2022.9771877(262-267)Online publication date: 10-Apr-2022
https://dl.acm.org/doi/10.1109/WCNC51071.2022.9771877
Ding W(2021)Finding Cheapest Deadline PathsComputing and Combinatorics10.1007/978-3-030-89543-3_40(476-486)Online publication date: 24-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89543-3_40
(2018)A heuristic approximation algorithm for the Steiner tree based on prior multicast nodesInternational Journal of Autonomous and Adaptive Communications Systems10.1504/IJAACS.2018.09369011:3(193-208)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1504/IJAACS.2018.093690
Kuhnle ACrawford VThai M(2018)Network Resilience and the Length-Bounded Multicut ProblemProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31794072:1(1-26)Online publication date: 3-Apr-2018
https://dl.acm.org/doi/10.1145/3179407
Song PLiu YLiu CQian D(2017)ParaFlowJournal of Network and Computer Applications10.1016/j.jnca.2017.03.00987:C(46-59)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.jnca.2017.03.009
Dabaghi FMovahedi ZLangar R(2017)A survey on green routing protocols using sleep-scheduling in wired networksJournal of Network and Computer Applications10.1016/j.jnca.2016.10.00577:C(106-122)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.jnca.2016.10.005
Sedeño-Noda AAlonso-Rodríguez S(2015)An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problemApplied Mathematics and Computation10.1016/j.amc.2015.05.109265:C(602-618)Online publication date: 15-Aug-2015
https://dl.acm.org/doi/10.1016/j.amc.2015.05.109
Hou RLui KLeung KBaker F(2014)Performance analysis of quantization-based approximation algorithms for precomputing the supported QoSJournal of Network and Computer Applications10.5555/2773807.277406040:C(244-254)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.5555/2773807.2774060
Huang JDuan QChen QSun YTanaka YWang W(2014)Guaranteeing end-to-end quality-of-service with a generic routing approachACM SIGAPP Applied Computing Review10.1145/2656864.265686514:2(8-22)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2656864.2656865
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents