Raptor codes will defeat rapacious telcos
Watching a stuttering YouTube video is frustrating. With all the technology at our command why can't we do better? Starting next year, we will.
Streaming video or herky-jerky video The Internet is a packet-based network. Each packet has a source and destination address and often a sequence number that describes where the packet belongs.
The stuttering results when video frames are dropped out of the video streams. When 2 packets can take wildly different routes or encounter sudden congestion something has to give - and your video quality is it.
This is one reason the telcos want to charge extra to deliver streaming video: it needs special treatment. But what if it didn't?
Raptor codes Invented in 2000 by Berkeley math professor Michael Luby, Raptor codes are a class of Fountain codes. They have fast, lightweight decoding while maintaining video quality even if more than 20% of the frames are lost.
High quality video won't need special treatment by the network. Raptor codes have been incorporated in several video standards. Digital Fountain is offering them in products for content distribution networks.
How it works The math is way beyond me, but the basic ideas are simple enough.
The video stream is encoded with extra data - repair data - as it is packetized and shipped over the network. The receiving decoder can can detect and often correct errors based only on the extra repair data.
This error correction is called forward error correction (FEC) because no feedback or retransmission from the sender is required. The packets contain the extra data needed to reconstruct lost packets.
The really cool part So won't all this extra data clog up the Internet even more? Not at all.
When packets get lost the normal recovery mechanism is to ask for the packet to be retransmitted. An extra request and a retransmission. With FEC that overhead is eliminated.
The extra redundancy can reduce latency and bandwidth use since the retransmissions aren't required. So we get high quality video at the same network load.
The Storage Bits take The telco's protection racket - nice little video stream you got there. Be a shame if something happened to it. - makes even less sense in a world with widespread FEC use. Telcos should focus on adding bandwidth as demand grows. Net neutrality is a great idea and has been for 160 years.
In a few years today's YouTube videos will look as quaint as Buster Keaton's silent masterpiece The General does to us. Kudos to Professor Luby and the Digital Fountain team for bringing real innovation to Internet TV.
Comments welcome, of course. If you love digging into serious math, download the PDF Raptor Codes by Amin Shokrollahi, Senior Member, IEEE, a peer-reviewed article published in the IEEE TRANSACTIONS ON INFORMATION THEORY in 2006.
For a lighter-weight intro with video examples, check out DF's presentation at the fall Demo conference here.
Update: The first couple of commenters wondered what the big deal is. To put is simply, much more efficient distribution of video across lousy networks.
Here is the abstract from the original paper on digital fountain codes:
Abstract—The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal, fully scalable protocol for these applications that we call a digital fountain. A digital fountain allows any number of heterogeneous clients to acquire bulk data with optimal efficiency at times of their choosing. Moreover, no feedback channels are needed to ensure reliable delivery, even in the face of high loss rates.
We develop a protocol that closely approximates a digital fountain using a new class of erasure codes that for large block sizes are orders of magnitude faster than standard erasure codes. We provide performance measurements that demonstrate the feasibility of our approach and discuss the design, implementation and performance of an experimental system.
Here's the PDF of A Digital Fountain Approach to Reliable Distribution of Bulk Data. This is a scholarly paper.