Some See in ‘Network Coding’ Networking’s Next Revolution

By Duffy, Jim

Some of high-tech’s biggest names – Microsoft, HP and Intel among them – are starting to embrace a technology called network coding to boost the throughput, scalability and efficiency of everything from content distribution to wireless networks. Network coding, largely under wraps in university and vendor laboratories since it was proposed seven years ago by a handful of researchers, is essentially an algorithm that proponents say could more than double network throughput while improving reliability and resistance to attacks. Network coding’s most ardent supporters say the technology could spark networking’s next revolution, while others say it is more likely to infiltrate network architectures quietly based on existing routing schemes.

Network coding works by separating messages into smaller bits of “evidence” that can be deduced by the destination node without transmitting, retransmitting or replicating the entire message (see graphic, page 18). 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 bitstreams 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.

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 doing trials of network coding to make its content distribution system more efficient (see “Microsoft’s network coding plan,” opposite page).Other big network players.such as Cisco, are keeping their plans hush-hush 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 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 Is and Os 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 the Massachusetts Institute of Technology, 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 such as Medard say network coding is particularly beneficial in sharedrouter infrastructures – such as the Internet – peer-to-peer content distribution and wireless mesh networks. In an article describing the concept, Medard and other researchers say network coding has the potential to dramatically speed up and improve the reliability of all kinds of communications systems, and may 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.

“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. 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 and Intel take on network coding

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

“It’s an exciting new technique,”says Mitchell Ttott, 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 way that traditional routing can be improved. Multicast creates copies of entire messages when the links to their destinations split, but network coding can alleviate that through its xor evidence technique, researchers say

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

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

“You can roll out the capability gradually but you have to turn it on all at once,”Tk>tt says.

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.

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 because it extends the range of a base station, Intel Research’s Sandhu says.The relay stations perform wireless backhaul to the base station.and network coding can make the twoway relay in the middle of an end-to-end basestation-to-client interaction more efficient by minimizing redundant packet routing, she says. In this application, network coding provides 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 as 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, she notes.

Intel is 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 environment, Sandhu says. Physical layer information may be lost as bits move up to the media-access-control layer, so Intel is looking at ways to capture the physicallayer channel information to do moreoptimal network coding.

This concept of eavesdropping and xor bitstream intermingling does raise security concerns, researchers acknowledge. MIT’s Medard, however, says network coding-with its ability to essentially disguise message and payload data – can enhance information security beyond encryption and cryptography by making traffic traverse networks an undecipherable algebraic stream. 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 eventually will supplant routers in large, shared infrastructures such as 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 also must 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.

“[With network coding you] can do things within the network that allow you to use it more efficiently or in different ways.”

Muriel Medard

Associate professor at MIT

Copyright Network World Inc. Dec 10, 2007

(c) 2007 Network World. Provided by ProQuest Information and Learning. All rights Reserved.