Tree Network Coding for Peer-to-Peer Networks

摘要

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 log~2 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 log~3 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) plog~2 n trees which results in a read/write complexity of O((δ + 1)~(t-1) nlog~3 n) for t rounds and in-degree δ.