idnits 2.17.1 draft-yang-nwcrg-bats-code-00.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 (October 20, 2018) is 2014 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '256' on line 296 -- Looks like a reference, but probably isn't: '0' on line 303 -- Looks like a reference, but probably isn't: '1' on line 303 == Missing Reference: 'K-1' is mentioned on line 303, but not defined Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 4 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 X. Huang 4 Intended status: Informational CUHK(SZ) 5 Expires: April 23, 2019 R.W. Yeung 6 CUHK 7 J. Zao 8 NCTU 9 October 20, 2018 11 BATS Code Scheme for Multi-hop File Delivery 12 draft-yang-nwcrg-bats-code-00 14 Abstract 16 This document describe a BATS code scheme for communication through a 17 multi-hop network. BATS code is a class of efficient linear network 18 coding scheme with a matrix generalization of fountain codes as the 19 outer code, and batch-based linear network coding as the inner code. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at https://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on April 23, 2019. 38 Copyright Notice 40 Copyright (c) 2018 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (https://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 57 2. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . 3 59 2.2. File Partitioning and Padding . . . . . . . . . . . . . . 4 60 2.3. File Delivery Procedures . . . . . . . . . . . . . . . . 4 61 2.3.1. Source Node Procedures . . . . . . . . . . . . . . . 4 62 2.3.2. Intermediate Node Procedures . . . . . . . . . . . . 5 63 2.3.3. Destination Node Procedures . . . . . . . . . . . . . 6 64 2.4. Recommandation for the Parameters . . . . . . . . . . . . 6 65 2.5. Example FDP Packets . . . . . . . . . . . . . . . . . . . 7 66 3. BATS Code Specification . . . . . . . . . . . . . . . . . . . 7 67 3.1. Background . . . . . . . . . . . . . . . . . . . . . . . 7 68 3.2. Outer Code Encoder . . . . . . . . . . . . . . . . . . . 7 69 3.3. Inner Code Encoder (Recoder) Recommandations . . . . . . 7 70 3.4. Decoder Recommandations . . . . . . . . . . . . . . . . . 8 71 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 72 5. Security Considerations . . . . . . . . . . . . . . . . . . . 8 73 5.1. Provision of Confidentiality Protection . . . . . . . . . 8 74 5.2. Countermeasures against Pollution Attacks . . . . . . . . 8 75 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 76 6.1. Normative References . . . . . . . . . . . . . . . . . . 9 77 6.2. Informative References . . . . . . . . . . . . . . . . . 9 78 Appendix A. Additional Stuff . . . . . . . . . . . . . . . . . . 10 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 81 1. Introduction 83 This document specifies a BATS code [BATS] scheme for file delivery 84 applications in multi-hop networks. The BATS code described here 85 includes an outer code and an inner code. The outer code is a matrix 86 generalization of the fountain codes (see also the RapterQ code 87 described in RFC 6330 [RFC6330]), which inherits the advantages of 88 reliability and efficiency and possesses the extra desirable property 89 of being network coding compatible. The inner code is formed by 90 linear network coding for combating packet loss, improving the 91 multicast efficiency, etc. A detailed design and analysis of BATS 92 codes are provided in BATSMonograph [BATSMonograph]. 94 1.1. Requirements Language 96 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 97 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 98 document are to be interpreted as described in RFC 2119 [RFC2119]. 100 2. Procedures 102 2.1. Introduction 104 A BATS code scheme includes an outer code encoder (also called 105 encoder), an inner code encoder (also called recoder) and a decoder. 106 The BATS code scheme described in this document can be used by a File 107 Delivery Protocol (FDP) with the following procedures. 109 Encoding at a source node which has the file for transmission: 111 * The FDP provides the file to be delivered and the related 112 information to the BATS encoder. 114 * The BATS encoder generates a sequence of batches, each 115 consisting of a set of coded packets and the information 116 pertaining to the batch. 118 * The FDP forms and transmits the FDP packets using the batches 119 and the corresponding batch information. 121 Recoding at an intermediate node that does not need the file: 123 * The FDP extracts the batches and the corresponding batch 124 information from its received FDP packets. 126 * A BAST recoder generates recoded packets of a batch. 128 * The FDP forms and transmits FDP packets using the recoded 129 packets and the corresponding batch information. 131 Decoding at a destination node that needs the file: 133 * The FDP extracts the batches and the corresponding batch 134 information from its received FDP packets. 136 * A BATS decoder tries to recover the transmitted file using the 137 received batches. 139 * The FDP sends the decoded file to the application that needs 140 the file. 142 2.2. File Partitioning and Padding 144 Suppose that the FDP has a file of F octets for transmission. The 145 construction of source packets from the file depends on two 146 parameters K and T: 148 o K: the number of source packets. 150 o T: the size of a source packet, in octets. 152 If F is smaller than T*K, the file needs to be padded to have T*K 153 octets, so that file can be partitioned into K source packets, each 154 of which has T octets. 156 2.3. File Delivery Procedures 158 2.3.1. Source Node Procedures 160 A source node has the file for transmission. The FDP will first pad 161 and partition the file into K source packets, each containing T 162 octets. The FDP provides the BATS encoder with the following 163 information: 165 o Batch size (M): the number of coded packets in a batch. 167 o Recoding field size (q): the number of elements in the finite 168 field for recoding. 170 o The degree distribution (DD), optional. 172 o A sequence of batch IDs (ID[i],i=0,1,...). 174 o Number of source packets (K). 176 o Packet size (T): the number of octets in a source packet. 178 o The source packets (b[i],i=0,1,...,K-1). 180 Using this information, the (outer code) encoder generates a batch 181 for each batch ID. For each batch ID, the encoder returns the FDP 183 o a sparse degree (d), and 185 o M coded packets (X'[i],i=0,1,...,M-1), each containing T' octets. 187 Here T' = T + M*ceil(log2(q))/8. 189 The FDP will use the batches to form FDP packets to be transmitted to 190 other network nodes towards the destination nodes. The FDP MUST 191 deliver with each coded packet its 193 o sparse degree, 195 o batch ID and certain extra information so that any receiver of the 196 coded packets of the batch can know whether the coded packets are 197 in the same batch or not, and whether two different batches are 198 generated from the same file or not. 200 The FDP MUST deliver the following information to each recoder: 202 o batch size M, and 204 o recoding field size q. 206 The FDP MUST deliver the following information to each decoder: 208 o batch size M, 210 o recoding field size q, 212 o the file size F, and 214 o the number of source packet K. 216 The packet length information is assumed to be known by all the 217 nodes. 219 2.3.2. Intermediate Node Procedures 221 An intermediate node does not need the file, but only helps to 222 deliver the file to the destination nodes. At an intermediate node, 223 the FDP only receives the FDP packets from the other network nodes, 224 and should be able to extract coded packets and the corresponding 225 batch information from these packets. 227 The FDP provides the recoder with the following information: 229 o the batch size M, 231 o the recoding field size q, 233 o a number of received coded packets of the same batch, each 234 containing T' octets, and 236 o a number M' of recoded packets to be generated. 238 The recoder uses the information provided by the FDP to generate M' 239 recoded packets, each containing T' octets. The FDP uses the M' 240 recoded packets to form the FDP packets for transmitting. 242 2.3.3. Destination Node Procedures 244 A destination node needs the file transmitted by the source node. At 245 the destination node, the FDP receives FDP packets from the other 246 network nodes, and should be able to extract coded packets and the 247 corresponding batch information from these packets. 249 The FDP provides the decoder with the following information: 251 o F: number of octets in the file, 253 o M: batch size, 255 o q: recoding field size, 257 o K: number of source packets 259 o A sequence of batches with their corresponding batch IDs and 260 degrees. 262 The decoder uses this information to decode the K source packets. If 263 successful, the decoder returns the recovered K source packets to the 264 FDP, which will use the source packets to form the source file. 266 2.4. Recommandation for the Parameters 268 The recommendation for the parameters M, K, T, and T' is shown as 269 follows: 271 o M is 8, 16 or 32. 273 o q is 2, 4, 8, 16, 32, 64, 128 or 256. 275 o T' is not larger than the maximum coded packet payload size. 277 o T = T' - M*ceil(log2(q))/8. 279 o K = ceil(F/T). 281 It is RECOMMENDED that K is at least 128. However, the encoder/ 282 decoder SHALL support an arbitrary positive integer value of K. 284 2.5. Example FDP Packets 286 A FDP can form a FDP packet by appending a header and a footer to 287 each coded packets. 289 The header should include F, M, K, q, batch ID, and degree. 291 3. BATS Code Specification 293 3.1. Background 295 The T octets of a source packets are treated as a column vector of T 296 elements in GF[256]. Linear algebra and matrix operations over 297 finite fields are assumed in this section. 299 Assume that a pseudo-random number generator Rand() is given. 301 3.2. Outer Code Encoder 303 Let b[0], b[1], ...,b[K-1] be the K source packets. A batch with 304 batch ID bID is generated in the following steps. 306 First, a degree DEG=DEG(bID) is sampled using the give degree 307 distribution and Rand() with the default seed. After that, 308 initialize Rand() with bID as the seed. 310 Second, using Rand() sample DEG packets among all the source packets. 311 Suppose the indices of the packets sampled are i_1, i_2, ..., i_DEG. 313 Third, sample a DEGxM generator matrix G. 315 Fourth, form the batch X = (b[i_1], b[i_2], ..., b[i_DEG])*G, where 316 each column is a coded packet of the batch. 318 Last, append coefficient vectors to the packets of the batches. Let 319 X[i], i=0,1,...,M-1, be the (i+1)th column of X. The coefficient 320 vector of X[i] is the (i+1)th column of the MxM identity matrix with 321 entries in GF(q), which can be represented by M*log2(q)/8 octets. 322 The coded packet X'[i] is formed by appending the coefficient vector 323 before X[i]. 325 3.3. Inner Code Encoder (Recoder) Recommandations 327 The inner code comprises (random) linear network coding applied on 328 the coded packets belonging to the same batch. At a particular 329 network node, recoded packets are generated by (random) linear 330 combinations of the received coded packets of a batch. The recoded 331 packets have the same batch ID, sparse degree and coded packet 332 length. 334 3.4. Decoder Recommandations 336 The belief propagation decoding algorithm suggested in the BATS code 337 paper [BATS] is recommanded. 339 4. IANA Considerations 341 This memo includes no request to IANA. 343 5. Security Considerations 345 Subsuming both Random Linear Network Codes (RLNC) and fountain codes, 346 BATS codes naturally inherit both their desirable capability of 347 offering confidentiality protection as well as their vulnerability 348 towards pollution attacks. 350 5.1. Provision of Confidentiality Protection 352 Since the transported messages are linearly combined with random 353 coefficients at each recoding node, it is statistically impossible to 354 recover individual messages by capturing the coded messages at any 355 one or small number of nodes. As long as the coding matrices of the 356 transported messages cannot be fully recovered, any attempt of 357 decoding is equivalent to randomly guessing the transported messages. 358 Thus, with the use of BATS codes, information confidentiality 359 throughout the data transport process is assured. 361 The only thread towards confidentiality exists in the form of 362 eavesdropping onto the initial encoding process, which takes place at 363 the encoding nodes. In these nodes, the transported files are 364 presented in plain text and can be read along their transfer paths. 365 Hence, information isolation between the encoding process and all 366 other user processes running on the node must be assured. 368 In addition, the authenticity and trustworthiness of the encoding, 369 recoding and decoding program running on all the nodes must be 370 attested by a trusted authority. Such a measure is also necessary in 371 countering the pollution attacks. 373 5.2. Countermeasures against Pollution Attacks 375 Like all network codes, BATS codes are vulnerable under pollution 376 attacks. In these attacks, one or more compromised coding node(s) 377 can pollute the coded messages or inject forged messages into the 378 coding network. These attacks can prevent the receivers from 379 recovering the transported files correctly. Although error detection 380 mechanisms can be put in place to prevent the receivers from getting 381 the wrong messages, detection and discard of the polluted messages 382 still constitute a form of denial-of-service (DoS) attack. 384 The research community has long been investigating the use of various 385 signature schemes (including homomorphic signatures) to identify the 386 forged messages and stall the attacks (see Zhao07 [Zhao07], Yu08 387 [Yu08], Agrawal09 [Agrawal09]). Nevertheless, these counter measures 388 are regarded as being computationally to expensive to be employed in 389 broadband communications. A practical approach to protect against 390 pollution attacks consists of the following system-level 391 countermeasures: 393 1. Attestation and Validation of all encoding, recoding and decoding 394 nodes in the network. Remote attestation and repetitive 395 validation of a node based on valid public key certificates with 396 proper authorization MUST be a pre-requisite of admitting that 397 node into a network and permitting it to remain in that network. 399 2. Attestation of all encoding, recoding and decoding programs used 400 in the coding nodes. All programs used to perform the BATS 401 encoding, recoding and decoding processes MUST be remotely 402 attested before they are permitted to run on any of the coding 403 nodes. Reloading or alteration of programs MUST NOT be permitted 404 during an encoding session. Programs MUST be attested or 405 validated again when they are executed in new execution 406 environments instantiated even in the same nodes. 408 3. Original Authentication of all coded messages using network or 409 transport level secure protocols such as IP-sec or TLS/DTLS MUST 410 be used to provide Peer or Message Origin Authentication to every 411 coded message sent through the coding network. 413 6. References 415 6.1. Normative References 417 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 418 Requirement Levels", BCP 14, RFC 2119, 419 DOI 10.17487/RFC2119, March 1997, 420 . 422 6.2. Informative References 424 [Agrawal09] 425 S. Agrawal and D. Boneh, "Homomorphic MACs: MAC-based 426 integrity for network coding", International Conference on 427 Applied Cryptography and Network Security , 2009. 429 [BATS] S. Yang and R.W. Yeung, "Batched Sparse Codes", IEEE 430 Transactions on Information Theory 60(9), 5322-5346, 2014. 432 [BATSMonograph] 433 S. Yang and R.W. Yeung, "BATS Codes: Theory and Practice", 434 Morgan & Claypool Publishers , 2017. 436 [RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T., 437 and L. Minder, "RaptorQ Forward Error Correction Scheme 438 for Object Delivery", RFC 6330, DOI 10.17487/RFC6330, 439 August 2011, . 441 [Yu08] Z. Yu, Y. Wei, B. Ramkumar, and Y. Guan, "An Efficient 442 Signature-Based Scheme for Securing Network Coding Against 443 Pollution Attacks", NFOCOM , 2008. 445 [Zhao07] F. Zhao, T. Kalker, M. Medard, and K.J. Han, "Signatures 446 for content distribution with network coding", ISIT , 447 2007. 449 Appendix A. Additional Stuff 451 This becomes an Appendix. 453 Authors' Addresses 455 Shenghao Yang 456 CUHK(SZ) 457 Shenzhen, Guangdong 458 China 460 Phone: +86 755 8427 3827 461 Email: shyang@cuhk.edu.cn 463 Xuan Huang 464 CUHK(SZ) 465 Shenzhen, Guangdong 466 China 468 Phone: +86 755 8427 3814 469 Email: 115010159@link.cuhk.edu.cn 470 Raymond W. Yeung 471 CUHK 472 Hong Kong, Hong Kong SAR 473 China 475 Phone: +852 3943 8375 476 Email: whyeung@ie.cuhk.edu.hk 478 John Zao 479 NCTU 480 Hsinchu, Taiwan 481 China 483 Email: jkzao@ieee.org