The history of modern communications systems has been marked by flashes of startling insight.

Claude E. Shannon, mathematician and engineer, launched one such revolution almost 60 years ago by laying the foundation of a new mathematical theory of communications--now known as information theory. Practical outgrowths of his work, which dealt with the compression and reliable transmission of data, can be seen today in the Internet, in landline and wireless telephone systems, and in storage devices, from hard drives to CDs, DVDs and flash memory sticks.

Shannon tackled communications over phone lines dedicated to individual calls. These days, information increasingly travels over shared networks (such as the Internet), in which multiple users simultaneously communicate through the same medium--be it a cable, an optical fiber or, in a wireless system, air. Shared networks can potentially improve the usefulness and efficiency of communications systems, but they also create competition for communal resources. Many people must vie for access to, say, a server offering downloadable songs or to a wireless hot spot.

The challenge, then, is to find ways to make the sharing go smoothly; parents of toddlers will recognize the problem. Network operators frequently try to solve the challenge by increasing resources, but that strategy is often insufficient. Copper wires, cables or fiber optics, for instance, can now provide high bandwidth for commercial and residential users yet are expensive to lay and difficult to modify and expand. Ultrawideband and multiple-antenna transmission systems can expand the number of customers served by wireless networks but may still fail to meet ever increasing demand.

Techniques for improving efficiency are therefore needed as well. On the Internet and other shared networks, information currently gets relayed by routers--switches that operate at nodes where signaling pathways, or links, intersect. The routers shunt incoming messages to links heading toward the messages' final destinations. But if one wants efficiency, are routers the best devices for these intersections? Is switching even the right operation to perform?

Until seven years ago, few thought to ask such questions. But then Rudolf Ahlswede of the University of Bielefeld in Germany, along with Ning Cai, Shuo-Yen Robert Li and Raymond W. Yeung, all then at the Chinese University of Hong Kong, published groundbreaking work that introduced a new approach to distributing information across shared networks. In this approach, called network coding, routers are replaced by coders, which transmit evidence about messages instead of sending the messages themselves. When receivers collect the evidence, they deduce the original information from the assembled clues.

Although this method may sound counterintuitive, network coding, which is still under study, has the potential to dramatically speed up and improve the reliability of all manner of communications systems and may well spark the next revolution in the field. Investigators are, of course, also exploring additional avenues for improving efficiency; as far as we know, though, those other approaches generally extend existing methods.

Bits Are Not Cars

Ahlswede and his colleagues built their proposal in part on the idea, introduced by Shannon, that transmitting evidence about data can actually be more useful than conveying the data directly. They also realized that a receiver would be able to deduce the original data once enough clues had been gathered but that the receiver would not need to obtain all of the evidence emitted. One kind of clue could be replaced by another, and all that was important was receiving some combination of clues that, together, would reveal the original message. (Receivers would be able to make sense of the evidence if they were informed in advance about the rules applied to generate it or if instructions on how to use the evidence were included in the evidence itself.)

This article was originally published with the title Breaking Network Logjams.

1 Comments

1. 1. timezone 03:05 AM 2/10/08

   Some of you may be interest to know that one of the authors of this article will be teaching a short course at MIT this summer (August 4-8, 2008), "Introduction to Network Coding". More info can be found here: http://web.mit.edu/mitpep/pi/courses/network_coding.html

   Reply | Report Abuse | Link to this