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.'"

I must be missing something.

[khasim]

The numbers they give do not correspond to the diagram.

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.

So they had originally started with one channel from A to D and that channel was also used by B sending to C.

They said that it was inefficient because A to D would have to wait at times for B to C.

Their "solution" seems to be to add a SECOND CHANNEL that will transmit a bit AS FAST AS THE PRIMARY CHANNEL and so both messages will get to their destination sooner.

Why not just use that secondary channel to transmit the data in the first place?

Did I miss something?

Re:realistic receiver connectivity and bandwidth

[johndoe42]

Not at all. This idea is cooler than it sounds in the article.

Rather than using the silly parity schemes as mentioned in the article, you'd use a long code (i.e. a code that could extend beyond a single transmission). Then, if you lose part of the transmission, you could request enough additional symbols to reconstruct the message. Any decent (i.e. maximum distance separable) erasure code has the property that the amount of data you need does not exceed the size of the message, even if you lose a subset of it that is unknown to the sender. These codes exist -- Reed-Solomon is an example. (As a stupid analogy, you could send a bunch of data by mailing a wad of RAID-6 hard drives (although you'd use a code that could survive more than two erasures) using different carriers, and then, when some get lost, you just mail more of the RAID array.)

I imagine that the current research is on even better codes that wouldn't require as much feedback to work well.

(Note: I am not a network coding theorist, but I have some knowledge of information theory and non-network coding.)