One document matched: draft-ietf-rmt-info-fec-03.ps

%!PS-Adobe-3.0
%%Creator: groff version 1.15
%%CreationDate: Tue Sep  3 11:55:31 2002
%%DocumentNeededResources: font Courier-Bold
%%+ font Times-Bold
%%+ font Times-Roman
%%+ font Courier
%%DocumentSuppliedResources: procset grops 1.15 3
%%Pages: 16
%%PageOrder: Ascend
%%Orientation: Portrait
%%EndComments
%%BeginProlog
%%BeginResource: procset grops 1.15 3
/setpacking where{
pop
currentpacking
true setpacking
}if
/grops 120 dict dup begin
/SC 32 def
/A/show load def
/B{0 SC 3 -1 roll widthshow}bind def
/C{0 exch ashow}bind def
/D{0 exch 0 SC 5 2 roll awidthshow}bind def
/E{0 rmoveto show}bind def
/F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def
/G{0 rmoveto 0 exch ashow}bind def
/H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/I{0 exch rmoveto show}bind def
/J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def
/K{0 exch rmoveto 0 exch ashow}bind def
/L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/M{rmoveto show}bind def
/N{rmoveto 0 SC 3 -1 roll widthshow}bind def
/O{rmoveto 0 exch ashow}bind def
/P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/Q{moveto show}bind def
/R{moveto 0 SC 3 -1 roll widthshow}bind def
/S{moveto 0 exch ashow}bind def
/T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def
/SF{
findfont exch
[exch dup 0 exch 0 exch neg 0 0]makefont
dup setfont
[exch/setfont cvx]cvx bind def
}bind def
/MF{
findfont
[5 2 roll
0 3 1 roll
neg 0 0]makefont
dup setfont
[exch/setfont cvx]cvx bind def
}bind def
/level0 0 def
/RES 0 def
/PL 0 def
/LS 0 def
/MANUAL{
statusdict begin/manualfeed true store end
}bind def
/PLG{
gsave newpath clippath pathbbox grestore
exch pop add exch pop
}bind def
/BP{
/level0 save def
1 setlinecap
1 setlinejoin
72 RES div dup scale
LS{
90 rotate
}{
0 PL translate
}ifelse
1 -1 scale
}bind def
/EP{
level0 restore
showpage
}bind def
/DA{
newpath arcn stroke
}bind def
/SN{
transform
.25 sub exch .25 sub exch
round .25 add exch round .25 add exch
itransform
}bind def
/DL{
SN
moveto
SN
lineto stroke
}bind def
/DC{
newpath 0 360 arc closepath
}bind def
/TM matrix def
/DE{
TM currentmatrix pop
translate scale newpath 0 0 .5 0 360 arc closepath
TM setmatrix
}bind def
/RC/rcurveto load def
/RL/rlineto load def
/ST/stroke load def
/MT/moveto load def
/CL/closepath load def
/FL{
currentgray exch setgray fill setgray
}bind def
/BL/fill load def
/LW/setlinewidth load def
/RE{
findfont
dup maxlength 1 index/FontName known not{1 add}if dict begin
{
1 index/FID ne{def}{pop pop}ifelse
}forall
/Encoding exch def
dup/FontName exch def
currentdict end definefont pop
}bind def
/DEFS 0 def
/EBEGIN{
moveto
DEFS begin
}bind def
/EEND/end load def
/CNT 0 def
/level1 0 def
/PBEGIN{
/level1 save def
translate
div 3 1 roll div exch scale
neg exch neg exch translate
0 setgray
0 setlinecap
1 setlinewidth
0 setlinejoin
10 setmiterlimit
[]0 setdash
/setstrokeadjust where{
pop
false setstrokeadjust
}if
/setoverprint where{
pop
false setoverprint
}if
newpath
/CNT countdictstack def
userdict begin
/showpage{}def
}bind def
/PEND{
clear
countdictstack CNT sub{end}repeat
level1 restore
}bind def
end def
/setpacking where{
pop
setpacking
}if
%%EndResource
%%IncludeResource: font Courier-Bold
%%IncludeResource: font Times-Bold
%%IncludeResource: font Times-Roman
%%IncludeResource: font Courier
grops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72
def/PL 792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron
/scaron/zcaron/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/space/exclam/quotedbl/numbersign/dollar/percent
/ampersand/quoteright/parenleft/parenright/asterisk/plus/comma/hyphen
/period/slash/zero/one/two/three/four/five/six/seven/eight/nine/colon
/semicolon/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N/O
/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright/circumflex
/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y
/z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase/guillemotleft
/guillemotright/bullet/florin/fraction/perthousand/dagger/daggerdbl
/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut
/dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash
/quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen
/brokenbar/section/dieresis/copyright/ordfeminine/guilsinglleft
/logicalnot/minus/registered/macron/degree/plusminus/twosuperior
/threesuperior/acute/mu/paragraph/periodcentered/cedilla/onesuperior
/ordmasculine/guilsinglright/onequarter/onehalf/threequarters
/questiondown/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE
/Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex
/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn
/germandbls/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla
/egrave/eacute/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis
/eth/ntilde/ograve/oacute/ocircumflex/otilde/odieresis/divide/oslash
/ugrave/uacute/ucircumflex/udieresis/yacute/thorn/ydieresis]def
/Courier@0 ENC0/Courier RE/Times-Roman@0 ENC0/Times-Roman RE
/Times-Bold@0 ENC0/Times-Bold RE/Courier-Bold@0 ENC0/Courier-Bold RE
%%EndProlog
%%Page: 1 1
%%BeginPageSetup
BP
%%EndPageSetup
/F0 10/Courier-Bold@0 SF(Internet Engineering Task Force)72 85 Q(RMT WG)
209.998 E 197.998(INTERNET-DRAFT M.)72 98 R(Luby/Digital Fountain)6 E
149.998(draft-ietf-rmt-info-fec-03.ps L.)72 111 R(Vicisano/Cisco)6 E
(J. Gemmell/Microsoft)383.998 124 Q(L. Rizzo/ACIRI and Univ. Pisa)
329.998 137 Q(M. Handley/ACIRI)407.998 150 Q(J. Crowcroft/UCL)407.998
163 Q 6(3S)407.998 176 S(eptember 2002)-6 E(Expires: March 2003)389.998
189 Q/F1 14/Times-Bold@0 SF(The Use of F)110.732 214 Q(orward Err)-.35 E
(or Corr)-.252 E(ection in Reliable Multicast)-.252 E/F2 11/Times-Bold@0
SF(Status of this Memo)72 252 Q/F3 11/Times-Roman@0 SF(This document is\
 an Internet-Draft and is in full conformance with all pro)72 271 Q
(visions of Section 10 of)-.165 E(RFC2026 [3].)72 284 Q
(Internet-Drafts are w)72 300.6 Q
(orking documents of the Internet Engineering T)-.11 E(ask F)-.88 E
(orce \(IETF\), its areas,)-.165 E(and its w)72 313.6 Q(orking groups.)
-.11 E(Note that other groups may also distrib)5.5 E(ute w)-.22 E
(orking documents as)-.11 E(Internet-Drafts.)72 326.6 Q
(Internet-Drafts are v)72 352.6 Q
(alid for a maximum of six months and may be updated, replaced, or)-.275
E(obsoleted by other documents at an)72 365.6 Q 2.75(yt)-.165 G 2.75
(ime. It)-2.75 F(is inappropriate to use Internet-Drafts as reference)
2.75 E(material or to cite them other than as a "w)72 378.6 Q
(ork in progress".)-.11 E
(The list of current Internet-Drafts can be accessed at http://www)72
404.6 Q(.ietf.or)-.715 E(g/ietf/1id-abstracts.txt)-.198 E 1.76 -.88
(To v)72 430.6 T(ie).88 E 2.75(wt)-.275 G(he list Internet-Draft Shado)
-2.75 E 2.75(wD)-.275 G(irectories, see http://www)-2.75 E(.ietf.or)
-.715 E(g/shado)-.198 E -.715(w.)-.275 G(html.).715 E
(This document is a product of the IETF RMT WG.)72 456.6 Q
(Comments should be addressed to the)5.5 E(authors, or the WG')72 469.6
Q 2.75(sm)-.605 G(ailing list at rmt@lbl.go)-2.75 E -.715(v.)-.165 G F2
(Abstract)72 501.6 Q F3(This memo describes the use of F)72 524.2 Q(orw)
-.165 E(ard Error Correction codes to ef)-.11 E(\214ciently pro)-.275 E
(vide and/or)-.165 E(augment reliability for one-to-man)72 537.2 Q 2.75
(yr)-.165 G(eliable data transport using IP multicast.)-2.75 E
(One of the k)5.5 E -.165(ey)-.11 G(properties of F)72 550.2 Q(orw)-.165
E(ard Error Correction codes in this conte)-.11 E
(xt is the ability to use the same pack)-.165 E(ets)-.11 E(containing F)
72 563.2 Q(orw)-.165 E
(ard Error Correction data to simultaneously repair dif)-.11 E
(ferent pack)-.275 E(et loss patterns at)-.11 E(multiple recei)72 576.2
Q -.165(ve)-.275 G 2.75(rs. Dif).165 F(ferent classes of F)-.275 E(orw)
-.165 E(ard Error Correction codes and some of their basic)-.11 E
(properties are described and terminology rele)72 589.2 Q -.275(va)-.275
G(nt to implementing F).275 E(orw)-.165 E(ard Error Correction)-.11 E
(Codes in a reliable multicast protocol is introduced.)72 602.2 Q
(Examples are pro)5.5 E(vided of possible abstract)-.165 E
(formats for pack)72 615.2 Q(ets carrying F)-.11 E(orw)-.165 E
(ard Error Correction data.)-.11 E(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 166.856(wcroft [P)
-.275 F(age 1])-.165 E EP
%%Page: 2 2
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 13/Times-Bold@0 SF -1.196
(Ta)239.126 85 S(ble of Contents)1.196 E/F2 10/Times-Roman@0 SF
(1. Rationale and Ov)72 123 Q(ervie)-.15 E(w)-.25 E F0 11
(......................)6.2 G F2(3)11.5 E
(1.1. Application of FEC codecs)82 135 Q F0 11(....................)4.4
G F2(5)11.5 E(2. FEC Codes)72 147 Q F0 11(..........................)
2.16 G F2(6)11.5 E(2.1. Simple codes)82 159 Q F0 11
(........................)4.39 G F2(6)11.5 E(2.2. Small block FEC codes)
82 171 Q F0 11(.....................)5.08 G F2(7)11.5 E(2.3. Lar)82 183
Q(ge block FEC codes)-.18 E F0 11(.....................)5.28 G F2(9)11.5
E(2.4. Expandable FEC codes)82 195 Q F0 11(.....................)5.93 G
F2(9)11.5 E(2.5. Source blocks with v)82 207 Q
(ariable length source symbols)-.25 E F0 11(.............)6.19 G F2(11)
6.5 E(3. Security Considerations)72 219 Q F0 11(......................)
7.17 G F2(12)6.5 E(4. Intellectual Property Disclosure)72 231 Q F0 11
(....................)3.3 G F2(12)6.5 E(5. Ackno)72 243 Q(wledgments)
-.25 E F0 11(........................).76 G F2(12)6.5 E(6. References)72
255 Q F0 11(..........................)3.58 G F2(12)6.5 E
(7. Authors' Addresses)72 267 Q F0 11(.......................)10.1 G F2
(13)6.5 E(8. Full Cop)72 279 Q(yright Statement)-.1 E F0 11
(......................)1.42 G F2(15)6.5 E F0(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 166.856(wcroft [P)
-.275 F(age 2])-.165 E EP
%%Page: 3 3
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 11/Times-Bold@0 SF(1.)72
85 Q/F2 14/Times-Bold@0 SF(Rationale and Ov)5.5 E(er)-.14 E(view)-.14 E
F0(There are man)72 101.6 Q 2.75(yw)-.165 G(ays to pro)-2.86 E
(vide reliability for transmission protocols.)-.165 E 2.75(Ac)5.5 G
(ommon method is to)-2.75 E
(use ARQ, automatic request for retransmission.)72 114.6 Q -.44(Wi)5.5 G
(th ARQ, recei).44 E -.165(ve)-.275 G(rs use a back channel to the).165
E(sender to send requests for retransmission of lost pack)72 127.6 Q
2.75(ets. ARQ)-.11 F -.11(wo)2.75 G(rks well for one-to-one).11 E
(reliable protocols, as e)72 140.6 Q(videnced by the perv)-.275 E(asi)
-.275 E .33 -.165(ve s)-.275 H(uccess of TCP/IP).165 E 5.5(.A)-1.221 G
(RQ has also been an)-5.5 E(ef)72 153.6 Q(fecti)-.275 E .33 -.165(ve r)
-.275 H(eliability tool for one-to-man).165 E 2.75(yr)-.165 G
(eliability protocols, and in particular for some reliable)-2.75 E
(IP multicast protocols.)72 166.6 Q(Ho)5.5 E(we)-.275 E -.165(ve)-.275 G
.88 -.44(r, f).165 H(or one-to-v).44 E(ery-man)-.165 E 2.75(yr)-.165 G
(eliability protocols, ARQ has)-2.75 E
(limitations, including the feedback implosion problem because man)72
179.6 Q 2.75(yr)-.165 G(ecei)-2.75 E -.165(ve)-.275 G
(rs are transmitting).165 E(back to the sender)72 192.6 Q 2.75(,a)-.44 G
(nd the need for a back channel to send these requests from the recei)
-2.75 E -.165(ve)-.275 G -.605(r.).165 G
(Another limitation is that recei)72 205.6 Q -.165(ve)-.275 G(rs may e)
.165 E(xperience dif)-.165 E(ferent loss patterns of pack)-.275 E
(ets, and thus)-.11 E(recei)72 218.6 Q -.165(ve)-.275 G
(rs may be delayed by retransmission of pack).165 E
(ets that other recei)-.11 E -.165(ve)-.275 G(rs ha).165 E .33 -.165
(ve l)-.22 H(ost that b).165 E(ut the)-.22 E(y)-.165 E(ha)72 231.6 Q .33
-.165(ve a)-.22 H(lready recei).165 E -.165(ve)-.275 G 2.75(d. This).165
F(may also cause w)2.75 E
(asteful use of bandwidth used to retransmit pack)-.11 E(ets)-.11 E
(that ha)72 244.6 Q .33 -.165(ve a)-.22 H(lready been recei).165 E -.165
(ve)-.275 G 2.75(db).165 G 2.75(ym)-2.75 G(an)-2.75 E 2.75(yo)-.165 G
2.75(ft)-2.75 G(he recei)-2.75 E -.165(ve)-.275 G(rs.).165 E(In en)72
270.6 Q(vironments where ARQ is either costly or impossible because the\
re is either a v)-.44 E(ery limited)-.165 E(capacity back channel or no\
 back channel at all, such as satellite transmission, a Data Carousel)72
283.6 Q(approach to reliability is sometimes used [1]. W)72 296.6 Q
(ith a Data Carousel, the sender partitions the)-.44 E(object into equa\
l length pieces of data, which we hereafter call source symbols, places\
 them into)72 309.6 Q(pack)72 322.6 Q(ets, and then continually c)-.11 E
(ycles through and sends these pack)-.165 E(ets. Recei)-.11 E -.165(ve)
-.275 G(rs continually).165 E(recei)72 335.6 Q .33 -.165(ve p)-.275 H
(ack).165 E(ets until the)-.11 E 2.75(yh)-.165 G -2.475 -.22(av e)-2.75
H(recei)2.97 E -.165(ve)-.275 G 2.75(dac).165 G(op)-2.75 E 2.75(yo)-.11
G 2.75(fe)-2.75 G(ach pack)-2.75 E 2.75(et. Data)-.11 F
(Carousel has the adv)2.75 E(antage)-.275 E
(that it requires no back channel because there is no data that \215o)72
348.6 Q(ws from recei)-.275 E -.165(ve)-.275 G(rs to the sender).165 E
(.)-.605 E(Ho)72 361.6 Q(we)-.275 E -.165(ve)-.275 G .88 -.44(r, D).165
H(ata Carousel also has limitations. F).44 E(or e)-.165 E
(xample, if a recei)-.165 E -.165(ve)-.275 G 2.75(rl).165 G(oses a pack)
-2.75 E(et in one)-.11 E(round of transmission it must w)72 374.6 Q
(ait an entire round before it has a chance to recei)-.11 E .33 -.165
(ve t)-.275 H(hat pack).165 E(et)-.11 E(ag)72 387.6 Q 2.75(ain. This)
-.055 F(may also cause w)2.75 E
(asteful use of bandwidth, as the sender continually c)-.11 E
(ycles through)-.165 E(and transmits the pack)72 400.6 Q
(ets until no recei)-.11 E -.165(ve)-.275 G 2.75(ri).165 G 2.75(sm)-2.75
G(issing a pack)-2.75 E(et.)-.11 E -.165(Fo)72 426.6 S(rw).165 E
(ard Error Correction \(FEC\) codes pro)-.11 E
(vide a reliability method that can be used to augment)-.165 E
(or replace other reliability methods, especially for one-to-man)72
439.6 Q 2.75(yr)-.165 G(eliability protocols such as)-2.75 E
(reliable IP multicast.)72 452.6 Q 1.76 -.88(We \214)5.5 H
(rst brie\215y re).88 E(vie)-.275 E 2.75(ws)-.275 G
(ome of the basic properties and types of FEC codes)-2.75 E(before re)72
465.6 Q(vie)-.275 E(wing their uses in the conte)-.275 E
(xt of reliable IP multicast.)-.165 E(Later)5.5 E 2.75(,w)-.44 G 2.75
(ep)-2.75 G(ro)-2.75 E(vide a more)-.165 E
(detailed description of some of FEC codes.)72 478.6 Q
(In the general literature, FEC refers to the ability to o)72 504.6 Q
-.165(ve)-.165 G(rcome both erasures \(losses\) and bit-le).165 E -.165
(ve)-.275 G(l).165 E(corruption. Ho)72 517.6 Q(we)-.275 E -.165(ve)-.275
G .88 -.44(r, i).165 H 2.75(nt).44 G
(he case of an IP multicast protocol, the netw)-2.75 E
(ork layers will detect)-.11 E(corrupted pack)72 530.6 Q
(ets and discard them or the transport layers can use pack)-.11 E
(et authentication to)-.11 E(discard corrupted pack)72 543.6 Q 2.75
(ets. Therefore)-.11 F
(the primary application of FEC codes to IP multicast)2.75 E
(protocols is as an erasure code.)72 556.6 Q
(The payloads are generated and processed using an FEC erasure)5.5 E
(encoder and objects are reassembled from reception of pack)72 569.6 Q
(ets containing the generated encoding)-.11 E
(using the corresponding FEC erasure decoder)72 582.6 Q(.)-.605 E(The i\
nput to an FEC encoder is some number k of equal length source symbols.)
72 608.6 Q(The FEC)5.5 E(encoder generates some number of encoding symb\
ols that are of the same length as the source)72 621.6 Q 2.75
(symbols. The)72 634.6 R(chosen length of the symbols can v)2.75 E
(ary upon each application of the FEC encoder)-.275 E(,)-.44 E
(or it can be \214x)72 647.6 Q 2.75(ed. These)-.165 F
(encoding symbols are placed into pack)2.75 E(ets for transmission.)-.11
E(The number)5.5 E(of encoding symbols placed into each pack)72 660.6 Q
(et can v)-.11 E(ary on a per pack)-.275 E(et basis, or a \214x)-.11 E
(ed number of)-.165 E
(symbols \(often one\) can be placed into each pack)72 673.6 Q 2.75
(et. Also,)-.11 F(in each pack)2.75 E(et is placed enough)-.11 E(inform\
ation to identify the particular encoding symbols carried in that pack)
72 686.6 Q 2.75(et. Upon)-.11 F(receipt of)2.75 E(pack)72 699.6 Q
(ets containing encoding symbols, the recei)-.11 E -.165(ve)-.275 G 2.75
(rf).165 G(eeds these encoding symbols into the)-2.75 E
(corresponding FEC decoder to recreate an e)72 712.6 Q(xact cop)-.165 E
2.75(yo)-.11 G 2.75(ft)-2.75 G(he k source symbols.)-2.75 E(Ideally)5.5
E 2.75(,t)-.715 G(he FEC)-2.75 E(decoder can recreate an e)72 725.6 Q
(xact cop)-.165 E 2.75(yf)-.11 G(rom an)-2.75 E 2.75(yko)-.165 G 2.75
(ft)-2.75 G(he encoding symbols.)-2.75 E(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 117.356
(wcroft Section)-.275 F 2.75(1. [P)2.75 F(age 3])-.165 E EP
%%Page: 4 4
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E(In a later section, we descr\
ibe a technique for using FEC codes as described abo)72 85 Q .33 -.165
(ve t)-.165 H 2.75(oh).165 G(andle)-2.75 E(blocks with v)72 98 Q
(ariable length source symbols.)-.275 E(Block FEC codes w)72 124 Q
(ork as follo)-.11 E 2.75(ws. The)-.275 F
(input to a block FEC encoder is k source symbols and a)2.75 E
(number n.)72 137 Q
(The encoder generates a total of n encoding symbols.)5.5 E
(The encoder is systematic if it)5.5 E(generates n-k redundant symbols \
yielding an encoding block of n encoding symbols in total)72 150 Q
(composed of the k source symbols and the n-k redundant symbols.)72 163
Q 2.75(Ab)5.5 G(lock FEC decoder has the)-2.75 E(property that an)72 176
Q 2.75(yko)-.165 G 2.75(ft)-2.75 G
(he n encoding symbols in the encoding block is suf)-2.75 E
(\214cient to reconstruct)-.275 E(the original k source symbols.)72 189
Q(Expandable FEC codes w)72 215 Q(ork as follo)-.11 E 2.75(ws. An)-.275
F -.165(ex)2.75 G(pandable FEC encoder tak).165 E(es as input k source)
-.11 E(symbols and generates as man)72 228 Q 2.75(yu)-.165 G
(nique encoding symbols as requested on demand, where the)-2.75 E(amoun\
t of time for generating each encoding symbol is the same independent o\
f ho)72 241 Q 2.75(wm)-.275 G(an)-2.75 E(y)-.165 E
(encoding symbols are generated.)72 254 Q(An e)5.5 E
(xpandable FEC decoder has the property that an)-.165 E 2.75(yko)-.165 G
2.75(ft)-2.75 G(he)-2.75 E(unique encoding symbols is suf)72 267 Q
(\214cient to reconstruct the original k source symbols.)-.275 E
(The abo)72 293 Q .33 -.165(ve d)-.165 H(e\214nitions e).165 E
(xplain the ideal situation when the reception of an)-.165 E 2.75(yke)
-.165 G(ncoding symbols is)-2.75 E(suf)72 306 Q(\214cient to reco)-.275
E -.165(ve)-.165 G 2.75(rt).165 G
(he k source symbols, in which case the reception o)-2.75 E -.165(ve)
-.165 G(rhead is 0%.).165 E -.165(Fo)5.5 G 2.75(rs).165 G(ome)-2.75 E(p\
ractical FEC codes, slightly more than k encoding symbols are needed to\
 reco)72 319 Q -.165(ve)-.165 G 2.75(rt).165 G(he k source)-2.75 E 2.75
(symbols. If)72 332 R
(k*\(1+ep\) encoding symbols are needed, we say the reception o)2.75 E
-.165(ve)-.165 G(rhead is ep*100%,).165 E
(e.g., if k*1.05 encoding symbols are needed then the reception o)72 345
Q -.165(ve)-.165 G(rhead is 5%.).165 E(Along a dif)72 371 Q(ferent dime\
nsion, we classify FEC codes loosely as being either small or lar)-.275
E 2.75(ge. A)-.198 F(small FEC code is ef)72 384 Q(\214cient in terms o\
f processing time requirements for encoding and decoding)-.275 E
(for small v)72 397 Q(alues of k, and a lar)-.275 E(ge FEC code is ef)
-.198 E(\214cient for encoding and decoding for much lar)-.275 E(ge)
-.198 E -.275(va)72 410 S(lues of k.).275 E
(There are implementations of block FEC codes that ha)5.5 E .33 -.165
(ve e)-.22 H(ncoding times).165 E(proportional to n-k times the length \
of the k source symbols, and decoding times proportional to l)72 423 Q(\
times the length of the k source symbols, where l is the number of miss\
ing source symbols among)72 436 Q(the k recei)72 449 Q -.165(ve)-.275 G
2.75(de).165 G(ncoding symbols and l can be as lar)-2.75 E(ge as k.)
-.198 E(Because of the gro)5.5 E(wth rate of the)-.275 E(encoding and d\
ecoding times as a product of k and n-k, these are typically considered\
 to be small)72 462 Q(block FEC codes.)72 475 Q
(There are block FEC codes with a small reception o)5.5 E -.165(ve)-.165
G(rhead that can generate n).165 E(encoding symbols and can decode the \
k source symbols in time proportional to the length of the n)72 488 Q
(encoding symbols.)72 501 Q(These codes are considered to be lar)5.5 E
(ge block FEC codes.)-.198 E(There are)5.5 E -.165(ex)72 514 S
(pandable FEC codes with a small reception o).165 E -.165(ve)-.165 G
(rhead that can generate each encoding symbol).165 E(in time roughly pr\
oportional to its length, and can decode all k source symbols in time r\
oughly)72 527 Q(proportional to their length.)72 540 Q
(These are considered to be lar)5.5 E(ge e)-.198 E(xpandable FEC codes.)
-.165 E -.88(We)5.5 G(describe e)72 553 Q
(xamples of all of these types of codes later)-.165 E(.)-.605 E(Ideally)
72 579 Q 2.75(,F)-.715 G(EC codes in the conte)-2.75 E
(xt of IP multicast can be used to generate encoding symbols that)-.165
E(are transmitted in pack)72 592 Q(ets in such a w)-.11 E
(ay that each recei)-.11 E -.165(ve)-.275 G 2.75(dp).165 G(ack)-2.75 E
(et is fully useful to a recei)-.11 E -.165(ve)-.275 G 2.75(rt).165 G(o)
-2.75 E(reassemble the object re)72 605 Q -.055(ga)-.165 G
(rdless of pre).055 E(vious pack)-.275 E
(et reception patterns. Thus, if some pack)-.11 E(ets are)-.11 E
(lost in transit between the sender and the recei)72 618 Q -.165(ve)
-.275 G .88 -.44(r, i).165 H
(nstead of asking for speci\214c retransmission of).44 E(the lost pack)
72 631 Q(ets or w)-.11 E(aiting till the pack)-.11 E
(ets are resent using Data Carousel, the recei)-.11 E -.165(ve)-.275 G
2.75(rc).165 G(an use an)-2.75 E(y)-.165 E
(other subsequent equal number of pack)72 644 Q(ets that arri)-.11 E .33
-.165(ve t)-.275 H 2.75(or).165 G(eassemble the object.)-2.75 E
(These pack)5.5 E(ets can)-.11 E(either be proacti)72 657 Q -.165(ve)
-.275 G(ly transmitted or the).165 E 2.75(yc)-.165 G(an be e)-2.75 E
(xplicitly requested by recei)-.165 E -.165(ve)-.275 G 2.75(rs. This)
.165 F(implies)2.75 E(that the same pack)72 670 Q
(et is fully useful to all recei)-.11 E -.165(ve)-.275 G
(rs to reassemble the object, e).165 E -.165(ve)-.275 G 2.75(nt).165 G
(hough the)-2.75 E(recei)72 683 Q -.165(ve)-.275 G(rs may ha).165 E .33
-.165(ve p)-.22 H(re).165 E(viously e)-.275 E(xperienced dif)-.165 E
(ferent pack)-.275 E(et loss patterns.)-.11 E(This property can)5.5 E
(reduce or e)72 696 Q -.165(ve)-.275 G 2.75(ne).165 G
(liminate the problems mentioned abo)-2.75 E .33 -.165(ve a)-.165 H
(ssociated with ARQ and Data Carousel).165 E(and thereby dramatically i\
ncrease the scalability of the protocol to orders of magnitude more)72
709 Q(recei)72 722 Q -.165(ve)-.275 G(rs.).165 E(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 117.356
(wcroft Section)-.275 F 2.75(1. [P)2.75 F(age 4])-.165 E EP
%%Page: 5 5
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 11/Times-Bold@0 SF(1.1.)72
85 Q/F2 13/Times-Bold@0 SF -.325(Ap)5.5 G(plication of FEC codecs).325 E
F0 -.165(Fo)72 101.6 S 2.75(rs).165 G(ome reliable IP multicast protoco\
ls, FEC codes are used in conjunction with ARQ to pro)-2.75 E(vide)-.165
E(reliability)72 114.6 Q 5.5(.F)-.715 G(or e)-5.665 E(xample, a lar)
-.165 E(ge object could be partitioned into a number of source blocks)
-.198 E(consisting of a small number of source symbols each, and in a \
\214rst round of transmission all of)72 127.6 Q
(the source symbols for all the source blocks could be transmitted.)72
140.6 Q(Then, recei)5.5 E -.165(ve)-.275 G(rs could report).165 E
(back to the sender the number of source symbols the)72 153.6 Q 2.75(ya)
-.165 G(re missing from each source block.)-2.75 E(The)5.5 E(sender cou\
ld then compute the maximum number of missing source symbols from each \
source)72 166.6 Q(block among all recei)72 179.6 Q -.165(ve)-.275 G 2.75
(rs. Based).165 F
(on this, a small block FEC encoder could be used to generate)2.75 E(fo\
r each source block a number of redundant symbols equal to the computed\
 maximum number)72 192.6 Q
(of missing source symbols from the block among all recei)72 205.6 Q
-.165(ve)-.275 G(rs, as long as this maximum).165 E
(maximum for each block does not e)72 218.6 Q
(xceed the number of redundant symbols that can be generated)-.165 E(ef)
72 231.6 Q(\214ciently)-.275 E 5.5(.I)-.715 G 2.75(nas)-5.5 G
(econd round of transmission, the serv)-2.75 E(er w)-.165 E
(ould then send all of these redundant)-.11 E(symbols for all blocks.)72
244.6 Q(In this e)5.5 E
(xample, if there are no losses in the second round of transmission)
-.165 E(then all recei)72 257.6 Q -.165(ve)-.275 G
(rs will be able to recreate an e).165 E(xact cop)-.165 E 2.75(yo)-.11 G
2.75(fe)-2.75 G(ach original block.)-2.75 E(In this case, e)5.5 E -.165
(ve)-.275 G(n).165 E(if dif)72 270.6 Q(ferent recei)-.275 E -.165(ve)
-.275 G(rs are missing dif).165 E(ferent symbols in dif)-.275 E
(ferent blocks, transmitted redundant)-.275 E(symbols for a gi)72 283.6
Q -.165(ve)-.275 G 2.75(nb).165 G(lock are useful to all recei)-2.75 E
-.165(ve)-.275 G(rs missing symbols from that block in the).165 E
(second round.)72 296.6 Q -.165(Fo)72 322.6 S 2.75(ro).165 G(ther relia\
ble IP multicast protocols, FEC codes are used in a Data Carousel f)
-2.75 E(ashion to)-.11 E(pro)72 335.6 Q(vide reliability)-.165 E 2.75
(,w)-.715 G(hich we call an FEC Data Carousel.)-2.75 E -.165(Fo)5.5 G
2.75(re).165 G(xample, an FEC Data Carousel)-2.915 E(using a lar)72
348.6 Q(ge block FEC code could w)-.198 E(ork as follo)-.11 E 2.75
(ws. The)-.275 F(lar)2.75 E(ge block FEC encoder produces n)-.198 E(enc\
oding symbols considering all the k source symbols of an object as one \
block. The sender)72 361.6 Q -.165(cy)72 374.6 S
(cles through and transmits the n encoding symbols in pack).165 E
(ets in the same order in each round.)-.11 E
(An FEC Data Carousel can ha)72 387.6 Q .33 -.165(ve m)-.22 H
(uch better protection ag).165 E(ainst pack)-.055 E
(et loss than a Data Carousel.)-.11 E -.165(Fo)72 400.6 S 2.75(re).165 G
(xample, a recei)-2.915 E -.165(ve)-.275 G 2.75(rc).165 G
(an join the transmission at an)-2.75 E 2.75(yp)-.165 G
(oint in time, and, as long as the recei)-2.75 E -.165(ve)-.275 G(r).165
E(recei)72 413.6 Q -.165(ve)-.275 G 2.75(sa).165 G 2.75(tl)-2.75 G
(east k encoding symbols during the transmission of the ne)-2.75 E
(xt n encoding symbols, the)-.165 E(recei)72 426.6 Q -.165(ve)-.275 G
2.75(rc).165 G(an completely reco)-2.75 E -.165(ve)-.165 G 2.75(rt).165
G(he object.)-2.75 E(This is true e)5.5 E -.165(ve)-.275 G 2.75(ni).165
G 2.75(ft)-2.75 G(he recei)-2.75 E -.165(ve)-.275 G 2.75(rs).165 G
(tarts recei)-2.75 E(ving)-.275 E(pack)72 439.6 Q
(ets in the middle of a pass through the encoding symbols.)-.11 E
(This method can also be used)5.5 E(when the object is partitioned into\
 blocks and a short block FEC code is applied to each block)72 452.6 Q
(separately)72 465.6 Q 5.5(.I)-.715 G 2.75(nt)-5.5 G(his case, as we e)
-2.75 E(xplain in more detail belo)-.165 E 1.43 -.715(w, i)-.275 H 2.75
(ti).715 G 2.75(su)-2.75 G(seful to interlea)-2.75 E .33 -.165(ve t)-.22
H(he symbols).165 E(from the dif)72 478.6 Q(ferent blocks when the)-.275
E 2.75(ya)-.165 G(re transmitted.)-2.75 E(Since an)72 504.6 Q 2.75(yn)
-.165 G(umber of encoding symbols can be generated using an e)-2.75 E
(xpandable FEC encoder)-.165 E(,)-.44 E
(reliable IP multicast protocols that use e)72 517.6 Q
(xpandable FEC codes generally rely solely on these codes)-.165 E
(for reliability)72 530.6 Q 5.5(.F)-.715 G(or e)-5.665 E
(xample, when an e)-.165 E
(xpandable FEC code is used in a FEC Data Carousel)-.165 E
(application, the encoding pack)72 543.6 Q(ets ne)-.11 E -.165(ve)-.275
G 2.75(rr).165 G(epeat, and thus an)-2.75 E 2.75(yko)-.165 G 2.75(ft)
-2.75 G(he encoding symbols in the)-2.75 E
(potentially unbounded number of encoding symbols are suf)72 556.6 Q
(\214cient to reco)-.275 E -.165(ve)-.165 G 2.75(rt).165 G
(he original k source)-2.75 E(symbols.)72 569.6 Q -.165(Fo)72 595.6 S
2.75(ry).165 G(et other reliable IP multicast protocols the method to o\
btain reliability is to generate enough)-2.75 E(encoding symbols so tha\
t each encoding symbol is transmitted at most once.)72 608.6 Q -.165(Fo)
5.5 G 2.75(re).165 G(xample, the)-2.915 E(sender can decide a priori ho)
72 621.6 Q 2.75(wm)-.275 G(an)-2.75 E 2.75(ye)-.165 G
(ncoding symbols it will transmit, use an FEC code to)-2.75 E(generate \
that number of encoding symbols from the object, and then transmit the \
encoding)72 634.6 Q(symbols to all recei)72 647.6 Q -.165(ve)-.275 G
2.75(rs. This).165 F(method is for e)2.75 E
(xample applicable to streaming protocols, where the)-.165 E(stream is \
partitioned into objects, the source symbols for each object are encode\
d into encoding)72 660.6 Q(symbols using an FEC code, and then the sets\
 of encoding symbols for each object are)72 673.6 Q
(transmitted one after the other using IP multicast.)72 686.6 Q(Luby/V)
72 769 Q(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 109.106
(wcroft Section)-.275 F 2.75(1.1. [P)2.75 F(age 5])-.165 E EP
%%Page: 6 6
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 11/Times-Bold@0 SF(2.)72
85 Q/F2 14/Times-Bold@0 SF(FEC Codes)5.5 E F1(2.1.)72 124 Q/F3 13
/Times-Bold@0 SF(Simple codes)5.5 E F0(There are some v)72 140.6 Q
(ery simple codes that are ef)-.165 E(fecti)-.275 E .33 -.165(ve f)-.275
H(or repairing pack).165 E(et loss under v)-.11 E(ery lo)-.165 E 2.75
(wl)-.275 G(oss)-2.75 E 2.75(conditions. F)72 153.6 R(or e)-.165 E
(xample, one simple w)-.165 E(ay to pro)-.11 E
(vide protection from a single loss is to partition)-.165 E
(the object into \214x)72 166.6 Q(ed size source symbols and then add a\
 redundant symbol that is the parity)-.165 E
(\(XOR\) of all the source symbols.)72 179.6 Q
(The size of a source symbol is chosen so that it \214ts perfectly)5.5 E
(into the payload of a pack)72 192.6 Q(et, i.e. if the pack)-.11 E
(et payload is 512 bytes then each source symbol is 512)-.11 E 2.75
(bytes. The)72 205.6 R(header of each pack)2.75 E
(et contains enough information to identify the payload.)-.11 E(In this)
5.5 E(case, this is an encoding symbol ID.)72 218.6 Q
(The encoding symbol IDs can consist of tw)5.5 E 2.75(op)-.11 G
(arts in this)-2.75 E -.165(ex)72 231.6 S 2.75(ample. The).165 F(\214rs\
t part is an encoding \215ag that is equal to 1 if the encoding symbol \
is a source)2.75 E
(symbol and is equal to 0 if the encoding symbol is a redundant symbol.)
72 244.6 Q(The second part of the)5.5 E(encoding symbol ID is a source \
symbol ID if the encoding \215ag is 1 and a redundant symbol ID if)72
257.6 Q(the encoding \215ag is 0.)72 270.6 Q
(The source symbol IDs can be numbered from 0 to k-1 and the redundant)
5.5 E(symbol ID can be 0.)72 283.6 Q -.165(Fo)5.5 G 2.75(re).165 G
(xample, if the object consists of four source symbols that ha)-2.915 E
.33 -.165(ve v)-.22 H(alues)-.11 E(a, b, c and d, then the v)72 296.6 Q
(alue of the redundant symbol is e = a XOR b XOR c XOR d.)-.275 E
(Then, the)5.5 E(pack)72 309.6 Q(ets carrying these symbols look lik)
-.11 E(e)-.11 E
(\(1, 0: a\), \(1, 1: b\), \(1, 2: c\), \(1, 3: d\), \(0, 0: e\).)
188.714 322.6 Q(In this e)72 348.6 Q
(xample, the encoding symbol ID consists of the \214rst tw)-.165 E 2.75
(ov)-.11 G(alues, where the \214rst v)-3.025 E(alue is)-.275 E
(the encoding \215ag and the second v)72 361.6 Q
(alue is either a source symbol ID or the redundant symbol ID.)-.275 E
(The portion of the pack)72 374.6 Q(et after the colon is the v)-.11 E
(alue of the encoding symbol.)-.275 E(An)5.5 E 2.75(ys)-.165 G
(ingle source)-2.75 E(symbol of the object can be reco)72 387.6 Q -.165
(ve)-.165 G(red as the parity of all the other symbols.).165 E -.165(Fo)
5.5 G 2.75(re).165 G(xample, if)-2.915 E(pack)72 400.6 Q(ets)-.11 E
(\(1, 0: a\), \(1, 1: b\), \(1, 3: d\), \(0, 0: e\))210.098 413.6 Q
(are recei)72 439.6 Q -.165(ve)-.275 G 2.75(dt).165 G
(hen the missing source symbol v)-2.75 E
(alue with source symbol ID = 2 can be reco)-.275 E -.165(ve)-.165 G
(red by).165 E(computing a XOR b XOR d XOR e = c.)72 452.6 Q(Another w)
72 478.6 Q(ay of forming the encoding symbol ID is to let v)-.11 E
(alues 0,...,k-1 correspond to the k)-.275 E(source symbols and v)72
491.6 Q(alue k correspond to the redundant symbol that is the XOR of th\
e k source)-.275 E(symbols.)72 504.6 Q
(When the number of source symbols in the object is lar)72 530.6 Q
(ge, a simple block code v)-.198 E(ariant of the)-.275 E(abo)72 543.6 Q
.33 -.165(ve c)-.165 H(an be used.).165 E(In this case, the source symb\
ols are grouped together into source blocks of)5.5 E
(some number k of consecuti)72 556.6 Q .33 -.165(ve s)-.275 H
(ymbols each, where k may be dif).165 E(ferent for dif)-.275 E
(ferent blocks.)-.275 E(If a)5.5 E(block consists of k source symbols t\
hen a redundant symbol is added to form an encoding block)72 569.6 Q
(consisting of k+1 encoding symbols.)72 582.6 Q
(Then, a source block consisting of k source symbols can be)5.5 E(reco)
72 595.6 Q -.165(ve)-.165 G(red from an).165 E 2.75(yko)-.165 G 2.75(ft)
-2.75 G(he k+1 encoding symbols from the associated encoding block.)
-2.75 E(Slightly more sophisticated w)72 621.6 Q
(ays of adding redundant symbols using parity can also be used. F)-.11 E
(or)-.165 E -.165(ex)72 634.6 S(ample, one can group a block consisting\
 of k source symbols in an object into a p x p square).165 E
(matrix, where p = sqrt\(k\).)72 647.6 Q(Then, for each ro)5.5 E 2.75
(war)-.275 G(edundant symbol is added that is the parity of all)-2.75 E
(the source symbols in the ro)72 660.6 Q 4.18 -.715(w. S)-.275 H
(imilarly).715 E 2.75(,f)-.715 G
(or each column a redundant symbol is added that is the)-2.75 E
(parity of all the source symbols in the column.)72 673.6 Q(Then, an)5.5
E 2.75(yr)-.165 G .55 -.275(ow o)-2.75 H 2.75(ft).275 G
(he matrix can be reco)-2.75 E -.165(ve)-.165 G(red).165 E(from an)72
686.6 Q 2.75(ypo)-.165 G 2.75(ft)-2.75 G(he p+1 symbols in the ro)-2.75
E 1.43 -.715(w, a)-.275 H(nd similarly for an).715 E 2.75(yc)-.165 G
2.75(olumn. Higher)-2.75 F(dimensional)2.75 E
(product codes using this technique can also be used.)72 699.6 Q(Ho)5.5
E(we)-.275 E -.165(ve)-.275 G .88 -.44(r, o).165 H(ne must be w).44 E
(ary of using these)-.11 E(constructions without some thought to)72
712.6 Q -.11(wa)-.275 G(rds the possible loss patterns of symbols.).11 E
(Ideally)5.5 E 2.75(,t)-.715 G(he)-2.75 E(property that one w)72 725.6 Q
(ould lik)-.11 E 2.75(et)-.11 G 2.75(oo)-2.75 G
(btain is that if k source symbols are encoded into n encoding)-2.75 E
(Luby/V)72 769 Q(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E
109.106(wcroft Section)-.275 F 2.75(2.1. [P)2.75 F(age 6])-.165 E EP
%%Page: 7 7
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E(symbols \(the encoding symbo\
ls consist of the source symbols and the redundant symbols\) then)72 85
Q(the k source symbols can be reco)72 98 Q -.165(ve)-.165 G(red from an)
.165 E 2.75(yko)-.165 G 2.75(ft)-2.75 G(he n encoding symbols.)-2.75 E
(Using the simple)5.5 E(constructions described abo)72 111 Q .33 -.165
(ve d)-.165 H
(oes not yield codes that come close to obtaining this ideal).165 E
(beha)72 124 Q(vior)-.22 E(.)-.605 E/F1 11/Times-Bold@0 SF(2.2.)72 163 Q
/F2 13/Times-Bold@0 SF(Small block FEC codes)5.5 E F0(Reliable IP multi\
cast protocols may use a block \(n, k\) FEC code [2]. F)72 179.6 Q
(or such codes, k source)-.165 E
(symbols are encoded into n > k encoding symbols, such that an)72 192.6
Q 2.75(yko)-.165 G 2.75(ft)-2.75 G(he encoding symbols can)-2.75 E
(be used to reassemble the original k source symbols.)72 205.6 Q
(Thus, these codes ha)5.5 E .33 -.165(ve n)-.22 H 2.75(or).165 G
(eception)-2.75 E -.165(ove)72 218.6 S
(rhead when used to encode the entire object directly).165 E 5.5(.B)
-.715 G(lock codes are usually systematic,)-5.5 E(which means that the \
n encoding symbols consist of the k source symbols and n-k redundant)72
231.6 Q(symbols generated from these k source symbols, where the size o\
f a redundant symbol is the)72 244.6 Q
(same as that for a source symbol.)72 257.6 Q -.165(Fo)5.5 G 2.75(re)
.165 G(xample, the \214rst simple code \(XOR\) described in the)-2.915 E
(pre)72 270.6 Q(vious subsection is a \(k+1, k\) code.)-.275 E
(In general, the freedom to choose n lar)5.5 E(ger than k+1 is)-.198 E
(desirable, as this can pro)72 283.6 Q(vide much better protection ag)
-.165 E(ainst losses.)-.055 E 2.75(Ap)5.5 G(opular e)-2.75 E
(xample of these)-.165 E(types of codes is a class of Reed-Solomon code\
s, which are based on algebraic methods using)72 296.6 Q
(\214nite \214elds.)72 309.6 Q
(Implementations of \(n, k\) FEC erasure codes are ef)5.5 E
(\214cient enough to be used by)-.275 E(personal computers [16]. F)72
322.6 Q(or e)-.165 E
(xample, [15] describes an implementation where the encoding and)-.165 E
(decoding speeds decay as C/j, where the constant C is on the order of \
10 to 80 Mbytes/second for)72 335.6 Q(Pentium class machines of v)72
348.6 Q(arious vintages and j is upper bounded by min\(k, n-k\).)-.275 E
(In practice, the v)72 374.6 Q(alues of k and n must be small \(for e)
-.275 E(xample belo)-.165 E 2.75(w2)-.275 G(56\) for such FEC codes as)
-2.75 E(lar)72 387.6 Q(ge v)-.198 E(alues mak)-.275 E 2.75(ee)-.11 G
(ncoding and decoding prohibiti)-2.75 E -.165(ve)-.275 G(ly e).165 E
(xpensi)-.165 E -.165(ve)-.275 G 5.5(.A).165 G 2.75(sm)-5.5 G(an)-2.75 E
2.75(yo)-.165 G(bjects are longer)-2.75 E
(than k symbols for reasonable v)72 400.6 Q
(alues of k and the symbol length \(e.g. lar)-.275 E
(ger than 16 kilobyte for k)-.198 E 2.75(=1)72 413.6 S 2.75(6u)-2.75 G
(sing 1 kilobyte symbols\), the)-2.75 E 2.75(yc)-.165 G(an be di)-2.75 E
(vided into a number of source blocks.)-.275 E(Each source)5.5 E
(block consists of some number k of source symbols, where k may v)72
426.6 Q(ary between dif)-.275 E(ferent source)-.275 E 2.75(blocks. The)
72 439.6 R(FEC encoder is used to encode a k source symbol source block\
 into a n encoding)2.75 E(symbol encoding block, where the number n of \
encoding symbols in the encoding block may v)72 452.6 Q(ary)-.275 E
(for each source block.)72 465.6 Q -.165(Fo)5.5 G 2.75(rar).165 G(ecei)
-2.75 E -.165(ve)-.275 G 2.75(rt).165 G 2.75(oc)-2.75 G(ompletely reco)
-2.75 E -.165(ve)-.165 G 2.75(rt).165 G
(he object, for each source block)-2.75 E(consisting of k source symbol\
s, k distinct encoding symbols \(i.e., with dif)72 478.6 Q
(ferent encoding symbol)-.275 E(IDs\) must be recei)72 491.6 Q -.165(ve)
-.275 G 2.75(df).165 G(rom the corresponding encoding block.)-2.75 E
-.165(Fo)5.5 G 2.75(rs).165 G(ome encoding blocks, more)-2.75 E
(encoding symbols may be recei)72 504.6 Q -.165(ve)-.275 G 2.75(dt).165
G(han there are source symbols in the corresponding source)-2.75 E
(block, in which case the e)72 517.6 Q
(xcess encoding symbols are discarded.)-.165 E(An e)5.5 E
(xample encoding structure)-.165 E(is sho)72 530.6 Q(wn in Figure 1.)
-.275 E(Luby/V)72 769 Q(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165
E 109.106(wcroft Section)-.275 F 2.75(2.2. [P)2.75 F(age 7])-.165 E EP
%%Page: 8 8
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 8/Courier@0 SF 14.4(|s)
91.2 85 S(ource symbol IDs)-14.4 E 14.4(|s)14.4 G(ource symbols IDs)
-14.4 E(|)9.6 E 14.4(|o)91.2 98 S 4.8(fs)-14.4 G(ource block 0)-4.8 E
14.4(|o)14.4 G 4.8(fs)-14.4 G(ource block 1)-4.8 E(|)14.4 E 124.8(||)
153.6 111 S 124.8(vv)153.6 124 S
(+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+)91.2 137 Q
(|0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 |)91.2 150 Q
(+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+)91.2 163 Q(|)206.4
176 Q(FEC encoder)187.2 189 Q(|)206.4 202 Q(v)206.4 215 Q
(+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+)72 228 Q
(|0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|)72 241 Q
(+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+)72 254 Q
139.2(^^)144 267 S 139.2(||)144 280 S 9.6(|e)72 293 S
(ncoding symbol IDs)-9.6 E 4.8(|e)38.4 G(ncoding symbol IDs)-4.8 E(|)
43.2 E 9.6(|o)72 306 S 4.8(fe)-9.6 G(ncoding block 0)-4.8 E 4.8(|o)38.4
G 4.8(fe)-4.8 G(ncoding block 1)-4.8 E(|)43.2 E/F2 10/Times-Roman@0 SF
(Figure 1. The encoding structure for an object di)72 345 Q
(vided into tw)-.25 E 2.5(os)-.1 G(ource)-2.5 E(blocks consisting of 8 \
source symbols each, and the FEC encoder is used to)72 358 Q(generate 2\
 additional redundant symbols \(10 encoding symbols in total\))72 371 Q
(for each of the tw)72 384 Q 2.5(os)-.1 G(ource blocks.)-2.5 E F0
(In man)72 413.6 Q 2.75(yc)-.165 G(ases, an object is partitioned into \
equal length source blocks each consisting of k)-2.75 E(contiguous sour\
ce symbols of the object, i.e., block c consists of the range of source\
 symbols [ck,)72 426.6 Q 2.75(\(c+1\)k-1]. This)72 439.6 R(ensures that\
 the FEC encoder can be optimized to handle a particular number k)2.75 E
(of source symbols.)72 452.6 Q(This also ensures that memory references\
 are local when the sender reads)5.5 E
(source symbols to encode, and when the recei)72 465.6 Q -.165(ve)-.275
G 2.75(rr).165 G(eads encoding symbols to decode.)-2.75 E(Locality of)
5.5 E(reference is particularly important when the object is stored on \
disk, as it reduces the disk seeks)72 478.6 Q 2.75(required. The)72
491.6 R(block number and the source symbol ID within that block can be \
used to uniquely)2.75 E(specify a source symbol within the object. If t\
he size of the object is not a multiple of k source)72 504.6 Q
(symbols, then the last source block will contain less than k symbols.)
72 517.6 Q(The block numbers can be numbered consecuti)72 543.6 Q -.165
(ve)-.275 G(ly starting from zero.).165 E(Encoding symbols within)5.5 E
2.75(ab)72 556.6 S
(lock can be uniquely identi\214ed by an encoding symbol ID.)-2.75 E
(One w)5.5 E(ay of identifying encoding)-.11 E(symbols within a block i\
s to use the combination of an encoding \215ag that identi\214es the sy\
mbol as)72 569.6 Q(either a source symbol or a redundant symbol togethe\
r with either a source symbol ID or a)72 582.6 Q(redundant symbol ID.)72
595.6 Q -.165(Fo)5.5 G 2.75(re).165 G(xample, an encoding \215ag v)
-2.915 E(alue of 1 can indicate that the encoding)-.275 E(symbol is a s\
ource symbol and 0 can indicate that it is a redundant symbol.)72 608.6
Q(The source symbol)5.5 E(IDs can be numbered from 0 to k-1 and the red\
undant symbol IDs can be numbered from 0 to n-)72 621.6 Q(k-1.)72 634.6
Q -.165(Fo)72 660.6 S 2.75(re).165 G
(xample, if the object consists 10 source symbols with v)-2.915 E
(alues a, b, c, d, e, f, g, h, i, and j, and)-.275 E 2.75(k=5a)72 673.6
S(nd n = 8, then there are tw)-2.75 E 2.75(os)-.11 G
(ource blocks consisting of 5 symbols each, and there are tw)-2.75 E(o)
-.11 E(encoding blocks consisting of 8 symbols each.)72 686.6 Q
(Let p, q and r be the v)5.5 E(alues of the redundant)-.275 E
(symbols for the \214rst encoding block, and let x, y and z be the v)72
699.6 Q(alues of the redundant symbols for)-.275 E
(the second encoding block.)72 712.6 Q
(Then the encoding symbols together with their identi\214ers are)5.5 E
(Luby/V)72 769 Q(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E
109.106(wcroft Section)-.275 F 2.75(2.2. [P)2.75 F(age 8])-.165 E EP
%%Page: 9 9
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 8/Courier@0 SF(\(0, 1, 0:\
 a\), \(0, 1, 1: b\), \(0, 1, 2: c\), \(0, 1, 3: d\), \(0, 1, 4: e\),)72
85 Q(\(0, 0, 0: p\), \(0, 0, 1: q\), \(0, 0, 2: r\),)72 98 Q(\(1, 1, 0:\
 f\), \(1, 1, 1: g\), \(1, 1, 2: h\), \(1, 1, 3: i\), \(1, 1, 4: j\),)72
111 Q(\(1, 0, 0: x\), \(1, 0, 1: y\), \(1, 0, 2: z\).)72 124 Q F0
(In this e)72 153.6 Q(xample, the \214rst v)-.165 E
(alue identi\214es the block number and the second tw)-.275 E 2.75(ov)
-.11 G(alues together)-3.025 E(identify the encoding symbol within the \
block, i.e, the encoding symbol ID consists of the)72 166.6 Q(encoding \
\215ag together with either the source symbol ID or the redundant symbo\
l ID depending)72 179.6 Q(on the v)72 192.6 Q
(alue of the encoding \215ag.)-.275 E(The v)5.5 E
(alue of the encoding symbol is written after the colon.)-.275 E
(Each block can be reco)72 205.6 Q -.165(ve)-.165 G(red from an).165 E
2.75(y5o)-.165 G 2.75(ft)-2.75 G
(he 8 encoding symbols associated with that block.)-2.75 E -.165(Fo)72
218.6 S 2.75(re).165 G(xample, reception of)-2.915 E/F2 11/Courier@0 SF
(\(0, 1, 1: b\), \(0, 1, 2: c\), \(0, 1, 3: d\), \(0, 0, 0: p\), \(0, 0\
, 1: q\))72 244.6 Q F0(is suf)74.75 270.6 Q(\214cient to reco)-.275 E
-.165(ve)-.165 G 2.75(rt).165 G
(he \214rst source block, and reception of)-2.75 E F2(\(1, 1, 0: f\), \
\(1, 1, 1: g\), \(1, 0, 0: x\), \(1, 0, 1: y\), \(1, 0, 2: z\))72 296.6
Q F0(is suf)72 335.6 Q(\214cient to reco)-.275 E -.165(ve)-.165 G 2.75
(rt).165 G(he second source block.)-2.75 E(Another w)72 361.6 Q(ay of u\
niquely identifying encoding symbols within a block is to let the encod\
ing)-.11 E(symbol IDs for source symbols be 0,...,k-1 and to let the en\
coding symbol IDs for redundant)72 374.6 Q(symbols be k,...,n-1.)72
387.6 Q/F3 11/Times-Bold@0 SF(2.3.)72 426.6 Q/F4 13/Times-Bold@0 SF(Lar)
5.5 E(ge block FEC codes)-.13 E F0 -.88(To)72 443.2 S
(rnado codes [12], [13], [10], [11], [9] are lar).88 E
(ge block FEC codes that pro)-.198 E(vide an alternati)-.165 E .33 -.165
(ve t)-.275 H(o).165 E(small block FEC codes.)72 456.2 Q(An \(n, k\) T)
5.5 E(ornado code requires slightly more than k out of n encoding)-.88 E
(symbols to reco)72 469.2 Q -.165(ve)-.165 G 2.75(rks).165 G
(ource symbols, i.e., there is a small reception o)-2.75 E -.165(ve)
-.165 G 2.75(rhead. The).165 F(bene\214t of the)2.75 E
(small cost of non-zero reception o)72 482.2 Q -.165(ve)-.165 G
(rhead is that the v).165 E(alue of k may be on the order of tens of)
-.275 E(thousands and still the encoding and decoding are ef)72 495.2 Q
2.75(\214cient. Because)-.275 F(of memory considerations,)2.75 E
(in practice the v)72 508.2 Q
(alue of n is restricted to be a small multiple of k, e.g., n = 2k.)
-.275 E -.165(Fo)5.5 G 2.75(re).165 G(xample, [4])-2.915 E
(describes an implementation of T)72 521.2 Q
(ornado codes where the encoding and decoding speeds are tens)-.88 E
(of me)72 534.2 Q -.055(ga)-.165 G
(bytes per second for Pentium class machines of v).055 E
(arious vintages when k is in the tens of)-.275 E(thousands and n = 2k.)
72 547.2 Q(The reception o)5.5 E -.165(ve)-.165 G(rhead for such v).165
E(alues of k and n is in the 5-10% range.)-.275 E -.88(To)72 560.2 S
(rnado codes require a lar).88 E
(ge amount of out of band information to be communicated to all)-.198 E
(senders and recei)72 573.2 Q -.165(ve)-.275 G(rs for each dif).165 E
(ferent object length, and require an amount of memory on the)-.275 E(e\
ncoder and decoder which is proportional to the object length times 2n/\
k.)72 586.2 Q -.88(To)72 612.2 S(rnado codes are designed to ha).88 E
.33 -.165(ve l)-.22 H .55 -.275(ow r).165 H(eception o).275 E -.165(ve)
-.165 G(rhead on a).165 E -.165(ve)-.22 G
(rage with respect to reception).165 E
(of a random portion of the encoding pack)72 625.2 Q 2.75(ets. Thus,)
-.11 F(to ensure that a recei)2.75 E -.165(ve)-.275 G 2.75(rc).165 G
(an reassemble the)-2.75 E(object with lo)72 638.2 Q 2.75(wr)-.275 G
(eception o)-2.75 E -.165(ve)-.165 G(rhead, the pack).165 E
(ets are permuted into a random order before)-.11 E(transmission.)72
651.2 Q F3(2.4.)72 690.2 Q F4(Expandable FEC codes)5.5 E F0
(All of the FEC codes described up to this point are block codes.)72
706.8 Q(There is a dif)5.5 E(ferent type of FEC)-.275 E
(codes that we call e)72 719.8 Q(xpandable FEC codes.)-.165 E(Lik)5.5 E
2.75(eb)-.11 G(lock codes, an e)-2.75 E(xpandable FEC encoder)-.165 E
(Luby/V)72 769 Q(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E
109.106(wcroft Section)-.275 F 2.75(2.4. [P)2.75 F(age 9])-.165 E EP
%%Page: 10 10
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E(operates on an object of kno)
72 85 Q(wn size that is partitioned into equal length source symbols.)
-.275 E(Unlik)5.5 E(e)-.11 E(block codes, there is no predetermined num\
ber of encoding symbols that can be generated for)72 98 Q -.165(ex)72
111 S(pandable FEC codes. Instead, an e).165 E
(xpandable FEC encoder can generate as fe)-.165 E 2.75(wo)-.275 G 2.75
(ra)-2.75 G 2.75(sm)-2.75 G(an)-2.75 E(y)-.165 E
(unique encoding symbols as required on demand.)72 124 Q 2.024 -1.012
(LT c)72 150 T(odes [6], [7], [8], [5] are an e)1.012 E(xample of lar)
-.165 E(ge e)-.198 E(xpandable FEC codes with a small reception)-.165 E
-.165(ove)72 163 S 2.75(rhead. An).165 F 2.024 -1.012(LT e)2.75 H(ncode\
r uses randomization to generate each encoding symbol randomly and)1.012
E(independently of all other encoding symbols.)72 176 Q(Lik)5.5 E 2.75
(eT)-.11 G(ornado codes, the number of source symbols)-3.63 E 2.75(km)72
189 S(ay be v)-2.75 E(ery lar)-.165 E(ge for L)-.198 E 2.75(Tc)-1.012 G
(odes, i.e., on the order of tens to hundreds of thousands, and the)
-2.75 E(encoder and decoder run ef)72 202 Q(\214ciently in softw)-.275 E
(are. F)-.11 E(or e)-.165 E(xample the encoding and decoding speeds)
-.165 E(for L)72 215 Q 2.75(Tc)-1.012 G(odes are in the range 3-20 me)
-2.75 E -.055(ga)-.165 G
(bytes per second for Pentium class machines of v).055 E(arious)-.275 E
(vintages when k is in the high tens of thousands.)72 228 Q(An L)5.5 E
2.75(Te)-1.012 G(ncoder can generate as fe)-2.75 E 2.75(wo)-.275 G 2.75
(ra)-2.75 G 2.75(sm)-2.75 G(an)-2.75 E(y)-.165 E
(encoding symbols as required on demand.)72 241 Q(When a ne)5.5 E 2.75
(we)-.275 G(ncoding symbol is to be generated by an)-2.75 E 2.024 -1.012
(LT e)72 254 T(ncoder)1.012 E 2.75(,i)-.44 G 2.75(ti)-2.75 G 2.75(sb)
-2.75 G(ased on a randomly chosen encoding symbol ID that uniquely desc\
ribes ho)-2.75 E(w)-.275 E(the encoding symbol is to be generated from \
the source symbols. In general, each encoding)72 267 Q(symbol ID v)72
280 Q(alue corresponds to a unique encoding symbol, and thus the space \
of possible)-.275 E
(encoding symbols is approximately four billion if for e)72 293 Q
(xample the encoding symbol ID is 4 bytes.)-.165 E
(Thus, the chance that a particular encoding symbol is the same as an)72
306 Q 2.75(yo)-.165 G(ther particular encoding)-2.75 E(symbol is in)72
319 Q -.165(ve)-.44 G
(rsely proportional to the number of possible encoding symbol IDs.).165
E(An L)5.5 E 2.75(Td)-1.012 G(ecoder)-2.75 E
(has the property that with v)72 332 Q
(ery high probability the receipt of an)-.165 E 2.75(ys)-.165 G
(et of slightly more than k)-2.75 E
(randomly and independently generated encoding symbols is suf)72 345 Q
(\214cient to reassemble the k source)-.275 E 2.75(symbols. F)72 358 R
(or e)-.165 E(xample, when k is on the order of tens to hundreds of tho\
usands the reception)-.165 E -.165(ove)72 371 S
(rhead is less than 5% with no f).165 E
(ailures in hundreds of millions of trials under an)-.11 E 2.75(yl)-.165
G(oss)-2.75 E(conditions.)72 384 Q(Because encoding symbols are randoml\
y and independently generated by choosing random)72 410 Q
(encoding symbol IDs, L)72 423 Q 2.75(Tc)-1.012 G(odes ha)-2.75 E .33
-.165(ve t)-.22 H
(he property that encoding symbols for the same k source).165 E(symbols\
 can be generated and transmitted from multiple senders and recei)72 436
Q -.165(ve)-.275 G 2.75(db).165 G 2.75(yar)-2.75 G(ecei)-2.75 E -.165
(ve)-.275 G 2.75(ra).165 G(nd)-2.75 E(the reception o)72 449 Q -.165(ve)
-.165 G(rhead and the decoding time is the same as if though all the en\
coding symbols).165 E(were generated by a single sender)72 462 Q 5.5(.T)
-.605 G(he only requirement is that the senders choose their)-5.5 E
(encoding symbol IDs randomly and independently of one another)72 475 Q
(.)-.605 E(There is a weak tradeof)72 501 Q 2.75(fb)-.275 G
(etween the number of source symbols and the reception o)-2.75 E -.165
(ve)-.165 G(rhead for).165 E 2.024 -1.012(LT c)72 514 T
(odes, and the lar)1.012 E
(ger the number of source symbols the smaller the reception o)-.198 E
-.165(ve)-.165 G 2.75(rhead. Thus,).165 F
(for shorter objects, it is sometimes adv)72 527 Q
(antageous to partition the object into man)-.275 E 2.75(ys)-.165 G
(hort source)-2.75 E
(symbols and include multiple encoding symbols in each pack)72 540 Q
2.75(et. In)-.11 F(this case, a single encoding)2.75 E(symbol ID is use\
d to identify the multiple encoding symbols contained in a single pack)
72 553 Q(et.)-.11 E(There are a couple of f)72 579 Q
(actors for choosing the appropriate symbol length/ number of source)
-.11 E(symbols tradeof)72 592 Q
(f. The primary consideration is that there is a \214x)-.275 E(ed o)
-.165 E -.165(ve)-.165 G(rhead per symbol in the).165 E -.165(ove)72 605
S(rall processing requirements of the encoding and decoding, independen\
t of the number of).165 E(source symbols.)72 618 Q
(Thus, using shorter symbols means that this \214x)5.5 E(ed o)-.165 E
-.165(ve)-.165 G(rhead processing per).165 E(symbol will be a lar)72 631
Q(ger component of the o)-.198 E -.165(ve)-.165 G
(rall processing requirements, leading to lar).165 E(ger)-.198 E -.165
(ove)72 644 S(rall processing requirements.).165 E 2.75(As)5.5 G
(econd much less important consideration is that there is a)-2.75 E
(component of the processing per symbol that depends log)72 657 Q
(arithmically on the number of source)-.055 E
(symbols, and thus for this reason there is a slight preference to)72
670 Q -.11(wa)-.275 G(rds fe).11 E(wer source symbols.)-.275 E(Lik)72
696 Q 2.75(es)-.11 G
(mall block codes, there is a point when the object is lar)-2.75 E
(ge enough that it mak)-.198 E(es sense to)-.11 E
(partition it into blocks when using L)72 709 Q 2.75(Tc)-1.012 G 2.75
(odes. Generally)-2.75 F(the object is partitioned into blocks)2.75 E
(whene)72 722 Q -.165(ve)-.275 G 2.75(rt).165 G
(he number of source symbols times the pack)-2.75 E
(et payload length is less than the size of)-.11 E(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 103.606
(wcroft Section)-.275 F 2.75(2.4. [P)2.75 F(age 10])-.165 E EP
%%Page: 11 11
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E(the object.)72 85 Q
(Thus, if the pack)5.5 E
(et payload is 1024 bytes and the maximum number of source)-.11 E
(symbols is 128,000 then an)72 98 Q 2.75(yo)-.165 G(bject o)-2.75 E
-.165(ve)-.165 G 2.75(r1).165 G(28 me)-2.75 E -.055(ga)-.165 G
(bytes will be partitioned into more than one).055 E 2.75(block. One)72
111 R(can choose the maximum number of source symbols to use, depending\
 on the desired)2.75 E(encoding and decoding speed v)72 124 Q
(ersus reception o)-.165 E -.165(ve)-.165 G(rhead tradeof).165 E 2.75
(fd)-.275 G 2.75(esired. Encoding)-2.75 F(symbols can)2.75 E
(be uniquely identi\214ed by a block number \(when the object is lar)72
137 Q(ge enough to be partitioned into)-.198 E
(more than one block\) and an encoding symbol ID.)72 150 Q
(The block numbers, if the)5.5 E 2.75(ya)-.165 G(re used, are)-2.75 E
(generally numbered consecuti)72 163 Q -.165(ve)-.275 G
(ly starting from zero within the object. The block number and the).165
E(encoding symbol ID are both chosen uniformly and randomly from their \
range when an encoding)72 176 Q(symbol is to be transmitted. F)72 189 Q
(or e)-.165 E
(xample, suppose the number of source symbols is 128,000 and)-.165 E
(the number of blocks is 2.)72 202 Q(Then, each pack)5.5 E
(et generated by the L)-.11 E 2.75(Te)-1.012 G
(ncoder could be of the form)-2.75 E(\(b, x: y\).)72 215 Q(In this e)5.5
E(xample, the \214rst v)-.165 E
(alue identi\214es the block number and the second v)-.275 E(alue)-.275
E(identi\214es the encoding symbol within the block.)72 228 Q(In this e)
5.5 E(xample, the block number b is either 0)-.165 E
(or 1, and the encoding symbol ID x might be a 32-bit v)72 241 Q 2.75
(alue. The)-.275 F -.275(va)2.75 G(lue y after the colon is the).275 E
-.275(va)72 254 S(lue of the encoding symbol.).275 E/F1 11/Times-Bold@0
SF(2.5.)72 293 Q/F2 13/Times-Bold@0 SF(Sour)5.5 E(ce blocks with v)-.234
E(ariable length sour)-.13 E(ce symbols)-.234 E F0 -.165(Fo)72 309.6 S
2.75(ra).165 G(ll the FEC codes described abo)-2.75 E -.165(ve)-.165 G
2.75(,a).165 G
(ll the source symbols in the same source block are all of)-2.75 E
(the same length.)72 322.6 Q(In this section, we describe a general tec\
hnique to handle the case when it is)5.5 E
(desirable to use source symbols of v)72 335.6 Q
(arying lengths in a single source block.)-.275 E(This technique is)5.5
E(applicable to block FEC codes.)72 348.6 Q
(Let l_1, l_2, ... , l_k be the lengths in bytes of k v)72 374.6 Q
(arying length source symbols to be considered)-.275 E
(part of the same source block.)72 387.6 Q(Let lmax be the maximum o)5.5
E -.165(ve)-.165 G 2.75(ri=1).165 G 2.75(,.)-2.75 G(.. , k of l_i.)-2.75
E 1.76 -.88(To p)5.5 H(repare the).88 E
(source block for the FEC encoder)72 400.6 Q 2.75(,p)-.44 G
(ad each source symbol i out to length lmax with a suf)-2.75 E(\214x of)
-.275 E(lmax-l_i zeroes, and then prepend to the be)72 413.6 Q
(ginning of this the v)-.165 E(alue l_i.)-.275 E(Thus, each padded)5.5 E
(source symbol is of length x+lmax, assuming that it tak)72 426.6 Q
(es x bytes to store an inte)-.11 E(ger with possible)-.165 E -.275(va)
72 439.6 S(lues 0,...,lmax, where x is a protocol constant kno).275 E
(wn to both the encoder and the decoder)-.275 E(.)-.605 E(These padded \
source symbols, each of length x+lmax, are the input to the encoder)72
452.6 Q 2.75(,t)-.44 G(ogether with)-2.75 E(the v)72 465.6 Q(alue n.)
-.275 E(The encoder then generates n-k redundant symbols, each of lengt\
h x+lmax.)5.5 E(The encoding symbols that are placed into pack)72 491.6
Q(ets consist of the original k v)-.11 E(arying length source)-.275 E
(symbols and n-k redundant symbols, each of length x+lmax.)72 504.6 Q
(From an)5.5 E 2.75(yko)-.165 G 2.75(ft)-2.75 G(he recei)-2.75 E -.165
(ve)-.275 G(d).165 E(encoding symbols, the FEC decoder recreates the k \
original source symbols as follo)72 517.6 Q 2.75(ws. If)-.275 F(all k)
2.75 E(original source symbols are recei)72 530.6 Q -.165(ve)-.275 G
(d, then no decoding is necessary).165 E 5.5(.O)-.715 G
(therwise, at least one)-5.5 E(redundant symbol is recei)72 543.6 Q
-.165(ve)-.275 G(d, from which the recei).165 E -.165(ve)-.275 G 2.75
(rc).165 G(an easily determine if the block is)-2.75 E(composed of v)72
556.6 Q(ariable-length source symbols: if the redundant symbol\(s\) is \
longer than the source)-.275 E(symbols then the source symbols are v)72
569.6 Q(ariable-length. Note that in a v)-.275 E
(ariable-length block the)-.275 E(redundant symbols are al)72 582.6 Q
-.11(wa)-.11 G
(ys longer than the longest source symbol, due to the presence of the)
.11 E(prepended symbol-length.)72 595.6 Q(The recei)5.5 E -.165(ve)-.275
G 2.75(rc).165 G(an determine the v)-2.75 E
(alue of lmax by subtracting x from)-.275 E(the length of a recei)72
608.6 Q -.165(ve)-.275 G 2.75(dr).165 G(edundant symbol.)-2.75 E -.165
(Fo)5.5 G 2.75(re).165 G(ach of the recei)-2.75 E -.165(ve)-.275 G 2.75
(do).165 G(riginal source symbols, the)-2.75 E(recei)72 621.6 Q -.165
(ve)-.275 G 2.75(rc).165 G
(an generate the corresponding padded source symbol as described abo)
-2.75 E -.165(ve)-.165 G 5.5(.T).165 G(hen, the)-5.5 E
(input to the FEC decoder is the set of recei)72 634.6 Q -.165(ve)-.275
G 2.75(dr).165 G(edundant symbols, together with the set of padded)-2.75
E(source symbols constructed from the recei)72 647.6 Q -.165(ve)-.275 G
2.75(do).165 G(riginal symbols.)-2.75 E(The FEC decoder then produces)
5.5 E(the set of k padded source symbols.)72 660.6 Q
(Once the k padded source symbols ha)5.5 E .33 -.165(ve b)-.22 H
(een reco).165 E -.165(ve)-.165 G(red, the).165 E
(length l_i of original source symbol i can be reco)72 673.6 Q -.165(ve)
-.165 G(red from the \214rst x bytes of the ith padded).165 E(source sy\
mbol, and then original source symbol i is obtained by taking the ne)72
686.6 Q(xt l_i bytes)-.165 E(follo)72 699.6 Q
(wing the x bytes of the length \214eld.)-.275 E(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 103.606
(wcroft Section)-.275 F 2.75(2.5. [P)2.75 F(age 11])-.165 E EP
%%Page: 12 12
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 11/Times-Bold@0 SF(3.)72
85 Q/F2 14/Times-Bold@0 SF(Security Considerations)5.5 E F0(The use of \
FEC, in and of itself, imposes no additional security considerations v)
72 101.6 Q(ersus sending the)-.165 E(same information without FEC.)72
114.6 Q(Ho)5.5 E(we)-.275 E -.165(ve)-.275 G .88 -.44(r, j).165 H
(ust lik).44 E 2.75(ef)-.11 G(or an)-2.75 E 2.75(yt)-.165 G
(ransmission system, a malicious)-2.75 E(sender may try to inject pack)
72 127.6 Q(ets carrying corrupted encoding symbols.)-.11 E(If a recei)
5.5 E -.165(ve)-.275 G 2.75(ra).165 G(ccepts one)-2.75 E(or more corrup\
ted encoding symbol in place of authentic ones then such a recei)72
140.6 Q -.165(ve)-.275 G 2.75(rm).165 G(ay)-2.75 E
(reconstruct a corrupted object.)72 153.6 Q(Application-le)72 179.6 Q
-.165(ve)-.275 G 2.75(lt).165 G
(ransmission object authentication can detect the corrupted transfer)
-2.75 E 2.75(,b)-.44 G(ut the)-2.97 E(recei)72 192.6 Q -.165(ve)-.275 G
2.75(rm).165 G(ust then discard the transferred object. Thus, injecting\
 corrupted encoding symbols the)-2.75 E(y)-.165 E(are accepted as v)72
205.6 Q(alid encoding symbols by a recei)-.275 E -.165(ve)-.275 G 2.75
(ri).165 G 2.75(sa)-2.75 G 2.75(tt)-2.75 G(he v)-2.75 E(ery least an ef)
-.165 E(fecti)-.275 E .33 -.165(ve d)-.275 H(enial of).165 E
(service attack.)72 218.6 Q(In light of this possibility)72 244.6 Q 2.75
(,F)-.715 G(EC recei)-2.75 E -.165(ve)-.275 G
(rs may screen the source address of a recei).165 E -.165(ve)-.275 G
2.75(ds).165 G(ymbol)-2.75 E(ag)72 257.6 Q
(ainst a list of authentic transmitter addresses.)-.055 E
(Since source addresses may be spoofed, transport)5.5 E
(protocols using FEC may pro)72 270.6 Q(vide mechanisms for rob)-.165 E
(ust source authentication of each encoding)-.22 E
(symbol. Multicast routers along the path of a FEC transfer may pro)72
283.6 Q(vide the capability of)-.165 E(discarding multicast pack)72
296.6 Q(ets that originated on that subnet, and whose source IP address\
 does not)-.11 E(correspond with that subnet.)72 309.6 Q
(It is recommended that a pack)72 335.6 Q
(et authentication scheme such as TESLA [14] be used in)-.11 E
(conjunction with FEC codes.)72 348.6 Q(Then, pack)5.5 E
(ets that cannot be authenticated can be discarded and the)-.11 E
(object can be reliably reco)72 361.6 Q -.165(ve)-.165 G
(red from the recei).165 E -.165(ve)-.275 G 2.75(da).165 G
(uthenticated pack)-2.75 E(ets.)-.11 E F1(4.)72 400.6 Q F2
(Intellectual Pr)5.5 E(operty Disclosur)-.252 E(e)-.252 E F0(The IETF h\
as been noti\214ed of intellectual property rights claimed in re)72
417.2 Q -.055(ga)-.165 G(rd to some or all of the).055 E
(speci\214cation contained in this document.)72 430.2 Q -.165(Fo)5.5 G
2.75(rm).165 G(ore information consult the online list of claimed)-2.75
E(rights.)72 443.2 Q F1(5.)72 482.2 Q F2(Ackno)5.5 E(wledgments)-.14 E
F0(Thanks to V)72 498.8 Q(incent Roca and Hayder Radha for their detail\
ed comments on this draft.)-.66 E F1(6.)72 537.8 Q F2(Refer)5.5 E(ences)
-.252 E F0([1] Acharya, S., Franklin, M., and Zdonik, S., `)72 554.4 Q
(`Dissemination- Based Data Deli)-.814 E -.165(ve)-.275 G(ry Using).165
E(Broadcast Disks')72 567.4 Q
(', IEEE Personal Communications, pp.50-60, Dec 1995.)-.814 E
([2] Blahut, R.E., `)72 593.4 Q
(`Theory and Practice of Error Control Codes')-.814 E(', Addison W)-.814
E(esle)-.88 E 1.43 -.715(y, M)-.165 H 2.75(A1).715 G(984.)-2.75 E
([3] Bradner)72 619.4 Q 2.75(,S)-.44 G
(., "The Internet Standards Process -- Re)-2.75 E
(vision 3", RFC2026, October 1996.)-.275 E([4] Byers, J.W)72 645.4 Q
(., Luby)-1.012 E 2.75(,M)-.715 G(., Mitzenmacher)-2.75 E 2.75(,M)-.44 G
(., and Re)-2.75 E(ge, A., `)-.165 E 1.76 -.88(`A D)-.814 H(igital F).88
E(ountain Approach to)-.165 E(Reliable Distrib)72 658.4 Q
(ution of Bulk Data')-.22 E(', Proceedings A)-.814 E(CM SIGCOMM '98, V)
-.44 E(ancouv)-1.221 E(er)-.165 E 2.75(,C)-.44 G(anada,)-2.75 E
(Sept 1998.)72 671.4 Q([5] Hak)72 697.4 Q(en, A., Luby)-.11 E 2.75(,M)
-.715 G(., Horn, G., Hernek, D., Byers, J., Mitzenmacher)-2.75 E 2.75
(,M)-.44 G(., "Generating high)-2.75 E
(weight encoding symbols using a basis", U.S. P)72 710.4 Q
(atent No. 6,411,223, June 25, 2002.)-.165 E(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 111.856
(wcroft Section)-.275 F 2.75(6. [P)2.75 F(age 12])-.165 E EP
%%Page: 13 13
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E([6] Luby)72 85 Q 2.75(,M)
-.715 G(., "Information Additi)-2.75 E .33 -.165(ve C)-.275 H
(ode Generator and Decoder for Communication Systems",).165 E(U.S. P)72
98 Q(atent No. 6,307,487, October 23, 2001.)-.165 E([7] Luby)72 124 Q
2.75(,M)-.715 G(., "Information Additi)-2.75 E .33 -.165(ve G)-.275 H
(roup Code Generator and Decoder for Communication).165 E
(Systems", U.S. P)72 137 Q(atent No. 6,320,520, No)-.165 E -.165(ve)
-.165 G(mber 20, 2001.).165 E([8] Luby)72 163 Q 2.75(,M)-.715 G
(., "Information Additi)-2.75 E .33 -.165(ve C)-.275 H
(ode Generator and Decoder for Communication Systems",).165 E(U.S. P)72
176 Q(atent No. 6,373,406, April 16, 2002.)-.165 E([9] Luby)72 202 Q
2.75(,M)-.715 G(., Mitzenmacher)-2.75 E 2.75(,`)-.44 G
(`Loss resilient code with double hea)-3.564 E
(vy tailed series of redundant)-.22 E(layers')72 215 Q(', U.S. P)-.814 E
(atent No. 6,195,777, February 27, 2001.)-.165 E([10] Luby)72 241 Q 2.75
(,M)-.715 G(., Mitzenmacher)-2.75 E 2.75(,M)-.44 G
(., Shokrollahi, A., Spielman, D., Stemann, V)-2.75 E(., `)-1.419 E
(`Message)-.814 E(encoding with irre)72 254 Q(gular graphing')-.165 E
(', U.S. P)-.814 E(atent No. 6,163,870, December 19, 2000.)-.165 E
([11] Luby)72 280 Q 2.75(,M)-.715 G(., Mitzenmacher)-2.75 E 2.75(,M)-.44
G(., Shokrollahi, A., Spielman, D., `)-2.75 E(`Ef)-.814 E
(\214cient Erasure Correcting)-.275 E(Codes')72 293 Q(', IEEE T)-.814 E
(ransactions on Information Theory)-.385 E 2.75(,S)-.715 G
(pecial Issue: Codes on Graphs and Iterati)-2.75 E -.165(ve)-.275 G
(Algorithms, pp. 569-584, V)72 306 Q(ol. 47, No. 2, February 2001.)
-1.419 E([12] Luby)72 332 Q 2.75(,M)-.715 G
(., Shokrollahi, A., Stemann, V)-2.75 E(., Mitzenmacher)-1.419 E 2.75
(,M)-.44 G(., Spielman, D., `)-2.75 E(`Loss resilient)-.814 E
(decoding technique')72 345 Q(', U.S. P)-.814 E
(atent No. 6,073,250, June 6, 2000.)-.165 E([13] Luby)72 371 Q 2.75(,M)
-.715 G(., Shokrollahi, A., Stemann, V)-2.75 E(., Mitzenmacher)-1.419 E
2.75(,M)-.44 G(., Spielman, D., `)-2.75 E(`Irre)-.814 E(gularly)-.165 E
(graphed encoding technique')72 384 Q(', U.S. P)-.814 E
(atent No. 6,081,909, June 27, 2000.)-.165 E
([14] Perrig, A., Canetti, R., Song, D., T)72 410 Q(yg)-.88 E(ar)-.055 E
2.75(,J)-.44 G(.D., "Ef)-2.75 E
(\214cient and Secure Source Authentication for)-.275 E
(Multicast", Netw)72 423 Q(ork and Distrib)-.11 E
(uted System Security Symposium, NDSS 2001, pp. 35-46,)-.22 E
(February 2001.)72 436 Q([15] Rizzo, L., `)72 462 Q(`Ef)-.814 E(fecti)
-.275 E .33 -.165(ve E)-.275 H
(rasure Codes for Reliable Computer Communication Protocols').165 E(',)
-.814 E -.44(AC)72 475 S 2.75(MS).44 G(IGCOMM Computer Communication Re)
-2.75 E(vie)-.275 E 1.43 -.715(w, V)-.275 H
(ol.27, No.2, pp.24-36, Apr 1997.)-.704 E([16] Rizzo, L., `)72 501 Q
(`On the Feasibility of Softw)-.814 E(are FEC')-.11 E(', DEIT T)-.814 E
(ech Report,)-.77 E(http://www)72 514 Q
(.iet.unipi.it/~luigi/softfec.ps, Jan 1997.)-.715 E/F1 11/Times-Bold@0
SF(7.)72 566 Q/F2 14/Times-Bold@0 SF -.7(Au)5.5 G(thors' Addr).7 E
(esses)-.252 E F0(Michael Luby)80.25 582.6 Q(luby@digitalfountain.com)
80.25 595.6 Q(Digital F)80.25 608.6 Q(ountain)-.165 E(39141 Ci)80.25
621.6 Q(vic Center Dri)-.275 E -.165(ve)-.275 G(Suite 300)80.25 634.6 Q
(Fremont, CA)80.25 647.6 Q(94538)5.5 E(Lorenzo V)80.25 673.6 Q(icisano)
-.66 E(lorenzo@cisco.com)80.25 686.6 Q(cisco Systems, Inc.)80.25 699.6 Q
(170 W)80.25 712.6 Q(est T)-.88 E(asman Dr)-.88 E(.,)-.605 E
(San Jose, CA, USA, 95134)80.25 725.6 Q(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 111.856
(wcroft Section)-.275 F 2.75(7. [P)2.75 F(age 13])-.165 E EP
%%Page: 14 14
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E(Jim Gemmell)80.25 85 Q
(jgemmell@microsoft.com)80.25 98 Q(Microsoft Research)80.25 111 Q
(301 Ho)80.25 124 Q -.11(wa)-.275 G(rd St., #830).11 E
(San Francisco, CA, USA, 94105)80.25 137 Q(Luigi Rizzo)80.25 163 Q
(luigi@iet.unipi.it)80.25 176 Q(Dip. di Ing. dell'Informazione)80.25 189
Q(Uni)80.25 202 Q -.165(ve)-.275 G(rsita` di Pisa).165 E
(via Diotisalvi 2, 56126 Pisa, Italy)80.25 215 Q(Mark Handle)80.25 241 Q
(y)-.165 E(mjh@icir)80.25 254 Q(.or)-.605 E(g)-.198 E
(ICSI Center for Internet Research)80.25 267 Q(1947 Center St.)80.25 280
Q(Berk)80.25 293 Q(ele)-.11 E 2.75(yC)-.165 G(A, USA, 94704)-2.75 E
(Jon Cro)80.25 319 Q(wcroft)-.275 E(J.Cro)80.25 332 Q
(wcroft@cl.cam.ac.uk)-.275 E
(Marconi Professor of Communications Systems)80.25 345 Q(Uni)80.25 358 Q
-.165(ve)-.275 G(rsity of Cambridge).165 E(Computer Laboratory)80.25 371
Q -.44(Wi)80.25 384 S(lliam Gates Building).44 E 2.75(JJT)80.25 397 S
(homson A)-2.75 E -.165(ve)-.814 G(nue).165 E(Cambridge)80.25 410 Q
(CB3 0FD)80.25 423 Q(Luby/V)72 769 Q(icisano/Gemmell/Rizzo/Handle)-.66 E
(y/Cro)-.165 E 111.856(wcroft Section)-.275 F 2.75(7. [P)2.75 F(age 14])
-.165 E EP
%%Page: 15 15
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E/F1 11/Times-Bold@0 SF(8.)72
85 Q/F2 14/Times-Bold@0 SF(Full Copyright Statement)5.5 E F0(Cop)72
101.6 Q(yright \(C\) The Internet Society \(2002\).)-.11 E
(All Rights Reserv)5.5 E(ed.)-.165 E(This document and translations of \
it may be copied and furnished to others, and deri)72 118.2 Q -.275(va)
-.275 G(ti).275 E .33 -.165(ve w)-.275 H(orks).055 E
(that comment on or otherwise e)72 131.2 Q
(xplain it or assist in its implementation may be prepared, copied,)
-.165 E(published and distrib)72 144.2 Q
(uted, in whole or in part, without restriction of an)-.22 E 2.75(yk)
-.165 G(ind, pro)-2.75 E(vided that the)-.165 E(abo)72 157.2 Q .33 -.165
(ve c)-.165 H(op).165 E(yright notice and this paragraph are included o\
n all such copies and deri)-.11 E -.275(va)-.275 G(ti).275 E .33 -.165
(ve w)-.275 H(orks.).055 E(Ho)72 170.2 Q(we)-.275 E -.165(ve)-.275 G .88
-.44(r, t).165 H(his document itself may not be modi\214ed in an).44 E
2.75(yw)-.165 G(ay)-2.86 E 2.75(,s)-.715 G(uch as by remo)-2.75 E
(ving the)-.165 E(cop)72 183.2 Q(yright notice or references to the Int\
ernet Society or other Internet or)-.11 E -.055(ga)-.198 G(nizations, e)
.055 E(xcept as)-.165 E(needed for the purpose of de)72 196.2 Q -.165
(ve)-.275 G(loping Internet standards in which case the procedures for)
.165 E(cop)72 209.2 Q
(yrights de\214ned in the Internet languages other than English.)-.11 E
(The limited permissions granted abo)72 225.8 Q .33 -.165(ve a)-.165 H
(re perpetual and will not be re).165 E -.22(vo)-.275 G -.11(ke).22 G
2.75(db).11 G 2.75(yt)-2.75 G(he Internet)-2.75 E
(Society or its successors or assigns.)72 238.8 Q
(This document and the information contained herein is pro)72 255.4 Q
(vided on an "AS IS" basis and THE)-.165 E
(INTERNET SOCIETY AND THE INTERNET ENGINEERING T)72 268.4 Q
(ASK FORCE DISCLAIMS)-1.023 E(ALL W)72 281.4 Q
(ARRANTIES, EXPRESS OR IMPLIED, INCLUDING B)-1.32 E(UT NO)-.11 E 2.75
(TL)-.44 G(IMITED T)-2.75 E 2.75(OA)-.198 G(NY)-2.75 E -1.32(WA)72 294.4
S(RRANTY THA)1.32 E 2.75(TT)-1.221 G(HE USE OF THE INFORMA)-2.75 E
(TION HEREIN WILL NO)-1.221 E 2.75(TI)-.44 G(NFRINGE)-2.75 E
(ANY RIGHTS OR ANY IMPLIED W)72 307.4 Q(ARRANTIES OF MERCHANT)-1.32 E
(ABILITY OR FITNESS)-1.023 E(FOR A P)72 320.4 Q(AR)-1.012 E
(TICULAR PURPOSE.")-.66 E(Luby/V)72 769 Q(icisano/Gemmell/Rizzo/Handle)
-.66 E(y/Cro)-.165 E 111.856(wcroft Section)-.275 F 2.75(8. [P)2.75 F
(age 15])-.165 E EP
%%Page: 16 16
%%BeginPageSetup
BP
%%EndPageSetup
/F0 11/Times-Roman@0 SF(INTERNET)72 49 Q 74.337(-DRAFT Expires:)-1.012 F
(March 2003)2.75 E(September 2002)97.766 E(Luby/V)72 769 Q
(icisano/Gemmell/Rizzo/Handle)-.66 E(y/Cro)-.165 E 111.856
(wcroft Section)-.275 F 2.75(8. [P)2.75 F(age 16])-.165 E EP
%%Trailer
end
%%EOF