Asymptotic Optimality of Randomized Peer-to-Peer Broadcast With Network Coding

The authors consider the problem of distributing k blocks from a source to N nodes in a Peer-to-Peer (P2P) network with both node upload and download capacity constraints. As k scales up, they prove for homogeneous networks that if network coding is allowed, randomly matching senders and receivers in each time slot asymptotically achieves the maximum downloading rate at each node. For heterogeneous networks with network coding allowed, they show that a fair and optimal downloading rate at each node can be asymptotically approached, if in each time slot, each node randomly allocates its upload bandwidth to its receivers that have available download bandwidth.