article

Approximation and heuristic algorithms for minimum-delay application-layer multicast trees

Authors:

Yuval ShavittAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 15, Issue 2

Pages 473 - 484

https://doi.org/10.1109/TNET.2007.892840

Published: 01 April 2007 Publication History

Abstract

In this paper we investigate the problem of finding minimum-delay application-layer multicast trees, such as the trees constructed in overlay networks. It is accepted that shortest path trees are not a good solution for the problem since such trees can have nodes with very large degree, termed high-load nodes. The load on these nodes makes them a bottleneck in the distribution tree, due to computation load and access link bandwidth constraints. Many previous solutions limited the maximum degree of the nodes by introducing arbitrary constraints. In this work, we show how to directly map the node load to the delay penalty at the application host, and create a new model that captures the trade offs between the desire to select shortest path trees and the need to constrain the load on the hosts. In this model the problem is shown to be NP-hard. We therefore present an approximation algorithm and an alternative heuristic algorithm. Our heuristic algorithm is shown by simulations to be scalable for large group sizes, and produces results that are very close to optimal.

References

[1]

{1} A. El-Sayed, V. Roca, and L. Mathy, "A survey of proposals for an alternative group communication service," IEEE Netw. Mag., vol. 17, no. 1, pp. 46-51, Jan./Feb. 2003.

[2]

{2} Y.-H. Chu, S. G. Rao, and H. Zhang, "A case for end system multicast," in Proc. ACM SIGMETRICS 2000, Santa Clara, CA, Jun. 2000, pp. 1-12.

[3]

{3} D. Pendarakis, S. Shi, D. Verma, and M. Waldvogel, "ALMI: An application level multicast inproceedings infrastructure," in Proc. 3rd USNIX Symp. Internet Technologies and Systems (USITS'01), San Francisco, CA, Mar. 2001, pp. 49-60.

[4]

{4} S. Shi and J. Turner, "Routing in overlay multicast networks," in Proc. IEEE INFOCOM, New York, Jun. 2002, vol. 3, pp. 1200-1208.

[5]

{5} S. Banerjee, C. Kommareddy, K. Kar, B. Bhattacharjee, and S. Khuller, "Construction of an efficient overlay multicast infrastructure for real-time applications," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, vol. 2, pp. 1521-1531.

[6]

{6} S. Banerjee, B. Bhattacharjee, and C. Kommareddy, "Scalable application layer multicast," in Proc. ACM SIGCOMM 2002, Pittsburgh, PA, Aug. 2002, pp. 205-217.

[7]

{7} N. Malouch, Z. Liu, D. Rubenstein, and S. Sahu, "A graph theoretic approach to bounding delay in proxy-assisted, end-system multicast," in Proc. 10th IEEE Int. Workshop on Quality of Service (IWQoS), Miami, FL, May 2002, pp. 106-115.

[8]

{8} S. Saroiu, P. K. Gummadi, and S. D. Gribble, "A measurement study of peer-to-peer file sharing systems," in Proc. Multimedia Computing and Networking 2002 (MMCN'02), San Jose, CA, Jan. 2002, pp. 156-170.

[9]

{9} I. Cidon, I. Gopal, and S. Kutten, "New models and algorithms for future networks," IEEE Trans. Inf. Theory, vol. 41, no. 3, pp. 769-780, May 1995.

[10]

{10} M. Castro, M. B. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, and A. Wolman, "An evaluation of scalable application-level multicast built using peer-to-peer overlays," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, vol. 2, pp. 1510-1520.

[11]

{11} S. Y. Shi, J. Turner, and M. Waldvogel, "Dimensioning server access bandwidth and multicast routing in overlay networks," in Proc. NOSSDAV 2001, Port Jefferson, NY, Jun. 2001, pp. 83-92.

[12]

{12} P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, and L. Zhang, "IDMaps: A global internet host distance estimation service," IEEE/ACM Trans. Netw., vol. 9, no. 5, pp. 525-540, Oct. 2001.

[13]

{13} A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, "Message multicasting in heterogeneous networks," SIAM J. Comput., vol. 30, no. 2, pp. 347-358, 2001.

[14]

{14} M. R. Garey and D. S. Johnson, Computers and Intractability. San Francisco, CA: Freeman, 1979.

[15]

{15} S. M. Hedetniemi, S. T. Hedetniemi, and A. L. Liestman, "A survey of gossiping and broadcasting in communication networks," Networks, vol. 18, no. 4, pp. 319-349, 1988.

[16]

{16} R. Ravi, "Rapid rumor ramification: Approximating the minimum broadcasting time," in Proc. 35th IEEE Symp. Foundations of Computer Science, 1994, pp. 202-213.

[17]

{17} G. Kortsarz and D. Peleg, "Approximation algorithm for minimum time broadcast," SIAM J. Discrete Math., vol. 8, pp. 401-427, 1995.

[18]

{18} M. Elkin and G. Kortsarz, "A sublogarithmic approximation algorithm for the undirected telephone broadcast problem: A path out of a jungle," in Proc. ACM Symp. Discrete Algorithms (SODA), Baltimore, MD, 2003, pp. 76-85.

[19]

{19} M. Elkin and G. Kortsarz, "Combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem," in Proc. ACM Symp. Theory of Computing (STOC), Montreal, QC, Canada, 2002, pp. 438-447.

[20]

{20} D. Raz and Y. Shavitt, "New models and algorithms for programmable networks," Comput. Netw., vol. 38, no. 3, pp. 311-326, 2002.

[21]

{21} A. Bar-Noy and S. Kipnis, "Designing broadcasting algorithms in the postal model for message passing systems," in Proc. Symp. Parallelism in Algorithms and Architectures (SPAA), San Diego, CA, Jun. 1992, pp. 13-22.

[22]

{22} L. Wei and D. Estrin, "The trade-offs of multicast trees and algorithms," in Proc. Int. Conf. Computer Communications and Networks (ICCCN'94), San Francisco, CA, Sep. 1994, pp. 902-926.

[23]

{23} T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms . New York: McGraw-Hill, 1990.

[24]

{24} P. Francis, "Yoid: Extending the multicast inetrnet architecture," White Paper {Online}. Available: http://www.aciri.org/yoid/ 1999.

[25]

{25} A. M. Farley and S. T. Hedetniemi, "Broadcasting in grid graphs," in Proc. 9th S-E Conf. Combinatorics, Graph Theory, and Computing, 1978, pp. 275-288.

[26]

{26} R. Albert and A. L. Barabasi, "Topology of evolving networks: Local events and universality," Phys. Rev. Lett., vol. 85, no. 24, pp. 5234-5237, Dec. 11, 2000.

Cited By

Zhang XWang LLi YSun M(2017)A Centralized Optimization Solution for Application Layer Multicast TreeIEEE Transactions on Network and Service Management10.1109/TNSM.2017.273152114:3(771-785)Online publication date: 6-Sep-2017
https://dl.acm.org/doi/10.1109/TNSM.2017.2731521
Mokhtarian KJacobsen H(2015)Minimum-delay multicast algorithms for mesh overlaysIEEE/ACM Transactions on Networking10.1109/TNET.2014.231073523:3(973-986)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2310735
Bhatia AHansdah R(2014)A media access and feedback protocol for reliable multicast over wireless channelWireless Networks10.1007/s11276-014-0746-620:8(2371-2383)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1007/s11276-014-0746-6
Show More Cited By

Index Terms

Approximation and heuristic algorithms for minimum-delay application-layer multicast trees

Recommendations

Construction of Application-Layer Multicast Trees for Message Distribution
ISPA '10: Proceedings of the International Symposium on Parallel and Distributed Processing with Applications

This paper considers the problem of constructing minimum-delay multicast trees for message dissemination in overlay networks in which nodal delays for processing messages are taken into account in addition to communication delays. The objective is to ...
Approximation and Heuristic Algorithms for End-System Based Application-Layer Multicast for Voice Conferences
AINA '11: Proceedings of the 2011 IEEE International Conference on Advanced Information Networking and Applications

This paper studies the problem of constructing application-layer multicast trees for end-system based voice conferences in which voice mixing and replication are performed at end systems. This problem is formulated as a degree-constrained node-weighted ...
Scalable application layer multicast
SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications

We describe a new scalable application-layer multicast protocol, specifically designed for low-bandwidth, data streaming applications with large receiver sets. Our scheme is based upon a hierarchical clustering of the application-layer multicast peers ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 15, Issue 2

April 2007

232 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 2007

Published in TON Volume 15, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
450
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang XWang LLi YSun M(2017)A Centralized Optimization Solution for Application Layer Multicast TreeIEEE Transactions on Network and Service Management10.1109/TNSM.2017.273152114:3(771-785)Online publication date: 6-Sep-2017
https://dl.acm.org/doi/10.1109/TNSM.2017.2731521
Mokhtarian KJacobsen H(2015)Minimum-delay multicast algorithms for mesh overlaysIEEE/ACM Transactions on Networking10.1109/TNET.2014.231073523:3(973-986)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2310735
Bhatia AHansdah R(2014)A media access and feedback protocol for reliable multicast over wireless channelWireless Networks10.1007/s11276-014-0746-620:8(2371-2383)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1007/s11276-014-0746-6
Chen YRadhakrishnan SDhall SKarabuk S(2013)On multi-stream multi-source multicast routingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2013.05.01257:15(2916-2930)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1016/j.comnet.2013.05.012
Huang ZWu WNahrstedt KRivas RArefin ABegen AMayer-Patel K(2011)SyncCastProceedings of the second annual ACM conference on Multimedia systems10.1145/1943552.1943562(69-80)Online publication date: 23-Feb-2011
https://dl.acm.org/doi/10.1145/1943552.1943562

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents