Non-Asymptotic Analysis of Network Coding Delay

Author

Nistor, Maricica ; Costa, Rui A. ; Vinhoza, Tiago T V ; Barros, Joao

Author_Institution

Inst. de Telecomun., Fac. de Eng. da Univ. do Porto, Porto, Portugal

fYear

2010

fDate

9-11 June 2010

Firstpage

1

Lastpage

6

Abstract

We present an expression for the delay distribution of Random Linear Network Coding over an erasure channel with a given loss probability. In contrast with previous contributions, our analysis is non- asymptotic in the sense that it is valid for any field size and any number of symbols. The results confirm that GF(16) already offers near-optimal decoding delay, whereas smaller field sizes (e.g. requiring only XOR operations) induce heavy tails in the delay distribution. A comparison with Automatic Repeat reQuest (ARQ) techniques (with perfect feedback) is also included.

Keywords

automatic repeat request; decoding; delays; linear codes; network coding; random codes; automatic repeat request; delay distribution; erasure channel; near-optimal decoding delay; nonasymptotic analysis; random linear network coding; Added delay; Automatic repeat request; Decoding; Feedback; Galois fields; Network coding; Peer to peer computing; Probability distribution; Telecommunication network reliability; Wireless networks;

fLanguage

English

Publisher

ieee

Conference_Titel

Network Coding (NetCod), 2010 IEEE International Symposium on

Conference_Location

Toronto, ON

Print_ISBN

978-1-4244-7189-8

Electronic_ISBN

978-1-4244-7188-1

Type

conf

DOI

10.1109/NETCOD.2010.5487665

Filename

5487665