Dikaliotis, Theodoros K. and Dimakis, Alexandros G. and Ho, Tracey and Effros, Michelle (2009) On the delay of network coding over line networks. In: ISIT 2009. IEEE , Piscataway, NJ, pp. 1408-1412. ISBN 978-1-4244-4312-3 http://resolver.caltech.edu/CaltechAUTHORS:20100816-110713053
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100816-110713053
We analyze a simple network where a source and a receiver are connected by a line of erasure channels of different reliabilities. Recent prior work has shown that random linear network coding can achieve the min-cut capacity and therefore the asymptotic rate is determined by the worst link of the line network. In this paper we investigate the delay for transmitting a batch of packets, which is a function of all the erasure probabilities and the number of packets in the batch. We show a monotonicity result on the delay function and derive simple expressions which characterize the expected delay behavior of line networks. Further, we use a martingale bounded differences argument to show that the actual delay is tightly concentrated around its expectation.
|Item Type:||Book Section|
|Additional Information:||© 2009 IEEE. This material is partly funded by subcontract #069153 issued by BAE Systems National Security Solutions, Inc. and supported by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego under Contract No. N66001- 08-C-2013, and by Caltech’s Lee Center for Advanced Networking.|
|Other Numbering System:|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||16 Aug 2010 18:14|
|Last Modified:||26 Dec 2012 12:19|
Repository Staff Only: item control page