An Analysis of Finite-Memory Random Linear Coding on Packet Streams

Desmond S.  Lun; Muriel  Medard; Payam  Pakzad; Christina  Fragouli; Ralf  Koetter

2nd International ICST Workshop on Network Coding, Theory, and Applications

Research Article

An Analysis of Finite-Memory Random Linear Coding on Packet Streams

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2006.1666502,
    author={Desmond S.  Lun and Muriel  Medard and Payam  Pakzad and Christina  Fragouli and Ralf  Koetter},
    title={An Analysis of Finite-Memory Random Linear Coding on Packet Streams},
    proceedings={2nd International ICST Workshop on Network Coding, Theory, and Applications},
    publisher={IEEE},
    proceedings_a={NETCOD},
    year={2006},
    month={8},
    keywords={},
    doi={10.1109/WIOPT.2006.1666502}
}

Desmond S. Lun
Muriel Medard
Payam Pakzad
Christina Fragouli
Ralf Koetter
Year: 2006
An Analysis of Finite-Memory Random Linear Coding on Packet Streams
NETCOD
IEEE
DOI: 10.1109/WIOPT.2006.1666502

Desmond S. Lun¹^,*, Muriel Medard¹^,*, Payam Pakzad²^,*, Christina Fragouli²^,*, Ralf Koetter³^,*

1: Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
2: Laboratoire d’algorithmique, Ecole Polytechnique Federale de Lausanne, CH-1015 Lausanne, Switzerland
3: Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA

*Contact email: dslun@mit.edu, medard@mit.edu, payam.pakzad@epfl.ch, christina.fragouli@epfl.ch, koetter@uiuc.edu

Abstract

We consider the following packet coding scheme: The coding node has a fixed, finite memory in which it stores packets formed from an incoming packet stream, and it sends packets formed from random linear combinations of its memory contents. We analyze the scheme in two settings: as a self-contained component in a network providing reliability on a single link, and as a component employed at intermediate nodes in a block-coded end-to-end connection. We believe that the scheme is a good alternative to automatic repeat request when feedback is too slow, too unreliable, or too difficult to implement.

Published: 2006-08-07
Publisher: IEEE

: http://dx.doi.org/10.1109/WIOPT.2006.1666502