On the Delay of Network Coding Over Line Networks
The authors analyze a simple network where a source and a receiver are connected by a line of erasure channels of different reliabilities. Recent prior work has shown that random linear network coding can achieve the min-cut capacity and therefore the asymptotic rate is determined by the worst link of the line network. In this paper, they investigate the delay for transmitting a batch of packets, which is a function of all the erasure probabilities and the number of packets in the batch. They show a monotonicity result on the delay function and derive simple expressions which characterize the expected delay behavior of line networks.