Network coding: networking's next revolution?

Network coding could re-engineer routing, content distribution and wireless, vendors and researchers say

Some of high tech's biggest names - Microsoft, HP and Intel among them - are starting to embrace a technology called network coding in an effort to boost throughput, scalability and efficiency of everything from content distribution to wireless networks.

Some of high tech’s biggest names – Microsoft, HP and Intel among them – are starting to embrace a technology called network coding in an effort to boost throughput, scalability and efficiency of everything from content distribution to wireless networks.

Network coding, largely shrouded in university and vendor labs since it was proposed seven years ago by a handful of researchers, is essentially an algorithm that proponents say can potentially more than double network throughput while also improving reliability and resistance to attacks. Network coding’s most ardent supporters say the technology could spark networking’s next revolution, while others say network coding is more likely to quietly infiltrate network architectures based on existing routing schemes.

Network coding works by separating messages into smaller bits of “evidence” that can then be deduced by the destination node without transmitting, retransmitting or replicating the entire message. It enables this evidence to traverse multiple paths to and from intermediary nodes which then send it on to the endstation. It does not require additional capacity or routes – it simply mixes evidence of messages into bit streams already supported by an existing network infrastructure.

"It’s like eavesdropping: You listen to what’s going on around you, you form an opinion, and then you improve the overall throughput and capacity by actually remembering and using the information you have,” says Sumeet Sandhu, principal investigator for cooperative wireless communication at Intel Research.

Diagram of network coding

Network coding could work its way into any number of products from routers to wireless systems or take the form of entirely new devices dubbed network coders. Intel sees the potential for the technology to extend the range of wireless base stations. Microsoft is already trialing network coding to make its content distribution system more efficient (read "Microsoft's network coding plan"). Other big network players, such as Cisco, are keeping their plans hush hush for now and declined to say more than this, through a spokesman: “We are investigating network coding as the theory helps distinguish a variety of different types of traffic, then prioritizes them to help increase the capacity of the network. Right now we do not offer any specific network coding products.”

Decoding network coding

To give you a better feel for what network coding is all about, here’s a further technical explanation.

Network coding manipulates the data inside the packet itself through what’s called a “bitwise exclusive or” (xor) operation to combine the information with that of another packet. A bitwise xor takes two bit patterns and performs the logical operation on each pair of corresponding bits, assigning a number “1” if the two bits are different and “0” if they are the same.

These 1s and 0s are the codes, or evidence, by which an endstation or any node with the intelligence to do so can deduce the message received from the sender. In this manner, network coding effectively allows destination nodes to receive multiple messages without an increase in the number of packets it receives or in overall network capacity.

“You’re using the algebraic nature of the data in order to give yourself more freedom with what you can do with the packets,” says Muriel Medard, an associate professor in the Electrical Engineering and Computer Science department at MIT, and a leading researcher in the field of network coding. “You can do things within the network that allow you to use it more efficiently or in different ways.”

Proponents like Medard say network coding is particularly beneficial in shared router infrastructures – such as the Internet -- peer-to-peer content distribution and wireless mesh networks. In an article describing the concept, Medard and other researchers state that network coding 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.

How a network operator implements network coding depends on what the operator is looking to accomplish, Medard says. It differs from MPLS traffic engineering – another, widely implemented method for increasing network capacity and efficiency – in that MPLS does not change the data within a packet; it adds an appendage, or label, to the packet (“MPLS explained”).

“You’re not just working on whatever fields of a packet you’ve selected to work on; you’re actually considering the possibility of working and operating on the data itself inside the packet,” Medard says. “But in the end you still recover the information you originally wanted.”

Current router and switching systems do not do this. They read the source and destination fields of packets and direct traffic accordingly by mapping input to outputs on the same node – they do not combine the contents of two different packets, nor do they map inputs on one node to outputs on another.

“But the ability to do something like xor can really benefit you quite a bit in the operation of your network,” Medard says. “By giving yourself the freedom of doing that…you’re dramatically changing the landscape of what you can do.”

Medard says network coders may not replace routers per se, but could function as an overlay to routing. But over time, network coding could become integral to the routing operation as its benefits become evident, essentially changing routing technology as we know it today.

Medard says she presented her technical research to Cisco engineers two or three years ago. She characterized the talk as “good” but stressed that it was technical and no commercial implications were discussed.

HP’s take on network coding

HP, like Microsoft, sees network coding having promise for peer-to-peer content distribution. HP is also collaborating with and funding MIT’s work in the field.

“It’s an exciting new technique,” says Mitchell Trott, a researcher in HP Labs. “It has a lot of potential but it’s not clear exactly which systems are going to benefit from it.”

An application for network coding in the network infrastructure is “a tougher question” than whether network coding can aid in content distribution, Trott says. It must be proved that it provides a large performance gain before infrastructure vendors adopt it, he says.

“You have to have a particular problem to solve – multicast is probably the one that would most benefit,” he says. “But of course, most people don’t even have multicast turned on.”

Multicast, which delivers information to a group of destinations simultaneously, can be made more efficient by network coding in the same manner that traditional routing can be improved. Multicast creates copies of entire messages when the links to the destinations split, but network coding can alleviate that through its xor evidence technique, researchers say.

Another factor making network coding questionable for network infrastructure, Trott says, is that switches and routers tend to sit in equipment racks for up to a decade.

“It would take quite a while to roll over the equipment to support these new techniques,” Trott says. There would also have to be new control and management protocols developed to track all of the packet and bit stream manipulations that coding routers and switches – or coders – perform in the network, and how their neighbor nodes are notified, he says.

“It’s one of these things which is I think a little bit hard to roll out gradually,” Trott says. “You can roll out the capability gradually but you have to turn it on all at once.”

So far, HP hasn’t quite found a fit for network coding in commercial products but Trott says that could change over time. He also says wireless mesh networks could benefit from the technique, especially ad hoc military sensor networks.

MIT researchers conducted research that shows coding provides a “severalfold increase” in throughput of wireless networks. MIT researchers say they saw a doubling of throughput in a very small setting and as much as fourfold in an experiment using UDP traffic involving 34 nodes on three floors of an MIT building.

Intel’s into network coding

Intel also expects network coding to benefit its wireless initiatives, specifically in WiMAX. Intel began its network coding research in 2006.

Multihop relay – in which WiMAX base stations and relay stations are controlled by the infrastructure -- can benefit from network coding in extending the range of a base station, says Intel Research’s Sandhu. The relay stations perform wireless backhaul to the base station, and network coding can make two-way relay in the middle of an end-to-end base station-to-client interaction more efficient by minimizing redundant packet routing, she says. In this application, network coding can provide throughput gains of 25% to 50% in simple two-way routing, she adds.

“You save time by doing this xor in the middle,” Sandhu says. “Instead of four time slots to do the end-to-end two-way communication, it only takes you three slots because in one slot you actually combine the two packets and send them out.”

But WiMAX is not an ad hoc network like a military sensor network would be – it’s centralized. A base station serving a cell with perhaps a few relays thrown in for range extension is usually the norm for a WiMAX network, Sandhu notes.

“It’s not a very rich infrastructure; there’s limited scope to play games with new tricks like network coding,” she says. “So we’re looking at this very simple two-way network only so far.”

Intel’s looking at network coding’s applicability at the physical layer of the OSI reference model as well for how it interacts with antennas in a multiple-input multiple-output (MIMO) environment, Sandhu says. Physical layer information may be lost as bits move up to the MAC layer, so Intel is looking at ways to capture the physical layer channel information to do more optimal network coding.

Sandhu could not say whether Intel has any product development planned or under way around network coding. But Sandhu says she does see its applicability to data communications across the board in addition to wireless and WiMAX.

What about security?

This concept of eavesdropping and xor bitstream intermingling does raise security concerns, researchers acknowledge.

But MIT’s Medard says network coding -- with its ability to essentially disguise message and payload data -- can actually enhance information security beyond encryption and cryptography by making traffic traversing networks an undecipherable algebraic stream.

“When you do this combination it has a data-hiding aspect,” Medard says. “When you have two bits, A and B, and you xor the two, seeing the xor you don’t know what either bit was. You may know something about the pair of the bits but you can’t figure out bit A unless you know bit B perfectly.”

Network coding techniques also provide the ability to detect malicious “pollution” attacks in peer-to-peer interactions and correct them, she says.

Still, much research needs to be done to determine network coding’s impact on security and a number of other issues beyond whether network coders will eventually supplant routers in large, shared infrastructures like the Internet. Users have to know how and when to implement network coding in cases where information cannot be mixed on a shared network; they must also consider the nuances between network coding in wired and wireless infrastructures; and the industry must determine how customers will be charged for telecommunications services when carriers mix customer traffic together.

Medard says she and others are considering such issues as they continue to delve into methods to improve the networks that are increasingly becoming more integral to society.

Learn more about this topic

 
Join the discussion
Be the first to comment on this article. Our Commenting Policies