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

Waste of Taxpayer money

[SpaceLifeForm (228190)]

All of that new NSA equipment would have to be re-worked.

I doubt that the taxpayers would approve.

don't worry

[geedra (1009933)]

we'll cut costs by outsourcing to china ;)

Re:

[elrous0 (869638)]

Well, who knows routers better than the Chinese? This system has the potential to let them block the word "democracy" at a MUCH faster rate.

Re:

[Karl Cocknozzle (514413)]

All of that new NSA equipment would have to be re-worked. I doubt that the taxpayers would approve.

I am posting in this thread because I'm fresh out of mod points... But even if I weren't, there isn't any "+1, Deftly Ironic" moderation or I'd set you up with one of those...

Re:Waste of Taxpayer money

[grcumb (781340)]

All of that new NSA equipment would have to be re-worked. I doubt that the taxpayers would approve.

I am posting in this thread because I'm fresh out of mod points... But even if I weren't, there isn't any "+1, Deftly Ironic" moderation or I'd set you up with one of those...

It was removed because people kept using it when they should have chosen the "+1, Biting Satire" option instead.

(For reference, this post should be modded "+1, Deadpan".)

This sounds vaguely like

[idontgno (624372)]

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.

Re:

[beyondkaoru (1008447)]

this already happens on really lossy transmissions -- especially things like satellite tv or, say, deep-ish space missions don't want to waste time retransmitting (in satellite tv, if you didn't get it, you can't ask for it again, your picture just looks terrible for a split second).

so, they use error correcting codes, like, for example, parity (like raid 4,5) or reed-solomon (i think that's used in raid 6 or 7 or something), or turbo-codes.

fyi, for the latter i don't actually know how it works.

anyway, this

I must be missing something.

[khasim (1285)]

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:

[Volante3192 (953645)]

That's what it was looking like to me...

It sounds the article's original hypothesis is 'Frames go from Router A to Router B.' So what they do to solve it is...add more routers. The diagram simply looks like 1 router that can route to 6 further routers (A-F) which then route to a further 20 (G-Z).

I'm probably missing something too...that seems too easy.

And they added FASTER routers. :)

[khasim (1285)]

The top router can only handle 6 outbound connections at 1 bit per second (total 6 bits per second).

The second rank of routers can handle TEN outbound connections at 1 bit per second (total 10 bits per second).

And they aren't adding any time delays for the merging of the data streams.

I think I can see what they're trying to do the pictures. And it doesn't look right to me (but who am I anyway). Their choke point (the first router) needs a LOT of information about the second rank of routers.

In essence, they'

Re:

[somersault (912633)]

I think you didn't RTFA.. though you aren't missing much. It vaguely states a method of compressing information together without having any reasonable way to uncompress it again. That's what they need to work out before this will be useful. And the fact that he says things like "the startling truth" before stating things that aren't at all startling makes him sound like either an idiot or a salesman..

Re:

[LiquidCoooled (634315)]

What happens when the second node goes down?
If you automatically broadcast the knowledge of the message across all available channels, if it gets to the other end its won.

This is the not putting all your eggs in one basket scenario which attempts to address bandwidth limitation issues.

It was only recently I was thinking about global communications on a wireless mesh without ISP involvement (reroute the backbone across home networks), I wonder if this could be the kickstart it needs?

Re:I must be missing something.

[markov_chain (202465)]

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.

That still wouldn't work.

[khasim (1285)]

For their system to work, it seems that A has to send to B and C

which blocks C from sending anything

but C must be sending to D at the same time so that the messages can be merged at the "coder" point.

And the coder would then use TWO transmissions to send the "hint" and the merged data.

It's still sending two data streams (one for merged stream and one for hints) when they were originally complaining about how it was a single channel.

Re:That still wouldn't work.

[markov_chain (202465)]

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.

Re:That still wouldn't work.

[SurturZ (54334)]

What about bad packets? Wouldn't error correction stuff the whole thing up? i.e. one re-sent packet and you lose out?

Re:No.

[SurturZ (54334)]

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.

Where is "D"?

[khasim (1285)]

Their discussion isn't about
A to B to C
and
C to B to A

It's about A sending to D while at the same time B is sending to C.

You've left off "D".

And you failed to account for how B would know ahead of time that C would be sending a message. Which fails completely when you try to account for "D" in the equation. You need to account for the packets telling B which points wish to transmit.

In your wireless example, it would be easier to just skip B and have A broadcast its message to all and sundry and then C can br

Re:

[markov_chain (202465)]

You've left off "D".
I wasn't explaining their example, I was giving you a different example where network coding can be put to good use with a clear reason for the existence of the additional unused resources. There are more good examples in wikipedia. [wikipedia.org]

And you failed to account for how B would know ahead of time that C would be sending a message.
That's an implementation detail. It's been solved by buffering some packets at B. There are good papers on this out there, like xor in the air. [mit.edu]


In your wi

Re:

[markov_chain (202465)]

Like the guy below said, check out the butterfly network on the wikipedia page, that explains it more clearly. The trick is that the transmissions are multicast, not unicast, and that the side links would go unused without coding.

Re:

[phooka.de (302970)]

Ahm... no.

In your example, C's response dos not depend on what C receives from A. Also, B is magically able to simutanously send two messages (no serial device can do that).

If the responce (C -> A) is indeed independent from the first message (A -> C), then A and C can sart sending in parallel, thus eliminating the gain in speed. Also, you assume that the message sent from A to C is identical to the message sent from C to A. Assuming that, I'd offen the even more efficient startegy of using A -> A,

butterfly and quantum networks

[kidquantum (956549)]

There is a good explaination in this reference [arxiv.org]. 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 [wikipedia.org]>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.

realistic receiver connectivity and bandwidth

[dltaylor (7510)]

In the article, I need to transmit all three messages to all receivers and the transmitter/intermediate node link has been fabricated as an obvious bottleneck. How often, in a real network, are the receivers going to have that much connectivity and bandwidth? Also, where is the knowledge that all receiver links are up? The loss of any receiver link means that it will get NO messages, since no complete message is routed of any of its links. If I add enough parity data to allow reconstruction of partial m

Re:

[johndoe42 (179131)]

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

Re:

[packetmon (977047)]

Not to mention anything encrypted via AH+ESP is actually useless. Oh and tunneling? How often would they drop at the expense of one router failing. There is no mention either about trust factors. Would these nodes+receivers be configurable to accept certifications, preshared keys, MD5 (or better) checksums. This has gotten to be the biggest *cough* rip off of stating "Hey I invented P2P!... But its for routers! And uh, its connectionless so don't expect error control or recovery! Isn't that cool!"

Man in the Middle Attacks

[jihadist (1088389)]

The problem with metadata, as Microsoft found out [slashdot.org] (note: not an MS-bashing post, just an example), is that by making information about information a higher source of "truth" than the information itself, you create an opportunity for any who control the metadata source (mass media, religion, network controllers) to re-define what is true.

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" [anus.com] 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?

Re:

[jamesh (87723)]

One has to wonder if a link to 'anus.com' is SFW...

Or you know...

[Cadallin (863437)]

They could just start dropping 2 out of ever 3 packets. That would give lots more capacity!

Re:Or you know...

[the_greywolf (311406)]

Comcast already does this.

It's called "cable Internet service."

This is for multicast

[Animats (122034)]

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.

Also wireless

[shadow_slicer (607649)]

This is also a hot topic in wireless networks. In multi-hop wireless networks it can enable nodes to forward many packets in a single transmission. A neat paper about this is here [mit.edu].

Also the coding people are going crazy about this too. There were a couple papers showing that network coding is a simple extension of linear block codes.

"deduce the original information..."

[NewbieV (568310)]

... "from the assembled clues"?

Congratulations. You've just hardwired a rumor mill. Everyone knows how fast those things travel.

Already 'sort of' happens?

[Tribbin (565963)]

Don't do routers already 'efficiently devide' amongst the intermediate nodes, if necessary, by monitoring used/free bandwidth? Isn't the effect the same?

I might be wrong; I just though this already sort of happens.

20 Questions

[BinarySkies (920189)]

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!

Re:

[grumling (94709)]

It was Ms. Scarlett in the conservatory with the candlestick.

The algorithm looks good, but there are holes.

[postbigbang (761081)]

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.

Mod parent up!

[khasim (1285)]

Exactly. Their diagram is pretty and has unused resources in the overly simplified "before" case ... but it does NOT scale when your have multiple senders and not every receiver wants every message.

So each point in their diagram will either have to be aware of every other point (you think routing tables are bad right now) or they have to send MASSIVE amounts of extra data.

Just from their diagram, they went from 3 lines to 6 lines at the first router. Then they fed those into 6 routers each with TEN lines.

Th

Network coding

[gardarh (1105395)]

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 [mit.edu] 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 [uiuc.edu]). 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.

Re:

[Jah-Wren Ryel (80510)]

A simple form of it is already in use today with great results.

It's Parchive [wikipedia.org] and it is crucial for the transmission of large data files through the usenet network. Usenet is essentially a multicast network, like that in the article and the development of parchive error correction files made it significantly more efficient, essentially bringing the need for retransmits down to nearly zero at a slight cost of 5-10% more data transmitted than would be necessary in a perfectly lossless network.

Nothing to see here folks

[by Anonymous Coward]

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.

isn't this just a trade-off?

[TheGratefulNet (143330)]

the usual tradeoff of squashing data and causing it to take up less space (and move faster) - but at the expense of compute complexity on the send or receive sides?

I do NOT want end nodes to have to work harder than they do today. and routers already do their thing very well. adding MORE complexity to save line bandwidth seems silly to me unless you are still dial-up bound.

Missing diagrams

[MECC (8478)]

The hypothetical six-node digital network depicted in the box on these two pages can help clarify those options.

I looked at the diagram link in the submission, and for the above referenced diagram that correlated to the example in the sentences that followed, and didn't find them. Anyone else encounter that problem?

Re:

[wellingj (1030460)]

Well it is a published paper. It's not like it's a big secret now, or even patentable. Thank god....

Re:

[shadowmatter (734276)]

Avalanche was about applying network coding to an overlay network; this research is about applying network coding at the network core itself. So while they share the same technology, expect fundamentally different challenges.

- sm

Re:Umm most traffic is unicast

[Spy Hunter (317220)]

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).

Re:

[Compholio (770966)]

Switch to someone that provides IPv6 (or use a 4-to-6 connection), IPv6 mandates support for multicast.

Re:Umm most traffic is unicast

[glwtta (532858)]

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.

Re:Isn't comprehensible to me

[BridgeBum (11413)]

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.

Re:

[sgtrock (191182)]

Now watch your latency go up by orders of magnitude. :(

Don't get me wrong. I think that what the research team has come up with is remarkable. I just don't see it as being an efficient use of resources. Demonstrate that the CPU cycles to do all this math won't impact throughput and latency, and I'll be the first to applaud them. Otherwise, it's just a nifty way of recovery that covers such small set of corner cases that it's not worth engineering for.

Re:

[SpaceLifeForm (228190)]

Parent should not be moderated 'troll'.

SSL would not work for example because it could not be trusted.

It would only be usable for Multicast where you don't care about the integrity of the data (ex: IPTV).

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.

It's a solution in search of a problem. We already have Multi