idnits 2.17.1 draft-yang-nwcrg-bats-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 16, 2020) is 1255 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 527 == Missing Reference: 'K-1' is mentioned on line 527, but not defined == Missing Reference: 'K-2' is mentioned on line 224, but not defined == Missing Reference: 'T-P-1' is mentioned on line 227, but not defined == Missing Reference: 'T-P' is mentioned on line 227, but not defined == Missing Reference: 'T-1' is mentioned on line 359, but not defined == Missing Reference: 'WI' is mentioned on line 365, but not defined -- Looks like a reference, but probably isn't: '1' on line 527 Summary: 0 errors (**), 0 flaws (~~), 7 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force S. Yang 3 Internet-Draft CUHK(SZ) 4 Intended status: Informational X. Huang 5 Expires: May 20, 2021 R.W. Yeung 6 CUHK 7 J.K. Zao 8 NCTU 9 November 16, 2020 11 BATS Coding Scheme for Multi-hop Data Transport 12 draft-yang-nwcrg-bats-04 14 Abstract 16 This document describes a BATS coding scheme for communication 17 through multi-hop networks. BATS code is a class of efficient linear 18 network coding scheme with a matrix generalization of fountain codes 19 as the outer code, and batch-based linear network coding as the inner 20 code. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at https://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on May 20, 2021. 39 Copyright Notice 41 Copyright (c) 2020 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (https://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 57 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 58 2. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 4 60 2.2. Data Delivery Procedures . . . . . . . . . . . . . . . . 5 61 2.2.1. Source Node Data Partitioning and Padding . . . . . . 5 62 2.2.2. Source Node Outer Code Encoding Procedure . . . . . . 6 63 2.2.3. Recoding Procedures . . . . . . . . . . . . . . . . . 7 64 2.2.4. Destination Node Procedures . . . . . . . . . . . . . 8 65 2.3. Recommendation for the Parameters . . . . . . . . . . . . 8 66 2.4. Example DDP Packet Format . . . . . . . . . . . . . . . . 9 67 2.4.1. Packet Header . . . . . . . . . . . . . . . . . . . . 9 68 2.4.2. Packet Payload . . . . . . . . . . . . . . . . . . . 10 69 2.4.3. Packet Footer . . . . . . . . . . . . . . . . . . . . 10 70 3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 11 71 3.1. Common Parts . . . . . . . . . . . . . . . . . . . . . . 11 72 3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 12 73 3.3. Inner Code Encoder (Recoder) . . . . . . . . . . . . . . 13 74 3.4. Belief Propagation Decoder . . . . . . . . . . . . . . . 13 75 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 76 5. Security Considerations . . . . . . . . . . . . . . . . . . . 14 77 5.1. Provision of Confidentiality Protection . . . . . . . . . 14 78 5.2. Countermeasures against Pollution Attacks . . . . . . . . 15 79 6. Data Delivery Protocol Considerations . . . . . . . . . . . . 16 80 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 16 81 7.1. Normative References . . . . . . . . . . . . . . . . . . 16 82 7.2. Informative References . . . . . . . . . . . . . . . . . 17 83 Appendix A. Additional Stuff . . . . . . . . . . . . . . . . . . 17 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 86 1. Introduction 88 This document specifies a BATS code [BATS] scheme for data delivery 89 in multi-hop networks. The BATS code described here includes an 90 outer code and an inner code. The outer code is a matrix 91 generalization of fountain codes (see also the RapterQ code described 92 in RFC 6330 [RFC6330]), which inherits the advantages of reliability 93 and efficiency and possesses the extra desirable property of being 94 network coding compatible. The inner code, also called recoding, is 95 formed by linear network coding for combating packet loss, improving 96 the multicast efficiency, etc. A detailed design and analysis of 97 BATS codes are provided in the BATS monograph [BATSMonograph]. 99 The BATS coding scheme can be applied in multi-hop networks formed by 100 wireless communication links, which are inherently unreliable due to 101 interference. Existing transport protocols like TCP use end-to-end 102 retransmission, while network protocols such as IP might enable 103 store-and-forward at the relays, so that packet loss would accumulate 104 along the way. 106 The BATS coding scheme can be used for various data delivery 107 applications like file transmission, video streaming over wireless 108 multi-hop networks, etc. Different from traditional forward error 109 correcting (FEC) schemes that are applied either hop-by-hop or end- 110 to-end, the BATS coding scheme combines the end-to-end coding (the 111 outer code) with certain hop-by-hop coding (the inner code), and 112 hence can potentially achieve better performance. 114 The coding scheme described here can be used in a network with 115 multiple communication flows. For each flow, the source node encodes 116 the data for transmission separately. Inside the network, however, 117 it is possible to mix the packets from different flows for recoding. 118 In this document, we describe a simple case where recoding is 119 performed within each flow. Note that the same encoding/decoding 120 scheme described here can be used with different recoding schemes as 121 long as they follow the principle as we illustrate in this document. 123 The purpose of this document is a preliminary BATS coding scheme for 124 researchers and engineers so that they can develop further the 125 network communication applications/protocols based on BATS codes. 126 Towards a sophisticated BATS code based network protocol, several 127 important research directions should be considered. One is about the 128 security issues. Another important current research is to design the 129 corresponding congestion control and routing algorithms for BATS 130 codes. 132 1.1. Requirements Language 134 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 135 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 136 document are to be interpreted as described in RFC 2119 [RFC2119]. 138 2. Procedures 139 2.1. Introduction 141 A BATS coding scheme includes an outer code encoder (also called 142 encoder), an inner code encoder (also called recoder) and a decoder. 143 The BATS coding scheme can be used for a single data flow that 144 includes a single source and one or multiple destinations. Thus 145 there exists only one encoder with multiple recoders and decoders. 146 The BATS coding scheme described in this document can be used by a 147 Data Delivery Protocol (DDP) with the following procedures. 149 Outer Code Encoding at a source node which has the data for 150 transmission: 152 * The DDP provides the data to be delivered and the related 153 information to the BATS encoder. 155 * The BATS encoder generates a sequence of batches, each 156 consisting of a set of coded packets and the information 157 pertaining to the batch. 159 The batches generated at the source node are further recoded 160 before transmitting: 162 * A BATS recoder generates recoded packets of a batch. 164 * The DDP forms and transmits the DDP packets using the batches 165 and the corresponding batch information. 167 Recoding at an intermediate node that does not need the data: 169 * The DDP extracts the batches and the corresponding batch 170 information from its received DDP packets. 172 * A BATS recoder generates recoded packets of a batch. 174 * The DDP forms and transmits DDP packets using the recoded 175 packets and the corresponding batch information. 177 Decoding at a destination node that needs the data: 179 * The DDP extracts the batches and the corresponding batch 180 information from its received DDP packets. 182 * A BATS decoder tries to recover the transmitted data using the 183 received batches. 185 * The DDP sends the decoded data to the application that needs 186 the data. 188 2.2. Data Delivery Procedures 190 Suppose that the DDP has F octets of data for transmission. We 191 describe the procedures of one BATS session for transmitting the F 192 octets. There is a limit on F of a single BATS session. If the 193 total data has more than the limit, the data needs to be transmitted 194 using multiple BATS sessions. The limit on F of a single BATS 195 session depends on the MTU (maximum transmission unit) of the 196 network, which MUST be known by the DDP. We have F is no more than 197 (MTU-10)2^16-1 octets. 199 2.2.1. Source Node Data Partitioning and Padding 201 The DDP first determines the following parameters: 203 o Batch size (M): the number of coded packets in a batch. 205 o Recoding field size (q): the number of elements in the finite 206 field for recoding. q is 2 or 2^8 208 o BATS payload size (TO): the number of payload octets in a BATS 209 packet, including the coded data and the coefficient vector. 211 Based on the above parameters, the parameters T, O and K are 212 calculated as follows: 214 o O: the number of octets of a coefficient vector, calculated as O = 215 ceil(M*log2(q)/8). 217 o T: the number of data octets of a BATS packet, calculated as T = 218 TO - O. 220 o K: number of source packets, calculated as K = floor(F/T)+1. 222 The data MUST be padded to have T*K octets, which will be partitioned 223 into K source packets b[0], ..., b[K-1], each of T octets. In our 224 padding scheme, b[0], ..., b[K-2] are filled with data bits, and 225 b[K-1] is filled with the remaining data octets and padding octets. 226 Let P = K*T-F denote the number of padding octets. We use b[K-1, 0], 227 ..., b[K-1, T-P-1] to denote the T-P source octets and b[K-1, T-P], 228 ..., b[K-1, T-1] to denote the P padding octets in b[K-1], 229 respectively. The padding process is shown in Figure 1. 231 Z = T - P 232 Let bl be the last source packet b[K-1] 233 for i = 1, 2, ... do 234 if Z + i >= T - 1 do 235 bl[Z...T-1] = i 236 break 237 bl[Z...Z+i-1] = i 238 Z = Z + i 240 Figure 1: Data Padding Process 242 2.2.2. Source Node Outer Code Encoding Procedure 244 The DDP provides the BATS encoder with the following information: 246 o Batch size (M): the number of coded packets in a batch. 248 o Recoding field size (q): the number of elements in the finite 249 field for recoding. 251 o MAX_DEG: the size of DD. 253 o The degree distribution (DD), which is an unsigned integer array 254 of size MAX_DEG+1. 256 o A sequence of batch IDs (j, j = 0, 1, ...). 258 o Number of source packets (K). 260 o Packet size (T): the number of octets in a source packet. 262 o The source packets (b[i], i = 0, 1, ..., K-1). 264 Using this information, the (outer code) encoder generates a batch 265 for each batch ID. For the batch ID j, the encoder returns the DDP 266 that contains 268 o a sparse degree d[j], and 270 o M coded packets (x[j,i], i =0, 1, ..., M-1), each containing TO 271 octets. 273 The DDP will use the batches to form DDP packets to be transmitted to 274 other network nodes towards the destination nodes. The DDP MUST 275 deliver with each coded packet its 277 o d: sparse degree 278 o BID: batch ID 280 The DDP MUST deliver the following information to each recoder: 282 o M: batch size M 284 o q: recoding field size 286 The DDP MUST deliver the following information to each decoder: 288 o M: batch size 290 o q: recoding field size 292 o K: the number of source packet 294 o T: the number of octets in a source packet 296 The BID is used by both recoders and decoders. The BATS payload size 297 TO MUST be known by all the nodes. 299 The DDP will also include some necessary extra information in the 300 packet header so that the network nodes can identify different BATS 301 sessions, and different end-to-end communication flows. However, 302 such specifications are beyond the scope of this document. 304 2.2.3. Recoding Procedures 306 Both the source node and the intermediate nodes perform recoding on 307 the batches before transmission. At the source node, the recoder 308 receives the batches from the outer code encoding procedure. At an 309 intermediate node, the DDP receives the DDP packets from the other 310 network nodes, and should be able to extract coded packets and the 311 corresponding batch information from these packets. 313 The DDP provides the recoder with the following information: 315 o the batch size M, 317 o the recoding field size q, 319 o a number of received coded packets of the same batch, each 320 containing TO octets, and 322 o link statistics, e.g., packet loss rates. 324 For a received batch, the recoder determines a positive integer Mr, 325 the number of recoded packets to be transmitted for the batch. The 326 recoder uses the information provided by the DDP to generate Mr 327 recoded packets, each containing TO octets. The DDP uses the Mr 328 recoded packets to form the DDP packets for transmitting. 330 2.2.4. Destination Node Procedures 332 A destination node needs the data transmitted by the source node. At 333 the destination node, the DDP receives DDP packets from the other 334 network nodes, and should be able to extract coded packets and the 335 corresponding batch information from these packets. 337 The DDP provides the decoder with the following information: 339 o M: batch size, 341 o q: recoding field size, 343 o K: the number of source packets 345 o T: the number of octets of a source packet 347 o A sequence of batches, each of which is formed by a number of 348 coded packets belonging to the same batch, with their 349 corresponding batch IDs and degrees. 351 The decoder uses this information to decode the K source packets. If 352 successful, the decoder returns the recovered K source packets to the 353 DDP, which will use the K source packets to form the F octets data. 354 The recommended padding process is shown as follows: 356 // this procedure returns the number P of padding octets 357 // at the end of b[K-1] 358 Let bl be the last decoded source packet b[K-1] 359 PL = bl[T-1] 360 if PL == 1 do 361 return P = 1 362 WI = T - 1 363 while bl[WI] == PL do 364 WI = WI - 1 365 return P = (1 + bl[WI]) * bl[WI] + T - WI - 1 367 Figure 2: Data Depadding Process 369 2.3. Recommendation for the Parameters 371 The recommendation for the parameters M and q is shown as follows: 373 o When q=2, M=16,32,64 374 o When q=256, M=8,16,32,64 376 It is RECOMMENDED that K is at least 128. However, the encoder/ 377 decoder SHALL support an arbitrary positive integer value less than 378 2^16. 380 2.4. Example DDP Packet Format 382 A DDP can form a DDP packet with a header (5 octets), a footer (3 383 octets) and a payload (TO octets). A DDP packet has totally 8+TO 384 octets. 386 2.4.1. Packet Header 388 The BATS packet header has 40 bits (5 octets) and includes fields 389 Packet_Count, Mq, Batch_ID, and Degree. 391 0 1 2 3 392 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 393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 394 | Packet_Count | Mq | Batch_ID | 395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 396 | Degree | 397 +-+-+-+-+-+-+-+-+ 399 Figure 3: BATS packet header format. 401 o Packet_Count: 16-bit unsigned integer, specifying the number K of 402 packets of the BATS session. 404 o Mq: 4-bit unsigned integer to specify the value of M and q as 405 Table 1. 407 o Batch_ID: 12-bit unsigned integer, specifying the batch ID BID of 408 the batch the packet belonging to. 410 o Degree: 8-bit unsigned integer, specifying the batch degree d of 411 the batch the packet belonging to. 413 +------+----+-----+----+ 414 | Mq | M | q | O | 415 +------+----+-----+----+ 416 | 0010 | 16 | 2 | 2 | 417 | 0100 | 32 | 2 | 4 | 418 | 0110 | 64 | 2 | 8 | 419 | 0001 | 8 | 256 | 8 | 420 | 0011 | 16 | 256 | 16 | 421 | 0101 | 32 | 256 | 32 | 422 | 0111 | 64 | 256 | 64 | 423 +------+----+-----+----+ 425 Table 1: Values of Mq field 427 2.4.2. Packet Payload 429 O T 430 +-----------------------+-------------------------------+ 431 | coefficient vector | coded data | 432 +-----------------------+-------------------------------+ 434 Figure 4: BATS packet payload format. 436 The payload has TO octets, where the first O octets contain the 437 coefficient vector and the remaining T octets contain the coded data. 438 Information in both fields MAY be encoded in JSON (ASCII) or protobuf 439 (binary) formats. 441 o coefficient vector: O octets. The range of the value of O is in 442 Table 1. 444 o coded data: T octets. T is at most MTU - 10, where 10 is the 445 total of the header and footer length plus the minimum value of O. 447 2.4.3. Packet Footer 449 0 1 2 450 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 451 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 452 | signature | parity check | 453 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 455 Figure 5: BATS packet footer format. 457 The footer has three octets. 459 o signature: 2 octets. A signature of the individual packet to 460 prevent pollution attack. 462 o parity check: 1 octet. A parity check field used to verity the 463 correctness of the packet. 465 3. BATS Code Specification 467 3.1. Common Parts 469 The T octets of a source packets are treated as a column vector of T 470 elements in GF(256). Linear algebra and matrix operations over 471 finite fields are assumed in this section. 473 Suppose that a pseudorandom number generator Rand() which generates 474 an unsigned integer of 32 bits is shared by both encoding and 475 decoding. The pseudorandom generator can be initialized by 476 Rand_Init(S) with seed S. When S is not provided, the pseudorandom 477 generator is initialized arbitrarily. One example of such a 478 pseudorandom generator is defined in RFC 8682 [RFC8682]. 480 A function called BatchSampler is used in both encoding and decoding. 481 The function takes two integers j and d as input, and generates an 482 array idx of d integers and a d x M matrix G. The function first 483 initializes the pseudorandom generator with j, sample d distinct 484 integers from 0 to K-1 as idx, and sample d*M integers from 0 to 255 485 as G. See the pseudocode in Figure 6. 487 function BatchSampler(j,d) 488 // initialize the pseudorandom generator by seed j. 489 Rand_Init(j) 490 // sample d distinct integers between 0 and K-1. 491 for k = 0, ..., d-1 do 492 r = Rand() % K 493 while r already exists in idx do 494 r = Rand() % K 495 idx[k] = r 497 // sample d x M matrix 498 for r = 0, ..., d-1 do 499 for c = 0,...,M-1 do 500 G[r,c] = Rand() % 256 502 return idx, G 504 Figure 6: Batch Sampler Function 506 3.2. Outer Code Encoder 508 Define a function called DegreeSampler that return an integer d using 509 the degree distribution DD. We expect that the empirical 510 distribution of the returning d converges to DD(d) when d < K. One 511 design of DegreeSampler is illustrated in Figure 7. 513 function DegreeSampler(j, DD) 514 Let CDF be an array 515 CDF[0] = 0 516 for i = 1, ..., MAX_DEG do 517 CDF[i] = CDF[i-1] + DD[i] 518 Rand_Init() 519 r = Rand() % CDF[MAX_DEG] 520 for d = 1, ..., MAX_DEG do 521 if r >= CDF[d] do 522 return min(d,K) 523 return min(MAX_DEG,K) 525 Figure 7: Degree Sampler Function 527 Let b[0], b[1], ..., b[K-1] be the K source packets. A batch with 528 BID j is generated using the following steps. 530 o Obtain a degree d by calling DegreeSampler with input j. 532 o Obtain idx and G[j] by calling BatchSampler with input j and d. 534 o Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d-1]]). Form the 535 batch X[j] = B[j]*G[j], whose dimension is T x M. 537 o Form the TO x M matrix Xr[j], where the first O rows of Xr[j] form 538 the M x M identity matrix I with entries in GF(q), and the last T 539 rows of Xr[j] is X[j]. 541 See the pseudocode of the batch generating process in Figure 8. 543 function GenBatch(j) 544 d = DegreeSampler(j) 545 (idx, G) = BatchSampler(j,d) 546 B = (b[idx[0]], b[idx[i]], ..., b[idx[d-1]]) 547 X = B * G 548 Xr = [I_M; X] 549 return Xr 551 Figure 8: Batch Generation Function 553 3.3. Inner Code Encoder (Recoder) 555 The inner code comprises (random) linear network coding applied on 556 the coded packets belonging to the same batch. At a particular 557 network node, recoded packets are generated by (random) linear 558 combinations of the received coded packets of a batch. The recoded 559 packets have the same BID, sparse degree and coded packet length. 561 The number Mr of recoded packets for a batch is decided first by the 562 recoder. Mr can be set as M. When the link statistics is known, the 563 recoder can try to obtain the link packet loss rate e for the link to 564 transmit the recoded batch, and set Mr to be (1+e)M. 566 Suppose that coded packets xr[i], i = 0, 1, ..., r-1, which have the 567 same BID j, have been received at an intermediate node. Using the 568 recommended packet format, it can be verified whether the 569 corresponding packet headers of these coded packets are the same. 570 Then a recoded packet can be generated by one of the following two 571 approaches: 573 o forwarding: when receiving xr[i], directly use xr[i] as a recoded 574 packet. 576 o linear combination recoding: (randomly) choose a sequence of 577 coefficients c[i], i = 0, 1, ..., r-1 from GF(q). Generate 578 c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] as a recoded packet. 580 A recoder can combine these two approaches to generate recoded 581 packets. For example, the recoder will output xr[i], i = 0, 1, ..., 582 r-1 as r systematic recoded packets and generate Mr-r recoded packets 583 using linear combinations of randomly chosen coefficients. 585 3.4. Belief Propagation Decoder 587 The decoder receives a sequence of batches Yr[j], j = 0, 1, ..., n-1, 588 each of which is a TO-row matrix over GF(256). The degree d[j] of 589 batch j is also known. Let Y[j] be the submatrix of the last T rows 590 of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]; when 591 q = 2, let H[j] be the matrix over GF(256) formed by embedding each 592 bit in the first M/8 rows of Yr[j] into GF(256). 594 By calling BatchSampler with input j and d[j], we obtain idx[j] and 595 G[j]. According to the encoding and recoding processes described in 596 Section 3.2 and Section 3.3, we have the system of linear equations 597 Y[j] = B[j]G[j]H[j] for each received batch with ID j, where B[j] = 598 (b[idx[j,0]], b[idx[j,1]], ..., b[idx[j,d-1]]) is unknown. 600 We describe a belief propagation (BP) decoder that can efficiently 601 solve the source packets when a sufficient number of batches have 602 been received. A batch j is said to be decodable if rank(G[j]H[j]) = 603 d[j] (i.e., the system of linear equations Y[j] = B[j]G[j]H[j] with 604 B[j] as the variable matrix has a unique solution). The BP decoding 605 algorithm has multiple iterations. Each iteration is formed by the 606 following steps: 608 o Decoding step: Find a batches j that is decodable. Solve the 609 corresponding system of linear equations Y[j] = B[j]G[j]H[j] and 610 decode B[j]. 612 o Substitution step: Substitute the decoded source packets into 613 undecodable batches. Suppose that a decoded source packet b[k] is 614 used in generating a undecodable Y[j]. The substitution involves 615 1) removing the entry in idx[j] corresponding to k, 2) removing 616 the row in G[j] corresponding to b[k], and 3) reducing d[j] by 1. 618 The BP decoder repeats the above steps until no batches are decodable 619 during the decoding step. 621 4. IANA Considerations 623 This memo includes no request to IANA. 625 5. Security Considerations 627 Subsuming both Random Linear Network Codes (RLNC) and fountain codes, 628 BATS codes naturally inherit both their desirable capability of 629 offering confidentiality protection as well as their vulnerability 630 towards pollution attacks. 632 5.1. Provision of Confidentiality Protection 634 Since the transported messages are linearly combined with random 635 coefficients at each recoding node, it is statistically impossible to 636 recover the individual messages by capturing the coded messages at 637 any one or small number of nodes. As long as the coding matrices of 638 the transported messages cannot be fully recovered, any attempt of 639 decoding any particular symbol of the transported messages is 640 equivalent to random guessing [Bhattad05]. 642 The threat towards confidentiality, however, also exists in the form 643 of eavesdropping on the initial encoding process, which takes place 644 at the encoding nodes. In these nodes, the transported data are 645 presented in plain text and can be read along their transfer paths. 646 Hence, information isolation between the encoding process and all 647 other user processes running on the node must be assured. 649 In addition, the authenticity and trustworthiness of the encoding, 650 recoding and decoding program running on all the nodes must be 651 attested by a trusted authority. Such a measure is also necessary in 652 countering pollution attacks. 654 5.2. Countermeasures against Pollution Attacks 656 Like all network codes, BATS codes are vulnerable under pollution 657 attacks. In these attacks, one or more compromised coding node(s) 658 can pollute the coded messages by injecting forged messages into the 659 coding network and thus prevent the receivers from recovering the 660 transported data correctly. 662 The research community has long been investigating the use of various 663 signature schemes (including homomorphic signatures) to identify the 664 forged messages and stall the attacks (see [Zhao07], [Yu08], 665 [Agrawal09]). However, these countermeasures are regarded as being 666 too computationally expensive to be employed in broadband 667 communications. Hence, a system-level approach based on Trusted 668 Computing [TC-Wikipedia] is proposed as a practical alternative to 669 protect BATS codes against pollution attacks. This Trusted Computing 670 based protection consists of the following countermeasures: 672 1. Attestation and Validation of all BATS encoding, recoding and 673 decoding nodes in the network. Remote attestation and repetitive 674 validation of the identity and capability of these node based on 675 valid public key certificates with proper authorization MUST be a 676 pre-requisite for admitting these nodes to a network and 677 permitting them to remain on that network. 679 2. Attestation of all encoding, recoding and decoding programs used 680 in the coding nodes. All programs used to perform the BATS 681 encoding, recoding and decoding processes MUST be remotely 682 attested before they are permitted to run on any of the coding 683 nodes. Reloading or alteration of programs MUST NOT be permitted 684 during an encoding session. Programs MUST be attested or 685 validated again when they are executed in new execution 686 environments instantiated even in the same node. 688 3. Original Authentication of all coded messages using network level 689 security protocols such as IPsec or Peer Authentication over 690 session-based communication using transport level security 691 protocols such as TLS/DTLS MUST be employed in order to provide 692 Message Origin or Communication Peer Authentication to every 693 coded message sent through the coding network. 695 6. Data Delivery Protocol Considerations 697 In addition to the security consideration, there are other issues to 698 be considered towards a fully functionally DDP based on the BATS 699 coding scheme described in this document. Here we discuss the 700 related routing and congestion control considerations, which are 701 research issues that need further elaborations. The general 702 information theoretical guideline is as follows: The outer code of a 703 BATS code can be regarded as a channel code for the channel induced 704 by the inner code, and hence the routing and congestion control 705 algorithms should try to maximize the capacity of the channel induced 706 by the inner code. 708 The BATS coding scheme is flexible for implementing multipath data 709 transmission. Different batches can be transmitted on a different 710 path between a source node and a destination node. For multicast, 711 however, we may allow the combination of certain batches during 712 recoding to improve the multicast throughput. Moreover, to benefit 713 from multiple source nodes, we would need different source node 714 generates statistically independent batches. 716 Congestion control for a DDP employing a BATS code scheme has several 717 extra design considerations. First, the end-to-end throughput should 718 be measured by the average rank rate (the total rank of all the 719 received batches over the time). Second, both the rate of 720 transmitting batches at the source nodes and the number of recoded 721 packets generated by recoding should be adjusted for congestion 722 control. Note that the number of recoded packets can be different 723 for different batch and at different node. Last but not the least, 724 for scenarios like wireless multihop networks, congestion control 725 needs to be performed hop-by-hop, instead of end-to-end as in TCP, 726 due to the high packet loss rate and the long end-to-end delay. 728 7. References 730 7.1. Normative References 732 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 733 Requirement Levels", BCP 14, RFC 2119, 734 DOI 10.17487/RFC2119, March 1997, 735 . 737 [RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., and E. Baccelli, 738 "TinyMT32 Pseudorandom Number Generator (PRNG)", RFC 8682, 739 DOI 10.17487/RFC8682, January 2020, 740 . 742 7.2. Informative References 744 [Agrawal09] 745 Agrawal, S. and D. Boneh, "Homomorphic MACs: MAC-based 746 integrity for network coding", International Conference on 747 Applied Cryptography and Network Security , 2009. 749 [BATS] Yang, S. and R. Yeung, "Batched Sparse Codes", IEEE 750 Transactions on Information Theory 60(9), 5322-5346, 2014. 752 [BATSMonograph] 753 Yang, S. and R. Yeung, "BATS Codes: Theory and Practice", 754 Morgan & Claypool Publishers , 2017. 756 [Bhattad05] 757 Bhattad, K. and K. Narayanan, "Weakly Secure Network 758 Coding", ISIT , 2007. 760 [RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T., 761 and L. Minder, "RaptorQ Forward Error Correction Scheme 762 for Object Delivery", RFC 6330, DOI 10.17487/RFC6330, 763 August 2011, . 765 [TC-Wikipedia] 766 "Trusted Computing", 767 Wikipedia https://en.wikipedia.org/wiki/Trusted_Computing. 769 [Yu08] Yu, Z., Wei, Y., Ramkumar, B., and Y. Guan, "An Efficient 770 Signature-Based Scheme for Securing Network Coding Against 771 Pollution Attacks", INFOCOM , 2008. 773 [Zhao07] Zhao, F., Kalker, T., Medard, M., and K. Han, "Signatures 774 for content distribution with network coding", ISIT , 775 2007. 777 Appendix A. Additional Stuff 779 This becomes an Appendix. 781 Authors' Addresses 783 Shenghao Yang 784 CUHK(SZ) 785 Shenzhen, Guangdong 786 China 788 Phone: +86 755 8427 3827 789 Email: shyang@cuhk.edu.cn 790 Xuan Huang 791 CUHK 792 Hong Kong, Hong Kong SAR 793 China 795 Phone: +852 3943 8375 796 Email: 1155136647@link.cuhk.edu.hk 798 Raymond W. Yeung 799 CUHK 800 Hong Kong, Hong Kong SAR 801 China 803 Phone: +852 3943 8375 804 Email: whyeung@ie.cuhk.edu.hk 806 John K. Zao 807 NCTU 808 Hsinchu, Taiwan 809 China 811 Email: jkzao@ieee.org