rfc9426.original   rfc9426.txt 
NWCRG S. Yang Internet Research Task Force (IRTF) S. Yang
Internet-Draft CUHK(SZ) Request for Comments: 9426 CUHK(SZ) & n-hop technologies
Intended status: Informational X. Huang Category: Informational X. Huang
Expires: 8 July 2023 R. W. Yeung ISSN: 2070-1721 CUHK
R. Yeung
CUHK & n-hop technologies
J. Zao
CUHK CUHK
J. K. Zao July 2023
NCTU
4 January 2023
BATS Coding Scheme for Multi-hop Data Transport BATched Sparse (BATS) Coding Scheme for Multi-hop Data Transport
draft-irtf-nwcrg-bats-07
Abstract Abstract
Linear network coding can in general improve the network In general, linear network coding can improve the network
communication performance in terms of throughput, latency and communication performance in terms of throughput, latency, and
reliability. BATched Sparse (BATS) code is a class of efficient reliability. BATched Sparse (BATS) code is a class of efficient
linear network coding scheme with a matrix generalization of fountain linear network coding scheme with a matrix generalization of fountain
codes as the outer code, and batch-based linear network coding as the codes as the outer code and batch-based linear network coding as the
inner code. This document describes a baseline BATS coding scheme inner code. This document describes a baseline BATS coding scheme
for communication through multi-hop networks, and discusses the for communication through multi-hop networks and discusses the
related research issues towards a more sophisticated BATS coding related research issues towards a more sophisticated BATS coding
scheme. This document is a product of the Coding for Efficient scheme. This document is a product of the Coding for Efficient
Network Communications Research Group (NWCRG). Network Communications Research Group (NWCRG).
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This document is not an Internet Standards Track specification; it is
provisions of BCP 78 and BCP 79. published for informational purposes.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document is a product of the Internet Research Task Force
and may be updated, replaced, or obsoleted by other documents at any (IRTF). The IRTF publishes the results of Internet-related research
time. It is inappropriate to use Internet-Drafts as reference and development activities. These results might not be suitable for
material or to cite them other than as "work in progress." deployment. This RFC represents the consensus of the Coding for
Efficient Network Communications Research Group of the Internet
Research Task Force (IRTF). Documents approved for publication by
the IRSG are not candidates for any level of Internet Standard; see
Section 2 of RFC 7841.
This Internet-Draft will expire on 8 July 2023. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
https://www.rfc-editor.org/info/rfc9426.
Copyright Notice Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the Copyright (c) 2023 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/ Provisions Relating to IETF Documents
license-info) in effect on the date of publication of this document. (https://trustee.ietf.org/license-info) in effect on the date of
Please review these documents carefully, as they describe your rights publication of this document. Please review these documents
and restrictions with respect to this document. Code Components carefully, as they describe your rights and restrictions with respect
extracted from this document must include Revised BSD License text as to this document.
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction
1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4 1.1. Requirements Language
2. A Use Case of BATS Coding Scheme . . . . . . . . . . . . . . 4 2. A Use Case of the BATS Coding Scheme
2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 5 2.1. Introduction
2.2. Data Delivery Procedures . . . . . . . . . . . . . . . . 6 2.2. DDP Procedures
2.2.1. Source Node Data Partitioning and Padding . . . . . . 6 2.2.1. Source Node Data Partitioning and Padding
2.2.2. Source Node Outer Code Encoding Procedure . . . . . . 7 2.2.2. Source Node Outer Code Encoding Procedure
2.2.3. Recoding Procedures . . . . . . . . . . . . . . . . . 9 2.2.3. Recoding Procedures
2.2.4. Destination Node Procedures . . . . . . . . . . . . . 10 2.2.4. Destination Node Procedures
2.3. Recommendation for the Parameters . . . . . . . . . . . . 11 2.3. Recommendation for the Parameters
2.4. Coding Parameters in DDP Packets . . . . . . . . . . . . 11 2.4. Coding Parameters in DDP Packets
2.4.1. Coding Parameter Format . . . . . . . . . . . . . . . 11 2.4.1. Coding Parameter Format
2.4.2. Coded Packet Format . . . . . . . . . . . . . . . . . 12 2.4.2. Coded Packet Format
3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 13 3. BATS Code Specification
3.1. Common Parts . . . . . . . . . . . . . . . . . . . . . . 13 3.1. Common Parts
3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 14 3.2. Outer Code Encoder
3.3. Inner Code Encoder (Recoder) . . . . . . . . . . . . . . 15 3.3. Inner Code Encoder (Recoder)
3.4. Outer Decoder . . . . . . . . . . . . . . . . . . . . . . 16 3.4. Outer Decoder
4. Research Issues . . . . . . . . . . . . . . . . . . . . . . . 17 4. Research Issues
4.1. Coding Design Issues . . . . . . . . . . . . . . . . . . 17 4.1. Coding Design Issues
4.2. Protocol Design Issues . . . . . . . . . . . . . . . . . 18 4.2. Protocol Design Issues
4.3. Usage Scenario Considerations . . . . . . . . . . . . . . 19 4.3. Usage Scenario Considerations
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 5. IANA Considerations
6. Security Considerations . . . . . . . . . . . . . . . . . . . 20 6. Security Considerations
6.1. Preventing Eavesdropping . . . . . . . . . . . . . . . . 20 6.1. Preventing Eavesdropping
6.2. Privacy-Preserving against Traffic Analysis . . . . . . . 21 6.2. Privacy Preservation against Traffic Analysis
6.3. Countermeasures against Pollution Attacks . . . . . . . . 22 6.3. Countermeasures against Pollution Attacks
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 7. References
7.1. Normative References . . . . . . . . . . . . . . . . . . 22 7.1. Normative References
7.2. Informative References . . . . . . . . . . . . . . . . . 23 7.2. Informative References
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 25 Acknowledgments
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25 Authors' Addresses
1. Introduction 1. Introduction
This document specifies a baseline BATched Sparse (BATS) code This document specifies a baseline BATched Sparse (BATS) code
[Yang14] scheme for data delivery in multi-hop networks, and [Yang14] scheme for data delivery in multi-hop networks and discusses
discusses the related research issues towards a more sophisticated the related research issues towards a more sophisticated scheme. The
scheme. The BATS code described here includes an outer code and an BATS code described here includes an outer code and an inner code.
inner code. The outer code is a matrix generalization of fountain The outer code is a matrix generalization of fountain codes (see also
codes (see also the RapterQ code described in RFC 6330 [RFC6330]), the RaptorQ code described in [RFC6330]), which inherits the
which inherits the advantages of reliability and efficiency and advantages of reliability and efficiency and possesses the extra
possesses the extra desirable property of being network coding desirable property of being compatible with network coding. The
compatible. The inner code, also called recoding, is formed by inner code, also called recoding, is formed by linear network coding
linear network coding for combating packet loss, improving the for combating packet loss, improving the multicast efficiency, etc.
multicast efficiency, etc. A detailed design and analysis of BATS A detailed design and analysis of BATS codes are provided in the BATS
codes are provided in the BATS monograph [Yang17]. monograph [Yang17].
A BATS coding scheme can be applied in multi-hop networks formed by A BATS coding scheme can be applied in multi-hop networks formed by
wireless communication links, which are inherently unreliable due to wireless communication links, which are inherently unreliable due to
interference, fading, multipath, etc. Existing transport protocols interference, fading, multipath, etc. Existing transport protocols
like TCP use end-to-end retransmission, while network protocols such like TCP use end-to-end retransmission, while network protocols such
as IP might enable store-and-forward at the relays, so that packet as IP might enable store-and-forward at the relays so that packet
loss would accumulate along the way. loss would accumulate along the way.
A BATS coding scheme can be used for various data delivery A BATS coding scheme can be used for various data delivery
applications like file transmission, video streaming over wireless applications, like file transmission, video streaming over wireless
multi-hop networks, etc. Different from traditional forward error multi-hop networks, etc. Different from the forward error correction
correcting (FEC) schemes that are applied either hop-by-hop or end- (FEC) schemes that are applied either hop-by-hop or end-to-end, the
to-end, the BATS coding scheme combines the end-to-end coding (the BATS coding scheme combines the end-to-end coding (the outer code)
outer code) with certain hop-by-hop coding (the inner code), and with certain hop-by-hop coding (the inner code) and hence can
hence can potentially achieve better performance. potentially achieve better performance.
The baseline coding scheme described here considers a network with The baseline coding scheme described here considers a network with
multiple communication flows. For each flow, the source node encodes multiple communication flows. For each flow, the source node encodes
the data for transmission separately. Inside the network, however, the data for transmission separately. However, inside the network,
it is possible to mix the packets from different flows for recoding. it is possible to mix the packets from different flows for recoding.
In this document, we describe a simple case where recoding is In this document, we describe a simple case where recoding is
performed within each flow. Note that the same encoding/decoding performed within each flow. Note that the same encoding/decoding
scheme described here can be used with different recoding schemes as scheme described here can be used with different recoding schemes as
long as they follow the principle as we illustrate in this document. long as they follow the principle we illustrate in this document.
In this document, we focus on the case that each flow has only one In this document, we focus on the case that each flow has only one
destination node. Communicating the same data to multiple destination node. Communicating the same data to multiple
destination nodes is called multicast. Refer to Section 4 for the destination nodes is called multicast. Refer to Section 4 for the
further discussion of multicast. further discussion of multicast.
The purpose of the baseline BATS coding scheme is twofold. First, it The purpose of the baseline BATS coding scheme is twofold. First, it
provides researchers and engineers a starting point for developing provides researchers and engineers a starting point for developing
network communication applications/protocols based on BATS codes. network communication applications/protocols based on BATS codes.
Second, it helps to make the research issues clearer towards a Second, it helps to make the research issues clearer towards a
sophisticated BATS code based network protocol. Important research sophisticated network protocol based on BATS codes. Important
directions include the security issues, congestion control and research directions include the security issues, congestion control,
routing algorithms for BATS codes, etc. routing algorithms for BATS codes, etc.
This document is a product of and represents the collaborative work This document is a product of and represents the collaborative work
and consensus of the Coding for Efficient Network Communications and consensus of the Coding for Efficient Network Communications
Research Group (NWCRG). It is not an IETF product and is not an IETF Research Group (NWCRG). It is not an IETF product and is not an IETF
standard. standard.
1.1. Requirements Language 1.1. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
document are to be interpreted as described in RFC 2119 [RFC2119]. "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 BATS Coding Scheme 2. A Use Case of the BATS Coding Scheme
The BATS coding scheme described in this document can be used, for The BATS coding scheme described in this document can be used, for
example, by a Data Delivery Protocol (DDP). Though this document is example, by a Data Delivery Protocol (DDP). Though this document is
not about a DDP, we briefly illustrate in this section how a BATS not about a DDP, in this section, we briefly illustrate how a BATS
coding scheme is employed by a DDP to make the role of the coding coding scheme is employed by a DDP to make the role of the coding
scheme clear. Some terms that will be used in this section are scheme clear. Some terms that will be used in this section are
summarized here: summarized here:
* DDP: data delivery protocol. DDP: Data Delivery Protocol
* DDP packet: the packet formed by a DDP employing a BATS coding DDP packet: the packet formed by a DDP employing a BATS coding
scheme. scheme
* source packet: the packet formed by the data for delivery. source packet: the packet formed by the data for delivery
* outer encoder: the outer code encoder of a BATS code. outer encoder: the outer code encoder of a BATS code
* recoder: the inner 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. outer decoder: the outer code decoder of a BATS code
* coded packet: the packet generated by the outer code encoder or a coded packet: the packet generated by the outer code encoder or a
recoder. recoder
* batch: a set of coded packets generated by a BATS coding scheme batch: a set of coded packets generated by a BATS coding scheme from
from the same subset of the source packets. the same subset of the source packets
* recoded packet: a coded packet generated by a recoder. recoded packet: a coded packet generated by a recoder
* degree: the number of source packets used to generate a batch by degree: the number of source packets used to generate a batch by the
the outer encoder. The degree can be different for different outer encoder. (The degree can be different for a different
batch. batch.)
Other common terms can be found in RFC 8406 [RFC8406]. Other common terms can be found in [RFC8406].
2.1. Introduction 2.1. Introduction
We describe a data delivery process that involves one source node, We describe a DDP that involves one source node, one destination
one destination node, and multiple intermediate nodes in between. A node, and multiple intermediate nodes in between. A BATS coding
BATS coding scheme includes an outer code encoder (also called outer scheme includes an outer code encoder (also called outer encoder), an
encoder), an inner code encoder (also called recoder), and an outer inner code encoder (also called recoder), and an outer decoder that
decoder which decodes the outer code and the inner code jointly as decodes the outer code and the inner code jointly, as illustrated in
illustrated in Figure 1. The functions of the outer encoder, recoder Figure 1. The functions of the outer encoder, recoder, and outer
and outer decoder are described below: decoder are described below:
| |
| {set of source packets} | {set of source packets}
v v
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| outer encoder | | outer encoder |
| v | source node | v | source node
| recoder | | recoder |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| |
| {set of DDP packets} | {set of DDP packets}
v v
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| | | |
| recoder | intermediate node | recoder | intermediate node
| | | |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| |
| {set of DDP packets} | {set of DDP packets}
v v
... ...
| |
| {set of DDP packets} | {set of DDP packets}
v v
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| | | |
| outer decoder | destination node | outer decoder | destination node
| | | |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
| |
| {set of source packets} | {set of source packets}
v v
Figure 1: A network model for data delivery. Figure 1: A Network Model for Data Delivery
At the source node, the DDP first processes the data to be delivered At the source node, the DDP first processes the data to be delivered
into a number of source packets each of the same number of bits (see into a number of source packets, each of the same number of bits (see
details in Section 2.2.1), and then provides all the source packets details in Section 2.2.1), and then provides all the source packets
to the outer encoder. The outer encoder will further generate a to the outer encoder. The outer encoder will further generate a
sequence of batches, each consisting of a fixed number of coded sequence of batches, each consisting of a fixed number of coded
packets (see the description in Section 2.2.2). packets (see the description in Section 2.2.2).
Each batch generated at the source node is further processed by the Each batch generated at the source node is further processed by the
recoder separately. The recoder may generate a number of new coded recoder separately. The recoder may generate a number of new coded
packets using the existing coded packets of the batch (see the packets using the existing coded packets of the batch (see the
description in Section 2.2.3). After processed by the recoder, the description in Section 2.2.3). After it is processed by the recoder,
DDP forms and transmits the DDP packets using the coded packets, The DDP forms and transmits the DDP packets using the coded packets,
together with the corresponding batch information. together with the corresponding batch information.
We assume that a DDP packet is either correctly received or We assume that a DDP packet is either correctly received or
completely erased during the communication. The DDP extracts the completely erased during the communication. The DDP extracts the
coded packets and the corresponding batch information from its coded packets and the corresponding batch information from its
received DDP packets. A recoder is employed at an intermediate node received DDP packets. A recoder is employed at an intermediate node
that does not need the data, and generates recoded packets for each that does not need the data and generates recoded packets for each
batch (see the description in Section 2.2.3). The DDP forms and batch (see the description in Section 2.2.3). The DDP forms and
transmits DDP packets using the recoded packets and the corresponding transmits DDP packets using the recoded packets and the corresponding
batch information. batch information.
The outer decoder is employed at the destination node that needs the The outer decoder is employed at the destination node that needs the
data. The DDP extracts the coded packets and the corresponding batch data. The DDP extracts the coded packets and the corresponding batch
information from its received DDP packets. The outer decoder tries information from its received DDP packets. The outer decoder tries
to recover the transmitted data using the received batches (see the to recover the transmitted data using the received batches (see the
description in Section 2.2.4). The DDP sends the decoded data to the description in Section 2.2.4). The DDP sends the decoded data to the
application that needs the data. application that needs the data.
2.2. Data Delivery Procedures 2.2. DDP Procedures
Suppose that the DDP has F octets of data for transmission. We Suppose that the DDP has F octets of data for transmission. We
describe the procedures of one BATS session for transmitting the F describe the procedures of one BATS session for transmitting the F
octets. There is a limit on F of a single BATS session. If the octets. There is a limit on F of a single BATS session. If the
total data has more than the limit, the data needs to be transmitted total data has more than the limit, the data needs to be transmitted
using multiple BATS sessions. The limit on F of a single BATS using multiple BATS sessions. The limit on F of a single BATS
session depends on the coding parameters to be discussed in this session depends on the coding parameters that are discussed in this
section, and will be calculated at the end of Section 2.4.2. section and the calculations described at the end of Section 2.4.2.
2.2.1. Source Node Data Partitioning and Padding 2.2.1. Source Node Data Partitioning and Padding
The DDP first determines the following parameters: The DDP first determines the following parameters:
* Batch size (M): the number of coded packets in a batch generated * batch size (M): the number of coded packets in a batch generated
by the outer encoder. by the outer encoder
* Recoding field size (q): the number of elements in the finite * recoding field size (q): the number of elements in the finite
field for recoding. q is 2 or 2^8 field for recoding, i.e., q is 2 or 2^8
* BATS payload size (TO): the number of payload octets in a BATS * BATS payload size (TO): the number of payload octets in a BATS
packet, including the coded data and the coefficient vector. packet, including the coded data and the coefficient vector
Based on the above parameters, the parameters T, CO and K are Based on the above parameters, the parameters T, CO, and K are
calculated as follows: calculated as follows:
* CO: the number of octets of a coefficient vector, calculated as CO * CO: the number of octets of a coefficient vector, calculated as CO
= ceil(M*log2(q)/8), which is also called the coefficient vector = ceil(M * log2(q) / 8), which is also called the coefficient
overhead. vector overhead
* T: the number of data octets of a coded packet, calculated as T = * T: the number of data octets of a coded packet, calculated as T =
TO - CO. TO - CO
* K: number of source packets, calculated as K = floor(F/T)+1. * K: number of source packets, calculated as K = floor(F / T) + 1
The data MUST be padded to have T*K octets, which will be partitioned The data MUST be padded to have T*K octets, which will be partitioned
into K source packets b[0], ..., b[K-1], each of T octets. In our into K source packets b[0], ..., b[K - 1], each of T octets. In our
padding scheme, b[0], ..., b[K-2] are filled with data octets, and padding scheme, b[0], ..., b[K - 2] are filled with data octets, and
b[K-1] is filled with the remaining data octets and padding octets. b[K - 1] is filled with the remaining data octets and padding octets.
Let P = K*T-F denote the number of padding octets. We use b[K-1, 0], Let P = K * T - F denote the number of padding octets. We use b[K -
..., b[K-1, T-P-1] to denote the T-P source octets and b[K-1, T-P], 1, 0], ..., b[K - 1, T - P - 1] to denote the T - P source octets and
..., b[K-1, T-1] to denote the P padding octets in b[K-1], b[K - 1, T - P], ..., b[K - 1, T - 1] to denote the P padding octets
respectively. The padding insertion process is shown in Figure 2. in b[K - 1], respectively. The padding insertion process is shown in
Figure 2.
Z = T - P Z = T - P
j = 1 j = 1
v = 1 v = 1
Let bl be the last source packet b[K-1] Let bl be the last source packet b[K - 1]
for i = Z, Z+1, ..., T-1 do for i = Z, Z + 1, ..., T - 1 do
bl[i] = j bl[i] = j
if i+1 >= v+Z do if i + 1 >= v + Z do
j += 1 j += 1
v += j v += j
Figure 2: Data Padding Insertion Process Figure 2: Data Padding Insertion Process
2.2.2. Source Node Outer Code Encoding Procedure 2.2.2. Source Node Outer Code Encoding Procedure
The DDP provides the BATS encoder with the following information: The DDP provides the BATS encoder with the following information:
* Batch size (M): the number of coded packets in a batch. * batch size (M): the number of coded packets in a batch
* Recoding field size (q): the number of elements in the finite * recoding field size (q): the number of elements in the finite
field for recoding. field for recoding
* Maximum degree (MAX_DEG): a positive integer that specifies the * maximum degree (MAX_DEG): a positive integer that specifies the
largest degree can be used. largest degree can be used
* Degree distribution (DD): an unsigned integer array of size * degree distribution (DD): an unsigned integer array of size
MAX_DEG+1. The i-th entry DD[i] is the probability that i is 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. chosen as the degree, where i is between 0 and MAX_DEG.
* A sequence of batch IDs (BID) (j, j = 0, 1, ...). * a sequence of batch IDs (BIDs) (j, j = 0, 1, ...)
* Number of source packets (K). * number of source packets (K)
* Packet size (T): the number of octets in a source packet. * packet size (T): the number of octets in a source packet
* Source packets (b[i], i = 0, 1, ..., K-1). * source packets (b[i], i = 0, 1, ..., K - 1)
Using this information, the outer encoder generates M coded packets Using this information, the outer encoder generates M coded packets
for each batch ID using the following steps to be described in for each BID using the following steps that are described in detail
details at Section 3.2: in Section 3.2:
* Obtain a degree d by sampling DD. Roughly, the value d is chosen * Obtain a degree d by sampling DD. Roughly, the value d is chosen
with probability DD[d]. with probability DD[d].
* Choose d source packets uniformly at random from all the K source * Choose d source packets uniformly at random from all the K source
packets. It is allowed that a source packet is used by mutiple packets. It is allowed that a source packet is used by multiple
batches. batches.
* Generate M coded packets using the d source packets. * Generate M coded packets using the d source packets.
The DDP receives from the outer encoder a sequence of batches, where From the outer encoder, the DDP receives a sequence of batches, where
the batch with ID j has the batch with ID j has M coded packets (x[j,i], i =0, 1, ..., M -
1), each containing TO octets.
* M coded packets (x[j,i], i =0, 1, ..., M-1), each containing TO
octets.
The DDP will use the batches to form DDP packets to be transmitted to The DDP will use the batches to form DDP packets to be transmitted to
other network nodes towards the destination nodes. The DDP MUST other network nodes towards the destination nodes. The DDP MUST
deliver with each coded packet with its batch ID, which will be deliver each coded packet with its batch ID, which will be further
further used by both recoder and decoder. used by both the recoder and decoder.
The DDP MUST deliver some of the information used by the encoder to The DDP MUST deliver some of the information used by the encoder to
each recoder and the decoder, either embedded in the DDP packets or each of the recoders and the decoder, either embedded in the DDP
transmitted using separated protocol messages: For recoders, the DDP packets or transmitted using separated protocol messages. For
MUST deliver the following information to each recoder: recoders, the DDP MUST deliver the following information to each
recoder:
* M: batch size * M: batch size
* q: recoding field size. * q: recoding field size
For the decoder, the DDP MUST deliver the following information to For the decoder, the DDP MUST deliver the following information to
the decoder: the decoder:
* M: batch size * M: batch size
* q: recoding field size * q: recoding field size
* K: the number of source packets * K: the number of source packets
* T: the number of octets in a source packet * T: the number of octets in a source packet
* DD: the degree distribution. * DD: the degree distribution
The BID is used by both recoders and decoders. We will illustrate in The BID is used by both recoders and decoders. In Section 2.4, we
Section 2.4 that how to embed BID, M, q, and K into DDP packets. The illustrate how to embed BID, M, q, and K into DDP packets. The
degree distribution DD does not need to be changed frequently. See degree distribution DD does not need to be changed frequently. See
Section 6 in [Yang17] about how to design a good degree distribution. Section 6 of [Yang17] about how to design a good degree distribution.
Once designed, the degree distribution can be shared between the Once designed, the degree distribution can be shared between the
source node and the destination node by the DDP, which is not further source node and the destination node by the DDP, which is not further
discussed here. discussed here.
2.2.3. Recoding Procedures 2.2.3. Recoding Procedures
Both the source node and the intermediate nodes perform recoding on Both the source node and the intermediate nodes perform recoding on
the batches before transmission. At the source node, the recoder the batches before transmission. At the source node, the recoder
receives the batches from the outer code encoding procedure. At an receives the batches from the outer code encoding procedure. At an
intermediate node, the DDP receives the DDP packets from the other intermediate node, the DDP receives the DDP packets from the other
network nodes. If the DDP choose not to recode, it just forwards the network nodes. If the DDP chooses not to recode, it just forwards
DDP packets it received. Otherwise, the DDP should be able to the DDP packets it received. Otherwise, the DDP should be able to
extract coded packets and the corresponding batch information from extract coded packets and the corresponding batch information from
these packets. these packets.
For a received batch, the DDP determines a positive integer Mr, the For a received batch, the DDP determines a positive integer (Mr) and
number of recoded packets to be transmitted for the batch, and the number of recoded packets to be transmitted for the batch, and
provides the recoder with the following information: DDP provides the recoder with the following information:
* the batch size M, * M: batch size
* the recoding field size q, * q: recoding field size
* a number of received coded packets of the same batch, each * a number of received coded packets of the same batch, each
containing TO octets, and containing TO octets
* the number of recoded packets to be generated (Mr). * Mr: the number of recoded packets to be generated
The recoder uses the information provided by the DDP to generate Mr The recoder uses the information provided by the DDP to generate Mr
recoded packets, each containing TO octets, to be described in recoded packets, each containing TO octets, which are described in
Section 3.3. The DDP uses the Mr recoded packets to form the DDP Section 3.3. The DDP uses the Mr recoded packets to form the DDP
packets for transmitting. packets for transmitting.
2.2.4. Destination Node Procedures 2.2.4. Destination Node Procedures
At the destination node, the DDP receives DDP packets from an At the destination node, the DDP receives DDP packets from an
intermediate network node, and should be able to extract coded intermediate network node and should be able to extract coded packets
packets and the corresponding batch information from these packets. and the corresponding batch information from these packets. The DDP
The DDP then employs an outer decoder to recover the data transmitted then employs an outer decoder to recover the data transmitted by the
by the source node. source node.
The DDP provides the outer decoder (to be described in Section 3.4) The DDP provides the outer decoder (to be described in Section 3.4)
with the following information: with the following information:
* M: batch size, * M: batch size
* q: recoding field size, * q: recoding field size
* K: the number of source packets * K: the number of source packets
* T: the number of octets of a source packet * T: the number of octets of a source packet
* A sequence of batches, each of which is formed by a number of * a sequence of batches, each of which is formed by a number of
coded packets belonging to the same batch, with their coded packets belonging to the same batch, with their
corresponding BIDs. corresponding BIDs
The decoder uses this information to decode the outer code and the The decoder uses this information to decode the outer code and the
inner code jointly and recover the K source packets (see details in inner code jointly and recover the K source packets (see details in
Section 3.4). If successful, the decoder returns the recovered K Section 3.4). If successful, the decoder returns the recovered K
source packets to the DDP, which will use the K source packets to source packets to the DDP, which will use the K source packets to
form the F octets data. The recommended padding deletion process is form the F octets data. The recommended padding deletion process is
shown as follows: shown as follows:
// this procedure returns the number P of padding octets // this procedure returns the number P of padding octets
// at the end of b[K-1] // at the end of b[K - 1]
Let bl be the last decoded source packet b[K-1] Let bl be the last decoded source packet b[K - 1]
PL = bl[T-1] PL = bl[T - 1]
if PL == 1 do if PL == 1 do
return P = 1 return P = 1
WI = T - 1 WI = T - 1
while bl[WI] == PL do while bl[WI] == PL do
WI = WI - 1 WI = WI - 1
return P = (1 + bl[WI]) * bl[WI] + T - WI - 1 return P = (1 + bl[WI]) * bl[WI] + T - WI - 1
Figure 3: Data Padding Deletion Process Figure 3: Data Padding Deletion Process
2.3. Recommendation for the Parameters 2.3. Recommendation for the Parameters
The recommendation for the parameters M and q is shown as follows: The recommendation for the parameters M and q is shown as follows:
* When q=2, M=16,32,64,128 * when q = 2, M = 16, 32, 64, 128
* When q=256, M=4,8,16,32 * when q = 256, M = 4, 8, 16, 32
It is RECOMMENDED that K is at least 128. The encoder/decoder SHALL It is RECOMMENDED that K is at least 128. The encoder/decoder SHALL
support an arbitrary positive integer value less than 2^16. However, support an arbitrary positive integer value less than 2^16. However,
the BATS coding scheme to be described is not optimized for small K. the BATS coding scheme to be described is not optimized for small K.
2.4. Coding Parameters in DDP Packets 2.4. Coding Parameters in DDP Packets
Here we provide an example of embedding the aforementioned BATS Here, we provide an example of embedding the aforementioned BATS
coding parameters into the DDP packets which will be used for coding parameters into the DDP packets that will be used for recoding
recoding and decoding. A DDP can form a DDP packet using a coded and decoding. A DDP can form a DDP packet using a coded packet by
packet by adding necessary information that can help to deliver the adding necessary information that can help to deliver the DDP packet
DPP packet to the next node, e.g., the DDP protocol version, to the next node (e.g., the version of the DDP, addresses, and
addresses and session identifiers. We will not go into the details session identifiers). We will not go into the details of formatting
of formatting these fields in a DDP packet, but focus on how to these fields in a DDP packet, but we focus on how to format the
format the coding parameters and the coded packet in a DDP packet. coding parameters and the coded packet in a DDP packet.
2.4.1. Coding Parameter Format 2.4.1. Coding Parameter Format
Here we provide an example of using 32 bits (4 octets) to embed the Here, we provide an example of using 32 bits (4 octets) to embed the
parameters K, M, q, and BID. The 32 bits are separated into three parameters K, M, q, and BID. The 32 bits are separated into three
subfields, denoted as K, Mq and BID, respectively, as illustrated in subfields, denoted as K, Mq, and BID, respectively, as illustrated in
Figure 4. Figure 4.
0 1 2 3 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 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 | | K | Mq | BID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: Coding parameter field format. Figure 4: Coding Parameter Field Format
* K: 16-bit unsigned integer, specifying the number of source K: 16-bit unsigned integer, specifying the number of source packets
packets of the BATS session. of the BATS session
* Mq: 3-bit unsigned integer to specify the value of M and q as Mq: 3-bit unsigned integer, specifying the value of M and q, as
Table 1. shown in Table 1
* BID: 13-bit unsigned integer, specifying the batch ID of the batch BID: 13-bit unsigned integer, specifying the batch ID of the batch
the packet belongs to. the packet belongs to
+=====+=====+=====+ +=====+=====+=====+
| Mq | M | q | | Mq | M | q |
+=====+=====+=====+ +=====+=====+=====+
| 000 | 16 | 2 | | 000 | 16 | 2 |
+-----+-----+-----+ +-----+-----+-----+
| 010 | 32 | 2 | | 010 | 32 | 2 |
+-----+-----+-----+ +-----+-----+-----+
| 100 | 64 | 2 | | 100 | 64 | 2 |
+-----+-----+-----+ +-----+-----+-----+
| 110 | 128 | 2 | | 110 | 128 | 2 |
+-----+-----+-----+ +-----+-----+-----+
| 001 | 4 | 256 | | 001 | 4 | 256 |
+-----+-----+-----+ +-----+-----+-----+
| 011 | 8 | 256 | | 011 | 8 | 256 |
+-----+-----+-----+ +-----+-----+-----+
| 101 | 16 | 256 | | 101 | 16 | 256 |
+-----+-----+-----+ +-----+-----+-----+
| 111 | 32 | 256 | | 111 | 32 | 256 |
+-----+-----+-----+ +-----+-----+-----+
Table 1: Values of Mq Table 1: Values of the
field Mq Field
The choice of the coding parameters depends on the computation cost, The choice of the coding parameters depends on the computation cost,
the network conditions and the expected end-to-end coding the network conditions, and the expected end-to-end coding
performance. Usually, a larger batch size M will have a better performance. Usually, a larger batch size M will have a better
coding performance, but higher computation cost for encoding, coding performance but higher computation cost for encoding,
recoding and decoding. The field size q affects the coefficient recoding, and decoding. The field size q affects the coefficient
vector overhead, and also the computation cost for recoding. Within vector overhead and also the computation cost for recoding. Within a
a BATS session, the BID field should be different for all batches, BATS session, the BID field should be different for all batches, and
and hence the maximum number of batches can be generated for the hence, the maximum number of batches that can be generated for the
outer encoder is 2^13. For different BATS sessions, batches can use outer encoder is 2^13. For different BATS sessions, batches can use
the same BID. the same BID.
2.4.2. Coded Packet Format 2.4.2. Coded Packet Format
CO T CO T
+-----------------------+-------------------------------+ +-----------------------+-------------------------------+
| coefficient vector | coded data | | coefficient vector | coded data |
+-----------------------+-------------------------------+ +-----------------------+-------------------------------+
Figure 5: Code packet format in a DDP packet. Figure 5: Code Packet Format in a DDP Packet
A coded packet has TO=T+CO octets, where the first CO octets contain A coded packet has TO=T+CO octets, where the first CO octets contain
the coefficient vector and the remaining T octets contain the coded the coefficient vector and the remaining T octets contain the coded
data. data.
* coefficient vector: CO = M*log2(q)/8 octets. For the values of M coefficient vector: CO = M * log2(q) / 8 octets. For the values of
and q in Table 1, CO is at most 32 octets when q is 256 and 6 M and q in Table 1, CO is at most 32 octets when q is 256 and 6
octets when q is 2. octets when q is 2.
* coded data: T octets. T should be chosen so that the whole DDP coded data: T octets. T should be chosen so that the whole DDP
packet is at most PMTU. packet is at most Path MTU (PMTU).
Using the above formation, we can calculate the largest file size F Using the above formation, we can calculate the largest file size (F)
for different parameters. For example, when q=2 and M=128, we have for different parameters. For example, when q = 2 and M = 128, we
CO = 6 octets. Counting the 4 octets for embedding the coding have CO = 6 octets. Counting the 4 octets for embedding the coding
parameters, we can choose T = PMTU-H-10, where H is the header length parameters, we can choose T = PMTU - H - 10, where H is the header
of a DDP packet. As K can be at most 2^16-1, F can be at most (PMTU- length of a DDP packet. As K can be at most 2^16 - 1, F can be at
H-10)(2^16-1) octets. In this case, K/M is about 2^9 and the BID most (PMTU - H - 10)(2^16 - 1) octets. In this case, K / M is about
field allows transmitting 2^4*K/M batches. 2^9 and the BID field allows transmitting 2^4 * K / M batches.
3. BATS Code Specification 3. BATS Code Specification
3.1. Common Parts 3.1. Common Parts
The T octets of a source packets are treated as a column vector of T The T octets of a source packet are treated as a column vector of T
elements in GF(256). The CO octets of coefficient vector are treated elements in GF(256). The CO octets of a coefficient vector are
as a column vector of CO elements in GF(q), where q=2 or q=256. treated as a column vector of CO elements in GF(q), where q = 2 or
Linear algebra and matrix operations over finite fields are assumed q = 256. Linear algebra and matrix operations over finite fields are
in this section. assumed in this section.
For the two elements of GF(2), their multiplication corresponds to a For the two elements of GF(2), their multiplication corresponds to a
logical AND operation and their addition is a logical XOR operation. logical AND operation, and their addition is a logical XOR operation.
An element of the field GF(256) can be represented by a polynomial An element of the field GF(256) can be represented by a polynomial
with binary coefficients and degree lower or equal to 7. The with binary coefficients and degree lower or equal to 7. The
addition between two elements of GF(256) is defined as the addition addition between two elements of GF(256) is defined as the addition
of the two binary polynomials. The multiplication between two of the two binary polynomials. The multiplication between two
elements of GF(256) is the multiplication of the two binary elements of GF(256) is the multiplication of the two binary
polynomials modulo a certain irreducible polynomial of degree 8, polynomials modulo a certain irreducible polynomial of degree 8,
called a primitive polynomial. One example of such a primitive called a primitive polynomial. One example of such a primitive
polynomial for GF(256) is: polynomial for GF(256) is:
x^8 + x^4 + x^3 + x^2 + 1 x^8 + x^4 + x^3 + x^2 + 1
A common primitive polynomial MUST be specified for all the finite A common primitive polynomial MUST be specified for all the finite
field multiplications over GF(256). Note that a binary polynomial of field multiplications over GF(256). Note that a binary polynomial of
degree less than 8 can be represented by a binary sequence of 8 bits, degree less than 8 can be represented by a binary sequence of 8 bits,
i.e., an octet. i.e., an octet.
Suppose that a pseudorandom number generator Rand() which generates Suppose that a pseudorandom number generator, Rand(), which generates
an unsigned integer of 32 bits is shared by both encoding and an unsigned integer of 32 bits, is shared by both encoding and
decoding. The pseudorandom generator can be initialized by decoding. The pseudorandom generator can be initialized by
Rand_Init(S) with seed S. When S is not provided, the pseudorandom Rand_Init(S) with seed S. When S is not provided, the pseudorandom
generator is initialized arbitrarily. One example of such a generator is initialized arbitrarily. One example of such a
pseudorandom generator is defined in RFC 8682 [RFC8682]. pseudorandom generator is defined in [RFC8682].
A function called BatchSampler is used in both encoding and decoding. A function called BatchSampler is used in both encoding and decoding.
The function takes two integers j and d as input, and generates an The function takes two integers, j and d, as input and generates an
array idx of d integers and a d x M matrix G. The function first array idx of d integers and a d x M matrix G. The function first
initializes the pseudorandom generator with j, sample d distinct initializes the pseudorandom generator with j, sample d distinct
integers from 0 to K-1 as idx, and sample d*M integers from 0 to 255 integers from 0 to K-1 as idx, and sample d*M integers from 0 to 255
as G. See the pseudocode in Figure 6. as G. See the pseudocode in Figure 6.
function BatchSampler(j,d) function BatchSampler(j, d)
// initialize the pseudorandom generator by seed j. // initialize the pseudorandom generator by seed j.
Rand_Init(j) Rand_Init(j)
// sample d distinct integers between 0 and K-1. // sample d distinct integers between 0 and K - 1.
for k = 0, ..., d-1 do for k = 0, ..., d - 1 do
r = Rand() % K r = Rand() % K
while r already exists in idx do while r already exists in idx do
r = Rand() % K r = Rand() % K
idx[k] = r idx[k] = r
// sample d x M matrix // sample d x M matrix
for r = 0, ..., d-1 do for r = 0, ..., d - 1 do
for c = 0,...,M-1 do for c = 0, ..., M - 1 do
G[r,c] = Rand() % 256 G[r, c] = Rand() % 256
return idx, G return idx, G
Figure 6: Batch Sampler Function Figure 6: Batch Sampler Function
3.2. Outer Code Encoder 3.2. Outer Code Encoder
Define a function called DegreeSampler that returns an integer d Define a function called DegreeSampler that returns an integer d
using the degree distribution DD. We expect that the empirical using the degree distribution DD. We expect that the empirical
distribution of the returning d converges to DD(d) when d < K. One distribution of the returning d converges to DD(d) when d < K. One
design of DegreeSampler is illustrated in Figure 7. Note that when K design of DegreeSampler is illustrated in Figure 7. Note that when K
< MAX_DEG, the degree value returned by DegreeSampler does not < MAX_DEG, the degree value returned by DegreeSampler does not
exactly follow the distribution DD, which however would not affect exactly follow the distribution DD, which however would not affect
the practical decoding performance for the outer decoder to be the practical decoding performance for the outer decoder to be
described in Section 3.4. described in Section 3.4.
function DegreeSampler(j, DD) function DegreeSampler(j, DD)
Let CDF be an array Let CDF be an array
CDF[0] = 0 CDF[0] = 0
for i = 1, ..., MAX_DEG do for i = 1, ..., MAX_DEG do
CDF[i] = CDF[i-1] + DD[i] CDF[i] = CDF[i - 1] + DD[i]
Rand_Init(j) Rand_Init(j)
r = Rand() % CDF[MAX_DEG] r = Rand() % CDF[MAX_DEG]
for d = 1, ..., MAX_DEG do for d = 1, ..., MAX_DEG do
if r >= CDF[d] do if r >= CDF[d] do
return min(d,K) return min(d, K)
return min(MAX_DEG,K) return min(MAX_DEG, K)
Figure 7: Degree Sampler Function. Figure 7: Degree Sampler Function
Let b[0], b[1], ..., b[K-1] be the K source packets. A batch with Let b[0], b[1], ..., b[K-1] be the K source packets. A batch with
BID j is generated using the following steps. BID j is generated using the following steps.
* Obtain a degree d by calling DegreeSampler with input j. * Obtain a degree d by calling DegreeSampler with input j.
* Obtain idx and G[j] by calling BatchSampler with input j and d. * Obtain 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]]). Form the * Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d - 1]]). Form the
batch X[j] = B[j]*G[j], whose dimension is T x M. 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 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 form the M x M identity matrix I with entries in GF(q) and the
last T rows of Xr[j] is X[j]. last T rows of Xr[j] is X[j].
See the pseudocode of the batch generating process in Figure 8. See the pseudocode of the batch generating process in Figure 8.
function GenBatch(j) function GenBatch(j)
d = DegreeSampler(j) d = DegreeSampler(j)
(idx, G) = BatchSampler(j,d) (idx, G) = BatchSampler(j, d)
B = (b[idx[0]], b[idx[i]], ..., b[idx[d-1]]) B = (b[idx[0]], b[idx[i]], ..., b[idx[d - 1]])
X = B * G X = B * G
Xr = [I; X] Xr = [I; X]
return Xr return Xr
Figure 8: Batch Generation Function. Figure 8: Batch Generation Function
3.3. Inner Code Encoder (Recoder) 3.3. Inner Code Encoder (Recoder)
In general, the inner code of a BATS code comprises (random) linear In general, the inner code of a BATS code comprises (random) linear
network coding applied on the coded packets belonging to the same network coding applied on the coded packets belonging to the same
batch. The recoded packets have the same BID. Suppose that coded batch. The recoded packets have the same BID. Suppose that coded
packets xr[i], i = 0, 1, ..., r-1, which have the same BID j, have packets xr[i], i = 0, 1, ..., r - 1, which have the same BID j, have
been received at an intermediate node, and Mr recoded packets are been received at an intermediate node and Mr recoded packets are
supposed to be generated. Following traditional random linear supposed to be generated. Following random linear network coding, a
network coding, a recoded packet can be generated by random linear recoded packet can be generated by a random linear combination:
combination: (randomly) choose a sequence of coefficients c[i], i = (randomly) choose a sequence of coefficients c[i], i = 0, 1, ..., r -
0, 1, ..., r-1 from GF(q), and generate 1 from GF(q) and generate c[0]xr[0] + c[1]xr[1] + ... + c[r - 1]xr[r
c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] as a recoded packet. This - 1] as a recoded packet. This recoding approach, called random
recoding approach, called random linear recoding, achieves good linear recoding, achieves good network coding performance for
network coding performance for multicast when the batch size is multicast when the batch size is sufficiently large.
sufficiently large.
For unicast communications in a single path as illustrated in For unicast communications in a single path, as illustrated in
Figure 1, it is not necessary to generate all the Mr recoded packets Figure 1, it is not necessary to generate all the Mr recoded packets
using random linear combination. Instead, xr[i], i = 0, 1, ..., r-1, using a random linear combination. Instead, xr[i], i = 0, 1, ..., r
are directly used as recoded packets, and max(Mr-r,0) recoded packets - 1 are directly used as recoded packets, and max(Mr - r, 0) recoded
are generated using linear combinations. Compared with random linear packets are generated using linear combinations. Compared with
recoding, this recoding approach, called systematic recoding, can random linear recoding, this recoding approach, called systematic
reduce both the computation cost and also the recoding latency that recoding, can reduce both the computation cost and the recoding
accumulates linearly with the number of nodes. Note that the use of latency that accumulates linearly with the number of nodes. Note
systematic recoding may not always achieve the optimal network coding that the use of systematic recoding may not always achieve the
performance as random linear recoding in more complicated optimal network coding performance as random linear recoding in more
communication scenarios that include multiple paths and multiple complicated communication scenarios that include multiple paths and
destination nodes. multiple destination nodes.
3.4. Outer Decoder 3.4. Outer Decoder
The decoder receives a sequence of batches Yr[j], j = 0, 1, ..., n-1, The decoder receives a sequence of batches, Yr[j], j = 0, 1, ..., n -
each of which is a TO-row matrix over GF(256). Let Y[j] be the 1, each of which 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 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 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] GF(256) formed by embedding each bit in the first M/8 rows of Yr[j]
into GF(256). For successful decoding, we require that the total into GF(256). For successful decoding, we require that the total
rank of all the batches is at least K. rank of all the batches is at least K.
The same degree distribution DD used for the outer encoder is The same degree distribution DD used for the outer encoder is
supposed to be known by the outer decoder. By calling DegreeSampler supposed to be known by the outer decoder. By calling DegreeSampler
and BatchSampler with input j, we obtain d[j], idx[j] and G[j]. and BatchSampler with input j, we obtain d[j], idx[j], and G[j].
According to the encoding and recoding processes described in According to the encoding and recoding processes described in
Section 3.2 and Section 3.3, we have the system of linear equations Sections 3.2 and 3.3, we have the system of linear equations Y[j] =
Y[j] = B[j]G[j]H[j] for each received batch with ID j, where B[j] = B[j]G[j]H[j] for each received batch with ID j, where B[j] =
(b[idx[j,0]], b[idx[j,1]], ..., b[idx[j,d-1]]) is unknown. (b[idx[j, 0]], b[idx[j, 1]], ..., b[idx[j, d - 1]]) is unknown.
We first describe a belief propagation (BP) decoder that can We first describe a belief propagation (BP) decoder that can
efficiently solve the source packets when a sufficient number of efficiently solve the source packets when a sufficient number of
batches have been received. A batch j is said to be decodable if batches have been received. A batch j is said to be decodable if
rank(G[j]H[j]) = d[j] (i.e., the system of linear equations Y[j] = rank(G[j]H[j]) = d[j] (i.e., the system of linear equations Y[j] =
B[j]G[j]H[j] with B[j] as the variable matrix has a unique solution). B[j]G[j]H[j] with B[j] as the variable matrix has a unique solution).
The BP decoding algorithm has multiple iterations. Each iteration is The BP decoding algorithm has multiple iterations. Each iteration is
formed by the following steps: formed by the following steps:
* Decoding step: Find a batch j that is decodable. Solve the * 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 corresponding system of linear equations Y[j] = B[j]G[j]H[j] and
decode B[j]. decode B[j].
* Substitution step: Substitute the decoded source packets into * Substitution Step: Substitute the decoded source packets into
undecodable batches. Suppose that a decoded source packet b[k] is undecodable batches. Suppose that a decoded source packet b[k] is
used in generating an undecodable Y[j]. The substitution involves used in generating an undecodable Y[j]. The substitution involves
1) removing the entry in idx[j] corresponding to k, 2) removing 1) removing the entry in idx[j] corresponding to k, 2) removing
the row in G[j] corresponding to b[k], and 3) reducing d[j] by 1. the row in G[j] corresponding to b[k], and 3) reducing d[j] by 1.
The BP decoder repeats the above steps until no batches are decodable The BP decoder repeats the above steps until no batches are decodable
during the decoding step. during the decoding step.
When the degree distribution DD in the outer code encoder (see When the degree distribution DD in the outer code encoder (see
Section 3.2) is properly designed, the BP decoder guarantees a high Section 3.2) is properly designed, the BP decoder guarantees a high
probability for the recovery of a given fraction of the source probability for the recovery of a given fraction of the source
packets when K is large. To recover all the source packets, a packets when K is large. To recover all the source packets, a
precode can be applied to the source packets to generate a fraction precode can be applied to the source packets to generate a fraction
of redundant packets before applying the outer code encoding. of redundant packets before applying the outer code encoding.
Moreover, when the BP decoder stops which may happen with a high Moreover, when the BP decoder stops, which may happen with a high
probability when K is relatively small, it is possible to continue probability when K is relatively small, it is possible to continue
with inactivation decoding, where certain source packets are treated with inactivation decoding, where certain source packets are treated
inactive so that a similar belief propagation process can be resumed. as inactive so that a similar belief propagation process can be
The reader is referred to RFC 6330 [RFC6330] for the design of a resumed. The reader is referred to [RFC6330] for the design of a
precode with a good inactivation decoding performance. precode with a good inactivation decoding performance.
4. Research Issues 4. Research Issues
The baseline BATS coding scheme described in Section 2 and Section 3 The baseline BATS coding scheme described in Sections 2 and 3 needs
needs various refinement and complement towards becoming a more various refinements and complements towards becoming a more
sophisticated network communication application. Various related sophisticated network communication application. Various related
research issues are discussed in this section, but the security research issues are discussed in this section, but the security-
related issues are left to Section 6. related issues are left to Section 6.
4.1. Coding Design Issues 4.1. Coding Design Issues
When the number of batches is sufficiently large, the BATS code When the number of batches is sufficiently large, the BATS code
specification in Section 3 has nearly optimal performance in the specification in Section 3 has nearly optimal performance in the
sense that the decoding can be successful with a high probability sense that the decoding can be successful with a high probability
when the total rank of all the batches used for decoding is just when the total rank of all the batches used for decoding is just
slightly larger than the number of source packet K. But when K is slightly larger than the number of source packet K. But when K is
small, the degree sampler function in Figure 7 and the BatchSampler small, the DegreeSampler function in Figure 7 and the BatchSampler
function in Figure 6 based on a pseudorandom generator may not sample function in Figure 6 based on a pseudorandom generator may not sample
all the source packets evenly, so that some of the source packets are all the source packets evenly so that some of the source packets are
not well protected. One approach to solve this issue is to generate not well protected. One approach to solve this issue is to generate
a deterministic degree sequence when the number of batches is a deterministic degree sequence when the number of batches is
relatively small, and design a special pseudorandom generator that relatively small and design a special pseudorandom generator that has
has a good sampling performance when K is small. a good sampling performance when K is small.
There are research issues related to recoding discussed in There are research issues related to recoding discussed in
Section 3.3. One question is how many recoded packets to generate Section 3.3. One question is how many recoded packets to generate
for each batch. Though it is asymptotically optimal when using the for each batch. Though it is asymptotically optimal when using the
same number of recoded packets for all batches, it has been shown same number of recoded packets for all batches, it has been shown
that transmitting a different number of recoded packets for different that transmitting a different number of recoded packets for different
batches can improve the recoding efficiency. The intuition is that batches can improve the recoding efficiency. For a batch with a
for a batch with a lower rank, a smaller number of recoded packets lower rank, the intuition is that a smaller number of recoded packets
need to be transmitted. This kind of recoding scheme is called need to be transmitted. This kind of recoding scheme is called
adaptive recoding [Yin19]. adaptive recoding [Yin19].
Packet loss in network communication is usually bursty, which may Packet loss in network communication is usually bursty, which may
harm the recoding performance. One way to resolve this issue is to harm the recoding performance. One way to resolve this issue is to
transmit the packets of different batches in a mixed order, which is transmit the packets of different batches in a mixed order, which is
also called batch interleaving [Yin20]. How to efficiently also called batch interleaving [Yin20]. How to efficiently
interleave batches without increasing end-to-end latency too much is interleave batches without increasing end-to-end latency too much is
a research issue. a research issue.
Though we only focus on the BATS coding scheme with one source node Though we only focus on the BATS coding scheme with one source node
and one destination node, a BATS coding scheme can be used for and one destination node, a BATS coding scheme can be used for
multiple source and destination nodes. To benefit from multiple multiple source and destination nodes. To benefit from multiple
source nodes, we would need different source nodes to generate source nodes, we would need different source nodes to generate
statistically independent batches. It is well-known that linear statistically independent batches. It is well-known that linear
network coding [Li03] achieves the multicast capacity. BATS codes network coding [Li03] achieves the multicast capacity. BATS codes
can benefit from network coding due to its inner code. For can benefit from network coding due to its inner code. For
multicast, each destination node performs independently the same multicast, each destination node independently performs the same
operations as described in this document, but the inner code should operations as described in this document, but the inner code should
be improved to taking multiple destination node into consideration. be improved to take multiple destination nodes into consideration.
How to efficiently implement multicast needs further research. How to efficiently implement multicast needs further research.
4.2. Protocol Design Issues 4.2. Protocol Design Issues
The baseline scheme in this document focuses on reliable The baseline scheme in this document focuses on reliable
communication. There are other issues to be considered towards communication. There are other issues to be considered towards
designing a fully functional DDP based on a BATS coding scheme. Here designing a fully functional DDP based on a BATS coding scheme.
we discuss some network management issues that are closely related to Here, we discuss some network management issues that are closely
a BATS coding scheme: routing, congestion control and media access related to a BATS coding scheme: routing, congestion control, and
control. media access control.
The outer code of a BATS code can be regarded as a channel code for The outer code of a BATS code can be regarded as a channel code for
the channel induced by the inner code, and hence the network the channel induced by the inner code, and hence, the network
management algorithms should try to maximize the capacity of the management algorithms should try to maximize the capacity of the
channel induced by the inner code. A network utility maximization channel induced by the inner code. A network utility maximization
problem [Dong20] for BATS coding can be applied to study routing, problem [Dong20] for BATS coding can be applied to study routing,
congestion control and media access control jointly. Compared with congestion control, and media access control jointly. Compared with
the network utility maximization for Internet, there are two major the network utility maximization for the Internet, there are two
differences. First, the network flow rate is not measured by the major differences. First, the network flow rate is not measured by
rate of the raw packets. Instead, a rank based measurement induced the rate of the raw packets. Instead, a rank-based measurement
by the inner code is applied for BATS coding schemes. Second, due to induced by the inner code is applied for BATS coding schemes.
recoding, the raw packet rate may not be the same for different links Second, due to recoding, the raw packet rate may not be the same for
of a flow, i.e., no flow conservation for BATS coding schemes. These different links of a flow, i.e., no flow conservation for BATS coding
differences affect both the objective and the constraints of the schemes. These differences affect both the objective and the
utility maximization problem. constraints of the utility maximization problem.
Practical congestion control, routing and media access control Practical congestion control, routing, and media access control
algorithms for BATS coding schemes deserve more research efforts. algorithms for BATS coding schemes deserve more research efforts.
The rate of transmitting batches can be controlled end-to-end. Due The rate of transmitting batches can be controlled end-to-end. Due
to the recoding operation, however, congestion control cannot be only to the recoding operation, however, congestion control cannot be only
performed end-to-end. The number of recoded packets generated for a performed end-to-end. The number of recoded packets generated for a
batch must be controlled at the intermediate nodes, which introduces batch must be controlled at the intermediate nodes, which introduces
new research issues for congestion control. A BATS coding scheme is new research issues for congestion control. A BATS coding scheme is
an extension of forward erasure correction coding. See RFC 9265 an extension of forward erasure correction coding. See [RFC9265] for
[RFC9265] for more discussion of forward erasure correction coding more discussion of forward erasure correction coding and congestion
and congestion control. control.
For routing, the BATS coding scheme is flexible for implementing data For routing, the BATS coding scheme is flexible for implementing data
transmission on multiple paths simultaneously. For unicast, it is transmission on multiple paths simultaneously. For unicast, it is
optimal to transmit all the packets of a batch on the same path optimal to transmit all the packets of a batch on the same path
between the source node and the destination node, and for multicast, between the source node and the destination node, and for multicast,
network coding gain can be obtained by transmitting packets of the network coding gain can be obtained by transmitting packets of the
same batch on different paths [Yang17]. Last, under the scenario of same batch on different paths [Yang17]. Lastly, under the scenario
BATS coding schemes, media access control can have some different of BATS coding schemes, media access control can have some different
considerations: Retransmission is not necessary, and a reasonably considerations: Retransmission is not necessary, and a reasonably
high packet loss rate can be tolerated. high packet loss rate can be tolerated.
4.3. Usage Scenario Considerations 4.3. Usage Scenario Considerations
There are more research issues pertaining to various usage scenarios. There are more research issues pertaining to various usage scenarios.
The reliable communication technique provided by BATS codes can be The reliable communication technique provided by BATS codes can be
used for a broad range of network communication scenarios. In used for a broad range of network communication scenarios. In
general, a BATS coding scheme is suitable for data delivery in general, a BATS coding scheme is suitable for data delivery in
networks with multiple hops and unreliable links. networks with multiple hops and unreliable links.
One class of typical usage scenario is wireless mesh and ad hoc One class of typical usage scenario is wireless mesh and ad hoc
networks [Toh02], including vehicular networks, wireless sensor networks [Toh02], including vehicular networks, wireless sensor
networks, smart lamppost networks, etc. These networks are networks, smart lamppost networks, etc. These networks are
characterized by a large number of network devices connected characterized by a large number of network devices connected
wirelessly with each other without a centralized network wirelessly with each other without a centralized network
infrastructure. A BATS coding scheme is suitable for high data load infrastructure. A BATS coding scheme is suitable for high data load
delivery in such networks without the requirement that the point-to- delivery in such networks without the requirement that the point-to-
point/one-hop communication is highly reliable. Therefore, employing point or one-hop communication is highly reliable. Therefore,
a BATS coding scheme can provide more freedom for media access employing a BATS coding scheme can provide more freedom for media
control, including power control, and physical-layer design so that access control, including power control, and physical-layer design so
the overall network throughput can be improved. that the overall network throughput can be improved.
Another typical usage scenario of BATS coding schemes is underwater Another typical usage scenario of BATS coding schemes is underwater
acoustic networks [Sprea19], where the propagation delay of acoustic acoustic networks [Sprea19], where the propagation delay of acoustic
waves in underwater can be as long as several seconds. Due to the waves underwater can be as long as several seconds. Due to the long
long delay, feedback based mechanisms become inefficient. Moreover, delay, feedback-based mechanisms become inefficient. Moreover,
point-to-point/one-hop underwater acoustic communication (for both point-to-point/one-hop underwater acoustic communication (for both
the forward and reverse directions) is highly unreliable. Due to the forward and reverse directions) is highly unreliable. Due to
these reasons, traditional networking techniques developed for radio these reasons, the networking techniques developed for radio and
and wireline networks cannot be directly applied to underwater wireline networks cannot be directly applied to underwater networks.
networks. As a BATS coding scheme does not rely on the feedback for As a BATS coding scheme does not rely on the feedback for reliability
reliability communication and can tolerate highly unreliable links, communication and can tolerate highly unreliable links, it makes a
it makes a good candidate for developing data delivery protocols for good candidate for developing data delivery protocols for underwater
underwater acoustic networks. acoustic networks.
Last but not least, due to its capability of performing multi-source Last but not least, due to its capability of performing multi-source,
multi-destination communications, a BATS coding scheme can be applied multi-destination communications, a BATS coding scheme can be applied
in various content distribution scenarios. For example, a BATS in various content distribution scenarios. For example, a BATS
coding scheme can be a candidate for the erasure code used in the coding scheme can be a candidate for the erasure code used in the
liquid data networking framework [Byers20] of CCN (content centric liquid data networking framework [Byers20] of content-centric
networking), and provides the extra benefit of network coding networking (CCN) and provides the extra benefit of network coding
[Zhang16]. [Zhang16].
5. IANA Considerations 5. IANA Considerations
This memo includes no request to IANA. This document has no IANA actions.
6. Security Considerations 6. Security Considerations
Subsuming both random linear network codes (RLNC) and fountain codes, Subsuming both random linear network codes (RLNCs) and fountain
BATS codes naturally inherit both their desirable security capability codes, BATS codes naturally inherit both their desirable security
of preventing eavesdropping, as well as their vulnerability towards capability of preventing eavesdropping as well as their vulnerability
pollution attacks. In this section, we discuss some related research towards pollution attacks. In this section, we discuss some related
issues. research issues.
6.1. Preventing Eavesdropping 6.1. Preventing Eavesdropping
Suppose that an eavesdropper obtains a batch where the degree value d Suppose that an eavesdropper obtains a batch where the degree value d
is strictly larger than the batch size M. Even if the eavesdropper is strictly larger than the batch size M. Even if the eavesdropper
has all the related encoding information, the system of linear has all the related encoding information, the system of linear
equations related to this batch does not have a unique solution, and equations related to this batch does not have a unique solution, and
the probability that the eavesdropper can guess the d source packets 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 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]). is the number of octets of a source packet (see also [Bhattad07]).
When inactivation decoding is applied, we can design the degree When inactivation decoding is applied, we can design the degree
distribution DD so that the smallest degree is M+1, and hence prevent distribution DD so that the smallest degree is M+1 and hence prevent
the eavesdropper from decoding source packets from individual the eavesdropper from decoding source packets from individual
batches. batches.
If we allow the eavesdropper to collect multiple batches and use If we allow the eavesdropper to collect multiple batches and use
inactivation decoding, the same security holds if the total rank of inactivation decoding, the same security holds if the total rank of
all the batches collected by the eavesdropper is less than the number all the batches collected by the eavesdropper is less than the number
of source packet. Therefore, if the DDP can manage to restrict the of source packet. Therefore, if the DDP can manage to restrict the
eavesdropper from collecting a sufficient number of coded packets, eavesdropper from collecting a sufficient number of coded packets,
the native security of BATS code is effective when T is sufficiently the security of BATS code is effective when T is sufficiently large.
large. Here by native security, we mean the security protection Here, by "intrinsic security", we mean the security protection
provided by the BATS coding scheme without extra enhancement. provided by the BATS coding scheme without extra enhancement.
If the eavesdropper can collect a sufficient number of coded packets If the eavesdropper can collect a sufficient number of coded packets
for correctly decoding, the native security of BATS code is for correctly decoding, the intrinsic security of BATS code is
ineffective. One solution in this case is to encrypt the whole data ineffective. One solution in this case is to encrypt the whole data
before using the BATS code scheme. Better schemes are desired before using the BATS code scheme. Better schemes are desired
towards reducing the computation cost of the whole data encryption towards reducing the computation cost of the whole data encryption
solution. This is a research issue that depends on specific BATS solution. This is a research issue that depends on specific BATS
code schemes, and will not be further discussed here. code schemes and will not be further discussed here.
The threat exists for eavesdropping on the initial encoding process, The threat exists for eavesdropping on the initial encoding process,
which takes place at the encoding nodes. In these nodes, the which takes place at the encoding nodes. In these nodes, the
transported data are presented in plain text and can be read along transported data are presented in plain text and can be read along
their transfer paths. Hence, information isolation between the their transfer paths. Hence, information isolation between the
encoding process and all other user processes running on the source encoding process and all other user processes running on the source
node MUST be assured. node MUST be assured.
In addition, the authenticity and trustworthiness of the encoding, In addition, the authenticity and trustworthiness of the encoding,
recoding and decoding program running on all the nodes MUST be recoding, and decoding program running on all the nodes MUST be
attested by a trusted authority. Such a measure is also necessary in attested by a trusted authority. Such a measure is also necessary in
countering pollution attacks. countering pollution attacks.
6.2. Privacy-Preserving against Traffic Analysis 6.2. Privacy Preservation against Traffic Analysis
A security issue closely related to eavesdropping is traffic A security issue closely related to eavesdropping is traffic
analysis. Even when eavesdropping is prevented, tracking the traffic analysis. Even when eavesdropping is prevented, tracking the traffic
flow patterns can help an attacker to know a certain information flow patterns can help an attacker to know certain information about
about the communication. Preventing traffic analysis is critical for the communication. Preventing traffic analysis is critical for
communications that need to be anonymous. In [Fan09], a homomorphic communications that need to be anonymous. In [Fan09], an approach
encryption based approach is proposed for network coding to prevent based on homomorphic encryption is proposed for network coding to
traffic analysis. However, homomorphic encryption could be too prevent traffic analysis. However, homomorphic encryption could be
computationally expensive for practical applications and cannot help too computationally expensive for practical applications and cannot
with the traffic analysis by monitoring the frequency and timing of help with the traffic analysis by monitoring the frequency and timing
network traffic. of network traffic.
The network traffic using network coding does not necessarily satisfy The network traffic using network coding does not necessarily satisfy
the flow conservation property, and hence network coding can be used the flow conservation property, and hence, network coding can be used
as a tool for defeating traffic analysis. For example, redundant as a tool for defeating traffic analysis. For example, redundant
network traffic can be generated by network coding to make it harder network traffic can be generated by network coding to make it harder
for an attacker to learn the true communication. Moreover, traffic for an attacker to learn the true communication. Moreover, traffic
analysis countermeasures can benefit from multipath communication analysis countermeasures can benefit from multipath communication
[Yang15], and network coding makes multipath communication more
[Yang15], and network coding makes multiple-path communication more
flexible and efficient. Therefore, using network coding brings new flexible and efficient. Therefore, using network coding brings new
research issues for both traffic analysis and its countermeasure. research issues for both traffic analysis and its countermeasure.
6.3. Countermeasures against Pollution Attacks 6.3. Countermeasures against Pollution Attacks
Like all network codes, BATS codes are vulnerable to pollution Like all network codes, BATS codes are vulnerable to pollution
attacks. In these attacks, one or more compromised coding node(s) attacks. In these attacks, one or more compromised coding node(s)
can pollute the coded messages by injecting forged packets into the can pollute the coded messages by injecting forged packets into the
network and thus prevent the receivers from recovering the network and thus prevent the receivers from recovering the
transported data correctly. Moreover, a small number of polluted transported data correctly. Moreover, a small number of polluted
packets can infect a large number of packets by recoding and decoding packets can infect a large number of packets by recoding and decoding
[Zhao07]. [Zhao07].
The research community has long been investigating the use of The research community has long been investigating the use of
homomorphic signatures to identify the forged packets and stall the homomorphic signatures to identify the forged packets and stall the
attacks (see [Zhao07], [Yu08], [Agrawal09]). In these schemes, the attacks (see [Zhao07], [Yu08], and [Agrawal09]). In these schemes,
source node attaches a signature to each packet to transmit, and the the source node attaches a signature to each packet to transmit, and
signature is allowed to be processed by network coding same as the the signature is allowed to be processed by network coding in the
payload. All the intermediate nodes and the destination node can same way as the payload. All the intermediate nodes and the
verify the signature attached to a received packet. However, these destination node can verify the signature attached to a received
countermeasures are regarded as being too computationally expensive packet. However, these countermeasures are regarded as being too
to be employed in broadband communications. computationally expensive to be employed in broadband communications.
A system-level approach based on trusted computing [TC-Wikipedia] can A system-level approach based on trusted computing [TC-Wikipedia] can
provide an alternative to protect BATS codes against pollution provide an alternative to protect BATS codes against pollution
attacks. Trusted computing consists of software and hardware attacks. Trusted computing consists of software and hardware
technologies so that a computer behaves as expected. Suppose that technologies so that a computer behaves as expected. Suppose that
all the network nodes employ trusted computing. Two nodes will first all the network nodes employ trusted computing. Two nodes will first
gain trust with each other, and then negotiate an authentication gain trust with each other and then negotiate an authentication
method for exchanging the coded packets of the BATS coding scheme. A method for exchanging the coded packets of the BATS coding scheme. A
network node would not use any packets received from other nodes network node would not use any packets received from other nodes
without trust to avoid the pollution attack. without trust to avoid the pollution attack.
7. References 7. References
7.1. Normative References 7.1. Normative References
[RFC2119] Bradner, S. and RFC Publisher, "Key words for use in RFCs [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
to Indicate Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <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, [RFC8406] Adamson, B., Adjih, C., Bilbao, J., Firoiu, V., Fitzek,
F., Ghanem, S., Lochin, E., Masucci, A., Montpetit, M., F., Ghanem, S., Lochin, E., Masucci, A., Montpetit, M.,
Pedersen, M., Peralta, G., Roca, V., Ed., Saxena, P., Pedersen, M., Peralta, G., Roca, V., Ed., Saxena, P., and
Sivakumar, S., and RFC Publisher, "Taxonomy of Coding S. Sivakumar, "Taxonomy of Coding Techniques for Efficient
Techniques for Efficient Network Communications", Network Communications", RFC 8406, DOI 10.17487/RFC8406,
RFC 8406, DOI 10.17487/RFC8406, June 2018, June 2018, <https://www.rfc-editor.org/info/rfc8406>.
<https://www.rfc-editor.org/info/rfc8406>.
[RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., Baccelli, E., and [RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., and E. Baccelli,
RFC Publisher, "TinyMT32 Pseudorandom Number Generator "TinyMT32 Pseudorandom Number Generator (PRNG)", RFC 8682,
(PRNG)", RFC 8682, DOI 10.17487/RFC8682, January 2020, DOI 10.17487/RFC8682, January 2020,
<https://www.rfc-editor.org/info/rfc8682>. <https://www.rfc-editor.org/info/rfc8682>.
7.2. Informative References 7.2. Informative References
[Agrawal09] [Agrawal09]
Agrawal, S. and D. Boneh, "Homomorphic MACs: MAC-based Agrawal, S. and D. Boneh, "Homomorphic MACs: MAC-Based
integrity for network coding", International Conference on Integrity for Network Coding", International Conference on
Applied Cryptography and Network Security , 2009. 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] [Bhattad07]
Bhattad, K. and K.R. Narayanan, "An efficient privacy- Bhattad, K. and K. Narayanan, "Weakly Secure Network
preserving scheme against traffic analysis attacks in Coding", April 2005.
network coding", ISIT , 2007.
[Byers20] Byers, J.W. and M. Luby, "Liquid Data Networking", ICN , [Byers20] Byers, J. and M. Luby, "Liquid Data Networking",
2020. 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.H.F. Yin, "Network [Dong20] Dong, Y., Jin, S., Yang, S., and H. Yin, "Network Utility
Utility Maximization for BATS Code enabled Multihop Maximization for BATS Code Enabled Multihop Wireless
Wireless Networks", ICC , 2020. 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, "Weakly [Fan09] Yanfei, Y., Yixin, Y., Haojin, H., and X. Sherman, "An
Secure Network Coding", INFOCOM , 2009. 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.R., Yeung, R.W., and N. Cai, "Linear Network [Li03] Li, S.-Y., Yeung, R., and N. Cai, "Linear network coding",
Coding", IEEE Transactions on Information Theory , 2003. 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., [RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T.,
Minder, L., and RFC Publisher, "RaptorQ Forward Error and L. Minder, "RaptorQ Forward Error Correction Scheme
Correction Scheme for Object Delivery", RFC 6330, for Object Delivery", RFC 6330, DOI 10.17487/RFC6330,
DOI 10.17487/RFC6330, August 2011, August 2011, <https://www.rfc-editor.org/info/rfc6330>.
<https://www.rfc-editor.org/info/rfc6330>.
[RFC9265] Kuhn, N., Lochin, E., Michel, F., Welzl, M., and RFC [RFC9265] Kuhn, N., Lochin, E., Michel, F., and M. Welzl, "Forward
Publisher, "Forward Erasure Correction (FEC) Coding and Erasure Correction (FEC) Coding and Congestion Control in
Congestion Control in Transport", RFC 9265, Transport", RFC 9265, DOI 10.17487/RFC9265, July 2022,
DOI 10.17487/RFC9265, July 2022,
<https://www.rfc-editor.org/info/rfc9265>. <https://www.rfc-editor.org/info/rfc9265>.
[Sprea19] Sprea, N., Bashir, M., Truhachev, D., Srinivas, K.V., [Sprea19] Sprea, N., Bashir, M., Truhachev, D., Srinivas, K.,
Schlegel, C., and C. Claudio Sacchi, "BATS Coding for Schlegel, C., and C. Sacchi, "BATS Coding for Underwater
Underwater Acoustic Communication Networks", OCEANS , Acoustic Communication Networks", OCEANS 2019 - Marseille,
2019. DOI 10.1109/OCEANSE.2019.8867299, June 2019,
<https://doi.org/10.1109/OCEANSE.2019.8867299>.
[TC-Wikipedia] [TC-Wikipedia]
"Trusted Computing", Wikipedia, "Trusted Computing", April 2023,
Wikipedia https://en.wikipedia.org/wiki/Trusted_Computing. <https://en.wikipedia.org/w/
index.php?title=Trusted_Computing&oldid=1151565594>.
[Toh02] Toh, C.K., "Ad Hoc Mobile Wireless Networks", Prentice [Toh02] Toh, C., "Ad Hoc Mobile Wireless Networks", Prentice Hall
Hall Publishers , 2002. Publishers, December 2001.
[Yang14] Yang, S. and R.W. Yeung, "Batched Sparse Codes", IEEE [Yang14] Yang, S. and R. Yeung, "Batched Sparse Codes", IEEE
Transactions on Information Theory 60(9), 5322-5346, 2014. 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 [Yang15] Yang, L. and F. Fengjun, "mTor: A multipath Tor routing
beyond bandwidth throttling", NCS , 2015. 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.W. Yeung, "BATS Codes: Theory and [Yang17] Yang, S. and R. Yeung, "BATS Codes: Theory and Practice",
Practice", Morgan & Claypool Publishers , 2017. Morgan & Claypool Publishers, September 2017.
[Yin19] Yin, H.H.F., Tang, B., Ng, K.H., Yang, S., Wang, X., and [Yin19] Yin, H., Tang, B., Ng, K., Yang, S., Wang, X., and Q.
Q. Zhou, "A Unified Adaptive Recoding Framework for Zhou, "A Unified Adaptive Recoding Framework for Batched
Batched Network Coding", ISIT , 2019. 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.H.F., Yeung, R.W., and S. Yang, "A Protocol Design [Yin20] Yin, H., Yeung, R., and S. Yang, "A Protocol Design
Paradigm for Batched Sparse Codes", Entroy , 2020. 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 [Yu08] Yu, Z., Wei, Y., Ramkumar, B., and Y. Guan, "An Efficient
Signature-Based Scheme for Securing Network Coding Against Signature-Based Scheme for Securing Network Coding Against
Pollution Attacks", INFOCOM , 2008. 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 [Zhang16] Zhang, G. and Z. Xu, "Combing CCN with network coding: An
architectural perspective", Computer Networks , 2016. 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.J. Han, [Zhao07] Zhao, F., Kalker, T., Medard, M., and K. Han, "Signatures
"Signatures for content distribution with network coding", for content distribution with network coding", 2007 IEEE
ISIT , 2007. International Symposium on Information Theory,
DOI 10.1109/ISIT.2007.4557283, June 2007,
<https://doi.org/10.1109/ISIT.2007.4557283>.
Acknowledgments Acknowledgments
The authors would like to thank the NWCRG chairs, Vincent Roca (our The authors would like to thank the NWCRG chairs, Vincent Roca (our
shepherd) and Marie-Jose Montpetit; and all those who provided shepherd) and Marie-Jose Montpetit, as well as all those who provided
comments -- namely (in alphabetical order), Emmanuel Lochin, David comments, namely (in alphabetical order), Emmanuel Lochin, David
Oran, and Colin Perkins. Oran, and Colin Perkins.
Authors' Addresses Authors' Addresses
Shenghao Yang Shenghao Yang
CUHK(SZ) CUHK(SZ) & n-hop technologies
Shenzhen Shenzhen
Guangdong, Guangdong,
China China
Phone: +86 755 8427 3827 Phone: +86 755 8427 3827
Email: shyang@cuhk.edu.cn Email: shyang@cuhk.edu.cn
Xuan Huang Xuan Huang
CUHK CUHK
Hong Kong Hong Kong
Hong Kong SAR, Hong Kong SAR,
China China
Phone: +852 3943 8375 Phone: +852 3943 8375
Email: 1155136647@link.cuhk.edu.hk Email: 1155136647@link.cuhk.edu.hk
Raymond W. Yeung Raymond W. Yeung
CUHK CUHK & n-hop technologies
Hong Kong Hong Kong
Hong Kong SAR, Hong Kong SAR,
China China
Phone: +852 3943 8375 Phone: +852 3943 8375
Email: whyeung@ie.cuhk.edu.hk Email: whyeung@ie.cuhk.edu.hk
John K. Zao John K. Zao
NCTU CUHK
Hsinchu Hong Kong
Taiwan, Hong Kong SAR,
China China
Email: jkzao@ieee.org Phone: +852 3943 8346
Email: johnzao@ie.cuhk.edu.hk
 End of changes. 182 change blocks. 
483 lines changed or deleted 512 lines changed or added

This html diff was produced by rfcdiff 1.48.