RFC 9426
BATched Sparse (BATS) Coding Scheme for Multi-hop Data Transport
RFC 9426: BATched Sparse (BATS) Coding Scheme for Multi-hop Data Transport 🦋
okay so bestie, this is the first part of a really cute RFC 💖 It's an Informational document from the IRTF, which means it's published for info and is not an Internet Standard 🌸 It's from July 2023, and it doesn't obsolete or update anything. The authors are S. Yang, X. Huang, R. Yeung, and J. Zao, mostly from CUHK, with Yang and Yeung also tied to n-hop technologies 🧚 It's a product of the Coding for Efficient Network Communications Research Group (NWCRG) ✨
The whole vibe is linear network coding, specifically BATS codes, which are giving "fountain codes meet network coding" energy 👑
Abstract ✨
Okay so linear network coding can make network communication better in terms of throughput, latency, and reliability 🔥 BATched Sparse (BATS) code is a class of efficient linear network coding scheme. Its outer code is a matrix generalization of fountain codes, and its inner code is batch-based linear network coding 💅 This document describes a baseline BATS coding scheme for communication through multi-hop networks, and it also talks about the research issues you'd need to deal with to get a more sophisticated version 🦋 This document is a product of the Coding for Efficient Network Communications Research Group (NWCRG) 🫶
Status of This Memo ✨
This document is not an Internet Standards Track specification. It's published for informational purposes 🌸
It's a product of the Internet Research Task Force (IRTF), which publishes the results of Internet-related research and development. Those results might not be suitable for deployment, so be chill about that 😭 This RFC represents the consensus of the Coding for Efficient Network Communications Research Group of the IRTF. Documents approved for publication by the IRSG are not candidates for any level of Internet Standard, see Section 2 of RFC 7841 💜
For the current status, errata, and how to give feedback, check https://www.rfc-editor.org/info/rfc9426 🎀
Copyright Notice ✨
Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved. 🌈
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication. Please review those documents carefully, because they describe your rights and restrictions with respect to this document 💅
Table of Contents 🧚
1. Introduction
1.1. Requirements Language
2. A Use Case of the BATS Coding Scheme
2.1. Introduction
2.2. DDP Procedures
2.2.1. Source Node Data Partitioning and Padding
2.2.2. Source Node Outer Code Encoding Procedure
2.2.3. Recoding Procedures
2.2.4. Destination Node Procedures
2.3. Recommendation for the Parameters
2.4. Coding Parameters in DDP Packets
2.4.1. Coding Parameter Format
2.4.2. Coded Packet Format
3. BATS Code Specification
3.1. Common Parts
3.2. Outer Code Encoder
3.3. Inner Code Encoder (Recoder)
3.4. Outer Decoder
4. Research Issues
4.1. Coding Design Issues
4.2. Protocol Design Issues
4.3. Usage Scenario Considerations
5. IANA Considerations
6. Security Considerations
6.1. Preventing Eavesdropping
6.2. Privacy Preservation against Traffic Analysis
6.3. Countermeasures against Pollution Attacks
7. References
7.1. Normative References
7.2. Informative References
Acknowledgments
Authors' Addresses1. Introduction 🎀
okay so this doc specifies a baseline BATched Sparse (BATS) code [Yang14] scheme for data delivery in multi-hop networks, and it also discusses the research issues towards a more sophisticated scheme 🦋 The BATS code here has two parts: an outer code and an inner code 💖
The outer code is a matrix generalization of fountain codes (see also the RaptorQ code described in [RFC6330]). It's reliable and efficient, and it's also compatible with network coding, which is so iconic 👑 The inner code, also called recoding, is formed by linear network coding to fight packet loss, improve multicast efficiency, and more 🔥 The detailed design and analysis live in the BATS monograph [Yang17] 📚
A BATS coding scheme can run over multi-hop networks made of wireless links. Those links are honestly unreliable because of interference, fading, multipath, and so on 😭 Existing transport protocols like TCP use end-to-end retransmission, and network protocols like IP might do store-and-forward at the relays, so packet loss can pile up along the way 💀
BATS can be used for all kinds of data delivery, like file transfer or video streaming over wireless multi-hop networks 🌸 Unlike forward error correction (FEC) schemes that run hop-by-hop or end-to-end, BATS mixes end-to-end coding (the outer code) with hop-by-hop coding (the inner code), so it can potentially perform better ✨
The baseline scheme handles a network with multiple communication flows. Each flow's source encodes its data separately, but inside the network you're allowed to mix packets from different flows for recoding 🧚 This document shows a simple case where recoding happens within each flow. The same encoding and decoding scheme works with different recoding schemes too, as long as they follow the principle illustrated here 💅
We focus on the case where each flow has only one destination node. Sending the same data to multiple destination nodes is called multicast, and Section 4 talks more about that 🫶
The baseline BATS scheme has two goals. First, it gives researchers and engineers a starting point for building network communication applications and protocols on BATS codes 🎀 Second, it makes the research issues clearer on the way to a sophisticated network protocol based on BATS codes 🦋 Big research directions include security, congestion control, and routing algorithms for BATS codes 🌈
This document is a product of and represents the collaborative work and consensus of the NWCRG. It is not an IETF product and it is not an IETF standard 💜
1.1. Requirements Language ✨
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🔥
2. A Use Case of the BATS Coding Scheme 💅
The BATS scheme here can be used, for example, by a Data Delivery Protocol (DDP) 🧚 This doc isn't about a DDP, but this section briefly shows how a DDP uses the coding scheme so the role of the coding scheme is clear 🌸 Some terms we'll use are summarized below 🎀
DDP: : Data Delivery Protocol
DDP packet: : the packet formed by a DDP employing a BATS coding scheme
source packet: : the packet formed by the data for delivery
outer encoder: : the outer code encoder of a BATS code
recoder: : the inner code encoder of a BATS code
outer decoder: : the outer code decoder of a BATS code
coded packet: : the packet generated by the outer code encoder or a recoder
batch: : a set of coded packets generated by a BATS coding scheme from the same subset of the source packets
recoded packet: : a coded packet generated by a recoder
degree: : the number of source packets used to generate a batch by the outer encoder. (The degree can be different for a different batch.)
Other common terms can be found in [RFC8406] 🦋
2.1. Introduction ✨
We describe a DDP with one source node, one destination node, and multiple intermediate nodes in between 💖 A BATS scheme includes an outer code encoder (also called outer encoder), an inner code encoder (also called recoder), and an outer decoder that decodes the outer and inner codes jointly, as shown in Figure 1 👑 Here's what each piece does:
|
| {set of source packets}
v
+-+-+-+-+-+-+-+-+
| outer encoder |
| v | source node
| recoder |
+-+-+-+-+-+-+-+-+
|
| {set of DDP packets}
v
+-+-+-+-+-+-+-+-+
| |
| recoder | intermediate node
| |
+-+-+-+-+-+-+-+-+
|
| {set of DDP packets}
v
...
|
| {set of DDP packets}
v
+-+-+-+-+-+-+-+-+
| |
| outer decoder | destination node
| |
+-+-+-+-+-+-+-+-+
|
| {set of source packets}
v
Figure 1: A Network Model for Data DeliveryAt the source node, the DDP first chops the data into a bunch of source packets, each with the same number of bits (more in Section 2.2.1 🌸). Then it hands all the source packets to the outer encoder 🧚 The outer encoder generates a sequence of batches, and each batch has a fixed number of coded packets (see Section 2.2.2 💅)
Each batch from the source node then gets processed by the recoder separately 🔥 The recoder may make new coded packets from the existing coded packets in the batch (see Section 2.2.3 🫶) After the recoder is done, the DDP forms and sends DDP packets using the coded packets plus the matching batch information ✨
We assume a DDP packet is either received correctly or completely erased during communication 😭 The DDP pulls the coded packets and batch information out of the DDP packets it receives 🦋 A recoder is used at an intermediate node that doesn't need the data, and it generates recoded packets for each batch (see Section 2.2.3 🌈) The DDP forms and sends DDP packets using those recoded packets and the batch information 💜
The outer decoder is used at the destination node that actually needs the data 🎀 It pulls the coded packets and batch information out of the received DDP packets and tries to recover the transmitted data from the received batches (see Section 2.2.4 💖) Then the DDP passes the decoded data up to the application that needs it 👑
2.2. DDP Procedures 🦋
Okay so, the DDP has F octets of data it needs to send 📦. Let's walk through what one BATS session does to get those F octets across. Bestie, there's a limit on F for a single BATS session 🚧. If your data is bigger than that limit, you need multiple BATS sessions. How big the limit is depends on the coding parameters in this section and the calculations at the end of Section 2.4.2 💅.
2.2.1. Source Node Data Partitioning and Padding 🧩
First, the DDP figures out these parameters:
- batch size (M): the number of coded packets in a batch generated by the outer encoder
- recoding field size (q): the number of elements in the finite field for recoding, i.e., q is 2 or 2^8
- BATS payload size (TO): the number of payload octets in a BATS packet, including the coded data and the coefficient vector
Based on those, it works out T, CO, and K like this:
- CO: the number of octets of a coefficient vector, calculated as
CO = ceil(M * log2(q) / 8), which is also called the coefficient vector overhead - T: the number of data octets of a coded packet, calculated as
T = TO - CO - K: number of source packets, calculated as
K = floor(F / T) + 1
The data MUST be padded so it comes out to T*K octets. Then it gets chopped into K source packets b[0], ..., b[K - 1], each T octets long. In this padding scheme, b[0], ..., b[K - 2] are filled with data octets, and b[K - 1] gets whatever data is left plus the padding octets. Let P = K * T - F be the number of padding octets. We use b[K - 1, 0], ..., b[K - 1, T - P - 1] for the T - P source octets, and b[K - 1, T - P], ..., b[K - 1, T - 1] for the P padding octets in b[K - 1]. The padding insertion process is shown in Figure 2 ✨.
Z = T - P
j = 1
v = 1
Let bl be the last source packet b[K - 1]
for i = Z, Z + 1, ..., T - 1 do
bl[i] = j
if i + 1 >= v + Z do
j += 1
v += jFigure 2: Data Padding Insertion Process
2.2.2. Source Node Outer Code Encoding Procedure 🎀
The DDP gives the BATS encoder this info:
- batch size (M): the number of coded packets in a batch
- recoding field size (q): the number of elements in the finite field for recoding
- maximum degree (MAX_DEG): a positive integer that specifies the largest degree can be used
- degree distribution (DD): an unsigned integer array of size MAX_DEG+1. The i-th entry DD[i] is the probability that i is chosen as the degree, where i is between 0 and MAX_DEG.
- a sequence of batch IDs (BIDs) (j, j = 0, 1, ...)
- number of source packets (K)
- packet size (T): the number of octets in a source packet
- source packets (b[i], i = 0, 1, ..., K - 1)
With that info, the outer encoder makes M coded packets for each BID using the steps in Section 3.2 🧠:
- Get a degree d by sampling DD. Roughly, the value d is chosen with probability DD[d].
- Choose d source packets uniformly at random from all the K source packets. It is allowed that a source packet is used by multiple batches.
- Generate M coded packets using the d source packets.
From the outer encoder, the DDP receives a sequence of batches. The batch with ID j has M coded packets (x[j,i], i =0, 1, ..., M - 1), each containing TO octets.
The DDP uses those batches to build DDP packets, which get sent to other network nodes on their way to the destination nodes 🚀. The DDP MUST deliver each coded packet with its batch ID, because the recoder and decoder both use it later.
The DDP MUST also deliver some of the info the encoder used to each recoder and the decoder. It can embed that info in the DDP packets or send it in separate protocol messages. For recoders, the DDP MUST deliver the following to each recoder:
- M: batch size
- q: recoding field size
For the decoder, the DDP MUST deliver the following to the decoder:
- M: batch size
- q: recoding field size
- K: the number of source packets
- T: the number of octets in a source packet
- DD: the degree distribution
The BID is used by both recoders and decoders. Section 2.4 shows how to embed BID, M, q, and K into DDP packets 💖. The degree distribution DD doesn't need to change often. For how to design a good degree distribution, see Section 6 of [Yang17]. Once it's designed, the source node and destination node can share it through the DDP, and that isn't discussed further here.
2.2.3. Recoding Procedures 🔁
Both the source node and the intermediate nodes recode the batches before transmission. At the source node, the recoder gets the batches from the outer code encoding procedure. At an intermediate node, the DDP gets DDP packets from other network nodes. If the DDP decides not to recode, it just forwards the DDP packets it received. Otherwise, the DDP should be able to pull out the coded packets and the matching batch info from those packets.
For a received batch, the DDP picks a positive integer (Mr), which is the number of recoded packets to send for that batch. Then the DDP gives the recoder this info:
- M: batch size
- q: recoding field size
- a number of received coded packets of the same batch, each containing TO octets
- Mr: the number of recoded packets to be generated
The recoder uses that info to generate Mr recoded packets, each containing TO octets. These are described in Section 3.3. The DDP then uses the Mr recoded packets to form the DDP packets it transmits 🌸.
2.2.4. Destination Node Procedures 🎯
At the destination node, the DDP gets DDP packets from an intermediate network node and should be able to pull out the coded packets and matching batch info from them. The DDP then uses an outer decoder to recover the data the source node sent 🕵️♀️.
The DDP gives the outer decoder (described in Section 3.4) this info:
- M: batch size
- q: recoding field size
- K: the number of source packets
- T: the number of octets of a source packet
- a sequence of batches, each of which is formed by a number of coded packets belonging to the same batch, with their corresponding BIDs
The decoder uses this info to decode the outer code and the inner code together, and recovers the K source packets (details in Section 3.4). If that works, the decoder hands the recovered K source packets back to the DDP, which uses them to rebuild the F octets of data. The recommended padding deletion process is shown below 👑:
// this procedure returns the number P of padding octets
// at the end of b[K - 1]
Let bl be the last decoded source packet b[K - 1]
PL = bl[T - 1]
if PL == 1 do
return P = 1
WI = T - 1
while bl[WI] == PL do
WI = WI - 1
return P = (1 + bl[WI]) * bl[WI] + T - WI - 1Figure 3: Data Padding Deletion Process
2.3. Recommendation for the Parameters 🌈
The recommended values for M and q are:
- when q = 2, M = 16, 32, 64, 128
- when q = 256, M = 4, 8, 16, 32
It is RECOMMENDED that K is at least 128. The encoder/decoder SHALL support an arbitrary positive integer value less than 2^16. Heads up though, the BATS coding scheme described here is not optimized for small K 🙈.
2.4. Coding Parameters in DDP Packets 🧚
Here's an example of how to embed the BATS coding parameters into the DDP packets used for recoding and decoding ✨. A DDP can build a DDP packet from a coded packet by adding whatever it needs to get the packet to the next node (for example, the DDP version, addresses, and session identifiers). We won't go into how those fields get formatted in a DDP packet. We're focusing on how to format the coding parameters and the coded packet inside it.
2.4.1. Coding Parameter Format 💜
In this example, 32 bits (4 octets) hold the parameters K, M, q, and BID. Those 32 bits are split into three subfields, called K, Mq, and BID, as shown in Figure 4 🍓.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| K | Mq | BID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 4: Coding Parameter Field Format
K: 16-bit unsigned integer, specifying the number of source packets of the BATS sessionMq: 3-bit unsigned integer, specifying the value of M and q, as shown in Table 1BID: 13-bit unsigned integer, specifying the batch ID of the batch the packet belongs to
+=====+=====+=====+
| Mq | M | q |
+=====+=====+=====+
| 000 | 16 | 2 |
+-----+-----+-----+
| 010 | 32 | 2 |
+-----+-----+-----+
| 100 | 64 | 2 |
+-----+-----+-----+
| 110 | 128 | 2 |
+-----+-----+-----+
| 001 | 4 | 256 |
+-----+-----+-----+
| 011 | 8 | 256 |
+-----+-----+-----+
| 101 | 16 | 256 |
+-----+-----+-----+
| 111 | 32 | 256 |
+-----+-----+-----+Table 1: Values of the Mq Field
Picking the coding parameters is a balancing act between computation cost, network conditions, and the coding performance you want 🤓. Usually a bigger batch size M gives better coding performance, but it costs more computation for encoding, recoding, and decoding. The field size q affects the coefficient vector overhead and also the computation cost for recoding. Within a BATS session, the BID field should be different for all batches, so the maximum number of batches the outer encoder can generate is 2^13. Different BATS sessions can reuse the same BID 💅.
2.4.2. Coded Packet Format ✨
Okay bestie, here's the coded packet layout 🎀 Take a look at Figure 5:
CO T
+-----------------------+-------------------------------+
| coefficient vector | coded data |
+-----------------------+-------------------------------+
Figure 5: Code Packet Format in a DDP PacketSo a coded packet is TO=T+CO octets long 💅 The first CO octets hold the coefficient vector, and the remaining T octets hold the coded data 🦋
- coefficient vector:
CO = M * log2(q) / 8octets. For the values of M and q in Table 1, CO is at most 32 octets when q is 256, and 6 octets when q is 2 ✨ - coded data:
Toctets. T should be chosen so that the whole DDP packet is at most Path MTU (PMTU) 💖
Using this layout, we can figure out the largest file size (F) for different parameters 🧮 For example, when q = 2 and M = 128, we get CO = 6 octets. Add the 4 octets used for embedding the coding parameters, and we can choose T = PMTU - H - 10, where H is the header length of a DDP packet. Since K can be at most 2^16 - 1, F can be at most (PMTU - H - 10)(2^16 - 1) octets. In this case, K / M is about 2^9, and the BID field lets you transmit 2^4 * K / M batches 🌈
3. BATS Code Specification ✨
3.1. Common Parts
Okay so the T octets of a source packet get treated like a column vector of T elements in GF(256) 🌸 The CO octets of a coefficient vector get treated like a column vector of CO elements in GF(q), where q = 2 or q = 256. This section assumes linear algebra and matrix operations over finite fields, so buckle up 🤓
For the two elements of GF(2), multiplication is a logical AND, and addition is a logical XOR 🫶 An element of GF(256) can be written as a polynomial with binary coefficients and degree lower than or equal to 7. Adding two GF(256) elements means adding those two binary polynomials. Multiplying them means multiplying the two binary polynomials and then reducing modulo an irreducible polynomial of degree 8, called a primitive polynomial. One example of a primitive polynomial for GF(256) is:
x^8 + x^4 + x^3 + x^2 + 1A common primitive polynomial MUST be specified for all the finite field multiplications over GF(256). ⚠️ Also, a binary polynomial of degree less than 8 can be represented by a binary sequence of 8 bits, which is just an octet 🧚
Suppose a pseudorandom number generator, Rand(), is shared by both encoding and decoding 🎲 It generates an unsigned integer of 32 bits. It can be initialized by Rand_Init(S) with seed S. If S is not provided, the generator gets initialized arbitrarily. One example of such a pseudorandom generator is defined in [RFC8682] 💜
A function called BatchSampler gets used in both encoding and decoding ✨ It takes two integers, j and d, as input, and it generates an array idx of d integers and a d x M matrix G. It starts by initializing the pseudorandom generator with j, then samples d distinct integers from 0 to K-1 as idx, and samples d*M integers from 0 to 255 as G. Check out the pseudocode in Figure 6 👀
function BatchSampler(j, d)
// initialize the pseudorandom generator by seed j.
Rand_Init(j)
// sample d distinct integers between 0 and K - 1.
for k = 0, ..., d - 1 do
r = Rand() % K
while r already exists in idx do
r = Rand() % K
idx[k] = r
// sample d x M matrix
for r = 0, ..., d - 1 do
for c = 0, ..., M - 1 do
G[r, c] = Rand() % 256
return idx, G
Figure 6: Batch Sampler Function3.2. Outer Code Encoder
So here's the deal with DegreeSampler 🍓 It's a function that returns an integer d using the degree distribution DD. We expect the empirical distribution of the returned d to converge to DD(d) when d < K. One design of DegreeSampler is shown in Figure 7. Heads up: when K < MAX_DEG, the degree value DegreeSampler returns doesn't exactly follow DD. The original says that won't really affect the practical decoding performance of the outer decoder described in Section 3.4, so no panic 🫠
function DegreeSampler(j, DD)
Let CDF be an array
CDF[0] = 0
for i = 1, ..., MAX_DEG do
CDF[i] = CDF[i - 1] + DD[i]
Rand_Init(j)
r = Rand() % CDF[MAX_DEG]
for d = 1, ..., MAX_DEG do
if r >= CDF[d] do
return min(d, K)
return min(MAX_DEG, K)
Figure 7: Degree Sampler FunctionLet b[0], b[1], ..., b[K-1] be the K source packets. A batch with BID j gets generated in these steps 🌷
- Get a degree d by calling DegreeSampler with input j.
- Get idx and G[j] by calling BatchSampler with input j and d.
- Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d - 1]]). Then form the batch X[j] = B[j] * G[j], whose dimension is T x M.
- Form the TO x M matrix Xr[j], where the first CO rows of Xr[j] form the M x M identity matrix I with entries in GF(q), and the last T rows of Xr[j] are X[j].
Here's the batch generating process in Figure 8 🎀
function GenBatch(j)
d = DegreeSampler(j)
(idx, G) = BatchSampler(j, d)
B = (b[idx[0]], b[idx[i]], ..., b[idx[d - 1]])
X = B * G
Xr = [I; X]
return Xr
Figure 8: Batch Generation Function3.3. Inner Code Encoder (Recoder)
Okay this part is giving network coding vibes 🦋 The inner code of a BATS code is basically (random) linear network coding applied to the coded packets that belong to the same batch. The recoded packets have the same BID. Say coded packets xr[i], i = 0, 1, ..., r - 1, all with the same BID j, have arrived at an intermediate node, and Mr recoded packets are supposed to be generated. Following random linear network coding, a recoded packet is made by a random linear combination: (randomly) choose a sequence of coefficients c[i], i = 0, 1, ..., r - 1 from GF(q), and generate c[0]xr[0] + c[1]xr[1] + ... + c[r - 1]xr[r - 1] as a recoded packet. This approach, called random linear recoding, gets good network coding performance for multicast when the batch size is sufficiently large 🌈
For unicast communications over a single path, as shown in Figure 1, you don't have to generate all Mr recoded packets with a random linear combination 🙈 Instead, xr[i], i = 0, 1, ..., r - 1 are used directly as recoded packets, and max(Mr - r, 0) recoded packets are generated using linear combinations. Compared with random linear recoding, this approach (called systematic recoding) can reduce both the computation cost and the recoding latency, which builds up linearly with the number of nodes. Note that systematic recoding may not always achieve the optimal network coding performance that random linear recoding does, in more complicated scenarios with multiple paths and multiple destination nodes 👀
3.4. Outer Decoder
So the decoder receives a sequence of batches, Yr[j], j = 0, 1, ..., n - 1, and each one is a TO-row matrix over GF(256) 💅 Let Y[j] be the submatrix of the last T rows of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]. When q = 2, let H[j] be the matrix over GF(256) formed by embedding each bit in the first M/8 rows of Yr[j] into GF(256). For successful decoding, the total rank of all the batches has to be at least K 🔥
The same degree distribution DD used by the outer encoder is supposed to be known by the outer decoder 🧠 By calling DegreeSampler and BatchSampler with input j, we get d[j], idx[j], and G[j]. Based on the encoding and recoding processes in Sections 3.2 and 3.3, each received batch with ID j gives us the system of linear equations Y[j] = B[j]G[j]H[j], where B[j] = (b[idx[j, 0]], b[idx[j, 1]], ..., b[idx[j, d - 1]]) is the unknown part 🫣
We start with a belief propagation (BP) decoder, which can efficiently solve for the source packets once enough batches have been received ✨ A batch j is decodable if rank(G[j]H[j]) = d[j]. (That means the system of linear equations Y[j] = B[j]G[j]H[j], with B[j] as the variable matrix, has a unique solution.) The BP decoding algorithm runs in multiple iterations, and each iteration has these steps 🔄
- Decoding Step: Find a batch j that is decodable. Solve the corresponding system of linear equations Y[j] = B[j]G[j]H[j], and decode B[j].
- Substitution Step: Substitute the decoded source packets into undecodable batches. Suppose a decoded source packet b[k] is used in generating an undecodable Y[j]. The substitution involves 1) removing the entry in idx[j] that corresponds to k, 2) removing the row in G[j] that corresponds to b[k], and 3) reducing d[j] by 1.
The BP decoder keeps repeating those steps until no batches are decodable during the decoding step 💖
When the degree distribution DD in the outer code encoder (see Section 3.2) is designed properly, the BP decoder guarantees a high probability of recovering a given fraction of the source packets when K is large 📈 To recover all the source packets, a precode can be applied to the source packets to generate a fraction of redundant packets before the outer code encoding is applied. Also, when the BP decoder stops, which may happen with high probability when K is relatively small, it's possible to continue with inactivation decoding. There, certain source packets are treated as inactive so that a similar belief propagation process can be resumed 🦋 The reader is referred to [RFC6330] for the design of a precode with good inactivation decoding performance 📚
4. Research Issues ✨
The baseline BATS coding scheme described in Sections 2 and 3 needs various refinements and complements before it can become a more sophisticated network communication application 🚀 Various related research issues are discussed in this section, but the security-related issues are left to Section 6 🔐
4.1. Coding Design Issues ✨
Okay bestie, when there are lots of batches, the BATS code specification in Section 3 is nearly optimal 😭🔥. Decoding can succeed with high probability when the total rank of all the batches used for decoding is just slightly larger than the number of source packets K. But when K is small 🥺, the DegreeSampler function in Figure 7 and the BatchSampler function in Figure 6, which are based on a pseudorandom generator, may not sample all the source packets evenly. That means some source packets end up not well protected 💀. One way to fix this is to generate a deterministic degree sequence when the number of batches is relatively small, and to design a special pseudorandom generator with good sampling performance when K is small 🧚.
There are research issues related to recoding, which we covered in Section 3.3 💅. One question is how many recoded packets to generate for each batch. Using the same number for all batches is asymptotically optimal, but it has been shown that transmitting a different number for different batches can improve recoding efficiency 🙌. The intuition is that a batch with a lower rank needs a smaller number of recoded packets to be transmitted. This kind of recoding scheme is called adaptive recoding [Yin19].
Packet loss in network communication is usually bursty 🌧️, which may harm recoding performance. One way to resolve this is to transmit the packets of different batches in a mixed order, which is also called batch interleaving [Yin20]. How to interleave batches efficiently without increasing end-to-end latency too much is a research issue 🤔.
Though we only focus on the BATS coding scheme with one source node and one destination node, a BATS coding scheme can be used with multiple source and destination nodes 🌐. To benefit from multiple source nodes, we would need different source nodes to generate statistically independent batches. It is well-known that linear network coding [Li03] achieves the multicast capacity. BATS codes can benefit from network coding because of their inner code 🧵. For multicast, each destination node independently performs the same operations described in this document, but the inner code should be improved to take multiple destination nodes into consideration. How to efficiently implement multicast needs further research 🦋.
4.2. Protocol Design Issues 🌸
The baseline scheme in this document focuses on reliable communication 💖. There are other issues to think about if you want to design a fully functional DDP based on a BATS coding scheme 🎀. Here we talk about some network management issues that are closely related to a BATS coding scheme: routing, congestion control, and media access control 👑.
The outer code of a BATS code can be regarded as a channel code for the channel induced by the inner code, so network management algorithms should try to maximize the capacity of the channel induced by the inner code ✨. A network utility maximization problem [Dong20] for BATS coding can be applied to study routing, congestion control, and media access control jointly. Compared with network utility maximization for the Internet, there are two major differences 💅. First, the network flow rate is not measured by the rate of the raw packets. Instead, a rank-based measurement induced by the inner code is applied for BATS coding schemes. Second, due to recoding, the raw packet rate may not be the same for different links of a flow, i.e., there is no flow conservation for BATS coding schemes 😭. These differences affect both the objective and the constraints of the utility maximization problem.
Practical congestion control, routing, and media access control algorithms for BATS coding schemes deserve more research efforts 🔬. The rate of transmitting batches can be controlled end-to-end. Due to the recoding operation, however, congestion control cannot be performed only end-to-end 🙈. The number of recoded packets generated for a batch must be controlled at the intermediate nodes, which introduces new research issues for congestion control. A BATS coding scheme is an extension of forward erasure correction coding. See [RFC9265] for more discussion of forward erasure correction coding and congestion control 🦋.
For routing, the BATS coding scheme is flexible for implementing data transmission on multiple paths simultaneously 🛤️. For unicast, it is optimal to transmit all the packets of a batch on the same path between the source node and the destination node. For multicast, network coding gain can be obtained by transmitting packets of the same batch on different paths [Yang17]. Lastly, under the scenario of BATS coding schemes, media access control can have some different considerations: retransmission is not necessary, and a reasonably high packet loss rate can be tolerated 🌈.
4.3. Usage Scenario Considerations 🌊
There are more research issues pertaining to various usage scenarios 🔭. The reliable communication technique provided by BATS codes can be used for a broad range of network communication scenarios. In general, a BATS coding scheme is suitable for data delivery in networks with multiple hops and unreliable links 🧡.
One class of typical usage scenario is wireless mesh and ad hoc networks [Toh02], including vehicular networks, wireless sensor networks, smart lamppost networks, etc. 🚗 These networks are characterized by a large number of network devices connected wirelessly with each other, without a centralized network infrastructure 📡. A BATS coding scheme is suitable for high data load delivery in such networks, without the requirement that point-to-point or one-hop communication is highly reliable. Therefore, employing a BATS coding scheme can provide more freedom for media access control, including power control, and physical-layer design, so that the overall network throughput can be improved 💜.
Another typical usage scenario of BATS coding schemes is underwater acoustic networks [Sprea19] 🐠, where the propagation delay of acoustic waves underwater can be as long as several seconds. Due to the long delay, feedback-based mechanisms become inefficient 🫠. Moreover, point-to-point/one-hop underwater acoustic communication (for both the forward and reverse directions) is highly unreliable. Due to these reasons, the networking techniques developed for radio and wireline networks cannot be directly applied to underwater networks. As a BATS coding scheme does not rely on feedback for reliability communication and can tolerate highly unreliable links, it makes a good candidate for developing data delivery protocols for underwater acoustic networks 🧜♀️.
Last but not least, due to its capability of performing multi-source, multi-destination communications, a BATS coding scheme can be applied in various content distribution scenarios 📦. For example, a BATS coding scheme can be a candidate for the erasure code used in the liquid data networking framework [Byers20] of content-centric networking (CCN), and provides the extra benefit of network coding [Zhang16] 🍓.
5. IANA Considerations 🎀
This document has no IANA actions. 🌸
6. Security Considerations 🚨
Subsuming both random linear network codes (RLNCs) and fountain codes, BATS codes naturally inherit both their desirable security capability of preventing eavesdropping and their vulnerability towards pollution attacks 😬. In this section, we discuss some related research issues 🔍.
6.1. Preventing Eavesdropping 🕵️♀️
Suppose that an eavesdropper obtains a batch where the degree value d is strictly larger than the batch size M. Even if the eavesdropper has all the related encoding information, the system of linear equations related to this batch does not have a unique solution. The probability that the eavesdropper can guess the d source packets used for encoding the batch correctly is 2^(-(d-M)T)<=2^(-T), where T is the number of octets of a source packet (see also [Bhattad07]). When inactivation decoding is applied, we can design the degree distribution DD so that the smallest degree is M+1, and hence prevent the eavesdropper from decoding source packets from individual batches 🙅♀️.
If we allow the eavesdropper to collect multiple batches and use inactivation decoding, the same security holds if the total rank of all the batches collected by the eavesdropper is less than the number of source packets. Therefore, if the DDP can manage to restrict the eavesdropper from collecting a sufficient number of coded packets, the security of the BATS code is effective when T is sufficiently large 💪. Here, by "intrinsic security", we mean the security protection provided by the BATS coding scheme without extra enhancement ✨.
If the eavesdropper can collect a sufficient number of coded packets for correctly decoding, the intrinsic security of the BATS code is ineffective 😱. One solution in this case is to encrypt the whole data before using the BATS code scheme. Better schemes are desired towards reducing the computation cost of the whole data encryption solution. This is a research issue that depends on specific BATS code schemes and will not be further discussed here 🔐.
The threat exists for eavesdropping on the initial encoding process, which takes place at the encoding nodes. In these nodes, the transported data are presented in plain text and can be read along their transfer paths 👀. Hence, information isolation between the encoding process and all other user processes running on the source node MUST be assured.
In addition, the authenticity and trustworthiness of the encoding, recoding, and decoding program running on all the nodes MUST be attested by a trusted authority. Such a measure is also necessary in countering pollution attacks 🛡️.
6.2. Privacy Preservation against Traffic Analysis 🕶️
A security issue closely related to eavesdropping is traffic analysis 🔎. Even when eavesdropping is prevented, tracking the traffic flow patterns can help an attacker know certain information about the communication. Preventing traffic analysis is critical for communications that need to be anonymous 🫥. In [Fan09], an approach based on homomorphic encryption is proposed for network coding to prevent traffic analysis. However, homomorphic encryption could be too computationally expensive for practical applications, and it cannot help with traffic analysis by monitoring the frequency and timing of network traffic 🥵.
The network traffic using network coding does not necessarily satisfy the flow conservation property, and hence, network coding can be used as a tool for defeating traffic analysis 🎭. For example, redundant network traffic can be generated by network coding to make it harder for an attacker to learn the true communication. Moreover, traffic analysis countermeasures can benefit from multipath communication [Yang15], and network coding makes multipath communication more flexible and efficient 🧩. Therefore, using network coding brings new research issues for both traffic analysis and its countermeasure 🏁.
6.3. Countermeasures against Pollution Attacks 🛡️
Okay bestie, BATS codes have a villain problem 💀 Like every network code, they're vulnerable to pollution attacks. A compromised coding node (or several) sneaks forged packets into the network, and then receivers can't recover the transported data correctly. Literally the worst. Even worse, a small number of polluted packets can spread to a huge number of packets through recoding and decoding [Zhao07]. One bad apple, whole basket ruined 🍎
The research community has been obsessed with homomorphic signatures for a long time as a way to spot forged packets and stop these attacks (see [Zhao07], [Yu08], and [Agrawal09]) ✨ The idea is that the source node attaches a signature to each packet it sends, and that signature can be processed by network coding in the same way as the payload. So every intermediate node and the destination node can check the signature on a packet they receive 🔍 The catch? These countermeasures are considered too computationally expensive to use in broadband communications 😭
A system-level approach based on trusted computing [TC-Wikipedia] can be an alternative way to protect BATS codes against pollution attacks 🌈 Trusted computing is a mix of software and hardware technologies that make sure a computer behaves as expected 🖥️ Picture this: suppose all the network nodes use trusted computing. Two nodes first gain trust with each other, then negotiate an authentication method for swapping the coded packets of the BATS coding scheme 🤝 After that, a network node would not use any packets received from other nodes without trust, which is how it dodges the pollution attack 💅
7. References 📚
7.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>.
[RFC8406] Adamson, B., Adjih, C., Bilbao, J., Firoiu, V., Fitzek,
F., Ghanem, S., Lochin, E., Masucci, A., Montpetit, M.,
Pedersen, M., Peralta, G., Roca, V., Ed., Saxena, P., and
S. Sivakumar, "Taxonomy of Coding Techniques for Efficient
Network Communications", RFC 8406, DOI 10.17487/RFC8406,
June 2018, <https://www.rfc-editor.org/info/rfc8406>.
[RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., and E. Baccelli,
"TinyMT32 Pseudorandom Number Generator (PRNG)", RFC 8682,
DOI 10.17487/RFC8682, January 2020,
<https://www.rfc-editor.org/info/rfc8682>.7.2. Informative References 🧚
[Agrawal09]
Agrawal, S. and D. Boneh, "Homomorphic MACs: MAC-Based
Integrity for Network Coding", International Conference on
Applied Cryptography and Network Security,
DOI 10.1007/978-3-642-01957-9_18, May 2009,
<https://doi.org/10.1007/978-3-642-01957-9_18>.
[Bhattad07]
Bhattad, K. and K. Narayanan, "Weakly Secure Network
Coding", April 2005.
[Byers20] Byers, J. and M. Luby, "Liquid Data Networking",
Proceedings of the 7th ACM Conference on Information-
Centric Networking, DOI 10.1145/3405656.3418710, September
2020, <https://doi.org/10.1145/3405656.3418710>.
[Dong20] Dong, Y., Jin, S., Yang, S., and H. Yin, "Network Utility
Maximization for BATS Code Enabled Multihop Wireless
Networks", ICC 2020 - 2020 IEEE International Conference
on Communications (ICC),
DOI 10.1109/ICC40277.2020.9148834, June 2020,
<https://doi.org/10.1109/ICC40277.2020.9148834>.
[Fan09] Yanfei, Y., Yixin, Y., Haojin, H., and X. Sherman, "An
Efficient Privacy-Preserving Scheme against Traffic
Analysis Attacks in Network Coding", IEEE INFOCOM 2009,
DOI 10.1109/INFCOM.2009.5062146, April 2009,
<https://doi.org/10.1109/INFCOM.2009.5062146>.
[Li03] Li, S.-Y., Yeung, R., and N. Cai, "Linear network coding",
IEEE Transactions on Information Theory,
DOI 10.1109/TIT.2002.807285, February 2003,
<https://doi.org/10.1109/TIT.2002.807285>.
[RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T.,
and L. Minder, "RaptorQ Forward Error Correction Scheme
for Object Delivery", RFC 6330, DOI 10.17487/RFC6330,
August 2011, <https://www.rfc-editor.org/info/rfc6330>.
[RFC9265] Kuhn, N., Lochin, E., Michel, F., and M. Welzl, "Forward
Erasure Correction (FEC) Coding and Congestion Control in
Transport", RFC 9265, DOI 10.17487/RFC9265, July 2022,
<https://www.rfc-editor.org/info/rfc9265>.
[Sprea19] Sprea, N., Bashir, M., Truhachev, D., Srinivas, K.,
Schlegel, C., and C. Sacchi, "BATS Coding for Underwater
Acoustic Communication Networks", OCEANS 2019 - Marseille,
DOI 10.1109/OCEANSE.2019.8867299, June 2019,
<https://doi.org/10.1109/OCEANSE.2019.8867299>.
[TC-Wikipedia]
Wikipedia, "Trusted Computing", April 2023,
<https://en.wikipedia.org/w/
index.php?title=Trusted_Computing&oldid=1151565594>.
[Toh02] Toh, C., "Ad Hoc Mobile Wireless Networks", Prentice Hall
Publishers, December 2001.
[Yang14] Yang, S. and R. Yeung, "Batched Sparse Codes", IEEE
Transactions on Information Theory, Vol. 60, Issue 9, pgs.
5322-5346, DOI 10.1109/TIT.2014.2334315, September 2014,
<https://doi.org/10.1109/TIT.2014.2334315>.
[Yang15] Yang, L. and F. Fengjun, "mTor: A multipath Tor routing
beyond bandwidth throttling", 2015 IEEE Conference on
Communications and Network Security (CNS),
DOI 10.1109/CNS.2015.7346860, September 2015,
<https://doi.org/10.1109/CNS.2015.7346860>.
[Yang17] Yang, S. and R. Yeung, "BATS Codes: Theory and Practice",
Morgan & Claypool Publishers, September 2017.
[Yin19] Yin, H., Tang, B., Ng, K., Yang, S., Wang, X., and Q.
Zhou, "A Unified Adaptive Recoding Framework for Batched
Network Coding", 2019 IEEE International Symposium on
Information Theory (ISIT), DOI 10.1109/ISIT.2019.8849277,
July 2019, <https://doi.org/10.1109/ISIT.2019.8849277>.
[Yin20] Yin, H., Yeung, R., and S. Yang, "A Protocol Design
Paradigm for Batched Sparse Codes", Entropy,
DOI 10.3390/e22070790, July 2020,
<https://doi.org/10.3390/e22070790>.
[Yu08] Yu, Z., Wei, Y., Ramkumar, B., and Y. Guan, "An Efficient
Signature-Based Scheme for Securing Network Coding Against
Pollution Attacks", IEEE INFOCOM 2008 - The 27th
Conference on Computer Communications,
DOI 10.1109/INFOCOM.2008.199, April 2008,
<https://doi.org/10.1109/INFOCOM.2008.199>.
[Zhang16] Zhang, G. and Z. Xu, "Combing CCN with network coding: An
architectural perspective", Computer Networks,
DOI 10.1016/j.comnet.2015.11.008, January 2016,
<https://doi.org/10.1016/j.comnet.2015.11.008>.
[Zhao07] Zhao, F., Kalker, T., Medard, M., and K. Han, "Signatures
for content distribution with network coding", 2007 IEEE
International Symposium on Information Theory,
DOI 10.1109/ISIT.2007.4557283, June 2007,
<https://doi.org/10.1109/ISIT.2007.4557283>.Acknowledgments 🫶
Big thank yous go out to the NWCRG chairs, Vincent Roca (our shepherd) and Marie-Jose Montpetit 💖 Also to everyone who left comments, listed in alphabetical order: Emmanuel Lochin, David Oran, and Colin Perkins 🌸
Authors' Addresses 💜
Shenghao Yang
CUHK(SZ) & n-hop technologies
Shenzhen
Guangdong,
China
Phone: +86 755 8427 3827
Email: shyang@cuhk.edu.cn
Xuan Huang
CUHK
Hong Kong
Hong Kong SAR,
China
Phone: +852 3943 8375
Email: 1155136647@link.cuhk.edu.hk
Raymond W. Yeung
CUHK & n-hop technologies
Hong Kong
Hong Kong SAR,
China
Phone: +852 3943 8375
Email: whyeung@ie.cuhk.edu.hk
John K. Zao
CUHK
Hong Kong
Hong Kong SAR,
China
Phone: +852 3943 8346
Email: johnzao@ie.cuhk.edu.hk📦 where this page comes from
- ietf: rfc9426 2023-07
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms