The Failure Probabilities of Random Linear Network Coding at Sink Nodes

Dan LI  Xuan GUANG  Fang-Wei FU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1255-1259
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1255
Type of Manuscript: LETTER
Category: Information Theory
network coding,  random linear network coding,  failure probability at sink nodes,  upper/lower bounds,  network topology information,  tightness,  

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

In the paradigm of network coding, when the network topology information cannot be utilized completely, random linear network coding (RLNC) is proposed as a feasible coding scheme. But since RLNC neither considers the global network topology nor coordinates codings between different nodes, it may not achieve the best possible performance of network coding. Hence, the performance analysis of RLNC is very important for both theoretical research and practical applications. Motivated by a fact that different network topology information can be available for different network communication problems, we study and obtain several upper and lower bounds on the failure probability at sink nodes depending on different network topology information in this paper, which is also the kernel to discuss some other types of network failure probabilities. In addition, we show that the obtained upper bounds are tight, the obtained lower bound is asymptotically tight, and we give the worst cases for different scenarios.