BATS Sparse Codes for Librecast

2026-09-28, France

Introduction

Our existing RaptorQ Forward Erasure Correction in liblcrq helps us cope with packet loss in our UDP multicast streams. By extending this library to support network coding we can fully utilise multiple links with multicast, allowing us to maximize throughput across diverse links. This is particularly useful in combination with our peer to peer overlay multicast, as multiple links between peers will be the normal mode of operation.

In July 2023 the Coding for Efficient Network Communications Research Group (NWCRG - now disbanded) of the Internet Research Task Force (IRTF) published RFC 9426. This was exciting for the Librecast team, as we’d been aware of BATS codes since our work implementing RaptorQ in early 2022 and we had been interested in how these can be applied to our work with multicast.

RFC 9426 (IRTF) describes BATched Sparse (BATS) Coding Scheme for Multi-hop Data Transport. As this is an IRTF RFC and not an IETF Standards Track document there is no standard to conform to and the RFC does not describe a complete protocol implementation.

The IRTF does not publish standards track RFCs (that being the task of the IETF), and the RFC does not describe a complete protocol implementation. Interoperation with other implementations is therefore unlikely (and also because we are unaware at the time of writing of any other attempts to implement this RFC, at least in FOSS software).

By combining the ideas and methods described in IRTF RFC 9426 with other sources, including the book, BATS Codes Theory and Practice by Shenghao Yang and Raymond W. Yeung (2022, Springer Press), we have put together an experimental BATS implementation for use with Librecast as part of our LCRQ library.

The Problems

Multi-Hop (Erasures)

IPv6 multicast, which is based on UDP, is inherently unreliable. Packets can arrive out of order, or may not arrive at all. In the language of network coding, these packet losses are called erasures. Unlike with TCP, there is no help from the network layer to cope with these erasures, so we need to find another way.

Forward error correction (FEC) codes, especially advanced fountain codes such as RaptorQ do an excellent job of recovering from erasures, but their operation is generally limited to end-to-end recovery on the receiving nodes.

Packet loss in multi-hop networks is cumulative. A rate of packet loss that may seem minor over a single hop, quickly reaches the point over multiple hops where it is unrecoverable using end-to-end techniques alone. In multi-hop wifi, mesh, and some overlay networks these losses can be severe over only a few hops.

While it is possible to use erasure codes such as RaptorQ on intermediate nodes to recover from packet loss, the storage requirements, computational overhead, and introduced latency make this prohibitive for many applications. A fountain code like RaptorQ operates on the full source data, with each node needing to reserve storage for and decode the full object before it can regenerate and send any lost packets.

Multi-Path (Network Throughput)

There is a second problem we’d like to solve, too. Routing.

When there are multiple diverse paths between source(s) and destination(s), making efficient use of the available network bandwidth is not achievable with traditional routing techniques. When multiple paths are available we do not want to choose between them (routing), we want to make full use of all available paths to achieve the optimal network flow.

In the case of multicast it has been shown that network coding is sufficient to achieve the optimum (max-flow) between a source and the receiving nodes.

Random Linear Network Coding (RLNC)

Linear network coding uses linear combinations of source data blocks to transmit data over a packet network.

Source data is first divided into blocks, with padding applied to the last block if required to ensure all blocks are the same size.

A generation (batch size) of packets (M) and a Galois field(GF) size is chosen (q).

NB: Most literature defines q such that GF(q) is the field size. In lcrq we use q such that GF(2q). Our definition is much more convenient to work with. Our q fits in uint8_t and we do not need to find log2(q) every time we want to work with bits.

The same irreducible polynomial must be used by all participating nodes. As this is not specified in the RFC, we have selected:

x8 + x4 + x3 + x2 + x + 1

which is the same polynomial used by IETF RFC 6330 (RaptorQ).

The data in each block is multiplied by random coding coefficients generated from the chosen Galois field and the packets in the batch are added (XOR) toegether. These operations on a finite field do not change the size of the data. The coding vectors are sent with the coded packets to enable decoding on receiver nodes.

On intermediate nodes the data can be recoded using the same method. More random coding coefficients are generated and multiplied against both the existing coding vectors and the data to recode a new generation of packets for sending. Additional packets can be generated when recoding to replace any lost to erasures.

Linear network coding shifts the problem of data transport from one of delivering a fixed set of packets to one of information distribution. As soon as a sufficient amount of coded packets is received decoding can proceed with a high degree of probablility. There is no need to request retransmission and wait for receipt of specific packets as the information is distributed across all coded packets.

In addition to coping with erasures, network coding allows us to fully utilize diverse network paths. Rather than making routing choices at each hop, we send (re)coded packets on all available paths to the receiver nodes.

BATS Sparse Codes (BATS)

BATS Codes combine an outer code and an inner code. The outer code is a matrix generalisation of a fountain code (essentially a Luby Transform (LT) Code with a coding vector applied). As the outer code is a fountain code, we can use it to generate a virtually unlimited number of symbols on the source nodes.

As the name suggests, BATS Codes are applied to batches of M source blocks, where M is an integer generally in the range 4 to 128. If M=1, the batch code becomes a simple LT code, and as there are no batches to recode the intermediate nodes simply forward the packets they receive.

On the intermediate nodes, an inner code (RLNC) can be applied which allows for the recovery of erasures (packet loss) on a hop-by-hop basis instead on relying solely on end-to-end erasure correction techniques (FEC).

On a multi-hop network packet loss is cumulative, and can quickly accumulate over several hops making the network virtually even with end-to-end erasure correction applied (such as RaptorQ).

A precode can be applied to the source data before coding to increase the probability of successful decoding. This also has the effect of greatly increasing the number of distinct packets available to the outer encoder for batch generation. The LCRQ library has support for RaptorQ as a precode.

Acknowledgements

LCRQ uses the fast Galois field multiplication technique described in:

J. S. Plank and K. M. Greenan and E. L. Miller (2013) “Screaming Fast Galois Field Arithmetic Using Intel SIMD Instructions”

LCRQ uses the Tiny Mersenne Twister derived from IETF RFC 8682 and originally by Mutsuo Saito and Makoto Matsumoto of Hiroshima University.

This work would not have been possible without the funding and support of NLnet through NGI Zero Core, part of the European Commission's Next Generation Internet program.

References