The optimal multimedia multicast routing problem is to determine a multicast tree of minimal cost to connect a given source node to a given set of destination nodes while fulfilling the delay requirement for multimedia information. This problem has been shown to be NP-complete (Kompella et al., 1993), and hence fast and good heuristic algorithms must be used in practice for a reasonable network size. The authors derive a lower bound on the cost of the optimal multicast trees by Lagrangean relaxation and problem decomposition. The numerical results for some standard test problems demonstrate that the lower bound is very tight and differs from the optimal solutions by only a few percent on average. In addition, the lower bound can be computed quite quickly and the computation time on a SUN workstation is only a few minutes for the networks with 100 nodes. This tight lower bound can be used to evaluate whether any given heuristic algorithm for multimedia multicast routing is close-to-optimal.
References
-
-
1)
-
B.N. Khoury ,
P.M. Pardalos ,
D.Z. Du
.
A test problem generator for the Steiner problem in graphs.
ACM Trans. Math. Softw.
,
4 ,
509 -
522
-
2)
-
D.P. Anderson
.
Metascheduling for continuous media.
ACM Trans. Comput. Syst.
,
3 ,
226 -
252
-
3)
-
L. Kou ,
G. Markowsky ,
L. Berman
.
A fast algorithm for Steiner trees.
Acta Inform.
,
141 -
145
-
4)
-
V.P. Kompella ,
J.C. Pasquale ,
G.C. Polyzos
.
Multicast routing formultimedia communication.
IEEE/ACM Trans. Netw.
,
3 ,
286 -
292
-
5)
-
A. Geoffrion
.
Lagrangean relaxation for integer programming.
Math. Program.
,
82 -
114
-
6)
-
Y.W. Leung ,
T.S. Yum
.
Connection optimisation for two types ofvideoconferences.
IEE Proc. Commun.
,
3 ,
133 -
140
-
7)
-
Zhu, Q., Parsa, M., Aceves, J.J.G.L.: `A source-based algorithm for delay-constrained minimum-cost multicasting', Proc. IEEE INFOCOM, 1995, p. 377–385.
-
8)
-
G.Y. Handler ,
I. Zang
.
A dual algorithm for the constrainedshortest path problem.
Networks
,
293 -
310
-
9)
-
C.R. Reeves
.
(1993)
Modern heuristic techniques for combinatorial problems.
-
10)
-
D. Deloddere ,
W. Verbiest ,
H. Verhille
.
Interactive video on demand.
IEEE Commun. Mag.
,
82 -
88
-
11)
-
J.R. Wullert ,
A.C.V. Lehmen ,
Y. Lu
.
Analysis of storage requirements for video-on-demand servers.
IEEE Trans. Circuits Syst. Video Technol.
,
4 ,
359 -
363
-
12)
-
T.S. Yum ,
M.S. Chen ,
Y.W. Leung
.
Video bandwidth allocation formultimedia teleconferences.
IEEE Trans. Commun.
,
2 ,
457 -
465
-
13)
-
Leung, Y.W., Yang, B.T.: `Test problems for multimedia multicastrouting', Internal report, 1997.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-com_19981798
Related content
content/journals/10.1049/ip-com_19981798
pub_keyword,iet_inspecKeyword,pub_concept
6
6