http://iet.metastore.ingenta.com
1887

Lower bound for multimedia multicast routing

Lower bound for multimedia multicast routing

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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. 1)
      • V.P. Kompella , J.C. Pasquale , G.C. Polyzos . Multicast routing formultimedia communication. IEEE/ACM Trans. Netw. , 3 , 286 - 292
    2. 2)
      • Y.W. Leung , T.S. Yum . Connection optimisation for two types ofvideoconferences. IEE Proc. Commun. , 3 , 133 - 140
    3. 3)
      • T.S. Yum , M.S. Chen , Y.W. Leung . Video bandwidth allocation formultimedia teleconferences. IEEE Trans. Commun. , 2 , 457 - 465
    4. 4)
      • D. Deloddere , W. Verbiest , H. Verhille . Interactive video on demand. IEEE Commun. Mag. , 82 - 88
    5. 5)
      • 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
    6. 6)
      • D.P. Anderson . Metascheduling for continuous media. ACM Trans. Comput. Syst. , 3 , 226 - 252
    7. 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. 8)
      • L. Kou , G. Markowsky , L. Berman . A fast algorithm for Steiner trees. Acta Inform. , 141 - 145
    9. 9)
      • A. Geoffrion . Lagrangean relaxation for integer programming. Math. Program. , 82 - 114
    10. 10)
      • C.R. Reeves . (1993) Modern heuristic techniques for combinatorial problems.
    11. 11)
      • G.Y. Handler , I. Zang . A dual algorithm for the constrainedshortest path problem. Networks , 293 - 310
    12. 12)
      • 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
    13. 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
Loading

Related content

content/journals/10.1049/ip-com_19981798
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address