< draft-irtf-nwcrg-bats-02.txt   draft-irtf-nwcrg-bats-03.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: 4 June 2022 R. W. Yeung Expires: 12 June 2022 R. W. Yeung
CUHK CUHK
J. K. Zao J. K. Zao
NCTU NCTU
1 December 2021 9 December 2021
BATS Coding Scheme for Multi-hop Data Transport BATS Coding Scheme for Multi-hop Data Transport
draft-irtf-nwcrg-bats-02 draft-irtf-nwcrg-bats-03
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 4 June 2022. This Internet-Draft will expire on 12 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
skipping to change at page 2, line 24 skipping to change at page 2, line 24
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 4
2. A Use Case of BATS Coding Scheme . . . . . . . . . . . . . . 4 2. A Use Case of BATS Coding Scheme . . . . . . . . . . . . . . 4
2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 5 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 . . . . . . . . . . . . . . . . . 9 2.2.3. Recoding Procedures . . . . . . . . . . . . . . . . . 9
2.2.4. Destination Node Procedures . . . . . . . . . . . . . 9 2.2.4. Destination Node Procedures . . . . . . . . . . . . . 10
2.3. Recommendation for the Parameters . . . . . . . . . . . . 10 2.3. Recommendation for the Parameters . . . . . . . . . . . . 10
2.4. Coding Parameters in DDP Packets . . . . . . . . . . . . 11 2.4. Coding Parameters in DDP Packets . . . . . . . . . . . . 11
2.4.1. Coding Parameter Format . . . . . . . . . . . . . . . 11 2.4.1. Coding Parameter Format . . . . . . . . . . . . . . . 11
2.4.2. Coded Packet Format . . . . . . . . . . . . . . . . . 12 2.4.2. Coded Packet Format . . . . . . . . . . . . . . . . . 12
3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 13 3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 13
3.1. Common Parts . . . . . . . . . . . . . . . . . . . . . . 13 3.1. Common Parts . . . . . . . . . . . . . . . . . . . . . . 13
3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 14 3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 14
3.3. Inner Code Encoder (Recoder) . . . . . . . . . . . . . . 15 3.3. Inner Code Encoder (Recoder) . . . . . . . . . . . . . . 15
3.4. Outer Code Decoder . . . . . . . . . . . . . . . . . . . 16 3.4. Outer Decoder . . . . . . . . . . . . . . . . . . . . . . 16
4. Research Issues . . . . . . . . . . . . . . . . . . . . . . . 17 4. Research Issues . . . . . . . . . . . . . . . . . . . . . . . 17
4.1. Coding Design Issues . . . . . . . . . . . . . . . . . . 17 4.1. Coding Design Issues . . . . . . . . . . . . . . . . . . 17
4.2. Protocol Design Issues . . . . . . . . . . . . . . . . . 18 4.2. Protocol Design Issues . . . . . . . . . . . . . . . . . 18
4.3. Application Related Issues . . . . . . . . . . . . . . . 19 4.3. Application Related Issues . . . . . . . . . . . . . . . 19
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
6. Security related Considerations . . . . . . . . . . . . . . . 20 6. Security related Considerations . . . . . . . . . . . . . . . 20
6.1. Preventing Eavesdropping . . . . . . . . . . . . . . . . 20 6.1. Preventing Eavesdropping . . . . . . . . . . . . . . . . 20
6.2. Countermeasures against Pollution Attacks . . . . . . . . 21 6.2. Countermeasures against Pollution Attacks . . . . . . . . 21
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.1. Normative References . . . . . . . . . . . . . . . . . . 22 7.1. Normative References . . . . . . . . . . . . . . . . . . 22
skipping to change at page 6, line 43 skipping to change at page 6, line 43
application that needs the data. 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 coding parameters to be discussed in this session depends on the coding parameters to be discussed in this
section, and will be calculated at the end of this section. section, and will be calculated 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. q is 2 or 2^8
skipping to change at page 8, line 36 skipping to change at page 8, line 36
* 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 mutiple
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 The DDP receives from the outer encoder a sequence of batches, where
the batch with ID j has the batch with ID j has
* 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
* 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
* 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 * DD: the degree distribution.
TO MUST be known by all the nodes.
The BID is used by both recoders and decoders. We will illustrate in
Section 2.4 that how to embed BID, M, q, and K into DDP packets. The
degree distribution DD does not need to be changed frequently. See
Section 6 in [Yang17] about how to design a good degree distribution.
Once designed, the degree distribution can be shared between the
source node and the destination node by the DDP, which is not further
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 choose not to recode, it just forwards the
DDP packets it received. Otherwise, the DDP should be able to 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
skipping to change at page 10, line 18 skipping to change at page 10, line 25
* 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 and degrees. 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. If successful, inner code jointly and recover the K source packets (see details in
the decoder returns the recovered K source packets to the DDP, which Section 3.4). If successful, the decoder returns the recovered K
will use the K source packets to form the F octets data. The source packets to the DDP, which will use the K source packets to
recommended padding deletion process is shown as follows: form the F octets data. The recommended padding deletion process is
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
skipping to change at page 12, line 48 skipping to change at page 12, line 48
2.4.2. Coded Packet Format 2.4.2. Coded Packet Format
O T O 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 octets, where the first O octets contain the A coded packet has TO=T+O octets, where the first O octets contain
coefficient vector and the remaining T octets contain the coded data. the coefficient vector and the remaining T octets contain the coded
. data.
* coefficient vector: O = M*log2(q)/8 octets. For the values of M * coefficient vector: O = M*log2(q)/8 octets. For the values of M
and q in Table 1, O is at most 32 octets when q is 256 and 6 and q in Table 1, O 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 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 O for different parameters. For example, when q=2 and M=128, we have O
skipping to change at page 13, line 30 skipping to change at page 13, line 30
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). The O octets of coefficient vector are treated elements in GF(256). The O octets of coefficient vector are treated
as a column vector of O elements in GF(q), where q=2 or q=256. 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 Linear algebra and matrix operations over finite fields are assumed
in this section. in this section.
For 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 an logical XOR operation. logical AND operation and their addition is an 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:
skipping to change at page 15, line 10 skipping to change at page 15, line 10
< 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() 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.
skipping to change at page 15, line 40 skipping to change at page 15, line 40
the M x M identity matrix I with entries in GF(q), and the last T the M x M identity matrix I with entries in GF(q), and the last T
rows of Xr[j] is X[j]. 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_M; 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 traditional random linear
network coding, a recoded packet can be generated by random linear network coding, a recoded packet can be generated by random linear
skipping to change at page 16, line 25 skipping to change at page 16, line 25
are directly used as recoded packets, and max(Mr-r,0) recoded packets are directly used as recoded packets, and max(Mr-r,0) recoded packets
are generated using linear combinations. Compared with random linear are generated using linear combinations. Compared with random linear
recoding, this recoding approach, called systematic recoding, can recoding, this recoding approach, called systematic recoding, can
reduce both the computation cost and also the recoding latency that reduce both the computation cost and also the recoding latency that
accumulates linearly with the number of nodes. Note that the use of accumulates linearly with the number of nodes. Note that the use of
systematic recoding may not always achieve the optimal network coding systematic recoding may not always achieve the optimal network coding
performance as random linear recoding in more complicated performance as random linear recoding in more complicated
communication scenarios that include multiple paths and multiple communication scenarios that include multiple paths and multiple
destination nodes. destination nodes.
3.4. Outer Code 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-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). Let Y[j] be the
batch j is also known. Let Y[j] be the submatrix of the last T rows submatrix of the last T rows of Yr[j]. When q = 256, let H[j] be the
of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]; when first M rows of Yr[j]; when q = 2, let H[j] be the matrix over
q = 2, let H[j] be the matrix over GF(256) formed by embedding each GF(256) formed by embedding each bit in the first M/8 rows of Yr[j]
bit in the first M/8 rows of Yr[j] into GF(256). For successful into GF(256). For successful decoding, we require that the total
decoding, we require that the total rank of all the batches is at rank of all the batches is at least K.
least K.
By calling BatchSampler with input j and d[j], we obtain idx[j] and The same degree distribution DD used for the outer encoder is
G[j]. According to the encoding and recoding processes described in 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].
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 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
skipping to change at page 18, line 52 skipping to change at page 18, line 52
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
by the inner code is applied for BATS coding schemes. Second, due to by the inner code is applied for BATS coding schemes. Second, due to
recoding, the raw packet rate of a flow may not be the same for recoding, the raw packet rate may not be the same for different links
different links, i.e., no flow conservation for BATS coding schemes. of a flow, i.e., no flow conservation for BATS coding schemes. These
These differences affect both the objective and the constraints of differences affect both the objective and the constraints of the
the utility maximization problem. 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.
Due to the recoding operation, congestion control cannot be only Due to the recoding operation, congestion control cannot be only
performed end-to-end. The rate of transmitting batches can be performed end-to-end. The rate of transmitting batches can be
controlled end-to-end, but the number of recoded packets generated controlled end-to-end, but the number of recoded packets generated
for a batch must be controlled at the intermediate nodes, which for a batch must be controlled at the intermediate nodes, which
introduces new research issues for congestion control. For routing, introduces new research issues for congestion control. For routing,
the BATS coding scheme is flexible for implementing multi-path data the BATS coding scheme is flexible for implementing multi-path data
transmission, and different batches can be transmitted on a different transmission, and different batches can be transmitted on a different
skipping to change at page 19, line 39 skipping to change at page 19, line 39
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, and physical-layer design so that
throughput can be improved. the overall network 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 techniques 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
skipping to change at page 21, line 15 skipping to change at page 21, line 15
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 sufficiently number of coded packets, eavesdropper from collecting a sufficiently number of coded packets,
the native security of BATS code is effective when T is sufficiently the native security of BATS code is effective when T is sufficiently
large. Here by native security, we mean the security protection large. Here by native 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 correct decoding, the native security of BATS code is for correctly decoding, the native security of BATS code is
ineffective. To prevent eavesdropping in this case, one research ineffective. One solution in this case is to encrypt the whole data
direction is to encrypt some of the crucial information used in before using the BATS code scheme. Better schemes are desired
decoding. Such information can be, for example, the batch ID and the towards reducing the computation cost of the whole data encryption
batch generator matrix. The security level of such schemes needs solution. This is a research issue that depends on specific BATS
further evaluations. 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
 End of changes. 26 change blocks. 
49 lines changed or deleted 57 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/