DocumentCode :
45026
Title :
On the Delay Advantage of Coding in Packet Erasure Networks
Author :
Dikaliotis, Theodoros K. ; Dimakis, Alexandros G. ; Ho, Tracey ; Effros, Michelle
Author_Institution :
California Inst. of Technol., Pasadena, CA, USA
Volume :
60
Issue :
5
fYear :
2014
fDate :
May-14
Firstpage :
2868
Lastpage :
2883
Abstract :
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.
Keywords :
delays; network coding; packet radio networks; telecommunication network routing; block delay; delay function; martingale bounded differences; negative binomial random variables; network coding; network routing; packet erasure networks; packet unicasting; Delays; Encoding; Network coding; Nickel; Random variables; Routing; Spread spectrum communication; Block delay; network coding; packet erasure correction; unicast;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2014.2306817
Filename :
6776539
Link To Document :
بازگشت