rlnc
Blazing Fast Erasure-Coding with Random Linear Network Coding (RLNC)
Introduction
rlnc is a Rust library crate that implements an advanced erasure-coding technique Random Linear Network Coding (RLNC) over galois field $GF(28)$ with irreducible polynomial $x8 + x4 + x3 + x + 1$. This library provides functionalities for blazing fast erasure-coding of data, reconstructing original data from coded pieces, and recoding existing coded pieces to new erasure-coded pieces, without ever decoding it back to original data. It performs runtime introspection of platform and uses the best of GFNI, AVX512, AVX2 and SSSE3 intrinsics on x86_64 and NEON intrinsics on arm64, for fast vector multiplication by a single scalar over $GF(2^8)$.
Following charts show performance of RLNC encoder, recoder and decoder on AWS EC2 m7a.large with AMD EPYC 9R14 - which has GFNI + AVX512 support. More on performance benchmarking below.
Let's take a practical example of how RLNC can be useful.
Imagine you want to send a book, split into 10 chapters, to a friend over a very unreliable mail service that often loses envelopes.
The old way is to send each of the 10 chapters in a separate envelope. If even 1 envelope gets lost, your friend can't read the whole book. They have to ask you to send that specific missing chapter again, which is slow and inefficient.
Random Linear Network Coding (RLNC) works like this: instead of sending the original chapters, you create 20 new "summary" envelopes. Each summary envelope is a unique, random mix of sentences from all the original 10 chapters. You then mail these 20 summary envelopes.
The magic is that your friend only needs to receive any 10 of these summary envelopes to perfectly reconstruct the entire book. It doesn't matter if the third one you sent gets lost, as long as another one arrives. Because each envelope contains information from the whole book, any 10 of them provide enough clues to solve the puzzle and rebuild the original 10 chapters.
This makes the transfer incredibly robust and efficient, as you don't need to worry about specific envelopes getting lost, just that enough of them make it to the destination.
RLNC can be used for erasure-coding both data-in-transit and data-in-rest - essentially increasing availability of original data by spreading it into many more pieces s.t. each of them is equally important. For a quick understanding of RLNC, have a look at my blog post @ https://itzmeanjan.in/pages/rlnc-in-depth.html.
Random Linear Network Coding (RLNC) excels in highly dynamic and lossy environments like multicast, peer-to-peer networks, and distributed storage, due to interesting properties such as encoding with random-sampled coefficients, any k out of n coded-pieces are sufficient to recover and recoding new pieces with existing erasure-coded pieces. Unlike Reed-Solomon, which requires specific symbols for deterministic recovery, RLNC allows decoding from any set of linearly independent packets. Compared to Fountain Codes, RLNC offers robust algebraic linearity with coding vector overhead, whereas Fountain codes prioritize very low decoding complexity and indefinite symbol generation, often for large-scale broadcasts.
Features
For now this crate implements only Full RLNC scheme.
- Encoder: Splits original data into fixed-size pieces and generates new coded pieces by linearly combining these original pieces with random coefficients, sampled from $GF(2^8)$.
- Decoder: Receives coded pieces, applies Gaussian elimination to recover the original data, and handles linearly dependent pieces gracefully.
- Recoder: Takes already coded pieces and generates new coded pieces from them, facilitating multi-hop data distribution without requiring intermediate decoding.
- Error Handling: Defines a custom
RLNCErrorenum to provide clear error messages for various operational failures.
Prerequisites
Rust stable toolchain; see https://rustup.rs for installation guide. MSRV for this crate is 1.89.0.
# While developing this library, I was using
)
Testing
For ensuring functional correctness of RLNC operations, the library includes a comprehensive test suite. Run all the tests by running following commands.
# Testing on host, first with `default` feature, then with `parallel` feature enabled.
# Testing on web assembly target, using `wasmtime`.
; ; ; ; ;
)
)
)
; ; ; ; ;
Code Coverage
To generate a detailed code coverage report in HTML format, use cargo-tarpaulin:
# Install cargo-tarpaulin if not already installed
||
||
||
||
||
||
||
||
||
||
||
||
||
||
||
||
This will create an HTML coverage report at tarpaulin-report.html that you can open in your web browser to view detailed line-by-line coverage information for all source files.
[!NOTE] There is a help menu, which introduces you to all available commands; just run
$ makefrom the root directory of this project.
Benchmarking
Performance benchmarks for several input configurations are included to evaluate the efficiency of this RLNC implementation.
To run the benchmarks, execute the following command from the root of the project:
[!WARNING] When benchmarking make sure you've disabled CPU frequency scaling, otherwise numbers you see can be misleading. I find https://github.com/google/benchmark/blob/b40db869/docs/reducing_variance.md helpful.
For visualizing benchmark results, run following command, which will produce PNG figures inside ./plots directory.
On 12th Gen Intel(R) Core(TM) i7-1260P
Running benchmarks on Linux 6.14.0-27-generic x86_64, compiled with rustc 1.88.0 (6b00bc388 2025-06-23).
| Component | Peak Median Throughput (default feature) |
Peak Median Throughput (parallel feature) |
Impact of number of pieces on performance |
|---|---|---|---|
| Full RLNC Encoder | 30.14 GiB/s | 23.39 GiB/s | The number of pieces original data got split into has a minimal impact on the encoding speed. |
| Full RLNC Recoder | 27.26 GiB/s | 12.63 GiB/s | Similar to the encoder, the recoder's performance remains largely consistent regardless of how many pieces the original data is split into. |
| Full RLNC Decoder | 1.59 GiB/s | Doesn't yet implement a parallel decoding mode | As the number of pieces increases, the decoding time increases substantially, leading to a considerable drop in throughput. This indicates that decoding is the most computationally intensive part of the full RLNC scheme, and its performance is inversely proportional to the number of pieces. |
In summary, the full RLNC implementation demonstrates excellent encoding and recoding speeds, consistently achieving GiB/s throughputs with minimal sensitivity to the number of data pieces. The parallel feature, leveraging Rust rayon data-parallelism framework, also provides good performance for both encoding and recoding. Whether you want to use that feature, completely depends on your usecase. However, decoding remains a much slower operation, with its performance significantly diminishing as the data is split into a greater number of pieces, and currently does not implement a parallel decoding algorithm.
Usage
To use rlnc library crate in your Rust project, add it as a dependency in your Cargo.toml:
[]
= "=0.8.6" # On x86_64 and aarch64 targets, it offers fast encoding, recoding and decoding, using SIMD intrinsics.
# or
= { = "=0.8.6", = "parallel" } # Uses `rayon`-based data-parallelism for fast encoding and recoding. Note, this feature, doesn't yet parallelize RLNC decoding.
= { = "=0.9.2" } # Required for random number generation
Full RLNC Workflow Example
I maintain an example demonstrating the Full RLNC workflow:
- Encoding original data into coded pieces.
- Recoding to generate new pieces from received coded pieces. It simulates a relay node.
- Finally decoding all received pieces to recover the original data.
[!NOTE] New recoded pieces could be either useful or not for the Decoder, based on Recoder input coded pieces i.e. from which they are recoded and whether they have already been seen by Decoder or not.
See full_rlnc.rs example program. Run the program with $ make example.