Analysis of Sparse Network Coding Method for Real-Time Applications

Document Type : Original Article

Authors

1 Department of Computer Science and Information Technology, Institute for Advanced Studies in Basic Sciences

2 Department of Computer Science and Information Technology

3 Department of Computer Science and Information Technology/ IASBS University

Abstract

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.

Keywords

References

Panwar, Sh. Sharma and A. K. Singh, “A survey on 5g: the next generation of mobile communication,” Physical Communication, vol.18, pp.64-84, 2016.
Cvijetic, Optical Network Evolution For 5g Mobile Applications And SDN-based Control, 2014 16th International Telecommunications Network Strategy and Planning Symposium (Networks), pp.1-5, 2014.
Garrido, D. E. Lucani, and R. Agüero, “A markov chain model for the decoding probability of sparse network coding,” IEEE Transactions on Communications, vol.65, no.4, pp.1675-1685, 2017.
Garrido, D. E. Lucani, and R. Aguero, How to tune sparse network coding over wireless links, 2017 IEEE Wireless Communications and Networking Conference (WCNC), pp 1-6, 2017.
Heide, M. V. Pedersen, F. K. H. P. Fitzek, and M.  Médard, “On code parameters and coding vector representation for practical rlnc,” 2011 IEEE International Conference on Communications (ICC), pp1-5, 2011.
Ho, M. Médard, R.  Koetter, D.  R.  Karger, M.  Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Transactions on Information Theory, vol.52, no.10, pp.4413-4430, 2006.
Ho, M.  Medard, J. Shi, M.  Effros, and D. R. Karger, On Randomized Network Coding, In Proceedings of the Annual Allerton Conference on Communication Control and Computing, vol.41, no.1,  pp.11-20, 2003.
Silva, W. Zeng, and F. R.  Kschischang, Sparse Network Coding with Overlapping Classes. 2009 Workshop on Network Coding, Theory, and Applications, pp.74-79, 2009.
W. Sorensen, A. S Badr, J. A. Cabrera, D. E. Lucani, J. Heide, and F. H. P. Fitzek, A Practical View on Tunable Sparse Network Coding, Proceedings of European Wireless 2015; 21th European Wireless Conference, pp.1-6, 2015.
Sanghavi, Intermediate Performance of Rateless Codes, 2007 IEEE Information Theory Workshop, pp.478-48, 2007.
Talari and N. Rahnavard, “On the intermediate symbol recovery rate of rateless codes”, IEEE Transactions on Communications, vol.60, no.5, pp.1237-1242, 2012.
Jun, P. Yang, J.  No, and H.  Park, “New fountain codes with improved intermediate recovery based on batched zigzag coding,” IEEE Transactions on Communications, vol.65, no.1, pp.23-36, 2017.
Kamra, V. Misra, J. Feldman, and D. Rubenstein, Growth codes: maximizing sensor network data persistence, Proceedings of The 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp.255-266, 2006.
Zarei, P. Pahlevani and M. Davoodi, “On the partial decoding delay of sparse network coding,” IEEE Communications Letters, vol. 22, pp.1668-1671, 2018.
Zarei, P. Pahlevani and D. E. Lucani, “An Analytical model for sparse network codes: Field Size considerations,” IEEE Communications Letters, vol.24, pp.729 -733, 2020.
Peterson and B. Davie, Computer networks: a systems approach, Elsevier, 2007.
B. Wilson, Generating Random Spanning Trees More Quickly Than The Cover Time, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp.296-303, 1996.
Pedersen, J.Heide and F.H.Fitzek, KODO: An Open And Research Oriented Network Coding Library, International Conference on Research in Networking, pp.145-152, 2011.

Files

Share

How to cite

Statistics