Repackaging data could 'double internet speed' Duncan Graham-Rowe
WHEN you post a letter to a friend, you stick it in an envelope, slap on an address and stamp and send it on its merry way. But imagine if a postal worker at one of the mail-handling centres were to rip open all the letters sent to the same town, add them together and mix up all the pages, and then send them all onward in a single parcel. It may sound like a recipe for disaster, but applying this idea to the internet could reduce the bottlenecks that clog up the web, and double the speed of information flow, its proponents claim. The idea, known as network coding, is already being put into practice to improve the way software and videos are transmitted over the internet. But why change the way data is sent over the internet when the existing system has apparently been working just fine for years? To understand the need for network coding it is useful to draw upon the common analogy of the internet being an information superhighway, with packets of information zipping around like cars on roads, says Muriel Medard, a computer scientist at the Massachusetts Institute of Technology. Things run smoothly until the vehicles reach an intersection that is only wide enough for one vehicle to pass through at a time. The cars then have to line up and take it in turns to pass, slowing the flow. Here's where the analogy breaks down because cars are physical objects, and have to obey physical laws, says Raymond Yeung of the Chinese University of Hong Kong. This is not true of information sent over the internet, so why treat it as if it were? "Information does not have to behave like a physical entity," he says. It is possible to manipulate the form of data without losing the information. Yeung has developed a solution to the bottleneck problem that exploits this characteristic of information. He used coding devices instead of the routers that read packets and forward them to their destinations. Then, when two packets are vying for space at an intersection, they are encoded into a single packet and sent at the same time. Once they hit the next coder, they are decoded into their original form, and if necessary recoded with another packet heading in the same direction, and sent on their way again, until they reach their final destination. By applying a linear mathematical function such as a simple boolean logic operation or a more complex simultaneous equation, for example, a potentially unlimited number of packets can be combined and then separated again to recover the originals. Clues can be added to the information within the packet to tell the decoder what mathematical function was used to encode the packets, making it easier to decode. In 2000 Yeung and colleagues Rudolf Ahlswede at the University of Bielefeld in Germany, and Ning Cai and Shuo-Yen Robert Li at the Chinese University of Hong Kong, applied this solution to an information flow problem known as a butterfly network. In this problem, the challenge is to allow two points on a network to send two distinct packets of data (A and B) to each of two distant destinations in the most efficient way possible (see diagram). With a traditional router-based system, A and B hit a bottleneck as their paths cross on one of their routes across the network. With network coding, however, A and B can be combined and delivered together to both destinations, where they are decoded. In this way, the number of operations that must be carried out by the central nodes is halved. At the very least this doubles the network's efficiency, but for a more complex network, the potential improvement is much greater, says Yeung. Indeed, researchers at MIT have demonstrated that a network coding-based system was five times as efficient as existing router-based systems in transmitting video via a 20-node Wi-Fi network. Given these advantages, why is the net not being instantly converted to network coding? It is not quite as simple as that, says Matthias Grossglauser, director of Nokia Research Center's Internet Laboratory in Helsinki, Finland. "It's very ingenious and elegant, but I have serious doubts that coders will replace the existing routers," he says. Not only would this be extremely expensive, says Grossglauser, but there are also drawbacks to the technique, such as the processing needed to code and decode the individual packets. And while there are rumours that the Chinese government is considering introducing some features of network coding into its routers, most experts agree that we are unlikely to ditch routers altogether any time soon. On the plus side, however, network coding is establishing itself as an efficient way to organise wireless and peer-to-peer networks. Wireless networks can be particularly problematic for the traditional routing method because nodes - or wireless devices - in the network can move, become obstructed or disappear out of range, says Christina Fragouli, a network coding expert at the Swiss Federal Institute in Lausanne. Because of this it is often necessary to design a management system into the network, requiring a node to send a packet repeatedly until it receives a receipt acknowledging its safe arrival from the next node in the network. If each packet is routed via a number of nodes before it reaches its destination, and each of these nodes must wait for an acknowledgement before it stops sending its packet, the network can quickly become overloaded as it waits for receipts that will never come, from lost, obstructed or out-of-range nodes. Network coding gets round this by allowing you to "multicast", or send all coded packets to all the nodes in range, without clogging up the system as packets cross each other en route. Only the destination node sends back an acknowledgement when it receives the information. "Because you don't have to manage the individual connections any more you can really increase the ability to get the data through faster," says Medard. In an experiment carried out by Frank Fitzek at the University of Aalborg in Denmark, each cellphone within a network was allocated 15 per cent of the available information, which they shared with each other by multicasting. Fitzek found that each of the devices was able to obtain 100 per cent of the information 10 times as fast as conventional router-based systems. He also found that even a cellphone's limited computational power could handle the coding and decoding requirements. It is this sort of performance that prompted the US Defense Advanced Research Projects Agency earlier this year to fund the development of a network-coding based wireless communication system for military personnel and vehicles at BAE Systems in Burlington, Massachusetts. Meanwhile, companies like the Chinese peer-to-peer video firm UUSee.com are using network coding to transmit files between its members more efficiently, says Yeung. By overlaying network coding on the existing infrastructure, videos that would normally take 6 minutes to download take just 30 seconds, he says. Similarly, Microsoft's Secure Content Distribution system is based on a network coding protocol called Avalanche. This was used last year to allow thousands of users to download a particularly large software program called Visual Studio. Compared to previous distribution software, the improvement in download speed for users was dramatic, says Christos Gkantsidis of Microsoft Research's systems and networking group in Cambridge, UK. "It would take them up to a few days to download," he says. "With this P2P system it takes just a few hours." To unsubscribe send a message to accessindia-requ...@accessindia.org.in with the subject unsubscribe. To change your subscription to digest mode or make any other changes, please visit the list home page at http://accessindia.org.in/mailman/listinfo/accessindia_accessindia.org.in
