Rerouting the Networks

prostoalex writes "Scientific American looks at a new approach to clearing networking jams, in research funded by the US military. Instead of using routers to route the packets from point A and point B, thus making some hop in the sequence critical for delivering the message, researchers are exploring a new approach called 'network coding.' (Here is the illustration cited in the article.)" Quoting: "[Four researchers] then at the University of Hong Kong published groundbreaking work that introduced a new approach to distributing information across shared networks. In... 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.'"

Comments

butterfly and quantum networks

[kidquantum]

There is a good explaination in this reference. Although that paper mostly treats the case of quantum networks (which is ubber cool) it gives the background. The standard example (not explained well in TFA) is the http://en.wikipedia.org/wiki/Network_coding>butter fly network and the wikipedia article does a reasonable job explaining it. Basically, even with the three different routes, there is still a bottleneck if you just reroute information. But by coding the information, you get it all through. The example of the butterfly network is very simple and worth learning -- just google it if the wikipedia entry or the arxiv paper doesn't help.

Re:That still wouldn't work.

[markov_chain]

The standard example in wireless networks goes like this. Suppose we have a 3-node chain A-B-C, where A has stuff to send to C, and vice versa, i.e. the communication is bidirectional. A and C are too far from each other, so they need to go through B.

Without any coding this is how time is spent:
1. A->B: pAB
2. B->C: pAB
3. C->B: pBA
4. B->A: pBA

Note than in steps 2 and 4, thanks to the nature of wireless channels both A and C get the packet transmitted by B. One of these receptions is thus wasted. With coding, it can be used to send the same data in 25% less time:

1. A->B: pAB
2. C->B: pBA
3. B->A, B->C: pAB xor pBA

To decode, A xors the received data with pAB, C with pBA.