Bottleneck Discovery and Overlay Management in Network Coded Peer-to-Peer Systems

The performance of peer-to-peer (P2P) networks depends critically on the good connectivity of the overlay topology. In this paper we study P2P networks for content distribution (such as Avalanche) that use randomized network coding techniques. The basic idea of such systems is that peers randomly combine and exchange linear combinations of the source packets. A header appended to each packet specifies the linear combination that the packet carries. In this paper we show that the linear combinations a node receives from its neighbors reveal structural information about the network. We propose algorithms to utilize this observation for topology management to avoid bottlenecks and clustering in network-coded P2P systems. Our approach is decentralized, inherently adapts to the network topology, and reduces substantially the number of topology rewirings that are necessary to maintain a well connected overlay. Moreover, this is done passively during the normal content distribution. This work demonstrates another value of using network coding and complements previous work that showed network coding achieves high utilization of the network resources.