Resource optimization in QoS multicast routing of real-time multimedia
Authors:
- J. NaorJNJ. Naor
- B. SchieberBSB. Schieber
- 7 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 1518-1527 vol.3
Abstract
We consider a network design problem, where applications require various levels of quality-of-service (QoS) while connections have limited performance. Suppose that a source needs to send a message to a heterogeneous set of receivers. The objective is to design a low cost multicast tree from the source that would provide the QoS levels (e.g., bandwidth) requested by the receivers. We assume that the QoS level required on a link is the maximum among the QoS levels of the receivers that are connected to the source through the link. In accordance, we define the cost of a link to be a function of the QoS level that it provides. This definition of cost makes this optimization problem more general than the classical Steiner tree problem. We consider several variants of this problem all of which are proved to be NP-hard. For the variant where QoS levels of a link can vary arbitrarily and the cost function is linear in its QoS level, we give a heuristic that achieves a multicast tree with cost at most a constant times the cost of an optimal multicast tree. The constant depends on the best constant approximation ratio of the classical Steiner tree problem. For the more general variant, where each link has a given QoS level and cost we present a heuristic that generates a multicast tree with cost O(min{logr,k}) times the cost of an optimal tree, where r denotes the number of receivers, and k denotes the number of different levels of QoS required. We generalize this result to hold for the case of many multicast groups.Keywords
This publication has 15 references indexed in Scilit:
- An active service framework and its application to real-time multimedia transcodingACM SIGCOMM Computer Communication Review, 1998
- An improved approximation ratio for the minimum latency problemMathematical Programming, 1998
- Video distribution on multicast networksIEEE Journal on Selected Areas in Communications, 1997
- Receiver-driven bandwidth adaptation for light-weight sessions1997
- An application level video gateway1995
- Dynamic Steiner Tree ProblemSIAM Journal on Discrete Mathematics, 1991
- Packet video and its integration into the network architectureIEEE Journal on Selected Areas in Communications, 1989
- Two-layer coding of video signals for VBR networksIEEE Journal on Selected Areas in Communications, 1989
- Steiner problem in networks: A surveyNetworks, 1987
- Yet more on the linear search problemIsrael Journal of Mathematics, 1970