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.)

Network coding breaks with the classic view that communications channels are analogous to roads and that bits are like the cars that travel those roads. But an understanding of the transportation model of communications is useful for grasping how the new scheme works and why it has such promise.

Shannon proved mathematically that every channel has a capacity--an amount of information it can relay during any given time frame--and that communications can proceed reliably as long as the channel's capacity is not exceeded. In the transportation analogy, a road's capacity is the number of cars per second it can handle safely. If traffic stays below capacity, a car entering the road at one end can generally be guaranteed to exit at the other end unchanged (barring the rare accident). Engineers have built increasingly complex communications systems based on the transportation model. For example, the phone systems Shannon pondered dedicate a distinct "road" to every conversation; two calls over traditional phone lines never share a single line at the same time and frequency.

Computer networks--and the Internet in particular--are essentially a maze of merging, branching and intersecting roads. Information traveling from one computer to another typically traverses several roads en route to its destination. Bits from a single message are grouped into packets (the carpools or buses of the information superhighway), each of which is labeled with its intended destination. Routers sit at the intersections of the roads, examine each packet's header and forward that packet toward its destination.

Ironically, the very transportation model that fueled today's sophisticated communications systems now stands in the way of progress. After all, bits are not cars. When two vehicles converge on the same narrow bridge, they must take turns traversing the bottleneck. When two bits arrive at a bottleneck, however, more options are possible--which is where network coding comes in.

How It Works

The hypothetical six-node digital network depicted in the box "The Basic Idea" can help clarify those options. Recall that in computers, all messages take the form of a string of binary code. Imagine that each link, or road, in this network can carry one bit--be it a 0 or a 1--per second and only in the direction designated by the corresponding arrow. Amy, a network user at node A, hopes to send information at one bit per second to Dana at node D. Meanwhile Ben at node B hopes to send, at exactly the same time and rate, information to Carl at node C. Can both Amy's and Ben's demands be satisfied simultaneously without exceeding any of the links' capacities?

In a router system (far left in the box), the outlook seems bleak. Both paths, from Amy to Dana and from Ben to Carl, require traversing link 5. This link becomes the equivalent of a narrow, one-lane bridge. The router at node E, where link 5 starts, receives a total of two bits per second (one from link 2 and one from link 3), but because link 5's capacity is one, the router can send only one bit per second along it. In the transportation model, such bottlenecks cause nightmare traffic jams, with more and more bits piling up over time, waiting their turn.

In the new approach (right part of the box), though, the plain router would be replaced by a coder, which would have more options than would be open to a traffic cop. Instead of relaying the actual bit streams collected at the bottleneck, the coder could send quite different information. It could, for example, add up the number of 1s that arrive during any given second and transmit a 0 if that sum is even. If the sum is odd, the device could transmit a 1. So, if link 5 simultaneously receives a 1 and a 0 from links 2 and 3, it carries a 1. If either two 0s or two 1s are received from links 2 and 3, link 5 carries a 0. The result then gets sent by router F down links 6 and 7 to Carl and Dana, respectively.

This approach replaces each pair of bits at node E with a hybrid of the two. Such a bit stream seems ridiculous. Our proposed coder has done the equivalent of combining one phone conversation with another in a way that obscures both. The apparent absurdity of the approach is precisely why it went uninvestigated for so long.

But sometimes apparent madness is true innovation. A hybrid bit stream may describe neither transmission perfectly, yet it can supply evidence about both. Suppose we additionally send Amy's missive to Carl along link 1 and Ben's to Dana along link 4. Sending these two messages uses network resources (links 1 and 4) that the routing system could not usefully employ for meeting Amy's and Ben's demands. Carl's node receives Amy's transmission and knows for each instant (from link 6) whether the number of 1s in the pair of messages issued by Amy and Ben is even or odd. If Carl's node is programmed to also "know" the rule used by the coders at the start of link 5 or if it can infer the rule from the evidence itself, the collected evidence will enable it to decipher the message sent by Ben. And Dana's node will similarly uncover Amy's message.

Clear Benefits

This strategy accomplishes two goals that were unthinkable given the limitations of the transportation model. First, it enables the bit leaving a node to travel two paths simultaneously, something a car cannot do. Second, it allows a pair of bit streams arriving at the head of a bottleneck to combine into a single stream, whereas two cars converging on one narrow bridge cannot become a single entity; one would have to wait for the other to pass before it could proceed across the bridge.

The data-handling approach exemplified by our six-node model (a minor variation on one first given by Ahlswede and his colleagues in 2000) can potentially increase the capacity of a network without requiring the addition of extra conduits because it avoids logjams. Using routing alone, our six-node network could sustain simultaneous transmissions averaging one half of a bit per second. (Because the two competing transmissions would have to share link 5, the effective data rate would be one bit per two seconds, or one half of a bit per second, for each of the competing demands.) With network coding, the same system supports simultaneous transmissions at one bit per second. So, here, network coding doubles capacity.

Sometimes network coding could yield even bigger capacity gains, sometimes none. But the approach would never decrease the capacity of a network because, at worst, it would precisely mimic the actions of router systems. It should also increase reliability and resistance to attacks in relatively substantial networks, because the interchangeable nature of evidence means that some packets of evidence can be lost without creating problems.

Lessons from Multicast Networks

So far much of the research into implementing network coding has focused on multicast networks--in which all receivers need to get the same information. Internet video games rely on multicast systems to update every player each time one makes a move. Webcasts of videos or live sporting events and new software released electronically to a large group of customers also travel over multicast networks. Today such networks still use routers, and a return to the transportation analogy helps to explain why designing them is usually quite difficult.

Imagine the country's highways teeming with cars. Each router is like a police officer directing traffic at a single intersection. Incoming cars join the queue behind vehicles that arrived before them. The officer reads each car's destination in turn and directs it on its way. The goal in system design is for each router to direct traffic in a way that not only speeds each subsequent car to its intended destination but also allows the nation's transportation system as a whole to satisfy as many drivers as possible.

Even a central designer with a complete map of all the nation's roads in hand would be hard put to determine the best possible strategy for every router to follow. The difficulty increases as the network changes over time: rush hours, road repairs, accidents and sporting events mean the roadways and the demands placed on them change constantly.

Intuition might suggest that designing a system reliant on network coding should be even harder, because there are more options to consider. A node could forward data unchanged, thereby mimicking a router. But it might also mix two or more incoming data streams before sending them on, and how it mixes them might also be open to consideration; further, different nodes might use different algorithms.

Luckily, this logic is flawed. Sometimes adding more options actually simplifies things. Without coding, architects of a multicast system would need to enumerate as many paths as possible from the transmitter to each receiver and then determine how many of those paths the network could support simultaneously. Even for simple networks, finding and testing all combinations of paths would be a dizzying task.

In contrast, a multicast system using network coding would be rather easy to design. The startling truth is that addition and multiplication are the only mathematical functions that coded networks need apply. Also, even if the function, or rule, programmed into each coder in a network is chosen independently of the message and the other coding functions and without any knowledge of the network layout, the system as a whole will, with extremely high probability, operate at peak performance. Even if the system changes over time, as can happen in mobile or reconfigurable networks, the network will continue to perform optimally without requiring redesign. To learn why, see "A Code Design Example".

Tomorrow's Networks

The operation of networks, then, will be very different if coders replace routers. The way our messages traverse networks will change: they will not only share "the road" with other transmissions but may become intimately entangled with traffic from a variety of other sources. Some might fear that such entanglement would compromise the security of the messages. More likely, though, traffic traversing networks would become a locally undecipherable algebraic stream. Users on the network would unwittingly collaborate to one another's mutual advantage, allowing not just higher rates or faster downloads of data but also, in the case of wireless networks, an improvement in energy efficiency. (Because each wireless transmission consumes energy, a node can reduce consumption by mixing together the information intended for several neighbors and sending only a single transmission.)

 


By changing how networks function, network coding may influence society in ways we cannot yet imagine.

 

Moreover, delays in downloading videos and lost cell phone calls will be far less common. On the Internet, routers fail or are taken down for maintenance and data packets are dropped all the time. That is why people must sometimes rerequest Web pages and why a site sometimes comes up slowly. Reliability will increase with network coding, because it does not require every single piece of evidence to get through.

And network managers will provide such benefits without having to add new communications channels, because better use will be made of existing channels. Network coding will thereby complement other communications technologies, allowing users to get as much as possible out of them.

Sometimes users will know that network coding is operating, because it may modify how some common applications, such as peer-to-peer downloads, function. Today someone seeking to download a file searches for a collaborating user on whose machine the file resides. In a system using network coding, the file would no longer be stored as a whole or in recognizable pieces.

But users would not personally have to figure out how to find the evidence needed to obtain the desired files. A request sent into a network from a user's computer or phone would cause either that individual's computer or a local server to scavenge through the network for pieces of evidence related to a file of interest. The gathered evidence, consisting of algebraically mixed pieces of information relating to the desired file, would help recover that file. Instead of putting together a puzzle whose pieces are recognizable fragments of a whole, the server or an individual's computer would solve a collection of algebraic equations. And, all the while, most people would remain blissfully unaware of these operations--just as most of us are ignorant of the complicated error-correction operations in our cell phones.

The military has recognized the robustness of network coding and is now funding research into its use in mobile ad hoc networks, which can form on the fly. Such networks are valuable in highly changeable environments, such as on the battlefield, where reliable communications are essential and establishing and maintaining an infrastructure of fiber-optic cables or cell towers is difficult. In an ad hoc network, every soldier's radio becomes a node in a communications system, and each node seeks out and establishes connections to neighboring nodes; together these connections establish a network's links. Every node can both send and receive messages and serve as an intermediary to pass along messages intended for other receivers. This technique extends communications capabilities far beyond the transmission range of a single node. It also allows enormous flexibility, because the network travels with the users, constantly reconfiguring and reestablishing connections as needed.

By changing how networks function, network coding may influence society in ways we cannot yet imagine. In the meantime, though, those of us who are studying it are considering the obstacles to implementation. Transitioning from our router-based system to a network-coded one will actually be one of the more minor hurdles. That conversion can be handled by a gradual change rather than a sudden overhaul; some routers could just be reprogrammed, and others not built to perform coding operations would be replaced little by little.

A bigger challenge will be coping with issues beyond replacing routers with coders. For instance, mixing information is a good strategy when the receiving node will gather enough evidence to recover what it desires from the mixture. This condition is always met in multicast networks but may not be the case in general. Moreover, in some circumstances, such as when multiple multicasts are transmitted, mixing information can make it difficult or impossible for users to extract the proper output. How, then, can nodes decide which information can and cannot be mixed when multiple connections share the same network? In what ways must network coding in wireless networks differ from its use in wired ones? What are the security advantages and implications of network coding? How will people be charged for communications services when one person's data are necessarily mixed with those of other users? In collaborations that span the globe, we and others are pondering how to unravel such knots even as we strive to enhance the capabilities of the communications networks that have become such an integral part of so many lives.

MORE TO EXPLORE

A Mathematical Theory of Communication. C. E. Shannon in Bell System Technical Journal, Vol. 27, pages 379-423 and 623-656; July and October 1948. Available at http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html

Network Information Flow. R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung in IEEE Transactions on Information Theory, Vol. 46, No. 4, pages 1204-1216; July 2000.

Linear Network Coding. S.-Y. R. Li, R. W. Yeung and N. Cai in IEEE Transactions on Information Theory, Vol. 49, No. 2, pages 371-381; February 2003.

An Algebraic Approach to Network Coding. R. Koetter and M. M?dard in IEEE/ACM Transactions on Networking, Vol. 11, No. 5, pages 782-795; October 2003.

Polynomial Time Algorithms for Multicast Network Code Construction. S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain and L.M.G.M. Tolhuizen in IEEE Transactions on Information Theory, Vol. 51, No. 6, pages 1973-1982; June 2005.

A Random Linear Network Coding Approach to Multicast. T. Ho, M. M?dard, R. Koetter, D. R. Karger, M. Effros, J. Shi and B. Leong in IEEE Transactions on Information Theory, Vol. 52, No. 10, pages 4413-4430; October 2006.