Classifying peer-to-peer network coding schemes

ABSTRACT

Modern 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 face the problem of dynamic participation of the peers and dynamic bandwidth in the network. A leaving peer can cause an unrecoverable loss of blocks and obstruct further downloads of the file. Furthermore, the choice which block needs to be sent to which peer is a hard question. A random choice leads to the coupon collector problem which decreases the transmission rate. Filesharing networks like BitTorrent or Splitstream face such problems.

Network Coding overcomes this problem by using error redundant codes of all blocks of the file. An efficient randomized variant of it, Practical Network Coding, transmits and recombines random linear combinations of the blocks of the partitioned file. As soon as enough linear combinations have been gathered, the original file can be decoded by a matrix operation, optimizing the network flow in any peer-to-peer network.

All known Network Coding schemes, however, suffer from a quadratic cost of read/write disk operations for both encoding and decoding. Since there is an increasing gap between the speed of mass storage devices and the main memory, this poses an obstacle to a wider use of Network Coding schemes.

In this paper we present and investigate new network coding schemes, which form a compromise between Network Coding and uncoded block transfer schemes like BitTorrent. These schemes, called Paircoding and Treecoding have smaller read/write costs for encoding and decoding than Practical Network Coding and higher throughput than BitTorrent.

We develop a new framework for comparing the throughput of data (performance) of such peer-to-peer file sharing systems and classify these systems, as well as a BitTorrent variant which uses forward error correction. The dynamics of peer-to-peer networks are described by a round model where the set of participating peers and their link quality changes after each round.

The framework compares two schemes for all possible dynamic scenarios. If the transmission rate of scheme A is at least as well as scheme B, then we say A performs as well as B. If this is the case and there is a scenario where A is better than B, we say A outperforms B. We show that all of our proposed coding schemes outperform BitTorrent, while being outperformed by Network Coding.

This leads to a hierarchy, where BitTorrent is the worst performer and Network Coding is the best performer regarding throughput. Regarding computation (disk read/write) complexity for decoding, BitTorrent and Foward Error Correction have linear time behavior, for Paircoding it is almost linear, Treecoding with one coding tree needs time O(n) and Network Coding has time O(n2).

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 , C. Liu , P. Sharma , L. Wei, Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification, RFC Editor, 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 , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564877]
• 9: Dave Levin , Katrina LaCurts , Neil Spring , Bobby Bhattacharjee, Bittorrent is an auction: analyzing and improving bittorrent's incentives, ACM SIGCOMM Computer Communication Review, v.38 n.4, October 2008
• 10: Christian Ortolf , Christian Schindelhauer , Arne Vater, Paircoding: Improving File Sharing Using Sparse Network Codes, Proceedings of the 2009 Fourth International Conference on Internet and Web Applications and Services, p.49-57, May 24-28, 2009 [doi>10.1109/ICIW.2009.16]
• 11: Michael Piatek, Tomas Isdal, Thomas Anderson, Arvind Krishnamurthy, and Arun Venkataramani. Do incentives build robustness in BitTorrent? In NSDI'07, Cambridge, MA, April 2007.
• 12: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.161-172, October 2001
• 13: Sylvia Ratnasamy , Mark Handley , Richard M. Karp , Scott Shenker, Application-Level Multicast Using Content-Addressable Networks, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.14-29, November 07-09, 2001
• 14: I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300--304, June 1960.
• 15: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 16: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 17: D. Waitzman , C. Partridge , S. E. Deering, Distance Vector Multicast Routing Protocol, RFC Editor, 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 , John D. Kubiatowicz, Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.11-20, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378347]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Nonsecret encoding schemes**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Performance

Keywords:
bittorrent, network coding, peer-to-peer networks