Lower bound for multimedia multicast routing

Access Full Text

Lower bound for multimedia multicast routing

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

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

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.

© IEE
Published

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.

Inspec keywords: multimedia communication; trees (mathematics); telecommunication network routing; computational complexity; optimisation

Other keywords: NP-complete problem; optimal solutions; problem decomposition; lower bound; source node; destination nodes; computation time; standard test problems; SUN workstation; Lagrangean relaxation; optimal multicast trees; delay requirement; optimal multimedia multicast routing; network size; heuristic algorithms; minimal cost

Subjects: Multimedia communications; Communication network design, planning and routing; Optimisation techniques

References

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