How MIT and Caltech's Coding Breakthrough Could Accelerate Mobile Network Speeds

colinneagle (2544914) writes "What if you could transmit data without link layer flow control bogging down throughput with retransmission requests, and also optimize the size of the transmission for network efficiency and application latency constraints? In a Network World post, blogger Steve Patterson breaks down a recent breakthrough in stateless transmission using Random Linear Network Coding, or RLNC, which led to a joint venture between researchers at MIT, Caltech, and the University of Aalborg in Denmark called Code On Technologies.

The RLNC-encoded transmission improved video quality because packet loss in the RLNC case did not require the retransmission of lost packets. The RLNC-encoded video was downloaded five times faster than the native video stream time, and the RLNC-encoded video streamed fast enough to be rendered without interruption.

In over-simplified terms, each RLNC encoded packet sent is encoded using the immediately earlier sequenced packet and randomly generated coefficients, using a linear algebra function. The combined packet length is no longer than either of the two packets from which it is composed. When a packet is lost, the missing packet can be mathematically derived from a later-sequenced packet that includes earlier-sequenced packets and the coefficients used to encode the packet."

Comments

Can we update the title please?

[hamster_nz]

"A better coding for data error correction and redundancy than Reed-Solomon" - this is News for Nerds after all.

And why the "oooh - flappy birds on my phone might be faster" slant? I want a faster SAN!.

Re:Can we update the title please?

[ajyand]

Reed-solmon is theoretically best. I hope this new encoding is practically better than Reed-Solmon.

Re:Can we update the title please?

[Zironic]

Because R-S assumes uniformly random error distribution which is usually not the case when it comes to wireless interference.

Nothing new under the sun, just new uses

[preaction]

Sounds like Parchive from usenet, which is a really good idea in a lossy environment now that I think about it.

Re:Nothing new under the sun, just new uses

[NoNonAlphaCharsHere]

Yup, sounds a lot like par2, except this system works inline, in a streaming context to repair mangled blocks/packets, where par2 uses out-of-band data (the par2 files) to do the repairs after all the data is transmitted.

Re:Nothing new under the sun, just new uses

[TubeSteak]

And like par2, it's going to require a healthy amount of processing from your CPU

The trends to higher-performance multicore processors and parallel operations everywhere in the network and on mobile devices lends itself to an encoding scheme utilizing linear algebra and matrix equations that might not have been possible in the past.

Notice they talk about multicore processors and not some hardware decoding embedded in the networking chip.
From their published paper

Abstract-- Random Linear Network Coding (RLNC) provides
a theoretically efficient method for coding. The drawbacks associ-
ated with it are the complexity of the decoding and the overhead
resulting from the encoding vector. Increasing the field size and
generation size presents a fundamental trade-off between packet-
based throughput and operational overhead. On the one hand,
decreasing the probability of transmitting redundant packets is
beneficial for throughput and, consequently, reduces transmission
energy. On the other hand, the decoding complexity and amount
of header overhead increase with field size and generation
length, leading to higher energy consumption. Therefore, the
optimal trade-off is system and topology dependent, as it depends
on the cost in energy of performing coding operations versus
transmitting data. We show that moderate field sizes are the
correct choice when trade-offs are considered. The results show
that sparse binary codes perform the best, unless the generation
size is very low.

Processing power is going to be an issue in mobile devices which have the most to gain from this innovation.

what the FEC...

[bugs2squash]

they've invented forward error correction, this could enable data communications and audio CDs.

Re:what the FEC...

[nyet]

FEC generally does not seek to recover lost data, only the proper state of flipped bits.

Re:what the FEC...

[TapeCutter]

Wow, were you aiming for humour? - Because it would be sad if you were serious

What people are saying is they have implemented FEC at the packet level. I don't know much about wireless but I do remember the maths lectures I attended 25yrs ago on error correction techniques. At the time I could perform the FEC algorithm by hand, I consider myself "mathematically inclined" and have been awarded bits of paper attesting to that inclination but to this day I still have just enough understanding of the mathematical concepts of error correction to marvel at the geniuses who worked it all out in the first place.

Packet FEC has been tried before and found to be wanting, but I would not be as quick as some to dismiss a strong claim by MIT just because others have failed in the past.

sounds like an ad for the future fast lane

[CaptainStumpy]

Xfinity video in your face 4650% faster! Xfinity introduces the RLNC fast lane data transmission! Its like an over caffeinated jaguar solving linear matrices while orbiting the earth in the space shuttle and doing coke. RAAAWRR! Don't like the jaguar? Tough floating jaguar shit, you don't have a choice! We own teh tubes! ©omcastic!

Word

[Dan East]

"the immediately earlier sequenced packet". There a word for that. It's called "previous". As in "the previous packet".

Re:Word

[Wraithlyn]

...so does "earlier"

Packet loss models?

[antifoidulus]

TFA doesn't seem to state what their assumptions were on how packets get lost and how many packet losses the algorithm can deal with, and what their distribution is. There are a lot of ways you can drop k packets out of n packets sent.

If you assume that every packet has a k/n chance of being lost, then being able to reconstruct a single missing packet could be incredibly useful. However cell phone packet losses tend to be incredibly bursty, i.e. they will have a very throughput for a while, but then all of a sudden(maybe you changed towers or went under a bridge etc) lose a whole ton of packets. Can this algorithm deal with bursty losses? I wish TFA was a bit more clear on that

Re:in simplified terms, it's forward error correct

[AK Marc]

I think they are lying.

Many of the details fail under closer examination. It doesn't "use" TCP-IP. It could use a propritary IP stack that is TCP/IP compatible. So it'll use IP addresses and port numbers like a TCP packet would so that switches and routers in the middle wouldn't know or care what it's doing. If they put it on an IPX/SPX core it'd fail to route across the Internet. But it isn't TCP. It doesn't use a TCP compliant stack. It just looks like one to the outside world. It will not re-transmit a lost packet via TCP mechanisms. But it'll work on the same hardware on both ends and software in the middle. You just have to replace the network stack on both ends, which isn't hard. Though they indicate that the only thing it needs is "software" on both ends. Maybe they'll be doing it over actual TCP/IP. That, and the way they keep saying TCP-IP, that includes UDP. They don't say TCP, or UDP. And I don't trust them when they keep saying TCP-IP, it should be a slash, not a dash. So is it running over TCP/IP (which could mean UDP)? Or does it run over TCP (which excludes UDP)?

Right.

[Animats]

This is yet another form of forward error correction. The claim is that it doesn't take any extra data to add forward error correction. That seems doubful, since it would violate Shannon's coding theorem.

This was tested against 3% random packet loss. If you have statistically well behaved packet loss due to noise, FEC works great. If you have bursty packet loss due to congestion, not so great.

Re:Right.

[MobyDisk]

The claim is that it doesn't take any extra data to add forward error correction. That seems doubful, since it would violate Shannon's coding theorem.

Yeah, that would be impossible. But I don't think they meant to claim that there is no extra data. When they say "The combined packet length is no longer than either of the two packets from which it is composed." I took that to mean that each packet is a fixed length. Not that they didn't add extra data to get to that packet length.

This was tested against 3% random packet loss. If you have statistically well behaved packet loss due to noise, FEC works great. If you have bursty packet loss due to congestion, not so great.

Yeah. It might be good for for wireless networks, where even a "5 bar" wireless network connection has a fairly consistent 1% packet loss. The QUIC protocol is another attempt to handle this better by using packet pacing, but QUIC isn't worth it in general even if it addresses this one specific problem.

parses like a teaspoon of sugar

[epine]

I've been parsing this kind of press release for a long, long time now. I can pretty much tell what we're dealing with by how hard it is to state the advantage of a new approach in narrow and precise language.

That this blurb doesn't even disclose the error model class (error correction is undefined without doing so) suggests that the main advantage of this codec lies more in the targeting of a particular loss model than a general advance in mathematical power.

Any error correction method looks good when fed data that exactly corresponds to the loss model over which it directly optimises.

The innovators of this might have something valuable, but they are clearly trying to construe it as more than it is. This suggests that there are other, equally viable ways to skin this particular cat.

Re:in simplified terms, it's forward error correct

[Mariner28]

Like Anonymous Coward, yours were my thoughts exactly. Why would one use TCP to stream video? It's one of the tenants of networking that losing packets is preferable to increasing jitter in the video or audio feed. And off the top of my head, I'd say that there hasn't been a widely used connection-based layer 2 protocol since X.25. Hell, that's why Frame Relay and later ATM were invented - to let the transport layer handle error detection (and retransmission if required). Even Ethernet uses just a CRC for forward error correction - if the receiver can't fix errors, the frame is dropped. It's up to the upper layers do actually do anything about it. And let's not get started about a 3% random error distribution in a wireless link - everyone knows that fading causes a whole stream of consecutive packets to be lost, not just an even statistical distribution of them. Stephen Max Patterson at Network World just proved he isn't qualified to write for Network World... And just a nit for you, AK Marc - if someone says UDP is "running over TCP/IP", tell them to put down the router and step away from the rack. They just aren't qualified.