A Caltech Library Service

Network codes with deadlines

Erez, Elona and Effros, Michelle and Ho, Tracey (2008) Network codes with deadlines. In: 46th Annual Allerton Conference on Communication, Control, and Computing. IEEE , Piscataway, NJ, pp. 339-346. ISBN 978-1-4244-2925-7.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


We investigate the effect of decoding deadlines on network coding capacity, specifically, the capacity curve of a network as a function of the allowed delay from the time a set of bits is transmitted by the source to the time it is fully decoded by the sinks. We show that scalar linear codes are not optimal even for multicast when the data has deadlines. In fact, infinite blocklength is required in general in order to achieve the optimal performance of linear block codes in these scenarios. We study the case of two types of data, where the first type has a tighter deadline than the other. We find for an interesting family of networks the optimal linear convolutional codes. We formulate a code design criterion for general networks with two data types. Finally, as an alternative approach, we show that the problem of multicast with deadlines can be transformed into a non-multicast problem without deadlines in an extended network. Using that approach, we find an upper bound on the complexity of checking the feasibility of the problem.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2008 IEEE. This work has been supported in part by the Defense Advanced Research Projects Agency (DARPA) under Contract No. W911NF-07-1-0029, and by Caltech’s Lee Center for Advanced Networking.
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)W911NF-07-1-0029
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Record Number:CaltechAUTHORS:20170404-165519201
Persistent URL:
Official Citation:E. Erez, M. Effros and T. Ho, "Network codes with deadlines," 2008 46th Annual Allerton Conference on Communication, Control, and Computing, Urbana-Champaign, IL, 2008, pp. 339-346. doi: 10.1109/ALLERTON.2008.4797577
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:75707
Deposited By: Kristin Buxton
Deposited On:05 Apr 2017 04:31
Last Modified:15 Nov 2021 16:35

Repository Staff Only: item control page