Relaying a fountain code across multiple nodes

Fountain codes are designed for erasure channels, and are particularly well suited for broadcast applications from a single source to its one hop receivers. In this context, the problem of designing a rateless code in the network case for on-the-fly recoding is very important, as relaying the data over multiple nodes is fundamentally useful in a network. Clearly, fountain codes are unsuited for on-line recoding (and simply forwarding over subsequent hops is provably suboptimal). Random linear codes are throughput optimal, but they do not enjoy the low complexity that is a prime feature of fountain codes. Can we get the low complexity of say, LT codes, while maintaining on-the-fly recoding and being throughput optimal? This paper proposes a novel solution to the above question. We consider packet level coding on a line network of discrete memoryless erasure channels (with potentially unlimited nodes), and exhibhit a coding scheme with (1) tatelessness (2) logarithmic per-symbol coding complexity (3) throughput optimality (achieves rates equal the min cut capacity) and (4) avoids the delay of having to decode and then re-encode entire block lengths at intermediate nodes.