Abstract：For a long time, store-and-forward had been the transport mode in network communications. In other words, information had been regarded as a commodity that only needs to be routed through the network, possibly with replication at the intermediate nodes. In the late 1990’s, a new concept called network coding fundamentally changed the way a network can be operated. Under the paradigm of network coding, information can be processed within the network for the purpose of transmission. It was demonstrated that compared with store-and-forward, the network throughput can generally be increased by employing network coding. Since then, network coding has made significant impact on different branches of information science. The impact of network coding has gone as far as mathematics, hysics, and biology. This expository work aims to be an introduction to this fast-growing subject with a detailed discussion of the basic theoretical results.
Yeung R W, Zhang Z. Distributed source codingfor satellite communications. IEEE Transactionson Information Theory, 1999, 45(4): 1111―1120 doi: 10.1109/18.761254
Ahlswede R, Cai N, Li S-Y R, Yeung R W. Network informationflow. IEEE Transactions on InformationTheory, 2000, 46(4): 1204―1216 doi: 10.1109/18.850663
Li S-Y R, Yeung R W, Cai N. Linear network coding. IEEETransactions on Information Theory, 2003, 49(2): 371―381 doi: 10.1109/TIT.2002.807285
Yeung R W, Cai N. Network error correction,Part I: Basic concepts and upper bounds. Communications in Information and Systems, 2006, 6(1): 19―36
Cai N, Yeung R W. Network error correction,Part II: Lower bounds. Communications inInformation and Systems, 2006, 6(1): 37―54
Koetter R, Kschischang F R. Coding for errors and erasuresin random network coding. IEEE Transactionson Information Theory, 2008, 54(8): 3579―3591 doi: 10.1109/TIT.2008.926449
Wu Y, Chou P A, Kung S-Y. Information exchange in wireless networks with networkcoding and physical-layer broadcast. In: Proceedings of 2005 Conference on Information Science and Systems. The Johns Hopkins University, 2005
Katti S, Rahul H, HuW, Katabi D, Médard M, Crowcroft J. XORs in the air: Practicalwireless network coding. IEEE/ACM Transactionson Networking, 2008, 16(3): 497―510 doi: 10.1109/TNET.2008.923722
Gkantsidis C, Rodriguez P R. Network coding for largescale content distribution. In: Proceedingsof IEEE INFOCOM 2005. Miami, FL, 2005
Rasala Lehman A. Networkcoding. Dissertation for the Doctoral Degree. Cambridge, MA: Massachusetts Institute of Technology, 2005
Cai N, Yeung R W. Secure network coding. In:Proceedings of 2002 IEEE International Symposium on Information Theory. Lausanne, 2002
Cai N, Yeung R W. Secure network coding. submitted to IEEE Transactions on Information Theory
Dougherty R, Freiling C, Zeger K. Networks, matroids, and non-Shannon information inequalities. IEEE Transactions on Information Theory, 2007, 53(6): 1949―1969 doi: 10.1109/TIT.2007.896862
Wu Y, Jain K, Kung S-Y. A unification of network coding and tree-packing (routing)theorems. IEEE Transactions on InformationTheory (Joint Special Issue of IEEE Transactionson Information Theory and IEEE/ACM Transactions on Networking on Networking and Information Theory), 2006, 52(6): 2398―2409
Mohsenian-Rad A H, Huang J, Wong V W S, Jaggi S, Schober R. A game-theoretic analysis of inter-sessionnetwork coding. In: Proceedings of IEEEInternational Conference on Communications 2009. Dresden, 2009
Lun D S, Ratnakar N, Médard M, Koetter R, Karger D R, Ho T, Ahmed E, Zhao F. Minimum-cost multicast over coded packetnetworks. IEEE Transactions on InformationTheory (Joint Special Issue of IEEE Transactionson Information Theory and IEEE/ACM Transactions on Networking on Networking and Information Theory), 2006, 52(6): 2608―2623
Hayashi M, Iwama K, Nishimura H, Raymond R, Yamashita S. Quantum network coding. Lecture Notes in Computer Science, 2007, 4393: 610―621 doi: 10.1007/978-3-540-70918-3_52
Liu J-Q. On information-theoretical formalization of intracellular communicationsbased on linear network coding. In: Proceedingsof SICE Annual Conference 2007. KagawaUniversity, 2007
Joint Special Issue on Networking and InformationTheory. IEEE Transactions on InformationTheory and IEEE/ACM Transactions on Networking, 2006, 52(6)
Special Issue on Cooperation in Wireless Networks. Springer—Wireless Personal Communications, 2007, 43(1)
Special Issue on Multiuser Cooperative Diversityfor Wireless Networks. EURASIP Journalon Wireless Communications and Networking, 2006
Special Issue on Network Coding. Journal of Communications and Networks, 2008, 10(4)
Special Issue on Network Coding for Wireless CommunicationNetworks. IEEE Journal on Selected Areasin Communications, 2009, 27(5)
Special Issue on Network Coding for Wireless Networks. EURASIP Journal on Wireless Communications andNetworking, 2010, Apr
Special Issue on Physical Layer Network Codingfor Wireless Cooperative Networks. EURASIPJournal on Wireless Communications and Networking, 2010, Jul
Graham-Rowe D. Repackagingdata could ‘double internet speed’. New Scientist, 2008, 2Oct, 24―25
Shannon C E. A Mathematical theory of communication. The Bell System Technical Journal, 1948, 27: 379―423, 623―656
Yeung R W. Information Theory and Network Coding. Springer, 2008
Bertsekas D, Gallager R. Data Networks. 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1992
Kurose J F, Ross K W. Computer Networking: A Top-DownApproach Featuring the Internet. 3rd ed. Addison Wesley, 2004
Hui J Y. Switching and Traffic Theory for Integrated Broadband Networks. Springer, 1990
Li S-Y R. Algebraic Switching Theory and Broadband Applications. Academic Press, 2000
Cheung K-M, Woo S, Stoenescu T, Chang C S, Klimesh M, Dolinar S, Cheng M K. Improved In Situ Communications Using Network Coding. Annual Report, JPL Task #R.07.023.014
Zhang S L, Liew S C, Lam P P. Physical-layer network coding. In: Proceedings of the Twelfth Annual International Conference on MobileComputing and Networking (Mobi-Com 2006). Los Angeles, CA, 2006
Yeung R W. Multilevel diversity coding with distortion. IEEE Transactions on Information Theory, 1995, 41(2): 412―422 doi: 10.1109/18.370142
McEliece R J. Finite Fields for Computer Scientists and Engineers. Kluwer Academic Publishers, 1987
Lin S, Costello D J Jr. Error Control Coding: Fundamentalsand Applications. Prentice-Hall, 1983 (2nd ed. 2004)
Blahut R E. Theory and Practice of Error Control Codes. Reading, MA: Addison-Wesley, 1983
Wicker S B. Error Control Systems for Digital Communication and Storage. Englewood Cliffs, NJ: Prentice-Hall, 1995
Fong S L, Yeung R W. Variable-rate linear networkcoding. In: Proceedings of 2006 IEEE InformationTheory Workshop. Chengdu, 2006, 409―412
Toledo A L,Wang X. Efficient multipath in sensornetworks using diffusion and network coding. In: Proceedings of the 40th Annual Conference on Information Sciencesand Systems. Princeton, NJ: Princeton University, 2006, 87―92
Koetter R, Médard M. An algebraic approach tonetwork coding. IEEE/ACM Transactions onNetworking, 2003, 11(5): 782―795 doi: 10.1109/TNET.2003.818197
Jaggi S, Sanders P, Chou P A, Effros M, Egner S, Jain K, Tolhuizen L. Polynomialtime algorithms for multicast network code construction. IEEE Transactions on Information Theory, 2005, 51(6): 1973―1982 doi: 10.1109/TIT.2005.847712
Ho T, Koetter R, Médard M, Karger D R, Effros M. The benefits of coding overrouting in a randomized setting. In: Proceedingsof 2003 IEEE International Symposium on Information Theory. Yokohama, 2003, 442
Cohen B. Incentivebuild robustness in BitTorrent. In: Proceedingsof the 1st Workshop on Economics of Peer-to-Peer Systems. Berkeley, CA, 2003
Liu Z, Wu C, Li B, Zhao S. UUSee: Large-scaleoperational on-demand streaming with random network coding. In: Proceedings of IEEE INFOCOM 2010. San Diego, CA, 2010
Yeung R W. Avalanche: A network coding analysis. Communications in Information and Systems, 2007, 7(4): 353―358
Byers J, Luby M, Mitzenmacher M. A digital fountain approach to asynchronous reliablemulticast. IEEE Journal on Selected AreasCommunications, 2002, 20(8): 1528―1540 doi: 10.1109/JSAC.2002.803996
Yeung R W, Li S-Y R, Cai N, Zhang Z. Network codingtheory. Foundations and Trends in Communicationsand Information Theory, 2005, 2(4 and 5): 241―381
Fraleigh J B. A First Course in Abstract Algebra. 7th ed. Addison Wesley, 2003
Erez E, Feder M. Convolutional network codes. In: Proceedings of 2004 IEEE International Symposiumon Information Theory. Chicago, IL, 2004, 146
Erez E, Feder M. Convolutional network codesfor cyclic networks. In: Proceedings ofthe First Workshop on Network Coding, Theory, and Applications (NetCod2005). Riva del Garda, 2005
Fragouli C, Soljanin E. Information flow decompositionfor network coding. IEEE Transactions onInformation Theory, 2006, 52(3): 829―848 doi: 10.1109/TIT.2005.864435
Barbero á I, Ytrehus ?. Cycle-logical treatment for“cyclopathic” networks. IEEETransactions on Information Theory (Joint Special Issue of IEEE Transactions on Information Theory and IEEE/ACMTransactions on Networking on Networking and InformationTheory), 2006, 52(6): 2795―2804
Li S-Y R, Yeung R W. On convolutional networkcoding. In: Proceedings of 2006 IEEE InternationalSymposium on Information Theory. Seattle, WA, 2006, 1743―1747
Li S-Y R, Ho S T. Ring-theoretic foundationof convolutional network coding. In: Proceedingsof the FourthWorkshop on Network Coding, Theory and Applications. Hong Kong, 2008, 1―6
Zhang Z, Yeung R W. On characterization of entropyfunction via information inequalities. IEEE Transactions on Information Theory, 1998, 44(4): 1440―1452 doi: 10.1109/18.681320
Fragouli C, Soljanin E. Network coding fundamentals. Foundations and Trends in Networking, 2007, 2(1): 1―133 doi: 10.1561/1300000003
