2010 · 12 citations · 10 references
ComputingComputer ScienceComputer NetworksDigital CommunicationInformation TheoryCoding TheoryCommunication NetworksErasure CodingError-correcting CodesNetwork Performance AnalysisRoutingCoding-theoretic CommunicationDelay-tolerant NetworkingErasure NetworksNegative Binomial DistributionNegative Binomial ModelsNetwork CodingRetransmission MechanismsRetransmission Protocols
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.
10
On coding for reliable communication over packet networks
Desmond S. Lun, Muriel Médard, R. Koetter et al. · Physical Communication · 2008 · 583 citations · Full text
Capacity of wireless erasure networks
A.F. Dana, Radhika Gowaikar, Ravi Palanki et al. · IEEE Transactions on Information Theory · 2006 · 413 citations
Robert M. Young · The Mathematical Gazette · 1991 · 120 citations