On coding for reliable communication over packet networks

Desmond S. Lun, Muriel Médard, Ralf Koetter, Michelle Effros

Research output: Contribution to journalArticlepeer-review

235 Scopus citations

Abstract

We consider the use of random linear network coding in lossy packet networks. In particular, we consider the following simple strategy: nodes store the packets that they receive and, whenever they have a transmission opportunity, they send out coded packets formed from random linear combinations of stored packets. In such a strategy, intermediate nodes perform additional coding yet do not decode nor wait for a block of packets before sending out coded packets. Moreover, all coding and decoding operations have polynomial complexity. We show that, provided packet headers can be used to carry an amount of side-information that grows arbitrarily large (but independently of payload size), random linear network coding achieves packet-level capacity for both single unicast and single multicast connections and for both wireline and wireless networks. This result holds as long as packets received on links arrive according to processes that have average rates. Thus packet losses on links may exhibit correlations in time or with losses on other links. In the special case of Poisson traffic with i.i.d. losses, we give error exponents that quantify the rate of decay of the probability of error with coding delay. Our analysis of random linear network coding shows not only that it achieves packet-level capacity, but also that the propagation of packets carrying "innovative" information follows the propagation of jobs through a queueing network, thus implying that fluid flow models yield good approximations.

Original languageEnglish (US)
Pages (from-to)3-20
Number of pages18
JournalPhysical Communication
Volume1
Issue number1
DOIs
StatePublished - Mar 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Keywords

  • Capacity
  • Erasure networks
  • Network coding
  • Packets
  • Relay networks

Fingerprint Dive into the research topics of 'On coding for reliable communication over packet networks'. Together they form a unique fingerprint.

Cite this