Network coding was introduced by Ahlswede et al. in a pioneering work in 2000. This paradigm encompasses coding and retransmission of messages at the intermediate nodes of the network. In contrast with traditional store-and-forward networking, network coding increases the throughput and the robustness of the transmission. Linear network coding is a practical implementation of this new paradigm covered by several research works that include rate characterization, error-protection coding, and construction of codes. Especially determining the coding characteristics has its importance in providing the premise for an efficient transmission. In this paper, we review the recent breakthroughs in linear network coding for acyclic networks with a survey of code constructions literature. Deterministic construction algorithms and randomized procedures are presented for traditional network coding and for network-control network coding. 1. Introduction The theoretical foundations of network coding were first provided by Ahlswede et al. [1]. The idea originated in the sphere of satellite communications, in the scenario in Figure 1. A satellite acts as relay node for the bidirectional communication between two ground stations in nonline-of-sight. The relay receives the data from the ground stations, and it broadcasts a function of the two messages (Figure 1(b)). Each station can decode the respective message from the transmitted and the received information, with a remarkable saving of bandwidth. Figure 1: Bidirectional communication through satellite. With the traditional method (a) the satellite (s) can receive and retransmit one message at a time. With network coding (b) a xor b is broadcasted to both ground nodes, which are able to decode the respective messages. Ahlswede et al. applied the idea of coding at intermediate nodes to general multinode networks, referring to it as the network information flow problem. Network coding allows network nodes to perform decoding and reencoding of the received information, resulting in the retransmission of messages that are a function of the incoming messages, as opposed to traditional routing (which can be regarded as a special case of network coding). The network equivalent of the satellite example is the butterfly network (Figure 2). The benefit of coding at the bottleneck edge is the increased rate with respect to the case of traditional networking, in which the intermediate node can only forward one packet at a time. The major achievement of network coding is, thus, the possibility of reaching the full theoretical
References
[1]
R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–1216, 2000.
[2]
P. A. Chou and Y. Wu, “Network coding for the internet and wireless networks,” Tech. Rep., Microsoft Research, June 2007.
[3]
S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “XORs in the air: practical wireless network coding,” IEEE/ACM Transactions on Networking, vol. 16, no. 3, pp. 497–510, 2008.
[4]
S. Jaggi, M. Langberg, S. Katti et al., “Resilient network coding in the presence of byzantine adversaries,” IEEE Transactions on Information Theory, vol. 54, no. 6, pp. 2596–2603, 2008.
[5]
N. Cai and T. Chan, “Theory of secure network coding,” Proceedings of the IEEE, vol. 99, no. 3, pp. 421–437, 2011.
[6]
D. Silva and F. R. Kschischang, “Universal secure network coding via rank-metric codes,” IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 1124–1135, 2011.
[7]
R. W. Yeung and N. Cai, “Network error correction. I. Basic concepts and upper bounds,” Communications in Information & Systems, vol. 6, no. 1, pp. 19–35, 2006.
[8]
N. Cai and R. W. Yeung, “Network error correction. II. Lower bounds,” Communications in Information & Systems, vol. 6, no. 1, pp. 37–54, 2006.
[9]
K. Jain, L. Lovász, and P. A. Chou, “Building scalable and robust peer-to-peer overlay networks for broadcasting using network coding,” Distributed Computing, vol. 19, no. 4, pp. 301–311, 2007.
[10]
C. Gkantsidis and P. R. Rodriguez, “Network coding for large scale content distribution,” in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05), vol. 4, pp. 2235–2245, March 2005.
[11]
S. Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 371–381, 2003.
[12]
R. Koetter and M. Médard, “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, vol. 11, no. 5, pp. 782–795, 2003.
[13]
R. W. Yeung and S.-Y. R. Li, “Polynomial time construction of generic linear network codes,” in Proceedings of the 43rd Allerton Conference on Communication, Control and Computing, September 2005.
[14]
A. R. Lehman and E. Lehman, “Complexity classification of network information flow problems,” in Proceedings of the 41st Annual Allerton Conference on Communication, Control and Computing, 2003.
[15]
S. Jaggi, P. Sanders, P. A. Chou et al., “Polynomial time algorithms for multicast network code construction,” IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1973–1982, 2005.
[16]
M. Langberg, A. Sprintson, and J. Bruck, “Network coding: a computational perspective,” IEEE Transactions on Information Theory, vol. 55, no. 1, pp. 147–157, 2009.
[17]
C. Fragouli, E. Soljanin, and A. Shokrollahi, “Network coding as a coloring problem,” in Proceedings of the Conference on Information Science and Systems (CISS '04), Princeton, NJ, USA, 2004.
[18]
T. H. Chan, “On the optimality of group network codes,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT '05), pp. 1992–1996, September 2005.
[19]
Z. Zhang and R. W. Yeung, “On characterization of entropy function via information inequalities,” IEEE Transactions on Information Theory, vol. 44, no. 4, pp. 1440–1452, 1998.
[20]
R. Dougherty, C. Freiling, and K. Zeger, “Networks, matroids, and non-Shannon information inequalities,” IEEE Transactions on Information Theory, vol. 53, no. 6, pp. 1949–1969, 2007.
[21]
R. Dougherty, C. Freiling, and K. Zeger, “Insufficiency of linear coding in network information flow,” IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2745–2759, 2005.
[22]
R. Dougherty, C. Freiling, and K. Zeger, “Linearity and solvability in multicast networks,” IEEE Transactions on Information Theory, vol. 50, no. 10, pp. 2243–2256, 2004.
[23]
S. Riis, “Graph entropy, network coding and guessing games,” Tech. Rep. CoRR abs/0711.4175, 2007, http://www.eecs.qmul.ac.uk/~smriis/RiisTRGraphEntro.pdf.
[24]
S. Riis, “Reversible and irreversible information networks,” IEEE Transactions on Information Theory, vol. 53, no. 11, pp. 4339–4349, 2007.
[25]
L. Song, R. W. Yeung, and N. Cai, “Zero-error network coding for acyclic networks,” IEEE Transactions on Information Theory, vol. 49, no. 12, pp. 3129–3355, 2003.
[26]
X. Yan, R. W. Yeung, and Z. Zhang, “The capacity region for multi-source multi-sink network coding,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT '07), pp. 116–120, June 2007.
[27]
J. Barros and S. D. Servetto, “Network information flow with correlated sources,” IEEE Transactions on Information Theory, vol. 52, no. 1, pp. 155–170, 2006.
[28]
R. W. Yeung, Information Theory and Network Coding, Springer, New York, NY, USA, 1st edition, 2008.
[29]
A. Ramamoorthy, K. Jain, P. A. Chou, and M. Effros, “Separating distributed source coding from network coding,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2785–2795, 2006.
[30]
Y. Wu, V. Stankovic, Z. Xiong, and S. Y. Kung, “On practical design for joint distributed source and network coding,” IEEE Transactions on Information Theory, vol. 55, no. 4, pp. 1709–1720, 2009.
[31]
T. Ho, M. Médard, R. Koetter et al., “A random linear network coding approach to multicast,” IEEE Transactions on Information Theory, vol. 52, no. 10, pp. 4413–4430, 2006.
[32]
M. Gadouleau and A. Goupil, “A matroid framework for noncoherent random network communications,” IEEE Transactions on Information Theory, vol. 57, no. 2, pp. 1031–1045, 2011.
[33]
E. Erez and M. Feder, “Efficient network code design for cyclic networks,” IEEE Transactions on Information Theory, vol. 56, no. 8, pp. 3862–3878, 2010.
[34]
J. Huang, L. Wang, T. Zhang, and H. Li, “Unified construction algorithm of network coding in cyclic networks,” in Proceedings of the 15th Asia-Pacific Conference on Communications (APCC '09), pp. 749–753, October 2009.
[35]
A. I. Barbero and ？. Ytrehus, “Cycle-logical treatment for “Cyclopathic” networks,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2795–2804, 2006.
[36]
S. Y. R. Li and Q. T. Sun, “Network coding theory via commutative algebra,” IEEE Transactions on Information Theory, vol. 57, no. 1, pp. 403–415, 2011.
[37]
K. Prasad and B. S. Rajan, “Network error correction for unit-delay, memory-free networks using convolutional codes,” in Proceedings of the IEEE International Conference on Communications (ICC '10), May 2010.
[38]
K. Prasad and B. S. Rajan, “On network-error correcting convolutional codes under the BSC edge error model,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT '10), pp. 2418–2422, June 2010.
[39]
R. W. Yeung, S. Y. R. Li, N. Cai, and Z. Zhang, “Network coding theory part I: single source,” Foundations and Trends in Communications and Information Theory, vol. 2, no. 4, pp. 241–329, 2006.
[40]
N. J. A. Harvey, D. R. Karger, and K. Murota, “Deterministic network coding by matrix completion,” in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), pp. 489–498, SIAM, Vancouver, Canada, 2005.
[41]
R. Dougherty, C. Freiling, and K. Zeger, “Linear network codes and systems of polynomial equations,” IEEE Transactions on Information Theory, vol. 54, no. 5, pp. 2303–2316, 2008.
[42]
S.-Y.R. Li, Q. T. Sun, and Z. Shao, “Linear network coding: theory and algorithms,” Proceedings of the IEEE, vol. 99, no. 3, pp. 372–387, 2011.
[43]
H. Balli, X. Yan, and Z. Zhang, “On randomized linear network codes and their error correction capabilities,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3148–3160, 2009.
[44]
X. Guang and F.-W. Fu, “The failure probability at sink node of random linear network coding,” in Proceedings of the IEEE International Conference on Information Theory and Information Security (ICITIS '10), pp. 876–879, Beijing, China, December 2010.
[45]
P. C. Yunnan, P. A. Chou, Y. Wu, and K. Jain, “Practical network coding,” in Allerton Conference in Communication, Control and Computing, Monticello, Ill, USA, October 2003.
[46]
T. Ho, M. Médard, and R. Koetter, “An information-theoretic view of network management,” IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1295–1312, 2005.
[47]
Z. Zhang, “Linear network error correction codes in packet networks,” IEEE Transactions on Information Theory, vol. 54, no. 1, pp. 209–218, 2008.
[48]
R. K？etter and F. R. Kschischang, “Coding for errors and erasures in random network coding,” IEEE Transactions on Information Theory, vol. 54, no. 8, pp. 3579–3591, 2008.
[49]
D. Silva, F. R. Kschischang, and R. K？etter, “A rank-metric approach to error control in random network coding,” IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 3951–3967, 2008.
[50]
S. Yang, R. W. Yeung, and C. K. Ngai, “Refined coding bounds and code constructions for coherent network error correction,” IEEE Transactions on Information Theory, vol. 57, no. 3, pp. 1409–1424, 2011.
[51]
S. Yang, R. W. Yeung, and Z. Zhang, “Weight properties of network codes,” European Transactions on Telecommunications, vol. 19, no. 4, pp. 371–383, 2008.
[52]
S. Yang, S.-W. Ho, J. Meng, and E.-H. Yang, “Optimality of subspace coding for linear operator channels over finite fields,” in IEEE Information Theory Workshop (ITW '10), pp. 1–5, Cairo, Egypt, January 2010.
[53]
D. Silva, F. R. Kschischang, and R. Kotter, “Communication over finite-field matrix channels,” IEEE Transactions on Information Theory, vol. 56, no. 3, pp. 1296–1305, 2010.
[54]
Z. Zhang, “Some recent progresses in network error correction coding theory,” in Proceedings of the 4th Workshop on Network Coding, Theory, and Applications (NetCod '08), pp. 1–5, January 2008.
[55]
H. Bahramgiri and F. Lahouti, “Robust network coding against path failures,” IET Communications, vol. 4, no. 3, pp. 272–284, 2010.
[56]
R. Matsumoto, “Construction algorithm for network error-correcting codes attaining the Singleton bound,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E90-A, no. 9, pp. 1729–1735, 2007.
[57]
X. Guang, F.-W. Fu, and Z. Zhang, “Construction of network error correction codes in packet networks,” in Proceedings of the IEEE International Symposium on Network Coding (NetCod '11), Beijing, China, July 2011.
[58]
Z. Zhang, X. Yan, and H. Balli, “Some key problems in network error correction coding theory,” in Proceedings of the IEEE Information Theory Workshop on Information Theory for Wireless Networks (ITW '07), pp. 131–135, July 2007.
[59]
M. Bossert and E. M. Gabidulin, “One family of algebraic codes for network coding,” in Proceedings of IEEE International Symposium on Information Theory (ISIT '09), vol. 4, pp. 2863–2866, IEEE Press, Seoul, Korea, 2009.
[60]
E. M. Gabidulin and M. Bossert, “Algebraic codes for network coding,” Problems of Information Transmission, vol. 45, no. 4, pp. 343–356, 2009.
[61]
M. Gadouleau and Z. Yan, “Packing and covering properties of subspace codes for error control in random linear network coding,” IEEE Transactions on Information Theory, vol. 56, no. 5, article no. 6, pp. 2097–2108, 2010.
[62]
D. Silva and F. R. Kschischang, “On metrics for error correction in network coding,” IEEE Transactions on Information Theory, vol. 55, no. 12, pp. 5479–5490, 2009.
[63]
Z. Zhang, “Theory and applications of network error correction coding,” Proceedings of the IEEE, vol. 99, no. 3, pp. 406–420, 2011.
[64]
T. Ho and D. S. Lun, Network Coding: An Introduction, Cambridge University Press, Cambridge, UK, 2008.
[65]
C. Fragouli and E. Soljanin, “Network coding fundamentals,” Foundations and Trends in Networking, vol. 2, no. 1, pp. 1–133, 2007.
[66]
C. Fragouli and E. Soljanin, “Network coding applications,” Foundations and Trends in Networking, vol. 2, no. 2, pp. 135–269, 2007.
[67]
M. Médard and A. Sprintson, Eds., Network Coding: Fundamentals and Applications, Cambridge University Press, Cambridge, UK, 2011.
