Optimal partition of QoS requirements with discrete cost functions
- 1 December 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 18 (12) , 2593-2602
- https://doi.org/10.1109/49.898739
Abstract
The future Internet is expected to support applications with quality of service (QoS) requirements. To this end, several mechanisms are suggested in the IETF; the most promising among them is DiffServ. An important problem in this framework is how to partition the QoS requirements of an application along a selected path. The problem which is, in general, NP-complete, was solved for continuous convex cost functions by Lorenz and Orda (see IEEE/ACM Trans. Networking. vol.6, p.768-78, 1998 and Proc. IEEE INFOCOM'99, p.246-53, 1999). This paper concentrates on discrete cost functions, which better model the existing and upcoming mechanisms in the Internet. We present efficient exact and approximated solutions for various conditions of the problem. We also show that although the more complex problem of QoS sensitive routing with discrete cost functions is hard, it has a fully polynomial approximation scheme.Keywords
This publication has 11 references indexed in Scilit:
- Call admission and resource reservation for multicast sessionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An analysis of Internet inter-domain topology and route stabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- QoS with differentiated servicesBell Labs Technical Journal, 2002
- QoS enabled voice support in the next generation Internet: issues, existing approaches and challengesIEEE Communications Magazine, 2000
- Internet telephony [Guest Editorial]IEEE Communications Magazine, 2000
- Resource allocation in a multicast treePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- Optimal partition of QoS requirements on unicast paths and multicast treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- QoS routing in networks with uncertain parametersIEEE/ACM Transactions on Networking, 1998
- An overview of quality of service routing for next-generation high-speed networks: problems and solutionsIEEE Network, 1998
- Approximation Schemes for the Restricted Shortest Path ProblemMathematics of Operations Research, 1992