r-Regular P2P Broadcast Networks: Optimal Delay and Throughput Using Network Coding

Abstract

We introduce a homogeneous r-regular network model for a peer-to-peer (P2P) video broadcast network. Such networks are simple to construct and allow the implementation of fairness strategies. We use our model to show why the greedy and rarest first push-based strategies give the suboptimal performance often observed in the literature. We propose a novel network coding based transmission strategy and prove that it results in optimal playback delay and throughput performance.