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

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.

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.

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.