On the delay advantage of coding in packet erasure networks

We consider the delay of network coding compared to routing for a family of simple networks with parallel links. We investigate the sub-linear 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 is scaling at least as fast as √n. The main technical contribution involves showing that the delay function for the routing retransmission strategy is unbounded. This problem is equivalent to computing the expected maximum of two negative binomial random variables. This problem has also been addressed previously and we derive the first exact characterization which might be of independent interest.