Internet DRAFT - draft-shen-rmt-bb-fec-srrscode
draft-shen-rmt-bb-fec-srrscode
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<N<65537, the vector
(Enc(s,0),...,Enc(s,N-1)=(f_{E,s}(RS[0]),...,f_{E,s}(RS[N-1]))
is an RS codeword of length N(see [3] for the definition of RS
code). Therefore, the encoder (4) generates an MDS code, an ideal
erasure recovering code.
It should be noted that the integer iin the encoding function of (4)
is limited to 2^16=65536. In order to extend the encoding function
to integers in the range beyond 2^16=65536, 32-bit RS symbol should
be considered.
3. SR-RS decoder
3.1. Overview of SR-RS decoding
It is shown in Section 2.5. that the code generated by SR-RS
encoding scheme is idea for erasure channel. Thus, if a source
working block has K working symbols, then as soon as K encoded
working symbols are received, all K source working symbols can be
recovered. Figure 2 presents a general diagram of an SR-RS decoding
scheme we proposed. When the K received Symbol IDs (SIDs) are all
source SIDs, then there is no need to operate further decoding,
otherwise those K SIDs are either all repair SIDs or a combination
of source SIDs and repair SIDs. The proposed SR-RS decoding is
operated in two procedures, see Figure 2. The first procedure,
called location function evaluating (generating), takes the received
K SIDs to generate a location function. The second procedure takes
Shen, et al. Expires May 16, 2013 [Page 8]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
the location function (or location evaluation values) and the K
received values of working symbols to produce the values of K source
working symbols. We call the second procedure source symbol recovery
engine. To produce the entire working block, one has to operate the
second procedure S times. However, if parallel implementation is
allowed, S recover engines can work in parallel.
+-----------------+ +--------+ +--------+ +--------+
|1st received SID | |1st K RS| |2nd K RS| |Sth K RS|
+-----------------+ |symbol | |symbol |...|symbol |
|2st received SID | |stream | |stream | |stream |
+-----------------+ +--------+ +--------+ +--------+
... | | |
+-----------------+ | | |
|kth received SID | | | |
+-----------------+ | | |
| | | |
V V V V
+---------------------+ +-----------------------------------+
| Location function | | Source symbol |
| Generator/Evaluator |--> | 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})<Y=(y_0,...,y_{v-1})
if and only if
x_0+2*x_1+...+2^{v-1}*x_{v-1}<y_0+2*y_1+...+2^{v-1}*y_{v-1}.
Then GF^v(2) can be enumerated by
GF^v(2)={X_0,...,X_{2^v-1}} with X_0<X_2<...<X_{2^v-1}.
Shen, et al. Expires May 16, 2013 [Page 11]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
Let f be a function from GF^v(2) to the integer ring Z. Denote
(8) [f] =(f(X_0),f(X_1),...,f(X_{2^v-1})).
Walsh-Hadamard transform (WHT) on f is defined by
WH(f)=[f]*H_v,
Where * is the vector multiplication.
Let F be a vector in Z^v, then the inverse Walsh-Hadamard transform
(IWHT) is defined by
IWH(F)=(1/2^v)*(F * H_v).
Then IWH(WH(f))=[f].
Before we state a crucial property of WHT, let us introduce two
operations:
o Component-wise product "x" in the dimension v integer space Z^n by
(a_0,...,a_{n-1})x(b_0,...,b_{n-1})=(a_0*b_0,...,a_{n-1}*b_{n-1}).
o Convolution product of two GF^v(2) to Z functions, f1 and f2 by
conv(f1,f2)(y) = sum{f1(x)*f2(XOR(y, x)): x in GF^v(2)},
where sum means add all the values f1(x)*f2(XOR(y,x) for x in
GF^v(2).
A crucial property of WH transform is
(9) WH(conv(f1,f2))=WH(f1) x WH(f2)
i.e. [conv(f1,f2)]=IWH(WH(f1)x WH(f2)).
3.4.3. Fast Walsh-Hadamard transform
A fast Walsh-Hadamard transform (FWHT) algorithm on a function f can
be presented as follows:
Step 1. Initialize: (F_{0,0},F_{0,1},...,F_{0,2^v-1})=[f] (see (8) for
the definition of [f])
Step 2. For i=1,...,v, inductively generate a size I vector
Shen, et al. Expires May 16, 2013 [Page 12]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
F_{i,j}=(F_{i-1,2j}+F_{i-1,2j+1}, F_{i-1,2j}-F_{i-1,2j+1}),
for j=0,...,2^{v-i}-1;
Step 3. Output WHT(f)=F_{v,0}.
In Step 2, the time complexity for everyiis V=2^v. Since the
algorithm needs such computations, the total time complexity is
v*2^v=V*log2(V). If parallel operation is allowed in implementation,
then the time complexity can be reduced. The lowest complexity for a
penalization implementation is log2(V).
3.4.4. Fast SR-RS decoding using fast WHT
The two steps SR-RS decoding in Section 3.3. can be speed up by
applying the fast WHT reviewed in Section 3.4.3. In fact, one can
use the algorithm in [6] [6]to carry this task. In this section, we
explain that algorithm within the content of this document.
Let SID set of all K received working symbols be
L = {u_0,...,u_{K-1}}, with u_0 <...<u_{K-1}
Let v be the smallest number such that u_{K-1}<2^v+1. Denote
(10) V=2^v
By (2), we have V<2^{16}+1. The following notation and functions
will be used to describe the fast decoding.
o Denote X and Y the vector in space GF^v(2).
o Denote theata = RS[2], we have {theat^n | n=0,...,2^{16}-2} =
{RS[i]| i=0,...,2^{16}-1}\{0}= GF(2^{16})
o Exp_GF(i)=theata^i, i=0,...,2^{16}-2
o Log_GF(theat^i)=i, i=0,...,2^{16}-2
o EXT(X) denotes, for X=(x_0,...,x_{v-1}) in GF^v(2), the element
(x_0,...,X_{v-1},0,...,0). Obviously, XOR(EXT(X),EXT(Y))=
EXT(XOR(X,Y)).
o SHT(RS[i]) denotes, for RS[i]=(i_0,...,i_{v-1},...,i_{15}), GF^v(2)
element (i_0,...,i_{v-1}).
o Log(X)=log_GF(EXT(X)) for X in GF^v(2).
Shen, et al. Expires May 16, 2013 [Page 13]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
o X_L(X), for X in GF^v(2), equals to 1 if X is in L, 0
otherwise.
o I(X)=1/EXT(X) for X in GF^v(2).
o Sum{a: a in a integer set A} denotes the summation of all the
integers in the set A
Furthermore,(6) can be written in the domain of GF^v(2) as
LPE(X)= prod{ prod(Exp_GF( X_L(X)*Log(XOR(X,Y))): y in GF^(2)}
Since EXT(SHT(RS[i]))=RS[i] with i<2^v and since GF^v(2)={SHT(RS[i])
|-1<i<2^v} we have
LPE(X)= LP(i,L\{i}) if X=SHT(RS[i]) and i in L,
LPE(X)= LP(i,L) if X=SHT(RS[i]) but i is not in L.
Moreover, Log_GF(LPE(X))=conv(X_L, Log)(X). Therefore, LPE(X) can be
evaluated using FWHT in(9). Basically this is Step 1 of two-step
decoding in Section 3.3.
Suppose the set of all S received RS symbols of SID u_i is
{gamma_{s,i} |s=0,...,S-1}.
After computing Psi(u_i,s) defined (7), a major calculation left to
the two-step decoding in Section 3.3. is
(11) XOR{prod(Psi(u,s),I(XOR(RS[i],RS[u]))):u is in L}
Since both Psi(u,s) and I(XOR(RS[i],RS[u]))are elements in
GF(2^{16}), they can be represented by a binary linear combinations
of GF(2^{16}) elements,theat,tehat^2,...,tehat^{15},i.e.
Psi = XOR{prod(Psi_i,theat^i): i=0,1...,15} and
I = XOR{prod(I_i,theat^i): i=0,1...,15}
where Psi_i and I_i are binary numbers. Then calculation of (11) can
be transform to the computation of conv(Psi_i,I_j)(X) for
i+j=0,...,30, which can be implemented using FWHT. We refer to [6]for
a more detailed computation procedure of (11) .
Shen, et al. Expires May 16, 2013 [Page 14]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
4. Protocol IEs
This section describes IEs that are used by the FEC. All fields are
big-endian.
The value of the FEC Encoding ID MUST be 8, as assigned by IANA (see
Section 7).
4.1. FEC Payload IEs
The FEC payload ID is a 4-byte field defined as follows:
[0:7] TBN, (8 bits, unsigned integer): A non-negative integer
identifier indicating the transmit block number.
[8:31] SID , (24 bits, unsigned integer): A non-negative integer
identifier indicating the transmit symbols in the packet. SID 0 to
K-1 indicate systematic symbols.
The FEC Payload ID is shown in Figure 3.
0 1 2 3
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TBN | SID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3 FEC Payload ID format
4.2. Common
The Common FEC Object Transmission Information elements used by this
FEC Scheme are:
[0:39] Transfer Length (F), (40 bits, unsigned integer): A non-
negative integer. This is the transfer length of the object in
bytes.
[40:47] are reserved.
[48:63] Transmit Symbol Size (T), (16 bits, unsigned integer): A
positive integer that is less than 2^16. This is the size of a
transmit symbol in units of bytes.
The encoded Common FEC Object Transmission Information format is
shown in Figure 4.
Shen, et al. Expires May 16, 2013 [Page 15]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
0 1 2 3
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transfer Length (F) |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Reserved | Symbol Size (T) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4 Encoded Common FEC IE for SR-RS FEC Scheme
4.3. Scheme Specific
The following parameters are carried in the Scheme-Specific FEC
Object Transmission Information element for this FEC Scheme:
[0:7] ZL: The number of transmit blocks with KL working symbols (and
the number of working blocks with KL working symbols). (8 bits,
unsigned integer)
[8:15] ZS: The number of transmit blocks with KS working symbols
(and the number ofworking blocks with KS working symbols). (8 bits,
unsigned integer)
[16:30] TW: The working symbol size in bytes (15 bits, unsigned
integer)
The encoded Specific FEC Object Transmission Information format is
shown in Figure 5.
0 1 2 3
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ZL | ZS | TW |M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5 FEC Payload ID format
5. Conventions used in this document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC-2119 [RFC2119].
In this document, these words will appear with that interpretation
only when in ALL CAPS. Lower case uses of these words are not to be
interpreted as carrying RFC-2119 significance.
Shen, et al. Expires May 16, 2013 [Page 16]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
6. Security Considerations
Users could potentially be subject to a denial of service attack if
a single erroneous packet is injected into the delivery stream.
Therefore, it is RECOMMENDED that source authentication and
integrity checking are applied to the file or data object before
delivering decoded data to applications. The hashing methodology of
SHA-256 is an example [2].
7. IANA Considerations
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
registration. For general guidelines on IANA considerations as they
apply to this document, see [RFC5052]. IANA is requested to assign
a value under the ietf:rmt:fec:encoding name-space to "SR-RS Code"
as the FEC Encoding ID value associated with this specification,
preferably the value 8.
8. References
8.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[2] "Secure Hash Standard", National Institute of Standards
and Technology FIPS PUB 180-3, October 2008.
8.2. Informative References
[3] F.J. McWilliams and N.J.A. Sloane, The Theory of Error-
Correcting Codes, North-Holland Mathematical Library, 1998
[4] I. Gohberg and V. Olshevsky, "Fast algorithms with
preprocessing for matrix-vector multiplication problems," J.
Complexity, vol. 10, 1994
[5] S. Gao, "A new algorithm for decoding reed-Solomon codes," In
Communications, Information and Network Security, V.Bhargava,
H.V.Poor, V.Tarokh, and S.Yoon, Vol. 2003 (2002), pp. 55-68
[6] Frederic Didier, "Efficient erasure decoding of Reed-Solomon
codes," arXiv: 0901.1886v1 [cs.IT], 2009
9. Acknowledgments
This document was prepared using 2-Word-v2.0.template.dot.
Shen, et al. Expires May 16, 2013 [Page 17]
Internet-Draft SR-RS Erasure Correction Scheme November 2012
Authors' Addresses
BZ(Bazhong) Shen
Broadcom
5300 California Ave.
Irvine, CA 92617
Email: bzshen@broadcom.com
Erik Stauffer
Broadcom
190 Mathilda Place
Sunnyvale, Ca 94086
Email: eriks@broadcom.com
Kamlesh Rath
Broadcom
190 Mathilda Place
Sunnyvale, Ca 94086
Email: krath@broadcom.com
Shen, et al. Expires May 16, 2013 [Page 18]
