|
|
Network coding theory: An introduction |
Raymond W. YEUNG, |
Institute of Network
Coding and Department of Information Engineering, The Chinese University
of Hong Kong, Hong Kong, China; |
|
|
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.
|
Keywords
network coding
network communications
wireless communications
cryptography
|
Issue Date: 05 September 2010
|
|
|
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
|
|
Effors M, Koetter R, Médard M. Breaking network logjams. Scientific American, 2007, 296(6): 78―85
doi: 10.1038/scientificamerican0607-78
|
|
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
|
|
Ho T, Lun D S. Network Coding: An Introduction. Cambridge University Press, 2008
doi: 10.1017/CBO9780511754623
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|