On the Delay Advantage of Coding in Packet Erasure Networks
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.
Additional Information
© 2014 IEEE. Manuscript received October 13, 2012; revised July 20, 2013; accepted December 21, 2013. Date of publication March 20, 2014; date of current version April 17, 2014. T. K. Dikaliotis and T. Ho were supported in part by BAE Systems National Security Solutions, Inc., under Contract 069153, in part by the Defense Advanced Research Projects Agency, in part by the Space and Naval Warfare System Center, San Diego, CA, USA, under Contract N66001-08-C-2013, in part by Caltech's Lee Center for Advanced Networking, and in part by Lincoln Labs through AFRL under Contract FA8721-05-C-0002. A. G. Dimakis was supported in part by the Center for the Mathematics of Information at Caltech, in part by NSF under Grants CCF 1344179 and 1344364, in part by Google, Los Angeles County, CA, USA, and in part by Intel, Santa Clara, CA. M. Effros was supported by NSF under Grant CCF-1018741. This paper was presented at the 2009 IEEE International Symposium on Information Theory and the 2010 IEEE Information Theory Workshop.Attached Files
Submitted - 1211.3174v1.pdf
Files
Name | Size | Download all |
---|---|---|
md5:a4fcbdcbf496cda15ca847117c4f6fa3
|
522.4 kB | Preview Download |
Additional details
- Eprint ID
- 45964
- DOI
- 10.1109/TIT.2014.2306817
- Resolver ID
- CaltechAUTHORS:20140529-100215879
- 069153
- BAE Systems National Security Solutions, Inc.
- Defense Advanced Research Projects Agency (DARPA)
- N66001-08-C-2013
- Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego
- Caltech Lee Center for Advanced Networking
- FA8721-05-C-0002
- Lincoln Labs AFRL
- Center for the Mathematics of Information, Caltech
- CCF-1344179
- NSF
- CCF-1344364
- NSF
- Intel
- CCF-1018741
- NSF
- Created
-
2014-05-29Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field