article

Efficient QoS partition and routing of unicast and multicast

Authors:

Dean H. Lorenz,

Yuval ShavittAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue 6

Pages 1336 - 1347

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

Published: 01 December 2006 Publication History

Abstract

In this paper, we study problems related to supporting unicast and multicast connections with quality of service (QoS) requirements. We investigate the problem of optimal routing and resource allocation in the context of performance dependent costs. In this context, each network element can offer several QoS guarantees, each associated with a different cost. This is a natural extension to the commonly used bi-criteria model, where each link is associated with a single delay and a single cost. This framework is simple yet strong enough to model many practical interesting networking problems.An important problems in this framework is finding a good path for a connection that minimizes the cost while retaining the end-to-end delay requirement. Once such a path (or a tree, in the multicast case) is found, one needs to partition the end-to-end QoS requirements among the links of the path (tree). We consider the case of general integer cost functions (where delays and cost are integers). As the related problem is NP complete, we concentrate on finding efficient ε-approximation solutions. We improve on recent previous results by Ergün et al. Lorenz and Orda, and Raz and Shavitt, both in terms of generality as well as in terms of complexity of the solution. In particular, we present novel approximation techniques that yield the best known complexity for the unicast QoS routing problem, and the first approximation algorithm for the QoS partition problem on trees, both for the centralized and distributed cases.

References

[1]

{1} G. Apostolopoulos, R. Guérin, S. Kamat, A. Orda, T. Przygienda, and D. Williams, "QoS Routing mechanisms and OSPF extensions," Internet RFC 2676, Aug. 1999.

[2]

{2} E. Crawley, R. Nair, B. Rajagopalan, and H. Sandick, "A framework for QoS-based routing in the Internet," Internet RFC 2386, Aug. 1998.

[3]

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

[4]

{4} D. Raz and Y. Shavitt, "Optimal partition of QoS requirements with discrete cost functions," in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 613-622.

[5]

{5} D. H. Lorenz and A. Orda, "Optimal partition of QoS requirements on unicast paths and multicast trees," in Proc. IEEE INFOCOM'99, New York, Mar. 1999, pp. 246-253.

[6]

{6} R. Nagarajan, J. F. Kurose, and D. Towsley, "Allocation of local quality of service constraints to meet end-to-end requirements," presented at the IFIP Workshop on the Performance Analysis of ATM Systems, Martinique, Jan. 1993.

[7]

{7} T. Ibaraki and N. Katoh, Resource Allocation Problems, the Foundations of Computing. Cambridge, MA: MIT Press, 1988.

[8]

{8} D. H. Lorenz and A. Orda, "QoS routing in networks with uncertain parameters," IEEE/ACM Trans. Netw., vol. 6, no. 6, pp. 768-778, Dec. 1998.

[9]

{9} V. Firoiu and D. Towsley, "Call admission and resource reservation for multicast sessions," in Proc. IEEE INFOCOM'96, San Francisco, CA, Apr. 1996, pp. 94-101.

[10]

{10} M. Kodialam and S. Low, "Resource allocation in a multicast tree," in Proc. IEEE INFOCOM'99, New York, Mar. 1999, pp. 262-266.

[11]

{11} D. S. Hochbaum, "Lower and upper bounds for the alloction problem and other nonlinear optimization problems," Math. Oper. Res., vol. 19, no. 2, pp. 390-409, 1994.

[12]

{12} V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, "Multicast routing for multimedia communication," IEEE/ACM Trans. Netw., vol. 1, no. 3, pp. 286-292, Jun. 1993.

[13]

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

[14]

{14} F. Ergün, R. Sinha, and L. Zhang, "QoS routing with performance-dependent costs," in Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, Mar. 2000, pp. 137-146.

[15]

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

[16]

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

[17]

{17} F. A. Kuipers, A. Orda, D. Raz, and P. Van Mieghem, "A comparison of exact and "ε-approximation algorithms for constrained routing," in Proc. IFIP Networking 2006, Coimbra, Portugal, May 2006, pp. 197-208.

[18]

{18} G. N. Frederickson and D. B. Johnson, "The complexity of selection and ranking in X + Y and matrices with sorted columns," J. Comput. Syst. Sci., vol. 24, pp. 197-208, 1982.

Cited By

Dolati MGhaderi MKhonsari A(2019)Proactive inter-datacenter multicast with realtime and bulk transfersProceedings of the International Symposium on Quality of Service10.1145/3326285.3329059(1-10)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3326285.3329059
Chen SShavitt Y(2019)SoMRJournal of Parallel and Distributed Computing10.1016/j.jpdc.2007.10.00468:2(137-149)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2007.10.004
Ye NXu XHurley P(2018)QoS protocols for end-to-end delay guarantee of instantaneous jobs on computer networksInformation-Knowledge-Systems Management10.5555/1735365.17353697:4(429-451)Online publication date: 14-Dec-2018
https://dl.acm.org/doi/10.5555/1735365.1735369
Show More Cited By

Index Terms

Efficient QoS partition and routing of unicast and multicast
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols
  2. Network services

Recommendations

Optimal partition of QoS requirements on unicast paths and multicast trees

We investigate the problem of optimal resource allocation for end-to-end QoS requirements on unicast paths and multicast trees. Specifically, we consider a framework in which resource allocation is based on local QoS requirements at each network link, ...
A scalable approach to the partition of QoS requirements in unicast and multicast

Supporting quality of service (QoS) in large-scale broadband networks poses major challenges, due to the intrinsic complexity of the corresponding resource allocation problems. An important problem in this context is how to partition QoS requirements ...
Multi-class QoS routing strategies based on the network state

With the exploding volume of traffic and expanding Quality of Service (QoS) requirements from emerging multimedia applications, extensive research has been carried out to address various issues in QoS routing with respect to the Internet. Traffic is ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue 6

December 2006

247 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2006

Published in TON Volume 14, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
458
Total Downloads

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

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dolati MGhaderi MKhonsari A(2019)Proactive inter-datacenter multicast with realtime and bulk transfersProceedings of the International Symposium on Quality of Service10.1145/3326285.3329059(1-10)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3326285.3329059
Chen SShavitt Y(2019)SoMRJournal of Parallel and Distributed Computing10.1016/j.jpdc.2007.10.00468:2(137-149)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2007.10.004
Ye NXu XHurley P(2018)QoS protocols for end-to-end delay guarantee of instantaneous jobs on computer networksInformation-Knowledge-Systems Management10.5555/1735365.17353697:4(429-451)Online publication date: 14-Dec-2018
https://dl.acm.org/doi/10.5555/1735365.1735369
Yang WLiang WLuo JDou WHelmy AMueller PZhang Y(2010)Energy-aware online routing with QoS constraints in multi-rate wireless ad hoc networksProceedings of the 6th International Wireless Communications and Mobile Computing Conference10.1145/1815396.1815562(721-725)Online publication date: 28-Jun-2010
https://dl.acm.org/doi/10.1145/1815396.1815562
Hölzl MRauschmayer AWirsing M(2008)Engineering of Software-Intensive SystemsSoftware-Intensive Systems and New Computing Paradigms10.1007/978-3-540-89437-7_1(1-44)Online publication date: 14-Nov-2008
https://dl.acm.org/doi/10.1007/978-3-540-89437-7_1
Cui YWu JXu K(2005)Precomputation for intra-domain QoS routingComputer Networks: The International Journal of Computer and Telecommunications Networking10.5555/1648533.164876647:6(923-937)Online publication date: 1-Apr-2005
https://dl.acm.org/doi/10.5555/1648533.1648766

View Options

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