idnits 2.17.1 draft-yang-nwcrg-bats-03.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 (May 25, 2020) is 1432 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 513 == Missing Reference: 'K-1' is mentioned on line 513, but not defined == Missing Reference: 'K-2' is mentioned on line 214, but not defined == Missing Reference: 'T-P-1' is mentioned on line 217, but not defined == Missing Reference: 'T-P' is mentioned on line 217, but not defined == Missing Reference: 'T-1' is mentioned on line 343, but not defined == Missing Reference: 'WI' is mentioned on line 349, but not defined -- Looks like a reference, but probably isn't: '1' on line 513 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: November 26, 2020 R.W. Yeung 6 CUHK 7 J.K. Zao 8 NCTU 9 May 25, 2020 11 BATS Coding Scheme for Multi-hop Data Transport 12 draft-yang-nwcrg-bats-03 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 November 26, 2020. 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 . . . . . . . . . . . . . . . . . . . . . . 3 60 2.2. Data Delivery Procedures . . . . . . . . . . . . . . . . 4 61 2.2.1. Source Node Data Partitioning and Padding . . . . . . 5 62 2.2.2. Source Node Outer Code Encoding Procedure . . . . . . 5 63 2.2.3. Recoding Procedures . . . . . . . . . . . . . . . . . 7 64 2.2.4. Destination Node Procedures . . . . . . . . . . . . . 7 65 2.3. Recommendation for the Parameters . . . . . . . . . . . . 8 66 2.4. Example DDP Packet Format . . . . . . . . . . . . . . . . 8 67 2.4.1. Packet Header . . . . . . . . . . . . . . . . . . . . 8 68 2.4.2. Packet Payload . . . . . . . . . . . . . . . . . . . 9 69 2.4.3. Packet Footer . . . . . . . . . . . . . . . . . . . . 10 70 3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 10 71 3.1. Common Parts . . . . . . . . . . . . . . . . . . . . . . 10 72 3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 11 73 3.3. Inner Code Encoder (Recoder) . . . . . . . . . . . . . . 12 74 3.4. Belief Propagation Decoder . . . . . . . . . . . . . . . 13 75 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 76 5. Security Considerations . . . . . . . . . . . . . . . . . . . 13 77 5.1. Provision of Confidentiality Protection . . . . . . . . . 14 78 5.2. Countermeasures against Pollution Attacks . . . . . . . . 14 79 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 80 6.1. Normative References . . . . . . . . . . . . . . . . . . 15 81 6.2. Informative References . . . . . . . . . . . . . . . . . 15 82 Appendix A. Additional Stuff . . . . . . . . . . . . . . . . . . 16 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16 85 1. Introduction 87 This document specifies a BATS code [BATS] scheme for data delivery 88 in multi-hop networks. The BATS code described here includes an 89 outer code and an inner code. The outer code is a matrix 90 generalization of fountain codes (see also the RapterQ code described 91 in RFC 6330 [RFC6330]), which inherits the advantages of reliability 92 and efficiency and possesses the extra desirable property of being 93 network coding compatible. The inner code, also called recoding, is 94 formed by linear network coding for combating packet loss, improving 95 the multicast efficiency, etc. A detailed design and analysis of 96 BATS codes are provided in the BATS monograph [BATSMonograph]. 98 The BATS coding scheme can be applied in multi-hop networks formed by 99 wireless communication links, which are inherently unreliable due to 100 interference. Existing network protocols like TCP/IP use end-to-end 101 retransmission and store-and-forward at the relays, so that packet 102 loss would accumulate along the way. 104 The BATS coding scheme can be used for various data delivery 105 applications like file transmission, video streaming over wireless 106 multi-hop networks, etc. Different from traditional forward error 107 correcting (FEC) schemes that are applied either hop-by-hop or end- 108 to-end, the BATS coding scheme combines the end-to-end coding (the 109 outer code) with certain hop-by-hop coding (the inner code), and 110 hence can potentially achieve better performance. 112 The coding scheme described here can be used in a network with 113 multiple communication flows. For each flow, the source node encodes 114 the data for transmission separately. Inside the network, however, 115 it is possible to mix the packets from different flows for recoding. 116 In this document, we describe a simple case where recoding is 117 performed within each flow. Note that the same encoding/decoding 118 scheme described here can be used with different recoding schemes as 119 long as they follow the principle as we illustrate in this document. 121 1.1. Requirements Language 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 125 document are to be interpreted as described in RFC 2119 [RFC2119]. 127 2. Procedures 129 2.1. Introduction 131 A BATS coding scheme includes an outer code encoder (also called 132 encoder), an inner code encoder (also called recoder) and a decoder. 133 The BATS coding scheme can be used for a single data flow that 134 includes a single source and one or multiple destinations. Thus 135 there exists only one encoder with multiple recoders and decoders. 136 The BATS coding scheme described in this document can be used by a 137 Data Delivery Protocol (DDP) with the following procedures. 139 Outer Code Encoding at a source node which has the data for 140 transmission: 142 * The DDP provides the data to be delivered and the related 143 information to the BATS encoder. 145 * The BATS encoder generates a sequence of batches, each 146 consisting of a set of coded packets and the information 147 pertaining to the batch. 149 The batches generated at the source node are further recoded 150 before transmitting: 152 * A BATS recoder generates recoded packets of a batch. 154 * The DDP forms and transmits the DDP packets using the batches 155 and the corresponding batch information. 157 Recoding at an intermediate node that does not need the data: 159 * The DDP extracts the batches and the corresponding batch 160 information from its received DDP packets. 162 * A BATS recoder generates recoded packets of a batch. 164 * The DDP forms and transmits DDP packets using the recoded 165 packets and the corresponding batch information. 167 Decoding at a destination node that needs the data: 169 * The DDP extracts the batches and the corresponding batch 170 information from its received DDP packets. 172 * A BATS decoder tries to recover the transmitted data using the 173 received batches. 175 * The DDP sends the decoded data to the application that needs 176 the data. 178 2.2. Data Delivery Procedures 180 Suppose that the DDP has F octets of data for transmission. We 181 describe the procedures of one BATS session for transmitting the F 182 octets. There is a limit on F of a single BATS session. If the 183 total data has more than the limit, the data needs to be transmitted 184 using multiple BATS sessions. The limit on F of a single BATS 185 session depends on the MTU (maximum transmission unit) of the 186 network, which MUST be known by the DDP. We have F is no more than 187 (MTU-10)2^16-1 octets. 189 2.2.1. Source Node Data Partitioning and Padding 191 The DDP first determines the following parameters: 193 o Batch size (M): the number of coded packets in a batch. 195 o Recoding field size (q): the number of elements in the finite 196 field for recoding. q is 2 or 2^8 198 o BATS payload size (TO): the number of payload octets in a BATS 199 packet, including the coded data and the coefficient vector. 201 Based on the above parameters, the parameters T, O and K are 202 calculated as follows: 204 o O: the number of octets of a coefficient vector, calculated as O = 205 ceil(M*log2(q)/8). 207 o T: the number of data octets of a BATS packet, calculated as T = 208 TO - O. 210 o K: number of source packets, calculated as K = floor(F/T)+1. 212 The data MUST be padded to have T*K octets, which will be partitioned 213 into K source packets b[0], ..., b[K-1], each of T octets. In our 214 padding scheme, b[0], ..., b[K-2] are filled with data bits, and 215 b[K-1] is filled with the remaining data octets and padding octets. 216 Let P = K*T-F denote the number of padding octets. We use b[K-1, 0], 217 ..., b[K-1, T-P-1] to denote the T-P source octets and b[K-1, T-P], 218 ..., b[K-1, T-1] to denote the P padding octets in b[K-1], 219 respectively. The padding process is shown in Figure 1. 221 Z = T - P 222 Let bl be the last source packet b[K-1] 223 for i = 1, 2, ... do 224 if Z + i >= T - 1 do 225 bl[Z...T-1] = i 226 break 227 bl[Z...Z+i-1] = i 228 Z = Z + i 230 Figure 1: Data Padding Process 232 2.2.2. Source Node Outer Code Encoding Procedure 234 The DDP provides the BATS encoder with the following information: 236 o Batch size (M): the number of coded packets in a batch. 238 o Recoding field size (q): the number of elements in the finite 239 field for recoding. 241 o MAX_DEG: the size of DD. 243 o The degree distribution (DD), which is an unsigned integer array 244 of size MAX_DEG+1. 246 o A sequence of batch IDs (j, j = 0, 1, ...). 248 o Number of source packets (K). 250 o Packet size (T): the number of octets in a source packet. 252 o The source packets (b[i], i = 0, 1, ..., K-1). 254 Using this information, the (outer code) encoder generates a batch 255 for each batch ID. For the batch ID j, the encoder returns the DDP 256 that contains 258 o a sparse degree d[j], and 260 o M coded packets (x[j,i], i =0, 1, ..., M-1), each containing TO 261 octets. 263 The DDP will use the batches to form DDP packets to be transmitted to 264 other network nodes towards the destination nodes. The DDP MUST 265 deliver with each coded packet its 267 o d: sparse degree 269 o BID: batch ID 271 The DDP MUST deliver the following information to each recoder: 273 o M: batch size M 275 o q: recoding field size 277 The DDP MUST deliver the following information to each decoder: 279 o M: batch size 281 o q: recoding field size 283 o K: the number of source packet 285 o T: the number of octets in a source packet 286 The BATS payload size TO MUST be known by all the nodes. 288 2.2.3. Recoding Procedures 290 Both the source node and the intermediate nodes perform recoding on 291 the batches before transmission. At the source node, the recoder 292 receives the batches from the outer code encoding procedure. At an 293 intermediate node, the DDP receives the DDP packets from the other 294 network nodes, and should be able to extract coded packets and the 295 corresponding batch information from these packets. 297 The DDP provides the recoder with the following information: 299 o the batch size M, 301 o the recoding field size q, 303 o a number of received coded packets of the same batch, each 304 containing TO octets, and 306 o link statistics, e.g., packet loss rates. 308 For a received batch, the recoder determines a positive integer Mr, 309 the number of recoded packets to be transmitted for the batch. The 310 recoder uses the information provided by the DDP to generate Mr 311 recoded packets, each containing TO octets. The DDP uses the Mr 312 recoded packets to form the DDP packets for transmitting. 314 2.2.4. Destination Node Procedures 316 A destination node needs the data transmitted by the source node. At 317 the destination node, the DDP receives DDP packets from the other 318 network nodes, and should be able to extract coded packets and the 319 corresponding batch information from these packets. 321 The DDP provides the decoder with the following information: 323 o M: batch size, 325 o q: recoding field size, 327 o K: the number of source packets 329 o T: the number of octets of a source packet 331 o A sequence of batches, each of which is formed by a number of 332 coded packets belonging to the same batch, with their 333 corresponding batch IDs and degrees. 335 The decoder uses this information to decode the K source packets. If 336 successful, the decoder returns the recovered K source packets to the 337 DDP, which will use the K source packets to form the F octets data. 338 The recommended padding process is shown as follows: 340 // this procedure returns the number P of padding octets 341 // at the end of b[K-1] 342 Let bl be the last decoded source packet b[K-1] 343 PL = bl[T-1] 344 if PL == 1 do 345 return P = 1 346 WI = T - 1 347 while bl[WI] == PL do 348 WI = WI - 1 349 return P = (1 + bl[WI]) * bl[WI] + T - WI - 1 351 Figure 2: Data Depadding Process 353 2.3. Recommendation for the Parameters 355 The recommendation for the parameters M and q is shown as follows: 357 o When q=2, M=16,32,64 359 o When q=256, M=8,16,32,64 361 It is RECOMMENDED that K is at least 128. However, the encoder/ 362 decoder SHALL support an arbitrary positive integer value less than 363 2^16. 365 2.4. Example DDP Packet Format 367 A DDP can form a DDP packet with a header (5 octets), a footer (3 368 octets) and a payload (TO octets). A DDP packet has totally 8+TO 369 octets. 371 2.4.1. Packet Header 373 The BATS packet header has 40 bits (5 octets) and includes fields 374 Packet_Count, Mq, Batch_ID, and Degree. 376 0 1 2 3 377 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 378 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 379 | Packet_Count | Mq | Batch_ID | 380 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 381 | Degree | 382 +-+-+-+-+-+-+-+-+ 384 Figure 3: BATS packet header format. 386 o Packet_Count: 16-bit unsigned integer, specifying the number K of 387 packets of the BATS session. 389 o Mq: 4-bit unsigned integer to specify the value of M and q as 390 Table 1. 392 o Batch_ID: 12-bit unsigned integer, specifying the batch ID BID of 393 the batch the packet belonging to. 395 o Degree: 8-bit unsigned integer, specifying the batch degree d of 396 the batch the packet belonging to. 398 +------+----+-----+----+ 399 | Mq | M | q | O | 400 +------+----+-----+----+ 401 | 0010 | 16 | 2 | 2 | 402 | 0100 | 32 | 2 | 4 | 403 | 0110 | 64 | 2 | 8 | 404 | 0001 | 8 | 256 | 8 | 405 | 0011 | 16 | 256 | 16 | 406 | 0101 | 32 | 256 | 32 | 407 | 0111 | 64 | 256 | 64 | 408 +------+----+-----+----+ 410 Table 1: Values of Mq field 412 2.4.2. Packet Payload 414 O T 415 +-----------------------+-------------------------------+ 416 | coefficient vector | coded data | 417 +-----------------------+-------------------------------+ 419 Figure 4: BATS packet payload format. 421 The payload has TO octets, where the first O octets contain the 422 coefficient vector and the remaining T octets contain the coded data. 424 Information in both fields MAY be encoded in JSON (ASCII) or protobuf 425 (binary) formats. 427 o coefficient vector: O octets. The range of the value of O is in 428 Table 1. 430 o coded data: T octets. T is at most MTU - 10, where 10 is the 431 total of the header and footer length plus the minimum value of O. 433 2.4.3. Packet Footer 435 0 1 2 436 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 437 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 438 | signature | parity check | 439 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 441 Figure 5: BATS packet footer format. 443 The footer has three octets. 445 o signature: 2 octets. A signature of the individual packet to 446 prevent pollution attack. 448 o parity check: 1 octet. A parity check field used to verity the 449 correctness of the packet. 451 3. BATS Code Specification 453 3.1. Common Parts 455 The T octets of a source packets are treated as a column vector of T 456 elements in GF(256). Linear algebra and matrix operations over 457 finite fields are assumed in this section. 459 Suppose that a pseudorandom number generator Rand() which generate an 460 unsigned integer of 32 bits is shared by both encoding and decoding. 461 The pseudorandom generator can be initialized by Rand_Init(S) with 462 seed S. When S is not provided, the pseudorandom generator is 463 initialized arbitrarily. One example of such a pseudorandom 464 generator is defined in RFC 8682 [RFC8682]. 466 A function called BatchSampler is used in both encoding and decoding. 467 The function takes two integers j and d as input, and generates an 468 array idx of d integers and a d x M matrix G. The function first 469 initializes the pseudorandom generator with j, sample d distinct 470 integers from 0 to K-1 as idx, and sample d*M integers from 0 to 255 471 as G. See the pseudocode in Figure 6. 473 function BatchSampler(j,d) 474 // initialize the pseudorandom generator by seed j. 475 Rand_Init(j) 476 // sample d distinct integers between 0 and K-1. 477 for k = 0, ..., d-1 do 478 r = Rand() % K 479 while r already exists in idx do 480 r = Rand() % K 481 idx[k] = r 483 // sample d x M matrix 484 for r = 0, ..., d-1 do 485 for c = 0,...,M-1 do 486 G[r,c] = Rand() % 256 488 return idx, G 490 Figure 6: Batch Sampler Function 492 3.2. Outer Code Encoder 494 Define a function called DegreeSampler that return an integer d using 495 the degree distribution DD. We expect that the empirical 496 distribution of the returning d converges to DD(d) when d < K. One 497 design of DegreeSampler is illustrated in Figure 7. 499 function DegreeSampler(j, DD) 500 Let CDF be an array 501 CDF[0] = 0 502 for i = 1, ..., MAX_DEG do 503 CDF[i] = CDF[i-1] + DD[i] 504 Rand_Init() 505 r = Rand() % CDF[MAX_DEG] 506 for d = 1, ..., MAX_DEG do 507 if r >= CDF[d] do 508 return min(d,K) 509 return min(MAX_DEG,K) 511 Figure 7: Degree Sampler Function 513 Let b[0], b[1], ..., b[K-1] be the K source packets. A batch with 514 BID j is generated using the following steps. 516 o Obtain a degree d by calling DegreeSampler with input j. 518 o Obtain idx and G[j] by calling BatchSampler with input j and d. 520 o Let B[j] = (b[idx[0]], b[idx[1]], ..., b[idx[d-1]]). Form the 521 batch X[j] = B[j]*G[j], whose dimension is T x M. 523 o Form the TO x M matrix Xr[j], where the first O rows of Xr[j] form 524 the M x M identity matrix I with entries in GF(q), and the last T 525 rows of Xr[j] is X[j]. 527 See the pseudocode of the batch generating process in Figure 8. 529 function GenBatch(j) 530 d = DegreeSampler(j) 531 (idx, G) = BatchSampler(j,d) 532 B = (b[idx[0]], b[idx[i]], ..., b[idx[d-1]]) 533 X = B * G 534 Xr = [I_M; X] 535 return Xr 537 Figure 8: Batch Generation Function 539 3.3. Inner Code Encoder (Recoder) 541 The inner code comprises (random) linear network coding applied on 542 the coded packets belonging to the same batch. At a particular 543 network node, recoded packets are generated by (random) linear 544 combinations of the received coded packets of a batch. The recoded 545 packets have the same BID, sparse degree and coded packet length. 547 The number Mr of recoded packets for a batch is decided first by the 548 recoder. Mr can be set as M. When the link statistics is known, the 549 recoder can try to obtain the link packet loss rate e for the link to 550 transmit the recoded batch, and set Mr to be (1+e)M. 552 Suppose that coded packets xr[i], i = 0, 1, ..., r-1, which have the 553 same BID j, have been received at an intermediate node. Using the 554 recommended packet format, it can be verified whether the 555 corresponding packet headers of these coded packets are the same. 556 Then a recoded packet can be generated by one of the following two 557 approaches: 559 o forwarding: when receiving xr[i], directly use xr[i] as a recoded 560 packet. 562 o linear combination recoding: (randomly) choose a sequence of 563 coefficients c[i], i = 0, 1, ..., r-1 from GF(q). Generate 564 c[0]xr[0]+c[1]xr[1]+...+c[r-1]xr[r-1] as a recoded packet. 566 A recoder can combine these two approaches to generate recoded 567 packets. For example, the recoder will output xr[i], i = 0, 1, ..., 568 r-1 as r systematic recoded packets and generate Mr-r recoded packets 569 using linear combinations of randomly chosen coefficients. 571 3.4. Belief Propagation Decoder 573 The decoder receives a sequence of batches Yr[j], j = 0, 1, ..., n-1, 574 each of which is a TO-row matrix over GF(256). The degree d[j] of 575 batch j is also known. Let Y[j] be the submatrix of the last T rows 576 of Yr[j]. When q = 256, let H[j] be the first M rows of Yr[j]; when 577 q = 2, let H[j] be the matrix over GF(256) formed by embedding each 578 bit in the first M/8 rows of Yr[j] into GF(256). 580 By calling BatchSampler with input j and d[j], we obtain idx[j] and 581 G[j]. According to the encoding and recoding processes described in 582 Section 3.2 and Section 3.3, we have the system of linear equations 583 Y[j] = B[j]G[j]H[j] for each received batch with ID j, where B[j] = 584 (b[idx[j,0]], b[idx[j,1]], ..., b[idx[j,d-1]]) is unknown. 586 We describe a belief propagation (BP) decoder that can efficiently 587 solve the source packets when a sufficient number of batches have 588 been received. A batch j is said to be decodable if rank(G[j]H[j]) = 589 d[j] (i.e., the system of linear equations Y[j] = B[j]G[j]H[j] with 590 B[j] as the variable matrix has a unique solution). The BP decoding 591 algorithm has multiple iterations. Each iteration is formed by the 592 following steps: 594 o Decoding step: Find a batches j that is decodable. Solve the 595 corresponding system of linear equations Y[j] = B[j]G[j]H[j] and 596 decode B[j]. 598 o Substitution step: Substitute the decoded source packets into 599 undecodable batches. Suppose that a decoded source packet b[k] is 600 used in generating a undecodable Y[j]. The substitution involves 601 1) removing the entry in idx[j] corresponding to k, 2) removing 602 the row in G[j] corresponding to b[k], and 3) reducing d[j] by 1. 604 The BP decoder repeats the above steps until no batches are decodable 605 during the decoding step. 607 4. IANA Considerations 609 This memo includes no request to IANA. 611 5. Security Considerations 613 Subsuming both Random Linear Network Codes (RLNC) and fountain codes, 614 BATS codes naturally inherit both their desirable capability of 615 offering confidentiality protection as well as their vulnerability 616 towards pollution attacks. 618 5.1. Provision of Confidentiality Protection 620 Since the transported messages are linearly combined with random 621 coefficients at each recoding node, it is statistically impossible to 622 recover the individual messages by capturing the coded messages at 623 any one or small number of nodes. As long as the coding matrices of 624 the transported messages cannot be fully recovered, any attempt of 625 decoding is equivalent to randomly guessing the transported messages. 626 Thus, with the use of BATS codes, information confidentiality 627 throughout the data transport process is assured. 629 The only threat towards confidentiality exists in the form of 630 eavesdropping on the initial encoding process, which takes place at 631 the encoding nodes. In these nodes, the transported data are 632 presented in plain text and can be read along their transfer paths. 633 Hence, information isolation between the encoding process and all 634 other user processes running on the node must be assured. 636 In addition, the authenticity and trustworthiness of the encoding, 637 recoding and decoding program running on all the nodes must be 638 attested by a trusted authority. Such a measure is also necessary in 639 countering pollution attacks. 641 5.2. Countermeasures against Pollution Attacks 643 Like all network codes, BATS codes are vulnerable under pollution 644 attacks. In these attacks, one or more compromised coding node(s) 645 can pollute the coded messages or inject forged messages into the 646 coding network. These attacks can prevent the receivers from 647 recovering the transported data correctly. Although error detection 648 mechanisms can be put in place to prevent the receivers from getting 649 the wrong messages, detection and discard of the polluted messages 650 still constitute a form of denial-of-service (DoS) attack. 652 The research community has long been investigating the use of various 653 signature schemes (including homomorphic signatures) to identify the 654 forged messages and stall the attacks (see Zhao07 [Zhao07], Yu08 655 [Yu08], Agrawal09 [Agrawal09]). Nevertheless, these countermeasures 656 are regarded as being computationally too expensive to be employed in 657 broadband communications. A practical approach to protect against 658 pollution attacks consist of the following system-level 659 countermeasures: 661 1. Attestation and Validation of all encoding, recoding and decoding 662 nodes in the network. Remote attestation and repetitive 663 validation of a node based on valid public key certificates with 664 proper authorization MUST be a pre-requisite for admitting that 665 node to a network and permitting it to remain in that network. 667 2. Attestation of all encoding, recoding and decoding programs used 668 in the coding nodes. All programs used to perform the BATS 669 encoding, recoding and decoding processes MUST be remotely 670 attested before they are permitted to run on any of the coding 671 nodes. Reloading or alteration of programs MUST NOT be permitted 672 during an encoding session. Programs MUST be attested or 673 validated again when they are executed in new execution 674 environments instantiated even in the same node. 676 3. Original Authentication of all coded messages using network or 677 transport level secure protocols such as IP-sec or TLS/DTLS MUST 678 be used to provide Peer or Message Origin Authentication to every 679 coded message sent through the coding network. 681 6. References 683 6.1. Normative References 685 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 686 Requirement Levels", BCP 14, RFC 2119, 687 DOI 10.17487/RFC2119, March 1997, 688 . 690 [RFC8682] Saito, M., Matsumoto, M., Roca, V., Ed., and E. Baccelli, 691 "TinyMT32 Pseudorandom Number Generator (PRNG)", RFC 8682, 692 DOI 10.17487/RFC8682, January 2020, 693 . 695 6.2. Informative References 697 [Agrawal09] 698 Agrawal, S. and D. Boneh, "Homomorphic MACs: MAC-based 699 integrity for network coding", International Conference on 700 Applied Cryptography and Network Security , 2009. 702 [BATS] Yang, S. and R. Yeung, "Batched Sparse Codes", IEEE 703 Transactions on Information Theory 60(9), 5322-5346, 2014. 705 [BATSMonograph] 706 Yang, S. and R. Yeung, "BATS Codes: Theory and Practice", 707 Morgan & Claypool Publishers , 2017. 709 [RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T., 710 and L. Minder, "RaptorQ Forward Error Correction Scheme 711 for Object Delivery", RFC 6330, DOI 10.17487/RFC6330, 712 August 2011, . 714 [Yu08] Yu, Z., Wei, Y., Ramkumar, B., and Y. Guan, "An Efficient 715 Signature-Based Scheme for Securing Network Coding Against 716 Pollution Attacks", INFOCOM , 2008. 718 [Zhao07] Zhao, F., Kalker, T., Medard, M., and K. Han, "Signatures 719 for content distribution with network coding", ISIT , 720 2007. 722 Appendix A. Additional Stuff 724 This becomes an Appendix. 726 Authors' Addresses 728 Shenghao Yang 729 CUHK(SZ) 730 Shenzhen, Guangdong 731 China 733 Phone: +86 755 8427 3827 734 Email: shyang@cuhk.edu.cn 736 Xuan Huang 737 CUHK 738 Hong Kong, Hong Kong SAR 739 China 741 Phone: +852 3943 8375 742 Email: 1155136647@link.cuhk.edu.hk 744 Raymond W. Yeung 745 CUHK 746 Hong Kong, Hong Kong SAR 747 China 749 Phone: +852 3943 8375 750 Email: whyeung@ie.cuhk.edu.hk 751 John K. Zao 752 NCTU 753 Hsinchu, Taiwan 754 China 756 Email: jkzao@ieee.org