A Markov Chain Model for Sparse Network Coding

Random Linear Network Coding (RLNC) has been demonstrated to provide an efficient communication scheme, leveraging a considerable stability against packet losses in error-prone network. However, it suffers from a high computational complexity and some novel approaches have been recently proposed. One of such solutions is Tunable Sparse Network Coding (TSNC), where merely few original packets are mixed in each transmission. The number of original packets to be mixed in each transmission can be chosen from a density parameter/distribution, which could be eventually adapted. In this article, we present a complete analytical model that describes the performance of SNC on a precise way. We exploit an absorbing Markov model where the states are defined by the number of transmitted coded packets received by the decoder, and the number of non-zero columns at decoding matrix. The model is validated by use of a simulation campaign, and the difference between model and simulation is negligible. The proposed model would enable a more accurate evaluation of the behavior of SNC techniques for large finite field size.