The Average Failure Probabilities of Random Linear Network Coding

Xuan GUANG  Fang-Wei FU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.10   pp.1991-2001
Publication Date: 2011/10/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1991
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Coding Theory
network coding,  linear network coding,  random network coding,  performance analysis,  average failure probability,  upper bounds,  

Full Text: PDF(368.8KB)>>
Buy this Article

In network coding, for the case that the network topology is unknown completely, random linear network coding has been proposed as an acceptable coding technique. In this paper, we define average failure probability of random linear network coding in order to characterize the performance of random network coding, and then analyze this failure probability for different known topological information of network. We obtain several upper bounds on the failure probabilities, and further show that, for some networks, these upper bounds are tight or asymptotically tight. Moreover, if the more topological information of the network is utilized, the better upper bounds are acquired.