Slashdot Mirror
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.'"
All of that new NSA equipment would have to be re-worked.
I doubt that the taxpayers would approve.
You are being MICROattacked, from various angles, in a SOFT manner.
we'll cut costs by outsourcing to china ;)
the information transmission equivalent of holography. On one level, it seems sensible and obvious. On another level, it's rather novel (at least, the application of holographic distribution of data to a network architecture). At least, I've never heard of it, either in real-world technology research or even (to my recollection) SF technology.
Welcome to the Panopticon. Used to be a prison, now it's your home.
You're right, their example is not very clear. It works best when there are extra resources available to the system that *can't* be used for other purposes; the best example of this is wireless communication, where all transmissions are broadcast. For example, if A sends a packet to B, but C also hears it, we can't possibly use the A-C transmission for some other data.
Tsunami -- You can't bring a good wave down!
From that, they can stage any number of man-in-the-middle attacks -- the least potent but most widespread of which is convincing a clueless electorate^W userbase that they are certain sources of acclaimed truth, and manipulating them for their own narrow or evil ends.
Philosophers write about this in inspiring 5-page screeds like "On Truth and Lies in a Non-Moral Sense" by Friedrich Nietzsche. That theory in itself is the foundation of postmodernism and some more dangerous philosophies as well. Could it be that philosophy applies to computer science?
Anti-Globalism
Note that this is a distribution network for multicasting. Nothing wrong with that, but it doesn't do anything for ordinary point to point Internet communications. The cable TV people might find it useful, though.
... "from the assembled clues"?
Congratulations. You've just hardwired a rumor mill. Everyone knows how fast those things travel.
"For every right, an equal responsibility..."
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.
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.
Tsunami -- You can't bring a good wave down!
Comcast already does this.
It's called "cable Internet service."
grey wolf
LET FORTRAN DIE!
What about bad packets? Wouldn't error correction stuff the whole thing up? i.e. one re-sent packet and you lose out?
Actually, most Internet traffic (BitTorrent) is multicast mapped onto unicast in a terribly inefficient manner. We are forced to use BitTorrent because ISPs refuse to implement multicast (which makes it hardly surprising that there is no multicast traffic on the Internet).
main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
Point A: (sends a picture of a ladybug)
Point B: 'Okay... is it an animal, vegetable, or mineral?'
Coder: 'It's an animal'
Point B: 'Is it... red?'
Sounds efficient!
Think of solving simultaneous equations. Something like:
2x + y - z = 1
x - y + z = 2
x + 2y - 3z = -4
Okay, now instead of x,y & z being numbers, imagine they are blocks of data. Bits. And instead of using addition and subtraction, make your operand xor.
Next step, pretend that your original message is the variables strung together in order, xyz.
Easy as 1,2,3.
My UID is the product of 2 primes.
Consider using the described method instead of routers, which use the ISO/OSI stack. The message uses an inference, in some ways like how striping works in a RAID 5 drive failure; the failed drive can be inferred from data on the surviving striped drives. Not a big deal. Chunks/nibbles of the messages have a low occupancy time within a cloud, but many receivers must evaluate many messages-- not all are intended for them and must be discarded or validated (imagine spoofing in such a concept as described in the diagrams!).
But in the message diagram, there's a talker, and a receiver that gets messages through inference. Between the two, the cloud between them becomes unbelievably saturated with diffuse messages-- the same reason that ATM looks good on paper with its 53-byte packets, but in reality can't deal with traffic jams. This is why MPLS and other deterministic routing methods were invented-- to qualify transmission routes, not just shoot them like a shotgun into a cloud, hoping that the intended receiver gets the message and deciphers it through receive-side heuristics.
This has been done before, and it didn't work. I'd love to hear comments on why this should succeed.
---- Teach Peace. It's Cheaper Than War.
Switch to someone that provides IPv6 (or use a 4-to-6 connection), IPv6 mandates support for multicast.
Hmm, that's like telling someone who's complaining that horses are hard to find to get a unicorn instead.
sic transit gloria mundi
Network coding is far from a brand new idea. It is introduced in a paper by Ahlswede http://pdos.csail.mit.edu/decouto/papers/ahlswede0 0.pdf published in 2000 and has ever since been a very popular research topic in the networking world (http://www.ifp.uiuc.edu/~koetter/NWC/index.html). These "clues" are linear equations where actual packets can be retrieved by applying a gaussian reduction on the equations.
Its most obvious applications are with multicasting where utilization of network links can indeed be increased in an informational theoretical perspective. The tradeoffs are increased CPU load on the intermediate and end nodes. The research so far is a bit from getting into the practical stages but it has promise. As for "99% of internet traffic being unicast"; even though that might be true, one needs to think outside the box. If it turns out that multicasting will be much cheaper than now (multicasting is now in most cases basically multiple unicasting), broadcasting TV through packet networks might become much more efficient and this proportion could change.
Finally, don't forget that research is still in early stages. I believe there are some years, even decades (if ever), until we will see any of this in practice. Maybe it turns out to be useless for computer networks, who knows. Even so, the basic principle might still prove useful for other applications such as routing inside solid state chips.
First of all, this particular algorithm is really only suited for multicasting the same data to many nodes at the same time. It does not help at all with point-to-point unicasting, which is what the majority of Internet traffic looks like. Secondly, the only real trick here is that you can XOR the data together to transmit more information. So if you have equal length messages A, B, and C, instead of transmitting all three to any particular node, you only transmit XORs of some subset of them (A^B and B^C, or A^C and B^C, etc.) and from those XOR'd versions you can then extract the original 3 messages. Magic! Transmit the equivalent of 2 messages but get 3 messages worth of data! Not groundbreaking; not revolutionary; it's actually a pretty old trick. I've thought for a long time about what real world situation this might be practical for, and have come up with pretty much nothing. It's cute, though.
I worked it out, coding is still better.
For the example before:
1. A->B: pAB
2. C->B: pBA
3. B->A, B->C: pAB xor pBA
Assume that at time=3 a bird flies between B & C. The sequence becomes:
1. A->B: pAB
2. C->B: pBA
3. B->A, B->C: pAB xor pBA [B->A SUCCESS, B->C ERROR]
4. B->C: pAB xor pBA [retry]
B resends the packet, but addresses it only to C. This is still quicker than routing, which would take 5 time slices.