On the Delay Distribution of Random Linear Network Coding

• Tipo: Artigo em Revista Científica Internacional
• Data: 2011

Autores

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

Revista

Título: IEEE Journal on Selected Areas in Communications

Vol. 29 Nº 5

Páginas: 1084-1093

ISSN: 0733-8716

Editora: IEEE

Indexação

ISI Web of Science

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia electrotécnica, electrónica e informática

Outras Informações

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).

Idioma: Inglês

Tipo (Avaliação Docente): Científica