Topological Properties Affect the Power of Network Coding in Decentralized Broadcast

Download Now Date Added: Dec 2009
Format: PDF

There exists a certain level of ambiguity regarding whether network coding can further improve download performance in P2P content distribution systems, as compared to commonly applied heuristics such as rarest first protocols. In this paper, the authors revisit the problem of broadcasting multiple data blocks from a single source in an overlay network using gossip like protocols. The new finding reveals that the marginal benefit of network coding critically depends on the dynamics of network topologies. They show that although network coding is optimal as a block selection mechanism, simple non-coding protocols are close to optimal in complete and random graphs, leading to marginal benefits of network coding.