A Caltech Library Service

Network Error Correction With Unequal Link Capacities

Kim, Sukwon and Ho, Tracey and Effros, Michelle and Avestimehr, Amir Salman (2011) Network Error Correction With Unequal Link Capacities. IEEE Transactions on Information Theory, 57 (2). pp. 1144-1164. ISSN 0018-9448.

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

Use this Persistent URL to link to this item:


This paper studies the capacity of single-source single-sink noiseless networks under adversarial or arbitrary errors on no more than z edges. Unlike prior papers, which assume equal capacities on all links, arbitrary link capacities are considered. Results include new upper bounds, network error-correction coding strategies, and examples of network families where our bounds are tight. An example is provided of a network where the capacity is 50% greater than the best rate that can be achieved with linear coding. While coding at the source and sink suffices in networks with equal link capacities, in networks with unequal link capacities, it is shown that intermediate nodes may have to do coding, nonlinear error detection, or error correction in order to achieve the network error-correction capacity.

Item Type:Article
Related URLs:
Additional Information:© 2011 IEEE. Manuscript received April 16, 2010; revised August 07, 2010; accepted September 24, 2010. Date of current version January 19, 2011. This work was supported in part by Subcontract #069153 issued by BAE Systems National Security Solutions, Inc. and by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare System Center (SPAWARSYSCEN), San Diego under Contract N66001-08-C-2013, by the National Science Foundation under Grant CNS 0905615, and by the California Institute of Technology Lee Center for Advanced Networking. The work of A. S. Avestimehr was supported in part by the NSF CAREER award 0953117. This paper is part of the special issue on “Facets of Coding Theory: From Algorithms to Networks,” dedicated to the scientific legacy of Ralf Koetter. The authors would like to thank the reviewers for their very insightful and detailed suggestions that were most helpful in improving this paper.
Funding AgencyGrant Number
BAE Systems National Security Solutions, Inc.069153
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Space and Naval Warfare System Center (SPAWARSYSCEN), San DiegoN66001-08-C-2013
NSFCNS 0905615
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Adversarial errors; Byzantine adversary; network coding; network error correction; nonlinear coding
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number11769520
Issue or Number:2
Record Number:CaltechAUTHORS:20110316-153639993
Persistent URL:
Official Citation:Sukwon Kim; Ho, T.; Effros, M.; Avestimehr, A.S.; , "Network Error Correction With Unequal Link Capacities," Information Theory, IEEE Transactions on , vol.57, no.2, pp.1144-1164, Feb. 2011 doi: 10.1109/TIT.2010.2095090 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22942
Deposited By: Tony Diaz
Deposited On:16 Mar 2011 22:45
Last Modified:03 Oct 2019 02:41

Repository Staff Only: item control page