Reliable Multicast Transport B. Shen Internet Draft Broadcom Intended status: Standards Track E. Stauffer Expires: May 2013 Broadcom K. Rath Broadcom November 14,2012 Systematic Rate-independent Reed-Solomon (SR-RS) Erasure Correction Scheme draft-shen-rmt-bb-fec-srrscode-01.txt Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on May 16, 2013. Copyright Notice Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this Shen, et al. Expires May 16, 2013 [Page 1] Internet-Draft SR-RS Erasure Correction Scheme November 2012 document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Abstract This document specifies a systematic rate-independent Reed-Solomon (SR-RS) Erasure correction scheme. The two properties, systematic and rate-independent, are fulfilled by Lagrange polynomial interpolation. When the number of output symbols is fixed this scheme essentially generates a Reed-Solomon (RS) code. Therefore, based on the MDS (maximum distance separable) property of RS code, this erasure correction scheme is optimal (ideal). Also in this document, a two-step fast recovering (decoding) algorithm using fast Walsh-Hadamard transform is presented for the proposed erasure correction scheme. This algorithm achieves the time complexity O(n*log2(n)), or linear if penalization implementation, such as multi-core processor, is allowed. Contents 1. Introduction...................................................3 2. Source file segmentation.......................................3 2.1. Transmit block............................................4 2.1.1. Working Blocks.......................................4 2.2. Parameter Selection.......................................4 2.3. Overview of systematic rate-independent encoding ........5 2.4. Parameters and functions used in SR-RS encoding...........6 2.5. SR-RS encoding............................................7 3. SR-RS decoder..................................................8 3.1. Overview of SR-RS decoding................................8 3.2. SR-RS decoding principle..................................9 3.3. A realization of the decoding principle: two-step SR-RS decoding (informative)........................................10 3.4. Fast decoding (informative)..............................11 3.4.1. Hadamard matrices...................................11 3.4.2. Walsh-Hadamard transform............................11 3.4.3. Fast Walsh-Hadamard transform.......................12 3.4.4. Fast SR-RS decoding using fast WHT..................13 4. Protocol IEs..................................................15 4.1. FEC Payload IEs..........................................15 4.2. Common...................................................15 4.3. Scheme Specific..........................................16 5. Conventions used in this document.............................16 6. Security Considerations.......................................17 7. IANA Considerations...........................................17 Shen, et al. Expires May 16, 2013 [Page 2] Internet-Draft SR-RS Erasure Correction Scheme November 2012 8. References....................................................17 8.1. Normative References.....................................17 8.2. Informative References...................................17 9. Acknowledgments...............................................17 1. Introduction This document specifies and explains a systematic rate-independent Reed-Solomon (SR-RS) Erasure correction scheme. The two properties, systematic and rate-independent, are fulfilled by Lagrange polynomial interpolation. When the number of output symbols is fixed this scheme essentially generates a Reed-Solomon (RS) code. Therefore, based on the MDS (maximum distance separable) property of RS code [3], this erasure correction scheme is optimal (ideal), i.e. when the number of un-erased packets is equal to the number of source packets, the entire source packets can be recovered. Previously, a Reed-Solomon (RS) code scheme for the reliable delivery of data objects on the packet erasure channel was proposed by Network Working Group RFC5510. In RFC5510, the systematic encoder uses a generator matrix which is a multiplication of an inverse of a square Vandermonde matrix and another rectangular Vandermonde matrix. Using this scheme, adding an extra repair symbol requires generating a new matrix inverse and a new rectangular Vandermond matrix. The decoding method suggested in RFC5510 requires matrix inversion and matrix multiplication. To speed up this decoding processing, RFC5510 refers [4] where FFT over real filed is applied. Unfortunately, it is well known [5] that the real field FFT method described in [4] cannot be properly operated over the working field of RS codes used in RFC 5510. Also in this document, a two-step fast recovering (decoding) algorithm using fast Walsh-Hadamard transform is presented for the proposed erasure correction scheme. This algorithm achieves the time complexity O(n*log2(n)), or linear if penalization implementation, such as multi-core processor or using hardware acceleration, is allowed. 2. Source file segmentation In order to encode large files within the working memory constraint, the source file may need to be segmented into transmit blocks and working blocks. Shen, et al. Expires May 16, 2013 [Page 3] Internet-Draft SR-RS Erasure Correction Scheme November 2012 2.1. Transmit block Given a source file of size F bytes and a transmit symbol size of T bytes, the file can be divided into ceil(F/T) transmit symbols. A source transmit block is a collection of KL or KS of these transmit symbols. KL and KS may be different if the total number of source transmit blocks does not evenly divide the number of transmit symbols required to represent the file. The number of source transmit blocks with KL transmit symbols and the number of source transmit blocks with KS transmit symbols are communicated to the decoder using parameters ZL and ZS, respectively. After encoding, a transmit block consists of a source transmit block and a repair transmit block. The transmit blocks are ordered such that the first ZL transmit block are encoded from source transmit blocks of size KL transmit symbols. The remaining ZS transmit blocks are encoded from source transmit blocks are of size KS transmit symbols. The parameters KS and KL are related to ZS and ZL via (1) KS = ceil( (F/T-ZL) / (ZL+ZS) ), KL=KS+1. 2.1.1. Working Blocks In order to satisfy the working memory requirement, the transmit symbols can be further subdivided into working symbols of size TW bytes. A transmit symbol therefore consists of T/TW working symbols. A source working block is then a collection of working symbols selected such that an entire source working block can fit into the working memory. The ith source working block in a transmit block consists of the ith working symbol of a transmit symbol. Additionally, a source working block is to be sized such the size of the working symbols remain a multiple of the byte alignment factor, AL. The KL (or KS) transmit symbols of a source transmit block can be viewed as a collection of working symbols or equivalently as a collection of source working blocks. After encoding, a working block consists of a source working block and a repair working block. The receiver attempts to decode on a subset of the source and repair working symbols in a working block. 2.2. Parameter Selection The code requires F, T, ZS, and TW. F is the total file size in Bytes. T is the transmit symbol size in bytes, and it is RECOMMENDED that it be equal to the packet payload size. The number Shen, et al. Expires May 16, 2013 [Page 4] Internet-Draft SR-RS Erasure Correction Scheme November 2012 of transmit blocks ZS with KS transmit symbols (the number of working blocks with KS working symbols) MUST be chosen such that (2) KL<=(2^16)*R where KL is computed in (1) and is the code rate for the worst performing link in a sector. (Note: the restriction of 2 R is due to the using of 16-bit symbol RS code in the correction scheme of this document. This number will be extended to (2^32)*R if 32-bit symbol RS code is used.) The working symbols size in bytes, TW, MUST be chosen small enough such that KL*TW is less than or equal to the working memory requirement. Additionally, TW MUST be chosen to be a multiple of the byte alignment factor AL and TW MUST be a divisor of T. The byte alignment, AL, is to be chosen based on the protocol and the typical machine architectures, a value of 4 (bytes) is Systematic rate-independent RS (SR-RS) encoder 2.3. Overview of systematic rate-independent encoding Figure 1 shows a general block diagram of (systematic rate- independent) SR-RS encoding scheme. The scheme takes a K source working symbols as input, where K=KL or KS. Since AL=4, every working symbol has even number of bytes, say 2*S bytes. Define an RS symbol a unit of bytes. Then a working symbol contains S RS symbols. All the first RS symbols in K source working symbols are grouped together becoming the first RS information stream, see Figure 1, and all the second RS symbols in the K source working symbols becomes the second RS information stream, etc. Together there are S RS information streams. The SR-RS encoding scheme works on every information streams individually, or in parallel. The scheme then generates encoded working symbols, with the first K output symbols being the source working symbols. Furthermore, this encoding scheme can generate as many as working symbols needed as long as the number of the symbols does not exceed 2^16. Therefore, we can say this scheme is systematic and rate independent. A detailed description of this encoding scheme will be described in the next two sections. Shen, et al. Expires May 16, 2013 [Page 5] Internet-Draft SR-RS Erasure Correction Scheme November 2012 <------- a working symbol ----------> +-----------------------------------------+ ^ |RS symbol| RS symbol | ... | RS symbol | | +-----------------------------------------+ | |RS symbol| RS symbol | ... | RS symbol | | +-----------------------------------------+ K source working ... symbols +-----------------------------------------+ | |RS symbol| RS symbol | ... | RS symbol | | +-----------------------------------------+ V | | | V V V +-----------------------------------------+ | SR-RS Encoder | +-----------------------------------------+ | | | V V V +-----------------------------------------+ |RS symbol| RS symbol | ... | RS symbol | Output working +-----------------------------------------+ symbol Figure 1 SR-RS encoding 2.4. Parameters and functions used in SR-RS encoding o RS symbols is a unit of 2 bytes, or 16 bits. o a ^ i denotes the operation a raised to the power i for any production o i + j denotes the sum of two integers i and j. o i * j denotes the product of two integers i and j. o XOR(u, v) denotes, for equal-length bit strings u and v, the bitwise exclusive-or of u and v. o GF(2^{16}) denotes a character 2 16-bit finite (Galois) field with 2^{16}=65536 elements. Elements of GF(2^{16}) can be considered as RS symbols. o RS[i] denotes, for an integer i in {0,1,...,2^16-1}, RS symbol (i_0,i_1,...,i_15), where i_j is a binary symbol and i=i_0+2*i_1+(2^2)*i_2+...+(2^15)*i_{15}. Shen, et al. Expires May 16, 2013 [Page 6] Internet-Draft SR-RS Erasure Correction Scheme November 2012 Thus, GF(2^{16})= {RS[i],i=0,1,...,65535} with the arithmetic operations defined in the following. o P(x)=1+x+x^3+x^{12}+x^{16}: primitive polynomial for GF(2^{16}} o alpha, alpha_i, beta,beta_i gamma, gamma_i represent RS symbols, i.e. element in GF(2^{16}) o XOR{alpha_i: i=1,...,n} = XOR(XOR(alpha_1,...,alpha_{n-1}),alpha_n) o poly(alpha) denotes, for a RS symbol alpha =(a_0,a_1,...,a_15), a binary polynomial a_0+a_1x+...+a_{15}x^{15}. o prod(alpha, beta) denotes, for two RS symbols alpha and beta, the RS symbol gamma such that poly (gamma) = (poly(a)*poly(b)) mod P(x) o prod{alpha_i : i=1,...,n} denotes prod(prod(alpha_1,...,alpha_{n- 1}),alpha_n). o alpha^2= prod(alpha,alpha), alpha^m =prod(alpha, alpha^{m-1}) o inv(alpha) denotes, for a RS symbol alpha, an inverse of alpha. inv(alpha) is also an RS symbol satisfying prod(inv(alpha),alpha)=1=RS[1]. o div(alpha, beta) denotes, for a RS symbols alpha and a non-zero RS symbol beta , prod(alpha, inv(beta)). o A location product function is defined by (3) LP(i, L) = prod(XOR(RS[i],RS[t]): t in L ) where L is a sub-set of integers o A\B denotes, for two sub-sets A and B, the set {a| a is in A but a is not in B}. 2.5. SR-RS encoding Input to the SR-RS encoding scheme is a source working block containing K source working symbols, (alpha_{0,j},alpha_{1,j},...,alpha_{S-1,j}), j=0,1,...,K-1. Shen, et al. Expires May 16, 2013 [Page 7] Internet-Draft SR-RS Erasure Correction Scheme November 2012 The i-th encoded working symbol is generated by the encoding function (4) Enc(s,i)=XOR{prod(alpha_{s,j},D(i,j)): j=0,...,K-1} where D(i,j)=div(LP(i,{0,...,K-1}\{j}), LP(j,{0,...,K-1}\{j})), LP(i,L) is defined in (3) . Since it only depends on the K source working symbols and it can generate up to 2^16=65536 working symbols, this encoding function is a rate-independent. Moreover, since (Enc(0,i),...,Enc(S-1,i)=(alpha_{0,j},...,alpha_{S-1,j})for j=0,1,...,K-1, the encoding (4) is systematic. Replacing RS[i] by a valuable x in (4) results, for s=0,...,S-1, a polynomial f_{E,s}(x). Thus, given a number K-1 | Recovery Engine | +---------------------+ +-----------------------------------+ | V K source working symbols Figure 2 SR-RS decoding By applying the fast Walsh-Hadamard transform on both procedures, a fast decoding can be achieved. 3.2. SR-RS decoding principle Input to a SR-RS decoding scheme is o A set of SIDs of the received K working symbols: L={u_0,...,u_{K- 1}}. o The working symbol corresponding to SID u_i: (gamma_{0,1},...,gamma_{S-1}), where i=0,1,...,K-1. The i-th decoded working symbol is generated by the decoding function (5) Dec(s,i)=XOR{prod(gamma_{s,j},D(i,u_j)):j=0,...,K-1} Shen, et al. Expires May 16, 2013 [Page 9] Internet-Draft SR-RS Erasure Correction Scheme November 2012 where D(i,u_j)=div(LP(i,L\{u_j}), LP(u_j,L\{u_j}), LP(i,L) is defined in (3). Replacing RS[i] by a valuable x in (5) results, for s=0,...,S-1, a polynomial f_{D,s}(x). Evaluating f_{D,s}(x) at location set L we obtain f_{D,s}(RS[u_1])=gamma_{i,s}=f_{E,s}(RS[u_i]), i=0,...,K-1 where the polynomial f_{E,s} is defined in Section 2.5. This proves that the two degree less than or equal to K polynomials f_{E,s} and f_{D,s} are the same. Therefore, the decoded K working symbols (Dec(0,0),...,Dec(S-1,0)),...,(Dec(0,K-1),...,Dec(S-1,K-1)) are the source working symbols. This proves the SR-RS decoding is optimal (ideal). 3.3. A realization of the decoding principle: two-step SR-RS decoding (informative) This section provides one of the realization method on the decoding principle defined in 3.2. Let the input to the decoding as defined in Section 3.2. Define an extended locator product function (6) LPE(i)= LP(i,L\{i}) if i is in L, LP(i,L) otherwise. and an evaluation function: (7) Psi(i,s)=div(gamma_{s,i},LPE(i)) The decoding principle defined Section 3.2. can then be carried out in the following two steps decoding: Step 1. Evaluate LPE(i) at i=0,...,K-1 as well as at i in L; Step 2: Step 2.1. Compute Psi(u_i,s) for i=0,...,K-1 and s=0,...,S-1. Step 2.2. Compute and output, for k in {0,...,K-1}\L and s=0,...,S-1. Dec(s,k)=prod(LPE(k),XOR{div(Psi(u_j,s),RS[k]+RS[u_j]):j=0,...,K-1}). Shen, et al. Expires May 16, 2013 [Page 10] Internet-Draft SR-RS Erasure Correction Scheme November 2012 3.4. Fast decoding (informative) This section presents a low complexity method for the decoding procedure in Section 3.3. 3.4.1. Hadamard matrices o Initialize: define 0 order a Hadamard matrix H_0=1 o Inductively define the order v Hadamard matrix a 2^v by 2^v matrix H_v, for v>0, has the (i,j)-th entry h_v(I,j), for i, j =0,...,2^v- 1, such that h_v(i,j)=h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 h_v(i,j+2^{v-1})= h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 h_v(i+2^{v-1},j)= h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 h_v(i+2^{v-1},j+2^{v-1})= -h_{v-1}(i,j) for i,j = 0,1,...,2^{v-1}-1 Picture-wise , we have +-- --+ | H_{v-1} H_{v-1} | H_v = | | | H_{v-1} - H_{v-1} | +-- --+ 3.4.2. Walsh-Hadamard transform Denote a dimension v binary vector space by GF^v(2)={X : X=(x_0,...,x_{v-1}),x_i is either 0 or 1 for i=0,...,v-1}. Define an order "<" on GF^v(2) by X=(x_0,...,x_{v-1})