idnits 2.17.1 draft-shen-rmt-bb-fec-srrscode-01.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 : ---------------------------------------------------------------------------- ** There are 7 instances of too long lines in the document, the longest one being 5 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 55 has weird spacing: '... and rate-i...' == Line 61 has weird spacing: '...adamard trans...' == Line 62 has weird spacing: '...rection schem...' == Line 63 has weird spacing: '...near if penal...' == Line 101 has weird spacing: '...tematic and ...' == (15 more instances...) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '0' is mentioned on line 330, but not defined -- Looks like a reference, but probably isn't: 'N-1' on line 330 -- Looks like a reference, but probably isn't: 'RFC2119' on line 710 -- Looks like a reference, but probably isn't: 'RFC5052' on line 728 -- Possible downref: Non-RFC (?) normative reference: ref. '2' Summary: 1 error (**), 0 flaws (~~), 8 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Reliable Multicast Transport B. Shen 2 Internet Draft Broadcom 3 Intended status: Standards Track E. Stauffer 4 Expires: May 2013 Broadcom 5 K. Rath 6 Broadcom 7 November 14,2012 9 Systematic Rate-independent Reed-Solomon (SR-RS) Erasure Correction 10 Scheme 11 draft-shen-rmt-bb-fec-srrscode-01.txt 13 Status of this Memo 15 This Internet-Draft is submitted in full conformance with the 16 provisions of BCP 78 and BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six 24 months and may be updated, replaced, or obsoleted by other documents 25 at any time. It is inappropriate to use Internet-Drafts as 26 reference material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html 34 This Internet-Draft will expire on May 16, 2013. 36 Copyright Notice 38 Copyright (c) 2012 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with 46 respect to this document. Code Components extracted from this 47 document must include Simplified BSD License text as described in 48 Section 4.e of the Trust Legal Provisions and are provided without 49 warranty as described in the Simplified BSD License. 51 Abstract 53 This document specifies a systematic rate-independent Reed-Solomon 54 (SR-RS) Erasure correction scheme. The two properties, systematic 55 and rate-independent, are fulfilled by Lagrange polynomial 56 interpolation. When the number of output symbols is fixed this 57 scheme essentially generates a Reed-Solomon (RS) code. Therefore, 58 based on the MDS (maximum distance separable) property of RS code, 59 this erasure correction scheme is optimal (ideal). Also in this 60 document, a two-step fast recovering (decoding) algorithm using fast 61 Walsh-Hadamard transform is presented for the proposed erasure 62 correction scheme. This algorithm achieves the time complexity 63 O(n*log2(n)), or linear if penalization implementation, such as 64 multi-core processor, is allowed. 66 Contents 67 1. Introduction...................................................3 68 2. Source file segmentation.......................................3 69 2.1. Transmit block............................................4 70 2.1.1. Working Blocks.......................................4 71 2.2. Parameter Selection.......................................4 72 2.3. Overview of systematic rate-independent encoding ........5 73 2.4. Parameters and functions used in SR-RS encoding...........6 74 2.5. SR-RS encoding............................................7 75 3. SR-RS decoder..................................................8 76 3.1. Overview of SR-RS decoding................................8 77 3.2. SR-RS decoding principle..................................9 78 3.3. A realization of the decoding principle: two-step SR-RS 79 decoding (informative)........................................10 80 3.4. Fast decoding (informative)..............................11 81 3.4.1. Hadamard matrices...................................11 82 3.4.2. Walsh-Hadamard transform............................11 83 3.4.3. Fast Walsh-Hadamard transform.......................12 84 3.4.4. Fast SR-RS decoding using fast WHT..................13 85 4. Protocol IEs..................................................15 86 4.1. FEC Payload IEs..........................................15 87 4.2. Common...................................................15 88 4.3. Scheme Specific..........................................16 89 5. Conventions used in this document.............................16 90 6. Security Considerations.......................................17 91 7. IANA Considerations...........................................17 92 8. References....................................................17 93 8.1. Normative References.....................................17 94 8.2. Informative References...................................17 95 9. Acknowledgments...............................................17 97 1. Introduction 99 This document specifies and explains a systematic rate-independent 100 Reed-Solomon (SR-RS) Erasure correction scheme. The two properties, 101 systematic and rate-independent, are fulfilled by Lagrange 102 polynomial interpolation. When the number of output symbols is fixed 103 this scheme essentially generates a Reed-Solomon (RS) code. 104 Therefore, based on the MDS (maximum distance separable) property of 105 RS code [3], this erasure correction scheme is optimal (ideal), i.e. 106 when the number of un-erased packets is equal to the number of 107 source packets, the entire source packets can be recovered. 109 Previously, a Reed-Solomon (RS) code scheme for the reliable 110 delivery of data objects on the packet erasure channel was proposed 111 by Network Working Group RFC5510. In RFC5510, the systematic encoder 112 uses a generator matrix which is a multiplication of an inverse of a 113 square Vandermonde matrix and another rectangular Vandermonde 114 matrix. Using this scheme, adding an extra repair symbol requires 115 generating a new matrix inverse and a new rectangular Vandermond 116 matrix. The decoding method suggested in RFC5510 requires matrix 117 inversion and matrix multiplication. To speed up this decoding 118 processing, RFC5510 refers [4] where FFT over real filed is 119 applied. Unfortunately, it is well known [5] that the real field FFT 120 method described in [4] cannot be properly operated over the 121 working field of RS codes used in RFC 5510. 123 Also in this document, a two-step fast recovering (decoding) 124 algorithm using fast Walsh-Hadamard transform is presented for the 125 proposed erasure correction scheme. This algorithm achieves the time 126 complexity O(n*log2(n)), or linear if penalization implementation, 127 such as multi-core processor or using hardware acceleration, is 128 allowed. 130 2. Source file segmentation 132 In order to encode large files within the working memory constraint, 133 the source file may need to be segmented into transmit blocks and 134 working blocks. 136 2.1. Transmit block 138 Given a source file of size F bytes and a transmit symbol size of T 139 bytes, the file can be divided into ceil(F/T) transmit symbols. A 140 source transmit block is a collection of KL or KS of these transmit 141 symbols. KL and KS may be different if the total number of source 142 transmit blocks does not evenly divide the number of transmit 143 symbols required to represent the file. The number of source 144 transmit blocks with KL transmit symbols and the number of source 145 transmit blocks with KS transmit symbols are communicated to the 146 decoder using parameters ZL and ZS, respectively. After encoding, a 147 transmit block consists of a source transmit block and a repair 148 transmit block. 150 The transmit blocks are ordered such that the first ZL transmit 151 block are encoded from source transmit blocks of size KL transmit 152 symbols. The remaining ZS transmit blocks are encoded from source 153 transmit blocks are of size KS transmit symbols. The parameters KS 154 and KL are related to ZS and ZL via 156 (1) KS = ceil( (F/T-ZL) / (ZL+ZS) ), KL=KS+1. 158 2.1.1. Working Blocks 160 In order to satisfy the working memory requirement, the transmit 161 symbols can be further subdivided into working symbols of size TW 162 bytes. A transmit symbol therefore consists of T/TW working 163 symbols. A source working block is then a collection of working 164 symbols selected such that an entire source working block can fit 165 into the working memory. The ith source working block in a transmit 166 block consists of the ith working symbol of a transmit symbol. 167 Additionally, a source working block is to be sized such the size of 168 the working symbols remain a multiple of the byte alignment factor, 169 AL. The KL (or KS) transmit symbols of a source transmit block can 170 be viewed as a collection of working symbols or equivalently as a 171 collection of source working blocks. 173 After encoding, a working block consists of a source working block 174 and a repair working block. The receiver attempts to decode on a 175 subset of the source and repair working symbols in a working block. 177 2.2. Parameter Selection 179 The code requires F, T, ZS, and TW. F is the total file size in 180 Bytes. T is the transmit symbol size in bytes, and it is 181 RECOMMENDED that it be equal to the packet payload size. The number 182 of transmit blocks ZS with KS transmit symbols (the number of 183 working blocks with KS working symbols) MUST be chosen such that 185 (2) KL<=(2^16)*R 187 where KL is computed in (1) and is the code rate for the worst 188 performing link in a sector. (Note: the restriction of 2 R is due to 189 the using of 16-bit symbol RS code in the correction scheme of this 190 document. This number will be extended to (2^32)*R if 32-bit symbol 191 RS code is used.) The working symbols size in bytes, TW, MUST be 192 chosen small enough such that KL*TW is less than or equal to the 193 working memory requirement. Additionally, TW MUST be chosen to be a 194 multiple of the byte alignment factor AL and TW MUST be a divisor of 195 T. The byte alignment, AL, is to be chosen based on the protocol 196 and the typical machine architectures, a value of 4 (bytes) is 197 Systematic rate-independent RS (SR-RS) encoder 199 2.3. Overview of systematic rate-independent encoding 201 Figure 1 shows a general block diagram of (systematic rate- 202 independent) SR-RS encoding scheme. The scheme takes a K source 203 working symbols as input, where K=KL or KS. Since AL=4, every 204 working symbol has even number of bytes, say 2*S bytes. Define an RS 205 symbol a unit of bytes. Then a working symbol contains S RS symbols. 206 All the first RS symbols in K source working symbols are grouped 207 together becoming the first RS information stream, see Figure 1, and 208 all the second RS symbols in the K source working symbols becomes 209 the second RS information stream, etc. Together there are S RS 210 information streams. The SR-RS encoding scheme works on every 211 information streams individually, or in parallel. The scheme then 212 generates encoded working symbols, with the first K output symbols 213 being the source working symbols. Furthermore, this encoding scheme 214 can generate as many as working symbols needed as long as the number 215 of the symbols does not exceed 2^16. Therefore, we can say this 216 scheme is systematic and rate independent. A detailed description of 217 this encoding scheme will be described in the next two sections. 219 <------- a working symbol ----------> 220 +-----------------------------------------+ ^ 221 |RS symbol| RS symbol | ... | RS symbol | | 222 +-----------------------------------------+ | 223 |RS symbol| RS symbol | ... | RS symbol | | 224 +-----------------------------------------+ K source working 225 ... symbols 226 +-----------------------------------------+ | 227 |RS symbol| RS symbol | ... | RS symbol | | 228 +-----------------------------------------+ V 229 | | | 230 V V V 231 +-----------------------------------------+ 232 | SR-RS Encoder | 233 +-----------------------------------------+ 234 | | | 235 V V V 236 +-----------------------------------------+ 237 |RS symbol| RS symbol | ... | RS symbol | Output working 238 +-----------------------------------------+ symbol 240 Figure 1 SR-RS encoding 242 2.4. Parameters and functions used in SR-RS encoding 244 o RS symbols is a unit of 2 bytes, or 16 bits. 246 o a ^ i denotes the operation a raised to the power i for any 247 production 249 o i + j denotes the sum of two integers i and j. 251 o i * j denotes the product of two integers i and j. 253 o XOR(u, v) denotes, for equal-length bit strings u and v, the 254 bitwise exclusive-or of u and v. 256 o GF(2^{16}) denotes a character 2 16-bit finite (Galois) field 257 with 2^{16}=65536 elements. Elements of GF(2^{16}) can be 258 considered as RS symbols. 260 o RS[i] denotes, for an integer i in {0,1,...,2^16-1}, RS symbol 261 (i_0,i_1,...,i_15), where i_j is a binary symbol and 263 i=i_0+2*i_1+(2^2)*i_2+...+(2^15)*i_{15}. 265 Thus, GF(2^{16})= {RS[i],i=0,1,...,65535} with the arithmetic 266 operations defined in the following. 268 o P(x)=1+x+x^3+x^{12}+x^{16}: primitive polynomial for GF(2^{16}} 270 o alpha, alpha_i, beta,beta_i gamma, gamma_i represent RS symbols, 271 i.e. element in GF(2^{16}) 273 o XOR{alpha_i: i=1,...,n} = XOR(XOR(alpha_1,...,alpha_{n-1}),alpha_n) 275 o poly(alpha) denotes, for a RS symbol alpha =(a_0,a_1,...,a_15), 277 a binary polynomial a_0+a_1x+...+a_{15}x^{15}. 279 o prod(alpha, beta) denotes, for two RS symbols alpha and beta, the 280 RS symbol gamma such that poly (gamma) = (poly(a)*poly(b)) mod 281 P(x) 283 o prod{alpha_i : i=1,...,n} denotes prod(prod(alpha_1,...,alpha_{n- 284 1}),alpha_n). 286 o alpha^2= prod(alpha,alpha), alpha^m =prod(alpha, alpha^{m-1}) 288 o inv(alpha) denotes, for a RS symbol alpha, an inverse of alpha. 289 inv(alpha) is also an RS symbol satisfying 290 prod(inv(alpha),alpha)=1=RS[1]. 292 o div(alpha, beta) denotes, for a RS symbols alpha and a non-zero 293 RS symbol beta , prod(alpha, inv(beta)). 295 o A location product function is defined by 297 (3) LP(i, L) = prod(XOR(RS[i],RS[t]): t in L ) 299 where L is a sub-set of integers 301 o A\B denotes, for two sub-sets A and B, the set {a| a is in A but 302 a is not in B}. 304 2.5. SR-RS encoding 306 Input to the SR-RS encoding scheme is a source working block 307 containing K source working symbols, 309 (alpha_{0,j},alpha_{1,j},...,alpha_{S-1,j}), j=0,1,...,K-1. 311 The i-th encoded working symbol is generated by the encoding 312 function 314 (4) Enc(s,i)=XOR{prod(alpha_{s,j},D(i,j)): j=0,...,K-1} 316 where D(i,j)=div(LP(i,{0,...,K-1}\{j}), LP(j,{0,...,K-1}\{j})), LP(i,L) 317 is defined in (3) . Since it only depends on the K source working 318 symbols and it can generate up to 2^16=65536 working symbols, this 319 encoding function is a rate-independent. 321 Moreover, since 323 (Enc(0,i),...,Enc(S-1,i)=(alpha_{0,j},...,alpha_{S-1,j})for j=0,1,...,K-1, 325 the encoding (4) is systematic. 327 Replacing RS[i] by a valuable x in (4) results, for s=0,...,S-1, a 328 polynomial f_{E,s}(x). Thus, given a number K-1 | Recovery Engine | 378 +---------------------+ +-----------------------------------+ 379 | 380 V 381 K source working symbols 383 Figure 2 SR-RS decoding 385 By applying the fast Walsh-Hadamard transform on both procedures, a 386 fast decoding can be achieved. 388 3.2. SR-RS decoding principle 390 Input to a SR-RS decoding scheme is 392 o A set of SIDs of the received K working symbols: L={u_0,...,u_{K- 393 1}}. 394 o The working symbol corresponding to SID u_i: 395 (gamma_{0,1},...,gamma_{S-1}), where i=0,1,...,K-1. 397 The i-th decoded working symbol is generated by the decoding 398 function 400 (5) Dec(s,i)=XOR{prod(gamma_{s,j},D(i,u_j)):j=0,...,K-1} 401 where D(i,u_j)=div(LP(i,L\{u_j}), LP(u_j,L\{u_j}), LP(i,L) is 402 defined in (3). 404 Replacing RS[i] by a valuable x in (5) results, for s=0,...,S-1, a 405 polynomial f_{D,s}(x). Evaluating f_{D,s}(x) at location set L we 406 obtain 408 f_{D,s}(RS[u_1])=gamma_{i,s}=f_{E,s}(RS[u_i]), i=0,...,K-1 410 where the polynomial f_{E,s} is defined in Section 2.5. This proves 411 that the two degree less than or equal to K polynomials f_{E,s} and 412 f_{D,s} are the same. Therefore, the decoded K working symbols 414 (Dec(0,0),...,Dec(S-1,0)),...,(Dec(0,K-1),...,Dec(S-1,K-1)) 416 are the source working symbols. This proves the SR-RS decoding is 417 optimal (ideal). 419 3.3. A realization of the decoding principle: two-step SR-RS decoding 420 (informative) 422 This section provides one of the realization method on the decoding 423 principle defined in 3.2. Let the input to the decoding as defined 424 in Section 3.2. Define an extended locator product function 426 (6) LPE(i)= LP(i,L\{i}) if i is in L, LP(i,L) otherwise. 428 and an evaluation function: 430 (7) Psi(i,s)=div(gamma_{s,i},LPE(i)) 431 The decoding principle defined Section 3.2. can then be carried out 432 in the following two steps decoding: 434 Step 1. Evaluate LPE(i) at i=0,...,K-1 as well as at i in L; 436 Step 2: 438 Step 2.1. Compute Psi(u_i,s) for i=0,...,K-1 and s=0,...,S-1. 440 Step 2.2. Compute and output, for k in {0,...,K-1}\L and s=0,...,S-1. 442 Dec(s,k)=prod(LPE(k),XOR{div(Psi(u_j,s),RS[k]+RS[u_j]):j=0,...,K-1}). 444 3.4. Fast decoding (informative) 446 This section presents a low complexity method for the decoding 447 procedure in Section 3.3. 449 3.4.1. Hadamard matrices 451 o Initialize: define 0 order a Hadamard matrix H_0=1 453 o Inductively define the order v Hadamard matrix a 2^v by 2^v matrix 454 H_v, for v>0, has the (i,j)-th entry h_v(I,j), for i, j =0,...,2^v- 455 1, such that 457 h_v(i,j)=h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 459 h_v(i,j+2^{v-1})= h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 461 h_v(i+2^{v-1},j)= h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 463 h_v(i+2^{v-1},j+2^{v-1})= -h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 465 Picture-wise , we have 467 +-- --+ 468 | H_{v-1} H_{v-1} | 469 H_v = | | 470 | H_{v-1} - H_{v-1} | 471 +-- --+ 473 3.4.2. Walsh-Hadamard transform 475 Denote a dimension v binary vector space by 477 GF^v(2)={X : X=(x_0,...,x_{v-1}),x_i is either 0 or 1 for i=0,...,v-1}. 479 Define an order "<" on GF^v(2) by 481 X=(x_0,...,x_{v-1})