On the Delay Advantage of Coding in Packet Erasure Networks

We consider the delay of network coding compared to routing with retransmissions in packet erasure networks with probabilistic erasures. We investigate the sublinear term in the block delay required for unicasting n packets and show that there is an unbounded gap between network coding and routing. In particular, we show that delay benefit of network coding scales at least as √n. Our analysis of the delay function for the routing strategy involves a major technical challenge of computing the expectation of the maximum of two negative binomial random variables. Previous characterizations of this expectation are approximate; we derive an exact characterization and analyze its scaling behavior, which may be of independent interest. We also use a martingale bounded differences argument to show that the actual coding delay is concentrated around its expectation.