Repair on demand with Reed–Solomon coding

Choosing how much repair data to send is part of designing for packet loss. A live stream may have a firm bandwidth budget and a deadline for every frame. A file broadcast may benefit from sending more repair data as receivers continue listening. Rateless Reed–Solomon designs aim to provide that flexibility while retaining a predictable recovery threshold.

A predictable recovery threshold

Reed–Solomon coding can reconstruct a block of 50 source packets from any 50 distinct, intact source or repair packets belonging to that block. If 15 source packets go missing, the 35 surviving packets and 15 repair packets are enough. Receiving the same repair packet twice adds no new information.

Conventional interfaces ask the application to choose the number of source and repair packets before encoding. That is a good fit when the transmission budget is known. Generating repair on demand lets the application begin with a modest allowance and request more when the transfer needs it.

For a broadcast, those additional packets can help receivers with different gaps in reception. The sender does not have to select a particular missing source packet for each listener. The application controls the schedule and any receiver feedback, while the codec generates repair data and reconstructs missing information.

The challenge is to make that flexibility efficient. Requests for additional repair should reuse preparation already performed for the source block. Otherwise, generating a little more protection can mean repeating much of the original work.

What the nanorq comparison found

In a 2024 study published in IEEE Transactions on Communications, Leilei Yu, Sian-Jheng Lin and Yunghsiang S. Han compared their rateless Reed–Solomon construction with nanorq, an open-source implementation of RaptorQ. Their approach combines fast transforms with an extension of the coding field, expanding the range of repair packets while keeping previously generated packets usable. ¹

The proposed codes achieved higher coding throughput for small blocks in the reported comparison. At larger sizes, RaptorQ benefited from encoding pre-calculation. Figures 6 and 7 used 32-byte packets, loss probabilities of 20% and 40%, and throughput calculated from the combined encoding and decoding time.

The receiver was given as many packets as the original source block, a condition called zero reception overhead. The proposed codes guarantee recovery at that threshold; RaptorQ can occasionally need more packets. Both speed and recovery success matter when interpreting these results.

Measuring for the intended workload

Choosing a codec starts with the needs of the application. Short blocks protected against a deadline place different demands on an implementation from large files distributed to many receivers.

Preparation, additional repair generation and decoding each deserve attention. Repeated repair requests for the same source block can reuse earlier work, while new source data or different loss patterns may require more preparation. Measurements should reflect those differences, using realistic packet sizes and transmission budgets and recording whether recovery succeeds.

An open implementation makes this kind of investigation possible. Researchers can examine the code, measure its behavior and test alternatives. The nanorq comparison shows the value of making a working implementation available for others to question and improve.

An experiment in nanors

nanors has an experimental rlrs branch that lets applications request additional repair packets for a fixed source block and reuse preparation across requests. ²

The branch uses a fixed coding field with a finite repair range. It is a separate implementation from the paper’s field-extension construction, and the published performance results do not describe it. Further work is needed to assess whether the flexibility of repair on demand justifies its computational overhead in practical workloads.

Developers can inspect nanorq and the nanors RLRS branch on GitHub, test them against their own workloads, and contribute to the investigation.

References