< draft-irtf-nwcrg-bats-01.txt   draft-irtf-nwcrg-bats-02.txt >
NWCRG S. Yang NWCRG S. Yang
Internet-Draft CUHK(SZ) Internet-Draft CUHK(SZ)
Intended status: Informational X. Huang Intended status: Informational X. Huang
Expires: 29 January 2022 R. W. Yeung Expires: 4 June 2022 R. W. Yeung
CUHK CUHK
J. K. Zao J. K. Zao
NCTU NCTU
28 July 2021 1 December 2021
BATS Coding Scheme for Multi-hop Data Transport BATS Coding Scheme for Multi-hop Data Transport
draft-irtf-nwcrg-bats-01 draft-irtf-nwcrg-bats-02
Abstract Abstract
BATS code is a class of efficient linear network coding scheme with a BATS code is a class of efficient linear network coding scheme with a
matrix generalization of fountain codes as the outer code, and batch- matrix generalization of fountain codes as the outer code, and batch-
based linear network coding as the inner code. This document based linear network coding as the inner code. This document
describes a baseline BATS coding scheme for communication through describes a baseline BATS coding scheme for communication through
multi-hop networks, and discusses the related research issues towards multi-hop networks, and discusses the related research issues towards
a more sophisticated BATS coding scheme. This document is a product a more sophisticated BATS coding scheme. This document is a product
of the Coding for Efficient Network Communications Research Group of the Coding for Efficient Network Communications Research Group
skipping to change at page 1, line 41 skipping to change at page 1, line 41
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on 29 January 2022. This Internet-Draft will expire on 4 June 2022.
Copyright Notice Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the Copyright (c) 2021 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 (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document. license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components and restrictions with respect to this document. Code Components
extracted from this document must include Simplified BSD License text extracted from this document must include Revised BSD License text as
as described in Section 4.e of the Trust Legal Provisions and are described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Simplified BSD License. provided without warranty as described in the Revised BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4
1.2. Terminology and Definitions . . . . . . . . . . . . . . . 4
2. A Use Case of BATS Coding Scheme . . . . . . . . . . . . . . 4 2. A Use Case of BATS Coding Scheme . . . . . . . . . . . . . . 4
2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 4 2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 5
2.2. Data Delivery Procedures . . . . . . . . . . . . . . . . 6 2.2. Data Delivery Procedures . . . . . . . . . . . . . . . . 6
2.2.1. Source Node Data Partitioning and Padding . . . . . . 6 2.2.1. Source Node Data Partitioning and Padding . . . . . . 6
2.2.2. Source Node Outer Code Encoding Procedure . . . . . . 7 2.2.2. Source Node Outer Code Encoding Procedure . . . . . . 7
2.2.3. Recoding Procedures . . . . . . . . . . . . . . . . . 8 2.2.3. Recoding Procedures . . . . . . . . . . . . . . . . . 9
2.2.4. Destination Node Procedures . . . . . . . . . . . . . 9 2.2.4. Destination Node Procedures . . . . . . . . . . . . . 9
2.3. Recommendation for the Parameters . . . . . . . . . . . . 10 2.3. Recommendation for the Parameters . . . . . . . . . . . . 10
2.4. Example DDP Packet Format . . . . . . . . . . . . . . . . 10 2.4. Coding Parameters in DDP Packets . . . . . . . . . . . . 11
2.4.1. Packet Header . . . . . . . . . . . . . . . . . . . . 10 2.4.1. Coding Parameter Format . . . . . . . . . . . . . . . 11
2.4.2. Packet Payload . . . . . . . . . . . . . . . . . . . 11 2.4.2. Coded Packet Format . . . . . . . . . . . . . . . . . 12
3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 11 3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 13
3.1. Common Parts . . . . . . . . . . . . . . . . . . . . . . 11 3.1. Common Parts . . . . . . . . . . . . . . . . . . . . . . 13
3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 12 3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 14
3.3. Inner Code Encoder (Recoder) . . . . . . . . . . . . . . 13 3.3. Inner Code Encoder (Recoder) . . . . . . . . . . . . . . 15
3.4. Belief Propagation Decoder . . . . . . . . . . . . . . . 14 3.4. Outer Code Decoder . . . . . . . . . . . . . . . . . . . 16
4. Research Issues . . . . . . . . . . . . . . . . . . . . . . . 15 4. Research Issues . . . . . . . . . . . . . . . . . . . . . . . 17
4.1. Coding Design Issues . . . . . . . . . . . . . . . . . . 15 4.1. Coding Design Issues . . . . . . . . . . . . . . . . . . 17
4.2. Protocol Design Issues . . . . . . . . . . . . . . . . . 16 4.2. Protocol Design Issues . . . . . . . . . . . . . . . . . 18
4.3. Application Related Issues . . . . . . . . . . . . . . . 17 4.3. Application Related Issues . . . . . . . . . . . . . . . 19
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
6. Security Considerations . . . . . . . . . . . . . . . . . . . 18 6. Security related Considerations . . . . . . . . . . . . . . . 20
6.1. Provision of Confidentiality Protection . . . . . . . . . 18 6.1. Preventing Eavesdropping . . . . . . . . . . . . . . . . 20
6.2. Countermeasures against Pollution Attacks . . . . . . . . 18 6.2. Countermeasures against Pollution Attacks . . . . . . . . 21
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.1. Normative References . . . . . . . . . . . . . . . . . . 19 7.1. Normative References . . . . . . . . . . . . . . . . . . 22
7.2. Informative References . . . . . . . . . . . . . . . . . 19 7.2. Informative References . . . . . . . . . . . . . . . . . 22
Appendix A. Additional Stuff . . . . . . . . . . . . . . . . . . 21 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 21 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24
1. Introduction 1. Introduction
This document specifies a baseline BATS code [Yang14] scheme for data This document specifies a baseline BATS code [Yang14] scheme for data
delivery in multi-hop networks, and discusses the related research delivery in multi-hop networks, and discusses the related research
issues towards a more sophisticated scheme. The BATS code described issues towards a more sophisticated scheme. The BATS code described
here includes an outer code and an inner code. The outer code is a here includes an outer code and an inner code. The outer code is a
matrix generalization of fountain codes (see also the RapterQ code matrix generalization of fountain codes (see also the RapterQ code
described in RFC 6330 [RFC6330]), which inherits the advantages of described in RFC 6330 [RFC6330]), which inherits the advantages of
reliability and efficiency and possesses the extra desirable property reliability and efficiency and possesses the extra desirable property
skipping to change at page 3, line 46 skipping to change at page 3, line 46
the data for transmission separately. Inside the network, however, the data for transmission separately. Inside the network, however,
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 as we illustrate in this document.
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 more clear towards a Second, it helps to make the research issues clearer towards a
sophisticated BATS code based network protocol. Important research sophisticated BATS code based network protocol. Important research
directions include the security issues, congestion control and directions include the security issues, congestion control and
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", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
1.2. Terminology and Definitions
* DDP: data delivery protocol.
* DDP packet: the packet formed by a DDP employing a BATS coding
scheme.
* source packet: the packet formed by the data for delivery.
* BATS/coded packet: the packet generated by a BATS code encoder/
recoder.
* batch: a set of coded packets generated by a BATS coding scheme
with the same subset of the source packets.
* recoded packet: a coded packet generated by a recoder.
* degree: the number of source packets used in a batch generation.
2. A Use Case of BATS Coding Scheme 2. A Use Case of 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, we briefly illustrate in this section 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. scheme clear. Some terms that will be used in this section are
summarized here:
2.1. Introduction * DDP: data delivery protocol.
A BATS coding scheme includes an outer code encoder (also called * DDP packet: the packet formed by a DDP employing a BATS coding
encoder), an inner code encoder (also called recoder) and a decoder, scheme.
which decodes the outer code and the inner code jointly. We describe
a data delivery process that involves one source node, one
destination node, and multiple intermediate nodes in between as
illustrated in Figure 1. This process includes the following
procedures:
+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+ * source packet: the packet formed by the data for delivery.
| source node | --> | intermediate node | --> ...
+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+ * outer encoder: the outer code encoder of a BATS code.
--> | intermediate node | --> | destination node |
+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+
Figure 1: A network model for data delivery. * recoder: the inner code encoder of a BATS code.
Outer code encoding is performed at the source node which has the * outer decoder: the outer code decoder of a BATS code.
data for transmission:
- The DDP provides the data to be delivered and the related * coded packet: the packet generated by the outer code encoder or a
information to the BATS encoder. recoder.
- The BATS encoder generates a sequence of batches, each * batch: a set of coded packets generated by a BATS coding scheme
consisting of a set of coded packets (also called BATS packets) from the same subset of the source packets.
and the information pertaining to the batch.
The batches generated at the source node are further recoded * recoded packet: a coded packet generated by a recoder.
before transmitting:
- A BATS recoder generates recoded packets of a batch. * degree: the number of source packets used to generate a batch by
the outer encoder. The degree can be different for different
batch.
- The DDP forms and transmits the DDP packets using the batches Other common terms can be found in RFC 8406 [RFC8406].
and the corresponding batch information.
Recoding is performed at an intermediate node that does not need 2.1. Introduction
the data:
- The DDP extracts the batches and the corresponding batch We describe a data delivery process that involves one source node,
information from its received DDP packets. one destination node, and multiple intermediate nodes in between. A
BATS coding scheme includes an outer code encoder (also called outer
encoder), an inner code encoder (also called recoder), and an outer
decoder which decodes the outer code and the inner code jointly as
illustrated in Figure 1. The functions of the outer encoder, recoder
and outer decoder are described below:
- A BATS recoder generates recoded packets of a batch. |
| {set of source packets}
v
+-+-+-+-+-+-+-+-+
| outer encoder |
| v | source node
| recoder |
+-+-+-+-+-+-+-+-+
|
| {set of DDP packets}
v
+-+-+-+-+-+-+-+-+
| |
| recoder | intermediate node
| |
+-+-+-+-+-+-+-+-+
|
| {set of DDP packets}
v
...
|
| {set of DDP packets}
v
+-+-+-+-+-+-+-+-+
| |
| outer decoder | destination node
| |
+-+-+-+-+-+-+-+-+
|
| {set of source packets}
v
- The DDP forms and transmits DDP packets using the recoded Figure 1: A network model for data delivery.
packets and the corresponding batch information.
Decoding is performed at the destination node that needs the data: 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
details in Section 2.2.1), and then provides all the source packets
to the outer encoder. The outer encoder will further generate a
sequence of batches, each consisting of a fixed number of coded
packets (see the description in Section 2.2.2).
- The DDP extracts the batches and the corresponding batch Each batch generated at the source node is further processed by the
information from its received DDP packets. recoder separately. The recoder may generate a number of new coded
packets using the existing coded packets of the batch (see the
description in Section 2.2.3). After processed by the recoder, the
DDP forms and transmits the DDP packets using the coded packets,
together with the corresponding batch information.
- A BATS decoder tries to recover the transmitted data using the We assume that a DDP packet is either correctly received or
received batches. completely erased during the communication. The DDP extracts the
coded packets and the corresponding batch information from its
received DDP packets. A recoder is employed at an intermediate node
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
transmits DDP packets using the recoded packets and the corresponding
batch information.
- The DDP sends the decoded data to the application that needs The outer decoder is employed at the destination node that needs the
the data. data. The DDP extracts the coded packets and the corresponding batch
information from its received DDP packets. The outer decoder tries
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
application that needs the data.
2.2. Data Delivery Procedures 2.2. Data Delivery 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 PMTU (path maximum transmission unit) of the session depends on the coding parameters to be discussed in this
network, which MUST be known by the DDP. We have F is no more than section, and will be calculated at the end of this section.
(PMTU-7)2^16-1 octets.
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. * Batch size (M): the number of coded packets in a batch generated
by the outer encoder.
* Recoding field size (q): the number of elements in the finite * Recoding field size (q): the number of elements in the finite
field for recoding. q is 2 or 2^8 field for recoding. 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, O and K are Based on the above parameters, the parameters T, O and K are
calculated as follows: calculated as follows:
* O: the number of octets of a coefficient vector, calculated as O = * O: the number of octets of a coefficient vector, calculated as O =
ceil(M*log2(q)/8). ceil(M*log2(q)/8), which is also called the coefficient vector
overhead.
* T: the number of data octets of a coded packet, calculated as T = * T: the number of data octets of a coded packet, calculated as T =
TO - O. TO - O.
* 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.
skipping to change at page 7, line 19 skipping to change at page 7, line 46
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 to be decribed at Section 3.2 with The DDP provides the BATS encoder with the following information:
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. * Maximum degree (MAX_DEG): a positive integer that specifies the
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. MAX_DEG+1. The i-th entry DD[i] is the possibility that i is
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 (BID) (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 code) encoder generates a batch Using this information, the outer encoder generates M coded packets
for each batch ID. The DDP recieves from the encoder a sequence of for each batch ID using the following steps to be described in
batches, where the batch with ID j has details at Section 3.2:
* Obtain a degree d by sampling DD. Roughly, the value d is chosen
with probability DD[d].
* Choose d source packets uniformly at random from all the K source
packets. It is allowed that a source packet is used by mutiple
batches.
* Generate M coded packets using the d source packets.
The DDP receives from the outer encoder a sequence of batches, where
the batch with ID j has
* a degree d[j], and * a degree d[j], and
* M coded packets (x[j,i], i =0, 1, ..., M-1), each containing TO * M coded packets (x[j,i], i =0, 1, ..., M-1), each containing TO
octets. 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 deliver with each coded packet with its
* d: degree
* BID: batch ID * BID: batch ID
The DDP MUST deliver the following information to each recoder: The DDP MUST deliver the following information to each recoder:
* M: batch size M * M: batch size M
* q: recoding field size * q: recoding field size
The DDP MUST deliver the following information to each decoder: The DDP MUST deliver the following information to each 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
The BID is used by both recoders and decoders. The BATS payload size The BID is used by both recoders and decoders. The BATS payload size
TO MUST be known by all the nodes. TO MUST be known by all the nodes.
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, and should be able to extract coded packets and the network nodes. If the DDP choose not to recode, it just forwards the
corresponding batch information from these packets. DDP packets it received. Otherwise, the DDP should be able to
extract coded packets and the corresponding batch information from
these packets.
If the DDP choose not to recode, it just forwards the packets it For a received batch, the DDP determines a positive integer Mr, the
received. Otherwise, the DDP can choose a recoder to be described in number of recoded packets to be transmitted for the batch, and
Section 3.3 and provides the recoder with the following information: provides the recoder with the following information:
* the batch size M, * the batch size M,
* the recoding field size q, * the recoding field size q,
* 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, and
* link statistics, e.g., packet loss rates. * the number of recoded packets to be generated (Mr).
For a received batch, the recoder determines a positive integer Mr, The recoder uses the information provided by the DDP to generate Mr
the number of recoded packets to be transmitted for the batch. The recoded packets, each containing TO octets, to be described in
recoder uses the information provided by the DDP to generate Mr Section 3.3. The DDP uses the Mr recoded packets to form the DDP
recoded packets, each containing TO octets. The DDP uses the Mr packets for transmitting.
recoded packets to form the DDP packets for transmitting.
2.2.4. Destination Node Procedures 2.2.4. Destination Node Procedures
A destination node needs the data transmitted by the source node. At A destination node needs the data transmitted by the source node. At
the destination node, the DDP receives DDP packets from an 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 and the corresponding batch information from these packets. packets and the corresponding batch information from these packets.
The DDP use a decoder described in Section 3.4 and provides the The DDP provides the outer decoder (to be described in Section 3.4)
decoder 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
skipping to change at page 10, line 9 skipping to change at page 10, line 43
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 * When q=2, M=16,32,64,128
* When q=256, M=8,16,32,64 * 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. Example DDP Packet Format 2.4. Coding Parameters in DDP Packets
A DDP can form a DDP packet with a header (5 octets) and a payload Here we provide an example of embedding the aforementioned BATS
(TO octets). A DDP packet has totally 5+TO octets. coding parameters into the DDP packets which will be used for
recoding and decoding. A DDP can form a DDP packet using a coded
packet by adding necessary information that can help to deliver the
DPP packet to the next node, e.g., the DDP protocol version,
addresses and session identifiers. We will not go into the details
of formatting these fields in a DDP packet, but focus on how to
format the coding parameters and the coded packet in a DDP packet.
2.4.1. Packet Header 2.4.1. Coding Parameter Format
The BATS packet header has 40 bits (5 octets) and includes fields K, Here we provide an example of using 32 bits (4 octets) to embed the
Mq, BID, and d. parameters K, M, q, and BID. The 32 bits are separated into three
subfields, denoted as K, Mq and BID, respectively, as illustrated in
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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| d |
+-+-+-+-+-+-+-+-+
Figure 4: BATS packet header 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 of the BATS session. packets of the BATS session.
* Mq: 4-bit unsigned integer to specify the value of M and q as * Mq: 3-bit unsigned integer to specify the value of M and q as
Table 1. Table 1.
* BID: 12-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.
* d: 8-bit unsigned integer, specifying the batch degree of the +=====+=====+=====+
batch the packet belongs to. | Mq | M | q |
+=====+=====+=====+
| 000 | 16 | 2 |
+-----+-----+-----+
| 010 | 32 | 2 |
+-----+-----+-----+
| 100 | 64 | 2 |
+-----+-----+-----+
| 110 | 128 | 2 |
+-----+-----+-----+
| 001 | 4 | 256 |
+-----+-----+-----+
| 011 | 8 | 256 |
+-----+-----+-----+
| 101 | 16 | 256 |
+-----+-----+-----+
| 111 | 32 | 256 |
+-----+-----+-----+
+======+====+=====+====+ Table 1: Values of Mq
| Mq | M | q | O | field
+======+====+=====+====+
| 0010 | 16 | 2 | 2 |
+------+----+-----+----+
| 0100 | 32 | 2 | 4 |
+------+----+-----+----+
| 0110 | 64 | 2 | 8 |
+------+----+-----+----+
| 0001 | 8 | 256 | 8 |
+------+----+-----+----+
| 0011 | 16 | 256 | 16 |
+------+----+-----+----+
| 0101 | 32 | 256 | 32 |
+------+----+-----+----+
| 0111 | 64 | 256 | 64 |
+------+----+-----+----+
Table 1: Values of Mq The choice of the coding parameters depends on the computation cost,
field the network conditions and the expected end-to-end coding
performance. Usually, a larger batch size M will have a better
coding performance, but higher computation cost for encoding,
recoding and decoding. The field size q affects the coefficient
vector overhead, and also the computation cost for recoding. Within
a BATS session, the BID field should be different for all batches,
and hence the maximum number of batches can be generated for the
outer encoder is 2^13. For different BATS sessions, batches can use
the same BID.
2.4.2. Packet Payload 2.4.2. Coded Packet Format
O T O T
+-----------------------+-------------------------------+ +-----------------------+-------------------------------+
| coefficient vector | coded data | | coefficient vector | coded data |
+-----------------------+-------------------------------+ +-----------------------+-------------------------------+
Figure 5: BATS packet payload format. Figure 5: Code packet format in a DDP packet.
The payload has TO octets, where the first O octets contain the A coded packet has TO octets, where the first O octets contain the
coefficient vector and the remaining T octets contain the coded data. coefficient vector and the remaining T octets contain the coded data.
. .
* coefficient vector: O octets. The range of the value of O is in * coefficient vector: O = M*log2(q)/8 octets. For the values of M
Table 1. and q in Table 1, O is at most 32 octets when q is 256 and 6
octets when q is 2.
* coded data: T octets. T is at most PMTU - 7, where 7 is the total * coded data: T octets. T should be chosen so that the whole DDP
length of the header plus 2, the minimum value of O. packet is at most PMTU.
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 O
= 6 octets. Counting the 4 octets for embedding the coding
parameters, we can choose T = PMTU-H-10, where H is the header length
of a DDP packet. As K can be at most 2^16-1, F can be at most (PMTU-
H-10)(2^16-1) octets. In this case, K/M is about 2^9 and the BID
field 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 packets are treated as a column vector of T
elements in GF(256). Linear algebra and matrix operations over elements in GF(256). The O octets of coefficient vector are treated
finite fields are assumed in this section. as a column vector of O elements in GF(q), where q=2 or q=256.
Linear algebra and matrix operations over finite fields are assumed
in this section.
For two elements of GF(2), their multiplication corresponds to a
logical AND operation and their addition is an logical XOR operation.
An element of the field GF(256) can be represented by a polynomial
with binary coefficients and degree lower or equal to 7. The
addition between two elements of GF(256) is defined as the addition
of the two binary polynomials. The multiplication between two
elements of GF(256) is the multiplication of the two binary
polynomials modulo a certain irreducible polynomial of degree 8,
called a primitive polynomial. One example of such a primitive
polynomial for GF(256) is:
x^8 + x^4 + x^3 + x^2 + 1
A common primitive polynomial should be specified for all the finite
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,
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 RFC 8682 [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
skipping to change at page 12, line 40 skipping to change at page 14, line 40
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 return an integer d using Define a function called DegreeSampler that returns an integer d
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. design of DegreeSampler is illustrated in Figure 7. Note that when K
< MAX_DEG, the degree value returned by DegreeSampler does not
exactly follow the distribution DD, which however would not affect
the practical decoding performance for the outer decoder to be
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() Rand_Init()
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
skipping to change at page 13, line 47 skipping to change at page 15, line 47
(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_M; X] Xr = [I_M; 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)
The inner code comprises (random) linear network coding applied on In general, the inner code of a BATS code comprises (random) linear
the coded packets belonging to the same batch. At a particular network coding applied on the coded packets belonging to the same
network node, recoded packets are generated by (random) linear batch. The recoded packets have the same BID. Suppose that coded
combinations of the received coded packets of a batch. The recoded packets xr[i], i = 0, 1, ..., r-1, which have the same BID j, have
packets have the same BID, degree and coded packet length. been received at an intermediate node, and Mr recoded packets are
supposed to be generated. Following traditional random linear
The number Mr of recoded packets for a batch is decided first by the network coding, a recoded packet can be generated by random linear
recoder. Mr can be set as M. When the link statistics is known, the combination: (randomly) choose a sequence of coefficients c[i], i =
recoder can try to obtain the link packet loss rate e for the link to 0, 1, ..., r-1 from GF(q), and generate
transmit the recoded batch, and set Mr to be (1+e)M. c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] as a recoded packet. This
recoding approach, called random linear recoding, achieves good
Suppose that coded packets xr[i], i = 0, 1, ..., r-1, which have the network coding performance for multicast when the batch size is
same BID j, have been received at an intermediate node. Using the sufficiently large.
recommended packet format, it can be verified whether the
corresponding packet headers of these coded packets are the same.
Then a recoded packet can be generated by one of the following two
approaches:
* forwarding: when receiving xr[i], directly use xr[i] as a recoded
packet.
* linear combination recoding: (randomly) choose a sequence of
coefficients c[i], i = 0, 1, ..., r-1 from GF(q). Generate
c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] as a recoded packet.
A recoder can combine these two approaches to generate recoded For unicast communications in a single path as illustrated in
packets. For example, the recoder will output xr[i], i = 0, 1, ..., Figure 1, it is not necessary to generate all the Mr recoded packets
r-1 as r systematic recoded packets and generate Mr-r recoded packets using random linear combination. Instead, xr[i], i = 0, 1, ..., r-1,
using linear combinations of randomly chosen coefficients. are directly used as recoded packets, and max(Mr-r,0) recoded packets
are generated using linear combinations. Compared with random linear
recoding, this recoding approach, called systematic recoding, can
reduce both the computation cost and also the recoding latency that
accumulates linearly with the number of nodes. Note that the use of
systematic recoding may not always achieve the optimal network coding
performance as random linear recoding in more complicated
communication scenarios that include multiple paths and multiple
destination nodes.
3.4. Belief Propagation Decoder 3.4. Outer Code 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-1,
each of which is a TO-row matrix over GF(256). The degree d[j] of each of which is a TO-row matrix over GF(256). The degree d[j] of
batch j is also known. Let Y[j] be the submatrix of the last T rows batch j is also known. Let Y[j] be the submatrix of the last T rows
of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]; when of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]; when
q = 2, let H[j] be the matrix over GF(256) formed by embedding each q = 2, let H[j] be the matrix over GF(256) formed by embedding each
bit in the first M/8 rows of Yr[j] into GF(256). bit in the first M/8 rows of Yr[j] into GF(256). For successful
decoding, we require that the total rank of all the batches is at
least K.
By calling BatchSampler with input j and d[j], we obtain idx[j] and By calling BatchSampler with input j and d[j], we obtain idx[j] and
G[j]. According to the encoding and recoding processes described in G[j]. According to the encoding and recoding processes described in
Section 3.2 and Section 3.3, we have the system of linear equations Section 3.2 and Section 3.3, we have the system of linear equations
Y[j] = B[j]G[j]H[j] for each received batch with ID j, where B[j] = Y[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 describe a belief propagation (BP) decoder that can efficiently We first describe a belief propagation (BP) decoder that can
solve the source packets when a sufficient number of batches have efficiently solve the source packets when a sufficient number of
been received. A batch j is said to be decodable if rank(G[j]H[j]) = batches have been received. A batch j is said to be decodable if
d[j] (i.e., the system of linear equations Y[j] = B[j]G[j]H[j] with rank(G[j]H[j]) = d[j] (i.e., the system of linear equations Y[j] =
B[j] as the variable matrix has a unique solution). The BP decoding B[j]G[j]H[j] with B[j] as the variable matrix has a unique solution).
algorithm has multiple iterations. Each iteration is formed by the The BP decoding algorithm has multiple iterations. Each iteration is
following steps: formed by the following steps:
* Decoding step: Find a batches 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 a 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
Section 3.2) is properly designed, the BP decoder guarantees a high
probability for the recovery of a given fraction of the source
packets when K is large. To recover all the source packets, a
precode can be applied to the source packets to generate a fraction
of redundant packets before applying the outer code encoding.
Moreover, when the BP decoder stops which may happen with a high
probability when K is relatively small, it is possible to continue
with inactivation decoding, where certain source packets are treated
inactive so that a similar belief propagation process can be resumed.
The reader is referred to RFC 6330 [RFC6330] for the design of a
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 Section 2 and Section 3
needs various refinement and complement towards becoming a more needs various refinement and complement 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
The BATS code specification in Section 3 has nearly optimal When the number of batches is sufficiently large, the BATS code
throughput when the number of source packets K is sufficiently large. specification in Section 3 has nearly optimal performance in the
But when K is small, the degree sampler function in Figure 7 and the sense that the decoding can be successful with a high probability
BatchSampler function in Figure 6 based on a pseudorandom generator when the total rank of all the batches used for decoding is just
may not sample all the source packets evenly, so that some of the slightly larger than the number of source packet K. But when K is
source packets are not well protected. One approach to solve this small, the degree sampler function in Figure 7 and the BatchSampler
issue is to generate a deterministic degree sequence when the number function in Figure 6 based on a pseudorandom generator may not sample
of batches is relatively small, and design a special pseudorandom all the source packets evenly, so that some of the source packets are
generator that has a good sampling performance when K is small. not well protected. One approach to solve this issue is to generate
a deterministic degree sequence when the number of batches is
The belief propagation decoder in Section 3.4 guarantees the recovery relatively small, and design a special pseudorandom generator that
of a given fraction of the source packets. To recover all the source has a good sampling performance when K is small.
packets, a precode can be applied to the source packets to generate a
fraction of redundant packets before applying the outer code
encoding. Moreover, when the belief propagation decoder stops, it is
possible to continue with inactivation decoding, where certain source
packets are treated inactive so that a similar belief propagation
process can be resumed. The reader is referred to RFC 6330 [RFC6330]
for the design of a precode with a good inactivation decoding
performance.
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. The intuition is that
for a batch with a lower rank, a smaller number of recoded packets for a batch with a lower rank, 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].
skipping to change at page 16, line 22 skipping to change at page 18, line 27
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 too much end-to-end latency is interleave batches without increasing too much end-to-end latency 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. For communicating the same data statistically independent batches. For communicating the same data
to multiple destination nodes, which is also call multicast, it is to multiple destination nodes, which is also called multicast, it is
well-known that linear network coding [Li03] achieves the mulicast well-known that linear network coding [Li03] achieves the mulicast
capacity. BATS codes can benefit from network coding due to its capacity. BATS codes can benefit from network coding due to its
inner code, but how to efficiently implement multicast needs further inner code, but how to efficiently implement multicast needs further
research. 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 functionally DDP based on a BATS coding scheme. designing a fully functional DDP based on a BATS coding scheme. Here
Here we discuss some network management issues that are closely we discuss some network management issues that are closely related to
related to a BATS coding scheme: routing, congestion control and a BATS coding scheme: routing, congestion control and media access
media access control. 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 Internet, there are two major
differences. First, the network flow rate is not measured by the differences. First, the network flow rate is not measured by the
rate of the raw packets. Instead, a rank based measurement induced rate of the raw packets. Instead, a rank based measurement induced
skipping to change at page 17, line 29 skipping to change at page 19, line 32
4.3. Application Related Issues 4.3. Application Related Issues
There are more research issues pertaining to different applications. There are more research issues pertaining to different applications.
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 application scenario is wireless mesh and ad hoc One class of typical application 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/one-hop communication is highly reliable. Therefore, employing
a BATS coding scheme can provide more freedom for media access a BATS coding scheme can provide more freedom for media access
control, including power control so that the overall network control, including power control so that the overall network
throughput can be improved. throughput can be improved.
Another typical application scenario of BATS coding schemes is Another typical application scenario of BATS coding schemes is
underwater acoustic networks [Sprea19], where the propagation delay underwater acoustic networks [Sprea19], where the propagation delay
of acoustic waves in underwater can be as long as several seconds. of acoustic waves in underwater can be as long as several seconds.
Due to the long delay, feedback based mechanisms become inefficient. Due to the long delay, feedback based mechanisms become inefficient.
Moreover, point-to-point/one-hop underwater acoustic communication Moreover, point-to-point/one-hop underwater acoustic communication
(for both the forward and reverse directions) is highly unreliable. (for both the forward and reverse directions) is highly unreliable.
Due to these reasons, traditional networking techinques developed for Due to these reasons, traditional networking techniques developed for
radio and wireline networks cannot be directly applied to underwater radio and wireline networks cannot be directly applied to underwater
networks. As a BATS coding scheme does not rely on the feedback for networks. As a BATS coding scheme does not rely on the feedback for
reliability communication and can tolerate highly unreliable links, reliability communication and can tolerate highly unreliable links,
it makes a good candidate for developing data delivery protocols for it makes a good candidate for developing data delivery protocols for
underwater acoustic networks. underwater 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 CCN (content centric
networking), and provides the extra benefit of network coding networking), and provides the extra benefit of network coding
[Zhang16]. [Zhang16].
5. IANA Considerations 5. IANA Considerations
This memo includes no request to IANA. This memo includes no request to IANA.
6. Security Considerations 6. Security related Considerations
Subsuming both Random Linear Network Codes (RLNC) and fountain codes, Subsuming both random linear network codes (RLNC) and fountain codes,
BATS codes naturally inherit both their desirable capability of BATS codes naturally inherit both their desirable security capability
offering confidentiality protection as well as their vulnerability of preventing eavesdropping, as well as their vulnerability towards
towards pollution attacks. pollution attacks. In this section, we discuss some related research
issues.
6.1. Provision of Confidentiality Protection 6.1. Preventing Eavesdropping
Since the transported messages are linearly combined with random Suppose that an eavesdropper obtains a batch where the degree value d
coefficients at each recoding node, it is statistically impossible to is strictly larger than the batch size M. Even the eavesdropper has
recover the individual messages by capturing the coded messages at all the related encoding information, the system of linear equations
any one or small number of nodes. As long as the coding matrices of related to this batch does not have a unique solution, and the
the transported messages cannot be fully recovered, any attempt of probability that the eavesdropper can guess the d source packets used
decoding any particular symbol of the transported messages is for encoding the batch correctly is 2^(d-M)T>=2^T (see also
equivalent to random guessing [Bhattad05]. [Bhattad05]). When inactivation decoding is applied, we can design
the degree distribution DD so that the smallest degree is M+1, and
hence prevent the eavesdropper from decoding source packets from
individual batches.
The threat towards confidentiality, however, also exists in the form If we allow the eavesdropper to collect multiple batches and use
of eavesdropping on the initial encoding process, which takes place inactivation decoding, the same security holds if the total rank of
at the encoding nodes. In these nodes, the transported data are all the batches collected by the eavesdropper is less than the number
presented in plain text and can be read along their transfer paths. of source packet. Therefore, if the DDP can manage to restrict the
Hence, information isolation between the encoding process and all eavesdropper from collecting a sufficiently number of coded packets,
other user processes running on the node must be assured. the native security of BATS code is effective when T is sufficiently
large. Here by native security, we mean the security protection
provided by the BATS coding scheme without extra enhancement.
If the eavesdropper can collect a sufficient number of coded packets
for correct decoding, the native security of BATS code is
ineffective. To prevent eavesdropping in this case, one research
direction is to encrypt some of the crucial information used in
decoding. Such information can be, for example, the batch ID and the
batch generator matrix. The security level of such schemes needs
further evaluations.
The threat exists for eavesdropping on the initial encoding process,
which takes place at the encoding nodes. In these nodes, the
transported data are presented in plain text and can be read along
their transfer paths. Hence, information isolation between the
encoding process and all other user processes running on the source
node MUST be assured.
In addition, the authenticity and trustworthiness of the encoding, 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. Countermeasures against Pollution Attacks 6.2. Countermeasures against Pollution Attacks
Like all network codes, BATS codes are vulnerable under 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 messages into the can pollute the coded messages by injecting forged packets into the
coding network and thus prevent the receivers from recovering the network and thus prevent the receivers from recovering the
transported data correctly. transported data correctly.
The research community has long been investigating the use of various The research community has long been investigating the use of various
signature schemes (including homomorphic signatures) to identify the signature schemes (including homomorphic signatures) to identify the
forged messages and stall the attacks (see [Zhao07], [Yu08], forged packets and stall the attacks (see [Zhao07], [Yu08],
[Agrawal09]). However, these countermeasures are regarded as being [Agrawal09]). However, these countermeasures are regarded as being
too computationally expensive to be employed in broadband too computationally expensive to be employed in broadband
communications. Hence, a system-level approach based on Trusted communications. Hence, a system-level approach based on Trusted
Computing [TC-Wikipedia] is proposed as a practical alternative to Computing [TC-Wikipedia] is proposed as a practical alternative to
protect BATS codes against pollution attacks. This Trusted Computing protect BATS codes against pollution attacks. This Trusted Computing
based protection consists of the following countermeasures: based protection consists of the following countermeasures:
1. Attestation and Validation of all BATS encoding, recoding and 1. Attestation and Validation of all BATS encoding, recoding and
decoding nodes in the network. Remote attestation and repetitive decoding nodes in the network. Remote attestation and repetitive
validation of the identity and capability of these node based on validation of the identity and capability of these node based on
skipping to change at page 19, line 31 skipping to change at page 22, line 21
2. Attestation of all encoding, recoding and decoding programs used 2. Attestation of all encoding, recoding and decoding programs used
in the coding nodes. All programs used to perform the BATS in the coding nodes. All programs used to perform the BATS
encoding, recoding and decoding processes MUST be remotely encoding, recoding and decoding processes MUST be remotely
attested before they are permitted to run on any of the coding attested before they are permitted to run on any of the coding
nodes. Reloading or alteration of programs MUST NOT be permitted nodes. Reloading or alteration of programs MUST NOT be permitted
during an encoding session. Programs MUST be attested or during an encoding session. Programs MUST be attested or
validated again when they are executed in new execution validated again when they are executed in new execution
environments instantiated even in the same node. environments instantiated even in the same node.
3. Original Authentication of all coded messages using network level 3. Origin Authentication of all coded messages using network level
security protocols such as IPsec or Peer Authentication over security protocols such as IPsec or Peer Authentication over
session-based communication using transport level security session-based communication using transport level security
protocols such as TLS/DTLS MUST be employed in order to provide protocols such as TLS/DTLS MUST be employed in order to provide
Message Origin or Communication Peer Authentication to every Message Integrity or Origin Authentication to every coded packet
coded message sent through the coding network. sent through the coding network.
7. References 7. References
7.1. Normative References 7.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs 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>.
[RFC8406] Adamson, B., Adjih, C., Bilbao, J., Firoiu, V., Fitzek,
F., Ghanem, S., Lochin, E., Masucci, A., Montpetit, M-J.,
Pedersen, M., Peralta, G., Roca, V., Ed., Saxena, P., and
S. Sivakumar, "Taxonomy of Coding Techniques for Efficient
Network Communications", RFC 8406, DOI 10.17487/RFC8406,
June 2018, <https://www.rfc-editor.org/info/rfc8406>.
[RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., and E. Baccelli, [RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., and E. Baccelli,
"TinyMT32 Pseudorandom Number Generator (PRNG)", RFC 8682, "TinyMT32 Pseudorandom Number Generator (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
skipping to change at page 20, line 21 skipping to change at page 23, line 21
Bhattad, K. and K.R. Narayanan, "Weakly Secure Network Bhattad, K. and K.R. Narayanan, "Weakly Secure Network
Coding", ISIT , 2007. Coding", ISIT , 2007.
[Byers20] Byers, J.W. and M. Luby, "Liquid Data Networking", ICN , [Byers20] Byers, J.W. and M. Luby, "Liquid Data Networking", ICN ,
2020. 2020.
[Dong20] Dong, Y., Jin, S., Yang, S., and H.H.F. Yin, "Network [Dong20] Dong, Y., Jin, S., Yang, S., and H.H.F. Yin, "Network
Utility Maximization for BATS Code enabled Multihop Utility Maximization for BATS Code enabled Multihop
Wireless Networks", ICC , 2020. Wireless Networks", ICC , 2020.
[Li03] Li, S.-Y.R.., Yeung, R.W., and N. Cai, "Linear Network [Li03] Li, S.-Y.R., Yeung, R.W., and N. Cai, "Linear Network
Coding", IEEE Transactions on Information Theory , 2003. Coding", IEEE Transactions on Information Theory , 2003.
[RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T., [RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T.,
and L. Minder, "RaptorQ Forward Error Correction Scheme and L. Minder, "RaptorQ Forward Error Correction Scheme
for Object Delivery", RFC 6330, DOI 10.17487/RFC6330, for Object Delivery", RFC 6330, DOI 10.17487/RFC6330,
August 2011, <https://www.rfc-editor.org/info/rfc6330>. August 2011, <https://www.rfc-editor.org/info/rfc6330>.
[Sprea19] Sprea, N., Bashir, M., Truhachev, D., Srinivas, K.V., [Sprea19] Sprea, N., Bashir, M., Truhachev, D., Srinivas, K.V.,
Schlegel, C., and C. Claudio Sacchi, "BATS Coding for Schlegel, C., and C. Claudio Sacchi, "BATS Coding for
Underwater Acoustic Communication Networks", OCEANS , Underwater Acoustic Communication Networks", OCEANS ,
skipping to change at page 21, line 16 skipping to change at page 24, line 16
Signature-Based Scheme for Securing Network Coding Against Signature-Based Scheme for Securing Network Coding Against
Pollution Attacks", INFOCOM , 2008. Pollution Attacks", INFOCOM , 2008.
[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 , 2016.
[Zhao07] Zhao, F., Kalker, T., Medard, M., and K.J. Han, [Zhao07] Zhao, F., Kalker, T., Medard, M., and K.J. Han,
"Signatures for content distribution with network coding", "Signatures for content distribution with network coding",
ISIT , 2007. ISIT , 2007.
Appendix A. Additional Stuff Acknowledgments
The authors would like to thank the NWCRG chairs, Vincent Roca (our
shepherd) and Marie-Jose Montpetit; and all those who provided
comments -- namely (in alphabetical order), Emmanuel Lochin, David
Oran, and Colin Perkins.
Authors' Addresses Authors' Addresses
Shenghao Yang Shenghao Yang
CUHK(SZ) CUHK(SZ)
Shenzhen Shenzhen
Guangdong, Guangdong,
China China
Phone: +86 755 8427 3827 Phone: +86 755 8427 3827
 End of changes. 95 change blocks. 
263 lines changed or deleted 384 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/