skip to main content
article

Characterizing overlay multicast networks and their costs

Published: 01 April 2007 Publication History

Abstract

Overlay networks among cooperating hosts have recently emerged as a viable solution to several challenging problems, including multicasting, routing, content distribution, and peer-to-peer services. Application-level overlays, however, incur a performance penalty over router-level solutions. This paper quantifies and explains this performance penalty for overlay multicast trees via: 1) Internet experimental data; 2) simulations; and 3) theoretical models. We compare a number of overlay multicast protocols with respect to overlay tree structure, and underlying network characteristics. Experimental data and simulations illustrate that the mean number of hops and mean per-hop delay between parent and child hosts in overlay trees generally decrease as the level of the host in the overlay tree increases. Overlay multicast routing strategies, overlay host distribution, and Internet topology characteristics are identified as three primary causes of the observed phenomenon. We show that this phenomenon yields overlay tree cost savings: Our results reveal that the normalized cost L(n)/U(n) is ∞ n0.9 for small n, where L(n) is the total number of hops in all overlay links, U(n) is the average number of hops on the source to receiver unicast paths, and n is the number of members in the overlay multicast session. This can be compared to an IP multicast cost proportional to n0.6 to n0.8.

References

[1]
{1} Y. Chu, S. Rao, S. Seshan, and H. Zhang, "Enabling conferencing applications on the internet using an overlay multicast architecture," in Proc. ACM SIGCOMM, 2001, pp. 55-67.
[2]
{2} J. Jannotti, D. Gifford, K. Johnson, M. Kaashoek, and J. O'Toole, Jr., "Overcast: Reliable multicasting with an overlay network," in Proc. Conf. Operating Systems Design and Implementation, Oct. 2000.
[3]
{3} S. Banerjee, B. Bhattacharjee, and C. Kommareddy, "Scalable application multicast," presented at the ACM SIGCOMM, Pittsburgh, PA, 2002.
[4]
{4} M. Kwon and S. Fahmy, "Topology-aware overlay networks for group communication," in Proc. ACM Conf. Network and Operating System Support for Digital Audio and Video (NOSSDAV), 2002, pp. 127-136.
[5]
{5} S. Shi, J. Turner, and M. Waldvogel, "Dimensioning server access bandwidth and multicast routing in overlay networks," in Proc. ACM Conf. Network and Operating System Support for Digital Audio and Video (NOSSDAV), 2001, pp. 83-91.
[6]
{6} S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman, J. Snell, A. Vahdat, G. Voelker, and J. Zahorjan, "Detour: A case for informed internet routing and transport," IEEE Micro, vol. 19, no. 1, pp. 50-59, Jan. 1999.
[7]
{7} D. G. Andersen, H. Balakrishnan, M. F. Kaashoek, and R. Morris, "Resilient overlay networks," in Proc. ACM Symp. Operating Systems Principles , Oct. 2001, pp. 131-145.
[8]
{8} J. Byers, J. Considine, M. Mitzenmacher, and S. Rost, "Informed content delivery across adaptive overlay networks," presented at the ACM SIGCOMM, Pittsburgh, PA, 2002.
[9]
{9} I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup protocol for internet applications," in Proc. ACM SIGCOMM, 2001, pp. 149-160.
[10]
{10} S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A scalable content-addressable network," in Proc. ACM SIGCOMM, 2001, pp. 161-172.
[11]
{11} A. Rowstron and P. Druschel, "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems," in Proc. ACM/IFIP Conf. Middleware, 2001.
[12]
{12} S. Fahmy and M. Kwon, "Characterizing overlay multicast networks," in Proc. IEEE Int. Conf. Network Protocols, 2003, pp. 61-70.
[13]
{13} R. Chalmers and K. Almeroth, "Modeling the branching characteristics and efficiency gains in global multicast trees," in Proc. IEEE INFOCOM , 2001, pp. 449-458.
[14]
{14} J. Chuang and M. Sirbu, "Pricing multicast communications: A cost-based approach," in Proc. Internet Society INET, Jul. 1998.
[15]
{15} G. Phillips, S. Shenker, and H. Tangmunarunkit, "Scaling of multicast trees: Comments on the Chuang-Sirbu scaling law," in Proc. ACM SIGCOMM , 1999, pp. 41-51.
[16]
{16} C. Adjih, L. Georgiadis, P. Jacquet, and W. Szpankowski, "Multicast tree structure and the power law," in Proc. Symp. Discrete Algorithms , 2002.
[17]
{17} Y. Chu, S. Rao, and H. Zhang, "A case for end system multicast," in Proc. ACM SIGMETRICS, 2000, pp. 1-12.
[18]
{18} Traceroute.org. {Online}. Available: http://www.traceroute.org
[19]
{19} Y. Zhang, V. Paxson, and S. Shenker, The stationarity of internet path properties: Routing, loss, and throughput AT&T Center for Internet Research at ICSI, Berkeley, CA, ACIRI Tech. Rep., May 2000 {Online}. Available: http://www.icir.org/vern/papers.html
[20]
{20} D. V. Houweling, Internet 2. {Online}. Available: http://www.in- ternet2.edu
[21]
{21} M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the internet topology," in Proc. ACM SIGCOMM, 1999, pp. 251-262.
[22]
{22} D. Watts and S. Strogatz, "Collective dynamics of small-world networks," Nature, vol. 363, pp. 202-204, 1998.
[23]
{23} A. Barabasi and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, pp. 509-512, 1999.
[24]
{24} L. Peterson, T. Anderson, D. Culler, and T. Roscoe, "A blueprint for introducing disruptive technology into the internet," in Proc. HotNets-I, Oct. 2002.
[25]
{25} A. Kuznetsov, Tracepath. {Online}. Available: ftp://ftp.inr.ac.ru/ip-routing/iputils-current.tar.gz
[26]
{26} S. Fahmy and M. Kwon, Characterizing overlay multicast networks and their costs Purdue Univ., West Lafayette, IN, Tech. Rep. CSD-TR-04- 007, 2004.
[27]
{27} J. Winick and S. Jamin, Inet-3.0: Internet Topology Generator Univ. Michigan, Ann Arbor, Tech. Rep. UM-CSE-TR-456-02, 2002.
[28]
{28} S. Jin and A. Bestavros, Small-world internet topologies: Possible causes and implications on scalability of end-system multicast Boston Univ., Boston, MA, Tech. Rep. BUCS-TR-2002-004, 2002.
[29]
{29} E. Zegura, K. Calvert, and S. Bhattacharjee, "How to model an internetwork," in Proc. IEEE INFOCOM, 1996, pp. 594-602.
[30]
{30} M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron, "Scribe: A large-scale and decentralized application-level multicast infrastructure," IEEE J. Sel. Areas Commun., vol. 20, no. 8, pp. 1489-1499, Oct. 2002.
[31]
{31} S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, "Topologically-aware overlay construction and server selection," in Proc. IEEE INFOCOM , 2002, pp. 1190-1199.
[32]
{32} N. Malouch, Z. Liu, D. Rubenstein, and S. Sahu, "A graph theoretic approach to bounding delay in proxy-assisted, end-system multicast," in Proc. IWQoS, May 2002, pp. 106-115.
[33]
{33} P. Radoslavov, H. Tangmunarunkit, H. Yu, R. Govindan, S. Shenker, and D. Estrin, On characterizing network topologies and analyzing their impact on protocol design Dept. Comput. Sci., Univ. Southern California, Los Angeles, Tech. Rep. USC-CS-TR-00-731, Feb. 2000.
[34]
{34} P. Mieghem, G. Hooghiemstra, and R. Hofstad, "On the efficiency of multicast," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 719-732, Dec. 2001.
[35]
{35} W. Szpankowski, Average Case Analysis of Algorithms in Sequences . New York: Wiley, 2001.

Cited By

View all

Recommendations

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

Publisher

IEEE Press

Publication History

Published: 01 April 2007
Published in TON Volume 15, Issue 2

Author Tags

  1. economies of scale
  2. group communication
  3. internet multicast
  4. overlay multicast
  5. overlay networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Fairness-oriented multicast routing for distributed interactive applicationsComputer Communications10.1016/j.comcom.2024.03.015219:C(229-242)Online publication date: 2-Jul-2024
  • (2020)Equitable Optimization for Multicast CommunicationInternational Journal of Decision Support System Technology10.4018/IJDSST.202007010112:3(1-25)Online publication date: 1-Jul-2020
  • (2015)Efficient massive contents distribution strategy for P2P using sensor smart networkInternational Journal of Distributed Sensor Networks10.1155/2015/5690632015(4-4)Online publication date: 1-Jan-2015
  • (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
  • (2010)Server selection in large-scale video-on-demand systemsACM Transactions on Multimedia Computing, Communications, and Applications10.1145/1671954.16719556:1(1-26)Online publication date: 22-Feb-2010
  • (2010)DOMIEEE Network: The Magazine of Global Internetworking10.1109/MNET.2010.551091824:4(45-51)Online publication date: 1-Jul-2010
  • (2010)An adaptive peer-to-peer live streaming system with incentives for resilienceComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2009.10.02254:8(1316-1327)Online publication date: 1-Jun-2010
  • (2009)Establishment and traffic measurement of overlay multicast testbed in KOREN, THaiREN and TEIN2Proceedings of the 6th International Conference on Mobile Technology, Application & Systems10.1145/1710035.1710077(1-7)Online publication date: 2-Sep-2009
  • (2009)Design of a scalable multicast scheme with an application-network cross-layer approachIEEE Transactions on Multimedia10.1109/TMM.2009.202610411:6(1160-1169)Online publication date: 1-Oct-2009
  • (2008)ClimberProceedings of the 7th international conference on Peer-to-peer systems10.5555/1855641.1855651(10-10)Online publication date: 25-Feb-2008
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media