Raptor codes will defeat rapacious telcos

Raptor codes will defeat rapacious telcos

Summary: Watching a stuttering YouTube video is frustrating. With all the technology at our command why can't we do better?

TOPICS: Big Data

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.

Topic: Big Data

Kick off your day with ZDNet's daily email newsletter. It's the freshest tech news and opinion, served hot. Get it.


Log in or register to join the discussion
  • Your assumption on saving in retransmits is incorrect...

    Most video streaming in this world uses UDP. While FEC may be able to help video quality - it is not going to help reduce bandwidth use because udp never retransmits dropped packets.
  • don't see the real innovation

    I don't see what is new here. Packing video data with extra "fix" data hast existed for decades. DVD does it as well, to account for scratched disks and so on.

    The lack of retransmition, as another reader pointed out, is common practice with UDP so this is no innovation either.

    I'm sure there is something else that makes this technology innovative. But from just reading the article, I'm not sure what that is.
  • Fountain codes - of which Raptor codes are a subset

    Thanks for the feedback. I probably should have gone deeper into the whole Fountain
    code area, which really is a significant invention based on some pretty spectacular
    math. Maybe I will later this afternoon.

    UDP won't provide quality video reliably. If you want quality video with the current
    infrastructure you need some way to recover lost packets. Raptor does that with FEC.

    R Harris
    • would be interesting...

      thanks for the clarification. It would be interesting to learn more about it. If you have the time, it might be worth digging a bit deeper and giving us an overview in a future article.
  • Net neutrality

    ...is the real issue here, all we really need is for a law mandating net neutrality to be passed in order for this issue of traffic prioritizing in return for extra money to be gotten rid of

    - John Musbach
    John Musbach
  • RE: Raptor codes will defeat rapacious telcos

    To tell the truth, I'm left a bit behind by all this. I have, however, wondered for quite some time how You Tube and the like can get by with such abysmal video. The comparison that comes first to mind is the way that I can receive Netflix online movies by way of a Comcast 6mbps connection; I find that it is very difficult to tell the difference between such a broadcast and a conventional definition DVD. As clear as the Netflix product is I can think of no plausible excuse for something like You Tube to be as poor as such transmissions are. They really should be very much ashamed, when such vastly superior transmissions are readily available.
  • RE: Raptor codes will defeat rapacious telcos

    You seem to be confused about the network loading effect of this technology (which conceptually dates back at least to Rabin's 1989 paper): in order to ensure that no data loss occurs at the destination, the source must usually send considerably *more* data than would be required if conventional retries were used.

    Furthermore, retries due to data loss only produce stuttering in naive implementations (or in those with extremely tight requirements for immediate display at the client): it takes relatively little buffering in the receiver to run the display a second or so behind the input such that any necessary retries can complete before the data is actually used (not that a dropped mpeg frame is usually all that noticeable anyway, which allows the client some discretion in prioritizing retries).

    I suspect that DF's technology may be most applicable to bulk multicast situations (e.g., broadcasts, or video-almost-on-demand where clients wait for the next scheduled stream to begin), where different receivers may lose different packets from a common stream and thus the aggregate retry load might exceed the cost of the redundant FEC data.

    - bill
    - bill
    • Good comment. (NoText)

      No added text from me.
  • RE: Raptor codes will defeat rapacious telcos

    Now if only CNN.com would adopt this system. Watching their streaming vids is like getting teeth pulled. Without benefit of anesthesia!
  • variable FEC overhead

    I haven't read the article but it seems to me that the FEC overhead could be variable. The client could detect the rate of dropped packets and notify the server accordingly (via TCP). The only drawback I see is more processing load on the server. If the network is performing well the increased bandwidth will be next to nothing but if packet loss is high bandwidth is ramped up as needed.
  • oops. Bandwidth != retransmission

    Your post conflates the amount of bandwidth required (4Mbit/sec for HD) with degree of packet loss.

    The "herky-jerky" you experience on Youtube is server & TCP related. Youtube et al use HTTP on TCP because it's always accessible behind firewalls/corporate proxies. UDP/Raptor is not.

    And remember that raptor codes won't help with TCP. At all. (TCP will always retransmit...)

    You have to compare Raptor codes to straight-up UDP.

    - Compared with UDP, it won't decrease retransmission.
    - Raptor codes won't decrease the bandwidth required.

    So what's the win with Raptor? Very little. Raptor codes could provide better quality than straight UDP in lossy networks, but NOT ANY BETTER in low loss networks.

    The "hard math" for FEC isn't that hard. Think RAID 5 for networks.

    I have nothing against DF, but don't get too excited about this: the use cases and benefits are small.
    friendly sceptic
  • Raptor Magic

    Seriously ,Magic is the nick name of raptor technology.I finally managed to develop a working implementation of RFC 5053 and is really having shocks and fun while testing.Man its power is way beyond.The developers of this technology deserve a lot of praise for making out this magic out of mathematics.

    Man there is no blockage in the way of this technology from controlling the MBMS domain.