On the Delay Distribution of Random Linear Network Coding

• Type: Article in International Scientific Journal
• Date: 2011

Authors

Maricica Nistor (Author) FEUP; Daniel E. Lucani (Author) FEUP; Tiago Travassos Vieira Vinhoza (Author) FEUP; Costa, Rui Filipe Mendes Alves da (Author) FEUP; João Francisco Cordeiro de Oliveira Barros (Author) FEUP

Journal

Title: IEEE Journal on Selected Areas in Communications

Vol. 29 No. 5

Pages: 1084-1093

ISSN: 0733-8716

Publisher: IEEE

Indexing

ISI Web of Science

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

Other information

DOI: 10.1109/JSAC.2011.110518

Abstract (EN): A fundamental understanding of the delay behavior of network coding is key towards its successful application in real-time applications with strict message deadlines. Previous contributions focused mostly on the average decoding delay, which although useful in various scenarios of interest is not sufficient for providing worst-case delay guarantees. To overcome this challenge, we investigate the entire delay distribution of random linear network coding for any field size and arbitrary number of encoded symbols (or generation size). By introducing a Markov chain model we are able to obtain a complete solution for the erasure broadcast channel with two receivers. A comparison with Automatic Repeat reQuest (ARQ) with perfect feedback, round robin scheduling and a class of fountain codes reveals that network coding on GF(24) offers the best delay performance for two receivers. We also conclude that GF(2) induces a heavy tail in the delay distribution, which implies that network coding based on XOR operations although simple to implement bears a relevant cost in terms of worst-case delay. For the case of three receivers, which is mathematically challenging, we propose a brute-force methodology that gives the delay distribution of network coding for small generations and field size up to GF(24).

Language: English

Type (Professor's evaluation): Scientific