A Caltech Library Service

Universal and Robust Distributed Network Codes

Ho, Tracey and Jaggi, Sidharth and Vyetrenko, Svitlana and Xia, Lingxiao (2011) Universal and Robust Distributed Network Codes. In: 2011 IEEE Infocom Conference Proceedings. IEEE , Piscataway, NJ, pp. 766-774. ISBN 978-1-4244-9919-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Random linear network codes can be designed and implemented in a distributed manner, with low computational complexity. However, these codes are classically implemented over finite fields whose size depends on some global network parameters (size of the network, the number of sinks) that may be unknown prior to code design. Also, the entire network code may have to be redesigned when a new node joins. In this work, we present the first universal and robust distributed linear network coding schemes. Our schemes are universal since they are independent of all network parameters. They are robust since in case nodes join or leave, the remaining nodes do not need to change their coding operations and the receivers can still decode. They are distributed since nodes need only have topological information about the part of the network upstream of them, which can be naturally streamed as part of the communication protocol. We present both probabilistic and deterministic schemes that are all asymptotically rate-optimal in the coding block-length, and have guarantees of correctness. Our probabilistic designs are computationally efficient, with order-optimal complexity. Our deterministic designs guarantee zero error decoding, albeit via codes with high computational complexity in general. Our coding schemes are based on network codes over “scalable fields”. Instead of choosing coding coefficients from one field at every node as in, each node uses linear coding operations over an “effective field-size” which depends on the node's distance from the source node. The analysis of our schemes requires technical tools that may be of independent interest. In particular, we generalize the Schwartz-Zippel lemma by proving a nonuniform version, wherein variables are chosen from sets of possibly different sizes. We also provide a novel robust distributed algorithm to assign unique IDs to network nodes.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE. Date of Current Version: 30 June 2011. This work was supported in part by RGC GRF grant 412608. University Grants Committee of the Hong Kong Special Administrative Region China (Project No. AoEIE-02/08), support from CUHK's MoE-Microsoft Key Laboratory of Human-centric Computing and Interface Technologies, the Air Force Office of Scientific Research under grant FA9550-10-1-0166 and Caltech's Lee Center for Advanced Networking.
Funding AgencyGrant Number
RGC GRF412608
Hong Kong Special Administrative Region University Grants CommitteeAoE/E-02/08
CUHK MoE-Microsoft Key Laboratory of Human-centric Computing and Interface TechnologiesUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-10-1-0166
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number 12086050
Record Number:CaltechAUTHORS:20120405-100929836
Persistent URL:
Official Citation:Ho, T.; Jaggi, S.; Vyetrenko, S.; Lingxiao Xia; , "Universal and robust distributed network codes," INFOCOM, 2011 Proceedings IEEE , vol., no., pp.766-774, 10-15 April 2011 doi: 10.1109/INFCOM.2011.5935297 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29993
Deposited By: Ruth Sustaita
Deposited On:05 Apr 2012 18:25
Last Modified:03 Oct 2019 03:46

Repository Staff Only: item control page