Fountain codes (2005) [pdf] | Hacker News Reader

Fountain codes (2005) [pdf]

docs.switzernet.com

37 pointsTomte7 comments

> However, Reed–Solomon codes have the disadvantage that they are practical only for small K, N, and q: standard implementations of encoding and decoding have a cost of order K(N-􏰀K)log2 N packet operations. Furthermore, with a Reed–Solomon code, as with any block code, one must estimate the erasure probability f and choose the code rate R=K/N before transmission. If we are unlucky and f is larger than expected and the receiver receives fewer than K symbols, what are we to do? We would like a simple way to extend the code on the fly to create a lower-rate (N', K) code. For Reed–Solomon codes, no such on-the-fly method exists.

You don't have to choose the rate before transmission. Reed-Solomon code is equivalent to sampling a K-degree polynomial. You can sample it all you want, i.e. increase N on-the-fly, up to the number of the elements in your field, if finite. Say, you want to broadcast your K blocks to L recipients reliably: after you have sent the K blocks you start sampling the polynomial and sending the redundant blocks. You don't need to decide a priory how many redundant blocks you will send: as soon as the last recipient reports receiving K blocks you are done. GF(2^64) is as good as infinite in that scenario.

This leaves me with so many follow up questions:

+ Are there practical problems using this in the real world?

+ Are there implementations of fountain codes?

+ Why haven't we replaced our traditional file transfer processes with fountain codes?

Could someone familiar with the topic please answer?

Any time you have a high bandwidth delay product (or just high delay) in a network link, fountain codes are useful. Note they aren't useful on top of TCP.

Some time in 2006-2010, while I was working on Google's web search infrqstructure, we switched to fountain codes for copying the index around the world.

The downsides are increased CPU usage and poor cache locality. Naive implementations aren't compatible with streaming or otherwise starting to use/play data/content before transfer is complete.

Without TCP, you'll probably need to implement TCP-friendly flow control.

I believe RaptorQ is a known implementation, and afaik it's used in low bandwidth satellite communication where FEC is just too expensive (measuring it's bandwidth usage). While FEC is indeed configurable through the ratio for the number of normal / FEC packets, it can be still too expensive in some situations.

I've used it in a startup that did motivation data transfers and it was the only way around. It was and likely will is patented which makes it less attractive and the places where it is the only solution are niche.

Could this technique be used for UDP data transfer over a lossy long fat pipe? I’ve been testing Tsunami-UDP, and although it works for most lossy networks, extremely lossy networks severely throttle it. A fountain code implementation should achieve full channel capacity. Has anyone implemented such a tool in open source, or are the commercial UDP data transfer tools using this as a patented method?

Yes, it works over udp. I've worked in the past in a startup that used fountain codes to transmit data over multicast and it worked beautifully. There was no need to retransmit specific packets and we only need to know when everyone got the file rather than what specific packets each client lost.

Reply on news.ycombinator.com