Asymptotic Rate Limits for Randomized Broadcasting With Network Coding

Date Added: Oct 2009
Format: PDF

Motivated by peer-to-peer content distribution and media streaming applications, the authors study the broadcasting problem in a time-discretized model, with integer valued upload and download capacity constraints at nodes. The authors analyze both deterministic centralized and randomized decentralized protocols that can achieve optimal packet receiving rates at the nodes. In particular, the authors consider a simple scheme that requires each node, in each time slot, to transmit to a random neighbor that is not yet chosen by any other nodes in that slot. They prove that such a surprisingly simple scheme can asymptotically achieve the optimal receiving rates in complete graphs with homogeneous node capacity. The proof involves applying randomized network coding and deriving the max-flow bounds achieved in the resulting transmission schedule.