• Newsroom Home
• Astronomy
• Biomedical Optics & Medical Imaging
• Defense & Security
• Electronic Imaging & Signal Processing
• Illumination & Displays
• Lasers & Sources
• Micro/Nano Lithography
• Nanotechnology
• Optical Design & Engineering
• Optoelectronics & Communications
• Remote Sensing
• Sensing & Measurement
• Solar & Alternative Energy
• Information for:

# Network coding offers new commmunications paradigm across multiple disciplines

Simple copying may be the most natural way to forward a message, but network coding is more efficient and has a wide range of applications.
24 May 2006, SPIE Newsroom. DOI: 10.1117/2.1200604.0102

The idea of network coding (NC, also known as netcode) is readily illustrated by the puzzle shown in Figure 1.1 Each arrow in the butterfly network is a channel for transmitting one bit of data. To receivers R1 and R2 the source intends to deliver a message represented by the two bits a and b. In straightforward fashion, bit a reaches node V and receiver R1 while bit b reaches V and R2. The dilemma concerns which bit node V should forward to node W upon receiving both data bits. If it forwards bit a, then receiver R1 will not get bit b. If it instead forwards b, R2 will not receive a.

Figure 1. A message is represented by the two bits a and b. Which bit should node V send to node W in order for the message to reach both receivers R1 and R2?

The solution is for node V to send out a bit indicating whether a and b are equal; for example, bit 0 when they are equal or otherwise bit 1. This new bit is called the binary sum or the exclusive OR between a and b in computer logic. When the new bit is forwarded from node W, it is used by receiver R1 to decode the value of b and by R2 for the value of a. While the dilemma confounds the conventional store-and-forward mechanism (i.e., copying), the solution suggests a fundamental concept that blends coding with data forwarding. Partial hints along these lines have appeared sporadically in the literature, including redundant array of independent disks (RAID),2 access to multi-channel LAN,3 and satellite networks.4 The concept was formalized as ‘network coding’ over a generic abstract network and its superiority to store-and-forward has been mathematically proven.5 Advantages can be quantified in terms of bit rate, latency, energy consumption, and other transmission variables.

What types of communications networks can benefit from NC? One general scenario is broadcasting and data transmission in nature (such as wireless communication) including ad hoc and sensor networks. Another prospective use involves separate transmissions competing for a channel. To benefit from NC, the main effort must be to encode at intermediate nodes and to decode at receivers. Complexity and latency of coding and decoding are minimal when the code is linear. Indeed, purely linear codes enable NC to achieve the best possible outcome,1,6 which assures feasibility of implementation in practical hardware and software applications. To date, all NC applications refer to linear network coding, despite their considerable variety.

Until now, the two most prominent applications have been in wireless communications and peer-to-peer (P2P) content distribution. A relatively simple wireless scenario is as follows. Two stations are located at a distance of double the transmission range. Between them lies a relay transmitter, at which a function cycle consists in the exchange of one packet from each station to the other. In the conventional store-and-forward model a cycle would require four time slots: two to receive a packet from each station and two to transmit to each station. With NC, the cycle can consist of just three time slots, replacing the two transmissions by broadcasting the binary sum of the two received packets. This reduction translates into 33% gain in bandwidth efficiency, solely through mathematical manipulation.

The dominant traffic on the Internet is currently P2P content distribution. Some nodes in a P2P network download blocks of data from the server. Meanwhile, every node maintains connections with neighboring peers, with which it exchanges blocks. Since a node transmits a block to different peers at different times, this is logically an asynchronous form of broadcasting, and hence it has a good fit with network coding. In fact, NC is the theoretic underpinning of Avalanche, the recently announced Microsoft alternative to BitTorrent.7 Among other benefits, it enhances Avalanche's information rate by 20 to 30%.8

To understand this P2P application, imagine a video segment partitioned into 100 4kb blocks at the server. Linear network coding adopts a field such as GF(256) as the alphabet and interprets every byte of information as an element within it. A packet transmitted over the P2P network is a linear combination over GF(256) of the 100 blocks. The 100 coefficients associated with the packet constitute a 100-dim vector over GF(256), which is called the global encoding kernel.9 According to the random network-coding scheme,10,11 the kernel is stored in the packet header, a 0.25% overhead in this instance. A node produces a packet by random linear combination of all blocks it currently stores and sends to a peer. Eventually, when the accumulated packet headers include 100 linearly independent global encoding kernels, a receiver can decode the video segment. Linear network coding theory guarantees linear independence among the first 100 received global encoding kernels when the field of alphabet is large enough and the linear combinations are by design. With 101 or more kernels under the random network scheme over the moderately large field GF(256), the probability of successful decoding is essentially 1.

Network coding theory represents one of the most important recent breakthroughs in network communications. It has stimulated multi-disciplinary research with a great variety of potential applications, including multicast, peer-to-peer communications, wireless networks, sensor networks, personal communications, B2C commerce, and other modalities. Since initial publications by researchers at The Chinese University of Hong Kong, NC has rapidly generated research that has had a fundamental impact upon information theory, coding theory, networking, switching theory, wireless communications, computer science, cryptography, operations research, and matrix theory. It is not unreasonable to say that NC represents a new transmission paradigm that may prove dominant in future communications technology.

Research supported in part by grants No. CUHK4231/04E and 414005 from the Research Grants Council of the Hong Kong Special Administrative Region, China.

Author
Shuo-Yen Robert Li
Department of Information Engineering and Network Coding Research Center, The Chinese University of Hong Kong
Hong Kong
China

Bob Li is Professor of Information Engineering at The Chinese University of Hong Kong and advisory professor to Beijing University of Posts & Telecommunications. His book on algebraic switching theory got the field started. He is a co-founder of network coding theory, and collaborated on Linear Network Coding, which won the 2005 IEEE Information Theory Society Paper Award. He holds 30 US patents and pending patents. He has taught at MIT and UI Chicago, and worked at Bell Labs/Bellcore.

References:
1. S. -Y. R. Li, R. W. Yeung, Network multicast flow via linear coding,
Proc. Int'l Symp. on Operations Research and its Applications (ISORA'98),
pp. 197-211, 1998.
2. M. O. Rabin, Efficient disperal of information for security, load balancing, and fault-tolerance,
Journal of ACM,
Vol: 36, pp. 335-348, 1989.
3. S.-Y. R. Li.,
A 100 percent efficient media-access protocol for multi-channel LAN,
Vol: 42, pp. 2803-2814, 1994.
4. R. W. Yeung, Z. Zhang, Distributed source coding for satellite communications,
IEEE Trans. on Information Theory,
Vol: IT-45, pp. 1111-1120, 1999.
5. R. Alshwede, N. Cai, S.-Y. R. Li, R. W. Yeung, Network information flow,
IEEE Trans. on Information Theory,
Vol: IT-46, pp. 1204-1216, 2000.
6. S. -Y. R. Li, R. W. Yeung, N. Cai, Linear network coding,
IEEE Trans. on Information Theory,
Vol: IT-49, no. 2, pp. 371-381, 2003.
7. BBC Newshttp://news.bbc.co.uk/1/hi/technology/4110302.stm.
8. C. Gkantsidis, P. R. Rodriguez, Network coding for large scale content distribution,
Proc. IEEE INFOCOM,
Vol: 4, pp. 2235-2245, 2005.
9. S. Y. R. Li, N. Cai, R. W. Yeung, On theory of linear network coding,
Proc. Int'l Symp. on Information Theory (ISIT'05),
pp. 273-277, 2005.
10. T. Ho, R. Koetter, M. Medard, D. R. Karger, M. Effros, The benefits of coding over routing in a randomized setting,
Proc. IEEE Int'l Symp. on Information Theory (ISIT'03),
pp. 442, 2003.
11. T. Ho, M. Medard, J. Shi, M. Effros, D. R. Karger, On randomized network coding,
Proc. 41st Annual Allerton Conf. on Communication, Control, and Computing,
2003.