A Caltech Library Service

A Random Linear Network Coding Approach to Multicast

Ho, Tracey and Médard, Muriel and Koetter, Ralf and Karger, David R. and Effros, Michelle and Shi, Jun and Leong, Ben (2006) A Random Linear Network Coding Approach to Multicast. IEEE Transactions on Information Theory, 52 (10). pp. 4413-4430. ISSN 0018-9448. doi:10.1109/TIT.2006.881746.

See Usage Policy.


Use this Persistent URL to link to this item:


We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly select linear mappings from inputs onto output links over some field. We show that this achieves capacity with probability exponentially approaching$1$with the code length. We also demonstrate that random linear coding performs compression when necessary in a network, generalizing error exponents for linear Slepian–Wolf coding in a natural way. Benefits of this approach are decentralized operation and robustness to network changes or link failures. We show that this approach can take advantage of redundant network capacity for improved success probability and robustness. We illustrate some potential advantages of random linear network coding over routing in two examples of practical scenarios: distributed network operation and networks with dynamically varying connections. Our derivation of these results also yields a new bound on required field size for centralized network coding on general multicast networks.

Item Type:Article
Related URLs:
URLURL TypeDescription
Shi, Jun0000-0003-1647-7762
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Manuscript received February 26, 2004; revised June 1, 2006. [Posted online: 2006-09-25] This work was supported in part by the National Science Foundation under Grants CCF-0325324, CCR-0325673, and CCR-0220039, by Hewlett-Packard under Contract 008542-008, and by Caltech’s Lee Center for Advanced Networking. Communicated by A. Ashikhmin, Associate Editor for Coding Theory. The authors would like to thank the anonymous reviewers for their detailed comments and suggestions which helped to substantially improve the presentation of this paper.
Subject Keywords:Distributed compression, distributed networking, multicast, network coding, random linear coding
Issue or Number:10
Record Number:CaltechAUTHORS:HOTieeetit06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5107
Deposited By: Archive Administrator
Deposited On:01 Oct 2006
Last Modified:08 Nov 2021 20:22

Repository Staff Only: item control page