Analysis of Sparse Network Coding Method for Real-Time Applications

Sparse network coding was introduced to reduce the computational complexity of the random linear network coding. In this method, most of the decoding matrix coefficients are zero. Partial decoding means the possibility of decoding a part of the raw packets is one of the capabilities of the sparse network coding method. We introduce three different models of sparse coding method as an approach to reduce decoding latency in real-time communication. More precisely, we first evaluate a sparse network coding for a no feedback configuration in terms of the performance of the total number of transmissions required, and the average packet decoding delay for a generation of raw packets, by introducing a Markov chain-based model. Then we evaluate the accuracy of the proposed model using extensive simulation and show that the proposed model can accurately estimate the number of required transmissions and decoding delay for a generation of packets. The results also evaluate the accuracy of the model in the erasure channel. In the following, we introduce the feedback-based model and we show that this model can create a better balance between the functions of the number of transmissions and the average decoding delay per packet. Finally, by focusing on the problem of finding the random spanning tree, we present a graph-based model for analyzing sparse network coding and show that although the proposed model is valid only for grade 2 sparsity, it also has the capacity to develop for lower sparsity.