On the Delay Advantage of Coding in Packet Erasure Networks
The authors consider the delay of network coding compared to routing for a family of simple networks with parallel links. They 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. This problem turns out to be equivalent with computing the expected maximum of two negative binomial random variables. This problem has also been addressed previously and they derive the first exact characterization which might be of independent interest.