Cited By
View all- AbuDaqa AMahmoud AAbu-Amara MSheltami T(2020)Survey of Network Coding Based P2P File Sharing in Large Scale NetworksApplied Sciences10.3390/app1007220610:7(2206)Online publication date: 25-Mar-2020
Tree network coding for peer-to-peer networks
Pages 114 - 123
Abstract
Partitioning is the dominant technique to transmit large files in peer-to-peer networks. A peer can redistribute each part immediately after its download. BitTorrent combines this approach with incentives for uploads and has thereby become the most successful peer-to-peer network. However, BitTorrent fails if files are unpopular and are distributed by irregularly participating peers. It is known that Network Coding always provides the optimal data distribution, referred as optimal performance. Yet, for encoding or decoding a single code block the whole file must be read and users are not willing to read O(n2) data blocks from hard disk for sending n message blocks. We call this the disk read/write complexity of an encoding.
It is an open question whether fast network coding schemes exist. In this paper we present a solution for simple communication patterns. Here, in a round model each peer can send a limited amount of messages to other peers. We define the depth of this directed acyclic communication graph as the maximum path length (not counting the rounds). In our online model each peer knows the bandwidth of its communication links for the current round, but neither the existence nor the weight of links in future rounds.
In this paper we analyze BitTorrent, Network Coding, Tree Coding, and Tree Network Coding. We show that the average encoding and decoding complexity of Tree Coding is bounded by O(kn log2 n) disk read/write-operations where k is the number of trees and n the number of data blocks.
Tree Coding has perfect performance in communication networks of depth two with a disk read/write complexity of O(pnt log3 n) where p is the number of peers, t is the number of rounds, and n is the number of data blocks. For arbitrary networks Tree Coding performs optimally using 2(δ+1) t-1 p log2 n trees which results in a read/write complexity of O((δ+1)t-1 n log3 n) for t rounds and in-degree δ
References
[1]
R. Ahlswede, Ning Cai, S. Y. R. Li, and R. W. Yeung. Network information flow. Information Theory, IEEE Transactions on, 46(4):1204--1216, 2000.
[2]
M. Castro, P. Druschel, A. Kermarrec, A. Nandi, A. Rowstron, and A. Singh. Splitstream: High-bandwidth content distribution in cooperative environments. In International Workshop on Peer-to-Peer Systems (IPTPS), LNCS, volume 2, 2003.
[3]
M. Castro, P. Druschel, A. Kermarrec, and A. Rowstron. SCRIBE: A large-scale and decentralized application-level multicast infrastructure. IEEE Journal on Selected Areas in communications (JSAC), 20(8):1489--1499, 2002.
[4]
P. Chou, Y. Wu, and K. Jain. Practical network coding. In Proceedings of the 41st Allerton Conference on Communication, Control, and Computing, September 2003.
[5]
Bram Cohen. Incentives build robustness in BitTorrent. Technical report, bittorrent.org, 2003.
[6]
D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, and C. Liu. Protocol independent Multicast-Sparse Mode (PIM-SM): protocol specification. RFC 2362, Internet Engineering Task Force, June 1998.
[7]
Christos Gkantsidis and Pablo Rodriguez. Network coding for large scale content distribution. In INFOCOM, pages 2235--2245. IEEE, 2005.
[8]
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, and Ben Y. Zhao. Distributed object location in a dynamic network. In SPAA'02: Proceedings of the fourteenth annual ACM symposium on parallel algorithms and architectures, pages 41--52, New York, NY, USA, 2002. ACM Press.
[9]
Dave Levin, Katrina Lacurts, Neil Spring, and Bobby Bhattacharjee. Bittorrent is an auction: analyzing and improving bittorrent's incentives. SIGCOMM Comput. Commun. Rev., 38(4):243--254, 2008.
[10]
Christian Ortolf, Christian Schindelhauer, and Arne Vater. Classifying peer-to-peer network coding schemes. In SPAA'09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, pages 310--318, New York, NY, USA, 2009. ACM.
[11]
Christian Ortolf, Christian Schindelhauer, and Arne Vater. Paircoding: Improving File Sharing Using Sparse Network Codes. In ICIW'09: Proceedings of the 2009 Fourth International Conference on Internet and Web Applications and Services, pages 49--57, Washington, DC, USA, 2009. IEEE Computer Society.
[12]
Michael Piatek, Tomas Isdal, Thomas Anderson, Arvind Krishnamurthy, and Arun Venkataramani. Do incentives build robustness in BitTorrent? In NSDI'07, Cambridge, MA, April 2007.
[13]
S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Computer Communication Review, volume 31, pages 161--172. Dept. of Elec. Eng. and Comp. Sci., University of California, Berkeley, 2001.
[14]
Sylvia Ratnasamy, Mark Handley, Richard M. Karp, and Scott Shenker. Application-level multicast using content-addressable networks. In Jon Crowcroft and Markus Hofmann, editors, Networked Group Communication, Third International COST264 Workshop, NGC 2001, London, UK, November 7-9, 2001, Proceedings, volume 2233 of Lecture Notes in Computer Science, pages 14--29. Springer, 2001.
[15]
Antony Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. Lecture Notes in Computer Science, In Proc. of the International Conference on Distributed Systems Platforms (IFIP/ACM), 2218:329--350, 2001.
[16]
Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In Roch Guerin, editor, Proceedings of the ACM SIGCOMM 2001 Conference (SIGCOMM-01), volume 31, 4 of Computer Communication Review, pages 149--160, New York, August 27--31 2001. ACM Press.
[17]
D. Waitzman, C. Partridge, and S. Deering. Distance vector multicast routing protocol. RFC 1075, Internet Engineering Task Force, November 1988.
[18]
Mea Wang and Baochun Li. How practical is network coding? Quality of Service, 2006. IWQoS 2006. 14th IEEE International Workshop on, pages 274--278, June 2006.
[19]
Shelley Q. Zhuang, Ben Y. Zhao, Anthony D. Joseph, Randy H. Katz, and John D. Kubiatowicz. Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In Proceedings of NOSSDAV, June 2001.
Index Terms
- Tree network coding for peer-to-peer networks
Recommendations
Classifying peer-to-peer network coding schemes
SPAA '09: Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architecturesModern peer-to-peer file sharing systems distribute large files among peers using block partitioning. Blocks can be redistributed by a peer even before the whole file is available which highly decreases the distribution time. All peer-to-peer networks ...
Cost-effective broadcast for fully decentralized peer-to-peer networks
Fully unstructured and decentralized peer-to-peer networks such as Gnutella are appealing for a variety of applications, among which file-sharing is the most prominent one. The decentralized nature of these systems provides a high degree of robustness ...
Locality in structured peer-to-peer networks
Distributed hash tables (DHTs), used in a number of structured peer-to-peer (P2P) systems, provide efficient mechanisms for resource placement and location. A key distinguishing feature of current DHT systems, such as Chord, Pastry, CAN and Tapestry, is ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2010
378 pages
Copyright © 2010 ACM.
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: 13 June 2010
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SPAA 10: 22nd ACM Symposium on Parallelism in Algorithms and Architectures
June 13 - 15, 2010
Santorini, Thira, Greece
Acceptance Rates
Overall Acceptance Rate 447 of 1,461 submissions, 31%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 279Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Jan 2025
Other Metrics
Citations
Cited By
View all- AbuDaqa AMahmoud AAbu-Amara MSheltami T(2020)Survey of Network Coding Based P2P File Sharing in Large Scale NetworksApplied Sciences10.3390/app1007220610:7(2206)Online publication date: 25-Mar-2020
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in