skip to main content
10.1145/1073814.1073824acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding

Published: 17 July 2005 Publication History

Abstract

We propose a scheme for building peer-to-peer overlay networks for broadcasting using network coding. The scheme addresses many practical issues such as scalability, robustness, constraints on bandwidth, and locality of decisions. We analyze the system theoretically and prove near optimal bounds on the parameters defining robustness and scalability. As a result we show that the effects of failures are contained locally, allowing the network to grow exponentially with server load. We also argue that adversarial failures are no more harmful than random failures.

References

[1]
R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network information flow IEEE Trans. Information Theory, IT-46 (2000), pp. 1204--1216.
[2]
A. Albanese, J. Blomer, J. Edmonds, M. Luby, and M. Sudan. Priority encoding transmission IEEE Trans. Information Theory, 42 (1996), pp. 1737--1744.
[3]
J. W. Byers, J. Considine, M. Mitzenmacher, and S. Rost. Informed content delivery across adaptive overlay networks in Proc. SIGCOMM, Pittsburgh, PA, Aug. 2002, ACM.
[4]
M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and A. Singh Splitstream: High-bandwidth content distribution in a cooperative environment in Proc. Int'l Workshop on Peer-to-Peer Systems, Feb. 2003.
[5]
P. Chou, Y. Wu, and K. Jain. Practical network coding. in Proc. Allerton Conf. Communications, Control, and Computing, Monticello, IL, Oct.2003.
[6]
Y. Chu, S. G. Rao, and H. Zhang A case for end system multicast in Joint Int'l Conf. Measurement and Modeling of Computer Systems (SIGMETRICS), June 2000.
[7]
B. Cohen Incentives build robustness in BitTorrent. http://bitconjurer.org/BitTorrent/bittorrentecon.pdf, May 2003.
[8]
J. Edmonds. Edge-disjoint branchings in Combinatorial Algorithms, R. Rustin, ed., Academic Press, NY, 1973, pp.91--96.
[9]
S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding IEEE Trans. Information Theory, IT-49 (2003), pp. 371--381.
[10]
V. N. Padmanabhan, H. J. Wang, and P. A. Chou. Resilient peer-to-peer streaming inProc. Int'l Conf. Network Protocols, Atlanta, GA, Nov. 2003.
[11]
______, Supporting heterogeneity and congestion control in peer-to-peer multicast streaming inProc. Int'l Workshop on Peer-to-Peer Systems, San Diego, CA, Feb. 2004.
[12]
R. Rejaie and S. Stafford. A framework for architecting peer-to-peer receiver-driven overlays in Proc. Int'l Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), Kinsale, Ireland, June 2004.
[13]
P. Rodriguez and C. Gkantsidis. Revolutionising content distribution. in Proc. Conf. Computer Communications (INFOCOM), Miami, FL, USA, Mar. 2005, IEEE.

Cited By

View all
  • (2017)Information transmission based on network coding over wireless networksTelecommunications Systems10.1007/s11235-016-0247-265:4(551-565)Online publication date: 1-Aug-2017
  • (2013)An efficient ECC-based mechanism for securing network coding-based P2P content distributionPeer-to-Peer Networking and Applications10.1007/s12083-013-0239-x7:4(572-589)Online publication date: 10-Nov-2013
  • (2012)Performance evaluation of video dissemination protocols over Vehicular Networks37th Annual IEEE Conference on Local Computer Networks -- Workshops10.1109/LCNW.2012.6424052(694-701)Online publication date: Oct-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing
July 2005
364 pages
ISBN:1581139942
DOI:10.1145/1073814
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 July 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Azuma
  2. coding
  3. file distribution
  4. inequalities
  5. multicast
  6. network
  7. overlay
  8. peer-to-peer
  9. security

Qualifiers

  • Article

Conference

PODC05

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2017)Information transmission based on network coding over wireless networksTelecommunications Systems10.1007/s11235-016-0247-265:4(551-565)Online publication date: 1-Aug-2017
  • (2013)An efficient ECC-based mechanism for securing network coding-based P2P content distributionPeer-to-Peer Networking and Applications10.1007/s12083-013-0239-x7:4(572-589)Online publication date: 10-Nov-2013
  • (2012)Performance evaluation of video dissemination protocols over Vehicular Networks37th Annual IEEE Conference on Local Computer Networks -- Workshops10.1109/LCNW.2012.6424052(694-701)Online publication date: Oct-2012
  • (2011)Layered Video Transmission Using Wireless Path Diversity Based on Grey Relational Analysis2011 IEEE International Conference on Communications (ICC)10.1109/icc.2011.5962784(1-6)Online publication date: Jun-2011
  • (2011)A new deterministic source coding method in peer-to-peer systems2011 IEEE 12th International Symposium on Computational Intelligence and Informatics (CINTI)10.1109/CINTI.2011.6108539(403-408)Online publication date: Nov-2011
  • (2010)A resilient and low-delay P2P streaming system based on network coding with random multicast trees2010 IEEE International Workshop on Multimedia Signal Processing10.1109/MMSP.2010.5662054(400-405)Online publication date: Oct-2010
  • (2010)Video transport over VANETsProceedings of the 2010 IEEE 35th Conference on Local Computer Networks10.1109/LCN.2010.5735735(32-39)Online publication date: 10-Oct-2010
  • (2010)Analyzing stream building processes in P2P streaming systems2010 5th International Conference on Computer Science & Education10.1109/ICCSE.2010.5593455(952-956)Online publication date: Aug-2010
  • (2010)An efficient dynamic-identity based signature scheme for secure network codingComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2009.08.00654:1(28-40)Online publication date: 1-Jan-2010
  • (2010)An immunological approach for file recovery over JXTA peer-to-peer frameworkInternational Journal of Network Management10.1002/nem.74120:4(181-197)Online publication date: 1-Jul-2010
  • Show More Cited By

View Options

Login options

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