ࡱ> }z{|`!"J6bpUC;8,\_`Gx] pǕ~]̏Y~db( U(B%hA@,C.}A]%؉K|q;*:(p8 sʕK'gǾ #qRֽ7=;3=3 ]U{{0Hc`Fz;ngT ^/ иKTrLs,Gw5!Pmc0 y/]߆:a-lۉTЋ!YØ̮eq}0@7O2S$08qJ;Gwhj:ݍia"t LQTi[1-t?.L140Na:0)~ )d?쇑}w#vdB}9ߊsǐ@v@v@v@v@v@v@v@v@v@v@v@v@v@v@v٣SywӀ2qחj#8@_>i$InT!,Ks( LKY~F͵-8#f9mm|Oy8j פ1ُ+hv/{|;&l#ocʘ?+O=?wl'ԛ9r3qYuj?{r6z&=uΠ4n}>ymf}p?++/Tk a>S je&~-XjKR:&~viI5s%kzrwM4Vv|G>|Gǭ0Oez^i|_IT.{ztv}MjUوt&ⴔkR&߉5i@kƌ;n4M7[iy XEF%8k6yvYȯfLD|$^&yg 3v^`!%FuK\8Bң'$=>q cOCͱ쀣hX88q'BฏcuGѦñAq0$>q O8pm:+8q'C!q8^Xhب8Ñ8Ñ8q!n`82 sT(X. X. X6fXa^XIJ'!x9`ˆ<,O,O, 3CX>yX IX IXq:`y7yXשO,/O,/"kˋ>|pcF^cx+O3!1#\c s&%G> #OB`9c9Y%2!O>c&X XR[_%c9AX?'S!|c,_] AX?'C`9>]IJ'a1Xq,pvvX?'u!c%,e]. BX?';B`y3Dz˛}alosOׇr#XN< {~ac\بgBtk8ȸIѳ̦MϕĿ~s}xc 1 bz&~]ˣ ׀K `={X^y^^ru͇{^#yN{; qx#Ǜh蘆xc X>\lxq$qSn=8iX8UNK:+H4=QO 4ӼzͅzFy-'KxNJb۫,]2{~O"~?czF܊#_677 h_'t4KRt` by#a 6}xk`r1#,#~PR )i$KP>!+p A]};Op39W|{{2}iNKη'35BX֨[JxGO ouJVSA|{-~_,umHpoZ+^1R%\##_iPweoxo%cxU4^i{E})6;bƵ뭸~v6Tq`=Ů͸ȴx\bKavļv|=R7q|Y kNElp8^~CʊzJ5'SuXڷBmQ[ܺAۺX7ndzdjW|hgNxǽN%=D#%-JxNJņZ:~M^11j|\|3%߬ⴔw7Ӽzͣ&xזhWo{8-k*wF25@Vl\Eg,7bѸF,\9QǪN*%9V3{p3{氣0i"Rsq9#/oڟ壒/oᴔ|9X1\$פn=D#tkX;V'j9X~N+Is@csH{TJVy}Ɯpwc9T{Q7OoS;V7!ޮeһ&꘽o\u?׊6?3ŵqǶRlKmrl&b }fC9{.w0 |o9IrqYΟ?[jiNKΟϯ KyC2ޱcoi-+JxNJ]ņWYī_+mAU |ΗjCƫcRJmr$#J`)|Bnb߇ϳol>\1O_y'?|#VyFN{ωo焥Ӻ>m>n/n=wxO(6rpccUj?&S]^|5\ω狃siPwP|Ci]y=JUC|v$^%~zV%= ǫ-h"W>H* ;>bm~ `:; +AxmW=H)xyB̓?_1G9mŝ\,/⑟%RBZN{L5Wbpk͞E1/]cLJ2\rA|G-}C2yRV4^l.NkwkϞx۴x-+ޝņZ:&%:U?+pTO>Wg=\Ͻ r'˿l w9F=2zFج%c o_/`ڡnJ=F U鮛RJq֨cÜFV:1꣘΂=F",u1냙[p ~O;HcJ2S93O/w]W81}z}Si!,חӟM4?Żwxj9|D8f=QGQ>Q嗏qc>GyL~`~t7T/^Ǜh[i񾩄wx{.p%*4~-HI[0P{)ĝ o9U`Ȋ;w6pNw3iĜcIS9u3vscDj?>i)c`vNX:+*q+c&ĥZt᭖7)qz_}{6Ӝr?& ߂t7T/yaoxY9G%/;ޟ+6"甶 &?${)ěo9M`( o6rØ7+@ܗt'z\F9N1>*4O)_i'ƚ݂eڥ}Hp|l<(]A:^[V4X҈b\Ip%޼YѨ/SB[I(V(jǨcT*(xk(U\1f+&fނT$9 K=xkuҷې\/;wU_o-}gHn;誯xq_7$ϗ;䪯xE_^4$7JNg:}37}u&3/}T@N%Zj7^\!|ilj\/kܫոUco-KnSYZj7~/15/k|RIWuƋ/7_jF9uyяRq1h.딾׸h-ƭG*^w+pw/}q}Yff\h͸;״:RZGjty_p?.aܯոU~?K>qVvW۵jΗr$j5^B ]5×7 %5=uxx^&nT}r8qÖtDLlK엞=*70 ar:~*ڌ,]KJ={E0l*Tؗ]el5ns~1~ 龈ֶ/wdwml`gOOg׆lGn}֎=-k;lڰmCYUPWa$@yU6JXTnIPd|UG%ϞcJ_ KTs[69-v&k1li- ;;nh[vWtwmnԞ)# 6+Ye|š'U6O\/ U*Wy aav0R[Ty8?d=FbW!?bt.+3Qx'F]~]Qbݨn>C.eGj&s~v #yȝaqd~gD9WvxAwqmyBG aBkȳRb9>.D~')<ԇsqLԇ2PE=CG32Y7k Q(@nF.c/XIS' NMt!7?it:L_Z=#퇋KclZS|x ;GyA^?G弜կŹ\]9zXkYkd=>GA JG΁!DCM3"yrI,tzP&M_9?)3tDDgu'zR/ܿ7YG2A1r `M1F'^Hv?TQJ"{Z;IoǬI?YZrzOTt`!pSW{Yvؖ,\_`G>x]}lsw?hbBbA KR&)*,bc1nڂ(n jqZQTCFV"RTT`!%4V"BڴA(*{w9ƽJ>{~;;3̠ ޴`8|!#`\ْsgT Fm6 WE YR*Z8Z8@1eogUZs`1{- ZV?|8<Ih(d~a-W<7(Uf&@܍ɓT= Q1{6Qm'J7Ajr "GLAy e2(P:QQE9rJ@>TQEލꝨ ף2T_ꏡT/EdPPPPPPPPPPPPPPPr#":#<#?>P -x}W1r80>,hCm'))zoP^ϵquxF4sd4@W5}]˹+-wu.|F[2+lG:Oᦻ=aDO&me*jps[{y[Us+'\۰ݘ]v~a]ӓGߋ^_pw NK 9-ugx9s:Q7GkM:xf<&3=ԗnA9x<~ }ʐki&&3=ԗNErN@f_;BgWYgpޭɹ% :)7#p 21 U!8is=Ӛ 9ձ8Mӗ@1Ckwq!5y4٧(˹N-;7i_Xߜ6r]Loȩ}wijN;~ ;;q aݝzs[YDJw ,~S:HKkv+߽.Ow_GwMwd4_n,tsQm!)!X"9F_Gxor}B7DF_Gx'qp K;%.6: ؝w)Lw)!YF_GwxqBI'~m==~HrQ=%޻xy8 OfP i3;~(cf{Q>CyKw/b[؉W(i=~,{KcW+u~O[sP#$\l+u~Y1Q3Joo%!F_GB ߳B Y.6: ݉~HvsQi!B\l+u~?@}AG6i۱Ԏ]ãQm0{m=X{;~⽀rS! Xb'^ٯ{BE[/ƅ"<GXGb'^ٯ[aԍl!S>:;~ ez!޵g-+e/b'^ٯBqx_C?$؈W(f!^o/!9F_G7Nq ʃ(!,mQ(n0{=X+j=+P=+x7PoKX+vQd!Qnz0swu$v: "2;yB觖-:;~Z 񶠯e=ۂ~Z2#Qm{f\Q}Bg&~"{eN_Glx*R9_~[巊o7O'J(V1ٕfv"?ϻV|x:Z~ w64?{@S-m#̗q*8*Ƕ:QrH>GXV>HmjT#oKyC"rAt~'}^l}6yU٬ϫ.u5@;[Ep7`yqz>۞(9m>6l>6hTC$́ﳃ|(ol{FVSQ泽˷泃fzx[چg&5m,7T/=ՙ|S3C1j(i_zM<+ʑc.Wee>^_= vz͕Ϳu;_v?S;o[VD^ֽ}ч/"SKgbshMc7ڍ[wy\}]n&aܶm?(w/56z.Rx,>&^t W 2*B@OAoEW^gEz`5:}ޖa jZg,[R;_n{@n7u4wwj{{VXYzN^@ƚG57%sI [PԚJk']uQxlˁAwށrO)i<ҿ׃>Cփfhvxdp&Xi_k2XV mƽ+9W7d,/Y0--RC8qȼ?t }j͚P8Obp\d.cL.w B4B u04,MѾ>EIh围7=v%FG 'i1ﴘw_%ȁ3ԖO}qu^\l\4sv=-s}Xlw7$W=җq|aÎ=>ιw\ :^}KCᤎ`+Cx #wG qG;dX)+eZ|=FԺd7neFIK6ce/ 8Gآ?G[Ae+Yb*ވr‚ޞP=xt!H»ߵ\%=| 0r`s-O0,on9v0u4Lք [AZ ow1oc 0r`vV x7Lt;X.xO - vL 1 +As;utng4Ɖ&lE+R< ;/P>❃hM^t SG8ui Pԥk<| 5{ ?JPԽ{CQ>:,9;ow P݁xbygJb9:::]&rze1?@CĻHZTyE]4ui Z,,C:x<>eyuVuf_{|6}]/;W| =Dr&MSDf\T93(MZ!E"R4C$gt4E iHιhH *jJfcž,QyMP3 5+"9S)"UA3Dr.?SDfl{TYL!3֙"Re3C$3EMgHfH=N5E;A\kU9ۂ̎HΆfHU *"9)"Uf23Dr/SDaf\TٽyLo!3["ReȺc)$O*/UYLA!,"Rk2C$gB2EʨdHUdH M*+"9ߏ)"U 3DrFSD>ܞJ${Oز,UnJ-{[>jĚ;#oִ}U DI1-{ӿXsŖ̭׿CjTФQЯ. ~?˫XVl]a݊To-mUۑ*1;4Gfm^.iy*) /L=5jL[oqhNt`bd7^Lp8]77N1`7^Ga6??C)c7! ~k >U q8A N' q8A NKFM5|Qxl6 @EhLd)m [YU]C .{\Ì?ړgӛ0a'1>Zi-*o|zB\w?W_bpM{+2[6zB!y,sϿ}ffoU}Oz^EuD#R YJO>[)ev{OTO־iFIX>8<7?-2t۾|s~}^=wQ渚ԜkQ[Lt%_bMH IxmWѶ6fA̯9p]v/_(=ngzן+56N}a'~UW)jNx\9~9TT9;RYݧIlsYC}Nj$.#5'GNs}wyE{W5G)iuy9e,#5.vٟB:ZyNcnes% iL?fGOH{Ǟ+`Y%U/ kBr^t~y\!8,yցxwF}r<~N<"ovq0$y H>7$xlp1T@s^Ox[xL10D0v<qC< a`+C(y\cc9_{9!L^qZ'qe\R}W!\\u.Bpfg$ ;| ߿Po~zC&jDkwt/Dh}.Hk9Ib z61B좛)MO Oѳ(Coߏ 4/4zx 550~ ǁy"p *b@0 | nny`U hVk{u`# [mv< < Rsπk/_a7;{Q8p8| q\$WSpOOb -_Ac8{1JW&ܖ>V^cl2*-ɺ̧ ŞBXSmKbշzgeYl.cr \i]؇|s}^0wQ^Xj|BgzbOvz̰ҨcģIA{apUݽ3qY7c:jlc c5_=6m{j6 }ӽVte= ' fG^qUGm1VC!Z ,F.jRW>u rhgAA#F2=NeQnNJϸck|V1>⮝;|&YC?X>ùg~|w]T.5x uY8O=M(n][Z0sI [Bo <%O1?_ /&mk~o{8(tX{\ƺs8?\F}|EX 7{rkǤG;6m[=F,ˡ߽ .c۸)vdpkyV&:scۦcۆ˨쏾m/R+W?O'3/}mR} \@TrwGvC57+0|R>CJ=' 0C #FZ>78{=#mQcYumly-_?'}pzs/,ˡe,9-i.]l {/Yɍ]P+3bSnhGO|YC?X>9NxFVE|K>JGms}"p%'GԷ1e?s"JWds.gP3|MɶV7OC5嫌j\SD"ړLlru;> mGa GQ^fs3eY[Φź(3updmAY6,m\kpe޲I-[q].\7zm4^[(}KQoTY*>qcu"Í1YV~&' dշfY}jH['[)OIOXeLs^1r]1cuX`UoGU}\]k2W{[ٻD;DzW{k|qwF {'K{-{zjs{{L{owA_{]=7 )_{S|M| {J{oI{Ѿ&]Mڛtwk {ۥs-{ڻ.wwe {󃯽55ddiu[5ٲZ<НHڇ-|Gtft3KNm]&ƅhsi眗s6# /3 MC~Thuȳ.җEu_seo+w4?euxxw5p'ۖ|0ֱ>ѕ[G2ӓZN1+{TF|cp,JYeZz~6FcyL,J_fX]ե2ϺJ_vh17#ũG5i+)oZ#52%zeoJ&IvԖDwwgw&Zۺ14GqFN6ʬ2Fmm̝E]11cypeMcͳ.җ*EFxTLVXkxu흭=mp|a]dFF@~]a8qy_(}/QAw^~ӓtf<xCe β--rZu/sߘyB 3M2!ϺJ_vh[aOq[$^f4݉P/}%9LVe>+~ٗrYȯVʳU /3,By֥PCw,F#]_ېhPz'y.>O R Q`!O0ρua ~ 8uxRKP46TDD!8)hgQMW Q -tšΊ~ /{wݽ B@T_0 rټChR -ᴱ-S4׏~fBf f a1o1j~b1'Q1>t\sOhѨmPjl;UuY^u+jTs>|-eI Hڵeod8ߕݏ|֥%3}C͵i:\wvnCF#Bׯ>(nx@:?^Dc{Ϛu#u_wn:[M\3}W!u-8C 7sJ ;*{`!c ׎@M(xkAߙ|mV$MBJir)֋BDH.fFbΞ aMқA=*q&qs.|f>]O@;^!;߬7+ 4&-2]o(IXvuۇc96^13oa~wtQ(G0Қ*ml-w(ʖW>%{52cg}>X_4q<2EӌϏӿ,Ɩ=RlyF\6<~<#C\ 4漼>=¬eü2R7||joi|p6 {sg-&_\#]!߈<3gqy0݆uxYoASR5u;T~{n!5?Ƨ*^S7u-y{3yQŚr$p`!w\ъo"1:ѱ1l` Excdd``6cd``baV d,FYzP1C&,7\6! KA?HZ l ~@P5< %! `Wf: P 27)?R@|!}9T T~2i%ļKcl0Lq8Dl* eZZǀNwdwBe2!g` ᣻=@;`{*a|7 \c[cF&&\r+޴fv.F}He p@(O %H  ^6BEquation Equation.30,Microsoft Equation 3.00 :EEquation Equation.30,Microsoft Equation 3.0e0AFEquation Equation.30,Microsoft Equation 3.00BGEquation Equation.30,Microsoft Equation 3.0/ 00DTimes New Roman6|dv 0|( 0DArialNew Roman6|dv 0|( 0" DArial Narrowan6|dv 0|( 0"0DSymbolarrowan6|dv 0|( 0 b(.2  @n?" dd@  @@`` 0eSE   $OI# AA%T(C%" ]} U~JF= B   ,!b"@#L'& 93232/0/.D$<,(:$&<2$"J6bpUC;2$񚻝x?Hhy'Xq2$SW{Yvx $$$2$ϣ'nQ.&%32$O0ρua H$$$2$c ׎I2$\ъo"1:ѱ1zL 0e0e     A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||`3f33@3Z g4KdKdv 0pppp@ <4!d!d` 0,7g4ddddv 0pp' p<4dddd` 0,7uʚ;2Nʚ;<4dddd{ 0h`___PPT9B/ 0&%? %O =,8FEC and Pseudo-ARQ for Receiver-driven Layered MulticasthPhilip A. Chou, Alex Mohr, Albert Wang, Sanjeev Mehrotra (Microsoft, University of Washington, Stanford)i90(1ProblemEfficient and robust broadcast of real-time audio and video over the near-term Internet Best-effort packet loss, jitter, out-of-sequence Heterogeneous transmission rate, loss rate, delay, jitter, receivers Feedback availablevX %7X %7]'ProblemFind ways to multicast real-time audio and video efficiently and robustly over the near-term Internet Best-effort packet loss, jitter, out-of-sequence Heterogeneous transmission rate, loss rate, delay, jitter, receiver capacity Dynamic Influence design of network services in longer termf %?4f %?  4Outline>Multicast Receiver-driven Layered Multicast FEC and Pseudo-ARQ MulticastBMechanism for broadcasting in packet networks: any receiver able to receive broadcast packets by  tuning in to broadcast address Our focus: IP networks Protocols: How to dynamically maintain a multicast routing tree IGMP, DVMRP/PIM/CBT/& How to forward packets along the tree IP Multicastb5& 5& -Packet Forwarding in a Multicast Routing Tree ! Grafting / Joining / Subscribing  !Pruning / Leaving / Unsubscribing   Observations(Bandwidth is conserved. Sender has no knowledge of receivers (likewise any interior router). Scalable: As new receivers join, no new resources (bandwidth, computation) are needed at the sender, and resources needed at any individual router are bounded. Joining and Leaving are a form of feedback. "Growth of Multicast Infrastructure!MBONE has grown from 901 routers in 1994 to 12000 routers in 1998 Commercial routers (e.g., Cisco) have been multicast enabled for last two years ISPs (e.g., UUNET, @HOME) have begun to provide multicast service Intranets are widely multicast enabled Much research and standardization work  Types of Multicast Applications2Reliable Multicast 1-to-M file transfer, distributed software updates, synch. of distributed databases, filesystems must be reliable, but delay is not constrained Real-time Multicast for broadcast of  live or pre-recorded audio/video need not be reliable, but delay is constrainedLcc$h   Reliable MulticastARQ-based error control need to avoid  repeat request implosion protocols use hierarchical re-transmitters (SRM, RMTP, RAMP, RMP, & ) FEC-based error control digital fountain Multiple channels for flow control`n#n# Real-time Multicast Error resilient source coding for error control in MBONE tools (nv), commercial systems FEC-based error control in MBONE tools (RAT), commercial systems fixed amount of redundancy ARQ-based error control commercial systems, LVMR Layered source coding for flow control0(D'0(D'@ dReceiver-driven Layered Multicast (S. McCanne  96)$3" &Code source in layers (base, enh1, enh2, & ) Send each layer to different multicast groupDynamic Joining/Leaving "The Case for FEC 2 )FEC for Receiver-driven Layered MulticastZAmount of redundancy must be receiver-driven to deal with heterogeneity, dynamics Generate FEC in layers, using a systematic rate-compatible code (for each source layer) Send each layer to different multicast group At each receiver, subscribe to number of source layers, number of parity layers for each source layer, to optimize received quality[Z[Generation of Parity PacketsBlock each source layer into K packets per block Apply systematic Reed-Solomon type code to packets (bytewise) to produce N-K parity packetse 3!Optimization at Each Receiver6Measure transmission rate and loss probability For this transmission rate and loss probability, minimize expected distortion (over number of source layers, and number of parity layers for each source layer) Subscribe to optimal number of source layers, and optimal number of parity layers for each source layer7"Expected Distortion and Rate C#Lagrangian Optimization  Unequal Error Protection  The Case for ARQFEC does not achieve capacity C = 1-p ARQ makes optimal use of forward channel Adapts to loss (erasure) probability p Used extensively for data transmission (e.g., TCP) and media transmission (e.g., VOD) Must avoid  repeat-request implosion Observe: for broadcast of real-time media, delay (number of repeat-requests) is boundedRJO0Pseudo-ARQ for Receiver-driven Layered MulticastSender transmits delayed versions of source Receivers  request repeats by subscribing and unsubscribing to delayed versions[ Hybrid FEC & Pseudo-ARQSender delays parity packets  Repeated info is actually parity infoEPEReduction in Network Traffic D$Markov Decision Process=Finite-state stochastic process in which a decision can be made at each step to influence the transition probabilities, in order to maximize an expected reward Sequence of decision rules is a policy Optimal policy, which minimizes expected cost (D+lR) of paths through state space, can be found by dynamic programming6>2EDState Space for FEC/Pseudo-ARQ G&CaveatsNo experiments so far, only analysis no actual network transmissions, no source coding, no channel coding source is modeled as D=s 22-2R channel is modeled as iid 20% packet loss, no packet jitter or resequencing assumed no join or leave latencies Little analysis of aggregate behavior%&%Z o&6& IF%Analyzed Systems- No error protection (original RLM) - Equal error protection, redundancy determined by sender; K=8; N=11,14,17,20 - Unequal error protection, determined by receiver; K=8; Ni=Ni* (RLM w/FEC) - FEC and Pseudo-ARQ; W=1,2,4,8, KW=8%13N23L3&4`A$ Results of Analysis  Issues for Further InvestigationEstimation of channel condition Accommodation for join/leave latency Clustering of channels Study of aggregate (social) behavior ImplementationSummary3FEC & Pseudo-ARQ allow error control when flow control alone is insufficient Layered (rate-compatible) FEC allows receiver-driven approach Pseudo-ARQ is more effective than FEC and uses only standard multicast machinery Hybrid FEC/Pseudo-ARQ enhances scalability Many issues remain for further investigation/&'()*+,-./ 0 1 I J KLMNOPQRSTUVWXYZ[\^  ` ̙33` ` ff3333f` 333MMM` f` f` 3>?" dd@,|?" dd@   " @ ` n?" dd@   @@``PR    @ ` ` p>> $(    6Tu P  T Click to edit Master title style! !  0x   RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0| ``  X*  0T `   Z*  0( `   Z*H  0޽h ? 3̙33 $Blank Presentation0 @j(    T|چ?? ?d   x* 2   T ?? ?   z*(2 p  0 ?` = :  T ?? ?F   RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  Z,?? ?dO   x* 2   Z?? ? O  z*(2 H  0iq ? ̙33P  P(  @   Ty?? ?d  y x* 2   T4y?? ?  y z*(2   ZLy?? ?dO  y x* 2   Z8y?? ? O y z*(2 H  0iq ? ̙33   (  l  C Ѐp  l  C `    H  0޽h ? ̙33   P( 0C l  C P   l  C t`  H  0޽h ? ̙33   p0(  x  c $وP   x  c $ڈP  H  0޽h ? ̙33   (  l  C P   l  C ġ  H  0޽h ? ̙33   (   l  C \ P   l  C A      H  0޽h ? ̙33   'x@P   (  xr x S p P   ^B x 6D  0p 2 x <w    1S^ x 6  ^ x 6   ^B  x@ 6D @ ^B  x 6D  ` ^B  x@ 6D  ` ^B  x@ 6D   ^B  x 6D   2 x <P{  Pp  1R2 x <~    1R^B x 6D  ``  x <   0 P  : ^B x@ 6D @ @^B x 6D  @^B x 6D @ 2 x <p    1R2 x <4o p  1R^B x 6D @ ^ x 6  0 P ^B x@ 6D @ @^B x 6D  @2 x <쌈 p  1R^B x 6D @ ^ x 6   ^B x 6D  @ ^B  x@ 6D   2x T ?   &  51(2 3x T ? p &  52(2pB Fx HD>?  `vB Gx ND>? ` @ `vB Ix ND>? `@ @  Jx <ԡ? `   @ S,G | data (2  x # lp¹G`H5I|J Kh[L M4NO? ` C : S,G - 1,2 : 2 x 6  ?  Kmulticast routing table(2 x 6(  ? ` :packet(2 x 6  ? `.S = Source Address G = Multicast Group Address/ 2/H x 0޽h ? x 3̙33_  @:}P[(  r  S H"\P0P  \ .8 P ^P2  <$\   1Sf  6  fB  6D@ `@ f   6  fB   6D `@ `fB  B 6D@ fB   6D ` fB  B 6D`  fB B 6D   fB  6D  2  <x)\P p  1R2  <,\   1RfB  6D` `   < 0 P  : fB B 6D @ @fB  6D @fB  6D @ 2  <r    1R2  <`u p  1RfB  6D @ f  60 P fB B 6D @ @fB  6D @2  <x p   1RfB  6D @ f  6  fB   6D @ fB !B 6D fB "B 6D  `2 # 6J p 1R` M 00 P 2 Q 6p 1R4l  ` o `,$D0xB \ HD>?   e N| ? @f  51(2 f N ?@ f  52(2lB i <D?@lB j <D? @lB k <D?@@ l 6?   >Join S,G (2  m  fՈGH/AIJ L M>N?r  C : S,G - 1,2 : 2 n 6, ?`` Kmulticast routing table(2z p  q  ,$D0rB r BD>?0  xB s HD>?0 p0 xB t HD>?pp0  u 6҈?  >Join S,G (2  v  f GH(IJ L M4Np?Pb A : S,G - 1 : 2 w 6 ?p Kmulticast routing table(2 x N Ĉ ?p 51(2l   } ,$D0`B yB 0D@@`B z 0D  `B { 0D@`B | 0D @H  0޽h ?/ mv 3̙33&  Z&R&`GT}0  ! "#$%&'()*+,-.-/0123$(  |r | S \P0P  \ x8 P Q}PfB | 6D0  2 | <\0   1Sf | 60  fB | 6D0@ `@ f | 60  fB  | 6D0 `@ `fB  |B 6D0@ fB  | 6D0 ` fB  |B 6D0`  fB  |B 6D0   fB | 6D0  2 | <4 \0P p  1R2 | <\0   1RfB | 6D0` `  | < 00 P  : fB |B 6D0 @ @fB | 6D0 @fB | 6D0 @ 2 | <d 0   1R2 | < 0p  1RfB | 6D0 @ f | 600 P fB |B 6D0@@fB | 6D0 @2 | < 0p 1RfB | 6D0@f | 60  fB | 6D0 @ fB !|B 6D0  `B F} BD?` ,$D0Gl  p R} p ,$D02 N} 6 /  1R` J} 01  fB K}B 6D1PfB L} 6D1P PfB M} 6D1rB O} BD?1P p  l @   S} p ,$D0 } <  ?2@  Kmulticast routing table(2` | 02P p@fB |B 6D2 ` ` fB | 6D2@` fB | 6D2 `  2 | 6 2   1RrB | BD?2 xB } HD>?2 `  ~B } ND>?2 ` ` ~B } ND>?2@`  } H4 ?2P`  ? Leave S,G (2  } # l0 GdQH9IʦJ L MkN?2 `` 2 A : S,G - 1 : 2 } TP  ?2P@ 51(2xB 7} HDԔ?2P xB 8} HDԔ?2 0 xB 9} HDԔ?2 pxB :} HDԔ?20  xB ;} HDԔ?2p xB <} HDԔ?2 xB =} HDԔ?2 P(l  @ T}  ,$D0` &} 030 P@xB +} HD?3P ~B ,} ND>?3  -} HD ?3  ? Leave S,G (2  .} # l G@H9IAJ L MtN?3`  C : S,G- 1, 2 : 2 /} <Ы  ?3F Kmulticast routing table(2xB 2} HDԔ?3@xB 3} HDԔ?3@ B} T  ?3@ 51(2H | 0޽h ?/ }.} 3̙33  $(  $l $ C ' P   l $ C E    H $ 0޽h ? ̙33  (( \@d@ (l ( C Ğ  `P   l ( C l    H ( 0޽h ? ̙33  ,(  ,l , C S    l , C  P   H , 0޽h ? ̙33  0( 2 0l 0 C  P   l 0 C <    H 0 0޽h ? ̙33  4(  4l 4 C P   l 4 C Ŀ`  H 4 0޽h ? ̙33^  %8 (  8l 8 C O\P`P  \  28 <<\ ? p  @ Base layer 2  =8 <\ ?   9...(2jB @8 BD?  jB A8 BD?` `  G8 <4\ ? p  Kto multicast group G0 2 H8 <\ ?@ p  \ Enh. layer 1 2   J8 <\ ?@   9...(2jB K8 BD?` `  Q8 <\ ?@ p  Kto multicast group G1 2 R8 <\ ? p  \ Enh. layer 2 2   T8 <\ ?   9...(2jB U8 BD?   [8 <\ ? p  Kto multicast group G2 2vB n8 ND?` o8 <\ ?` <time(2 q8 < \  \  s8 0\ p D0Receivers subscribe to as many layers as desired w8 T\?   YS0t:(2  x8 T\? P  YS0t+18(2  y8 T0\? P  YS0t+28(2  z8 Tp\?  YS0t+38(2  {8 T\? `  YS0t+48(2  |8 T\? `  [S0t+5:(2  }8 T0\?@   WS1t8(2  ~8 T\?@ P  YS1t+18(2  8 Tt\?@ P  YS1t+28(2  8 T`?@  YS1t+38(2  8 T`?@ `  YS1t+48(2  8 TP `?@ `  YS1t+58(2  8 T`?   WS2t8(2  8 T`? P  YS2t+18(2  8 TH`? P  YS2t+28(2  8 T`?  YS2t+38(2  8 T`? `  YS2t+48(2  8 T$`? `  YS2t+58(2 H 8 0޽h ? ̙333"  !!=N@@[!( p  @l @ C L,`P  ` :8 @ @ K@@ @2 @ </`` 1Sf @ 6 @f  @ 6 @ lB  @B <DԔ  lB  @ <DԔ  lB @B <DԔ P lB @ <DԔP P 2 @ </`  1R2 @ <3`@ `  1RlB @ <DԔ  @ <8`   : 2 @ <:``@` 1R2 @ < @` 1Rf @ 6  lB @B <DԔplB @ <DԔ 2 @ <4@` 1RlB @ <DԔppf  @ 6  @ lB !@ <DԔ@ lB "@B <DԔ0 P ~B %@ NDԔ?~B &@ NDԔ?~B '@ NDԔ?xB (@ HDԔ?`~B )@ NDԔ? 00~B *@ NDԔ?0~B +@ NDԔ?  0~B ,@ NDԔ?``xB -@ HDԔ?`lB .@B <DԔ@ lB /@B <DԔ   lB 0@ <DԔ lB 1@ <DԔ @lB 2@B <DԔp @lB 3@B <DԔ` lB 4@B <DԔ 0 lB 5@ <DԔ lB 6@ <DԔ 0 lB 7@ <DԔ 0 lB 8@ <DԔ xB 9@ HDԔ? P xB :@ HDԔ? xB ;@ HDԔ? 0 0 lB <@B <DԔ`  lB =@ <DԔ0 0@lB >@ <DԔ@lB ?@B <DԔ@0@ D@ 0J` `  GReceivers subscribe and unsubscribe according to instantaneous capacityHG8 M  N@M xB A@ HD?` `~B B@ ND?P ` F@ <O` ?`  Ctransmission rate(2 G@ BS` ?PM p^ ] loss prob (2 B H@ TD?  I@  0e0e    BCPDE@F  A@  5% 8c8c     ?A)BCD|E||PHtKC 8]E0 @      ` L@ 6W` ? T  51(2 M@ 6[` ? 50(2H @ 0޽h ? ̙33&  &&AE0 &(    r  S Y`P  ` :8 @ @ B@ @2  <``` 1Sf  6 @f  6 @ lB B <DԔ  lB   <DԔ  lB  B <DԔ P lB   <DԔP P 2   <e`  1R2   <h`@ `  1RlB  <DԔ   <Tm`   : 2  <p``@` 1R2  <s` @` 1Rf  6  lB B <DԔplB  <DԔ 2  <v` 1RlB  <DԔppf  6  @ lB  <DԔ@ lB B <DԔ0 P ~B  NDԔ?~B  NDԔ?~B  NDԔ?xB  HDԔ?`~B  NDԔ? 00~B  NDԔ?0~B   NDԔ?  0~B ! NDԔ?``xB " HDԔ?`lB #B <DԔ@ lB $B <DԔ   lB % <DԔ lB & <DԔ @lB 'B <DԔp @lB (B <DԔ` lB )B <DԔ 0 lB * <DԔ lB + <DԔ 0 lB , <DԔ 0 lB - <DԔ xB . HDԔ? P xB / HDԔ? xB 0 HDԔ? 0 0 lB 1B <DԔ`  lB 2 <DԔ0 0@lB 3 <DԔ@lB 4B <DԔ@0@ 5 0` @  i9Problem is that ambient congestion may always be present ::d ? <3? P  @ Hes`?, >(2  A HQϣĈ`?@ ,T  >(2 V 8 K  EK xB 7 HD?` `~B 8 ND?P ` 9 < ` ?`  Ctransmission rate(2 : B` ?PK p\ ] loss prob (2 B ; TD?  <  0e0e    BCPDE@F  @  5% 8c8c     ?A)BCD|E||PHtKC 8]E0 @      ` =  0e0e    BCpDELF$ @  Ԕ 8c8c     ?A)BCD|E||p/aSfi+Ci ]Eh0@       `  C 6ȓ` ? T  51(2 D 6p` ? 50(2H  0޽h ? ̙33  (  l  C `P0P  ` l  C `0 ` H  0޽h ? 3̙33t  $'HH (  Hd 1H <? @P `l H C p`P  ` l H C ,` @ `  H <ܦ` ? @  B Source layer 2  H <<` ?   9...(2jB H BD? p jB  H BD? p  H <` ? @  mto multicast group Gx 2 H <d` ?p @0  DParity layer 1 2 H < ` ?p 0  9...(2jB H BD? p  H <` ?p @0  oto multicast group Gx.1 2 H <` ? @  DParity layer 2 2 H <` ?   9...(2jB H BD?p H <D` ? @  oto multicast group Gx.2 2 &H <`` ?p@0 DParity layer 3 2 'H <` ?p0 9...(2jB (H BD?p )H <` ?p@0 oto multicast group Gx.3 2 5H TD`? p  sStK:(2  6H T`? p  uStK+1:(2  7H T`?   uStK+2:(2  8H Z`?  ]S(t+1)K:(2  ;H T`?p 0  \Pt+1,1:(2  H T`? P  ZPt,2:(2  ?H Tb?p 00 \Pt+1,3:(2  @H Tb?p 0 ZPt,3:(2  AH Zx b? 0  _ S(t+1)K+1: (2  BH Zb? 0  _ S(t+1)K+2: (2  CH T$b ? p`  GK*(2pB DH@ HDo? @P pB EH@ HDo? @P pB FH HDo?@   GH Zb ? P  IN-K*(2pB HH HDo? `H H 0޽h ? ̙33  (  l  C tbP  b l  C 0 b b H  0޽h ? 3̙33  %a((  l  C x$bP  b `  c $A ??X `  `  c $A  ??@   pB  HD?PPM pB  @ HD?M P M   # 0e0e    B}CDE@F    Ԕ 8c8c     ?A)BCD|E||@@ @o.} @     `P   <(b ?M  4  9layer(2j  B ?CPM j ( B ?VPM j ) B ? PM j . B ?PPM  0 TL-b ?P PD02(2  1 Tt1b ?P PD12(2  2 Zh5b ?m{ B& $(2 3 T,9b ?P<  PD82(2  4 T=b ?P PD22(2  5 TBb ?M p  A1$(2 6 TGb ?M p0  A2$(2 7 TJb ?M 0  A3$(2 8 TNb ?M   A0$(2 : TRb ?M   A8$(2 ; TVb ?P PD32(2  > TL[b ?   B& $(2jB @ BD? P P W  B # 0e0e    BCDE(F   Ԕ 8c8c     ?A)BCD|E|| A 7`9' @   P `  H N_b ? P - A1$(2 Q Ncb ?`  A0$(2 T N`hb ? P  A0$(2 U Nbb ?` p0  A1$(2 V Nob ?` p0  A3$(2 W Nsb ?`   A2$(2 Y Nwb ? =  Ri=Ni /KX (2  d [ < ?pP ` jB _ BD?` P P` 1 ` NTb ?@   pi=p(Ri )l (2   a N4b ?  g raw loss prob$(2 H  0޽h ? 3̙33  h` ?(  r  S hbP  b `  c $A ??0 `  c $A ?? " jB  BD?P   NАb ? 0 A0$(2  Nb ? p A1$(2  NDb ? p  A3$(2  Nb ? 0  A2$(2  Nb ? @ `R=N /K>(2 jB  BD?   # # 0e0e    BCDE(F   Ԕ 8c8c     ?A)BCD|E|| A 7`9' @      * # 0e0e    BCDE(F   Ԕ 8c8c     ?A)BCD|E|| A 7`9' @   `   , # 0e0e    BCDE(F   Ԕ 8c8c     ?A)BCD|E|| A 7`9' @      - # 0e0e    BCDE(F   Ԕ 8c8c     ?A)BCD|E|| A 7`9' @     . Nb ?] PS12(2  / NЬb ? -  PS22(2  0 NLb ?   PS32(2  2 Tb ? i  B& $(2dB 3 <D?  dB 5 <D?  dB 6 <D?  dB 7 <D?  @dB 8 <D? ` dB 9 <D? ` dB : <D? ` dB ; <D?` ` pB < HD?  pB = HD? v pB > HD? .7 pB ? HD?  H  0޽h ? 3̙33  zr0L (  Ll L C bP  b ^ L 6A ? H L 0޽h ? ̙33  @<( \@~@ <l < C bP  b l < C lb` b H < 0޽h ? ̙33X   P*SX0 (  Xl X C bP0P  b l X C b  b  X <b ? @  C Source stream 2 X <Lb ?   9...(2jB X BD?0 p0 jB  X BD? p  X <b ? @  Jto multicast group G 2 X <b ? @P  FDelayed stream 1 2 X <tb ? P  9...(2jB X BD? p  X <X Tb? p  XSt:(2  ?X T(b? p  ZSt+1:(2  CX Thb?   ZSt+2:(2  DX THh?  ZSt+3:(2  EX Th? 0  ZSt+4:(2  FX T h? 0  ZSt+5:(2  GX TTh ? pP  XSt:(2  HX Th ? pP  ZSt-1:(2  IX Th ? p ZSt-1:(2  JX Th ?p ZSt-2:(2  KX T!h ?  XSt:(2  LX T%h?  P  ZSt+1:(2  MX T*h?  ZSt+1:(2  OX T/h ? P  ZSt+2:(2  PX Tt4h? 0 P  ZSt+3:(2  QX T8h ?` ZSt+3:(2  RX T|=h ? 0P  ZSt+4:(2  SX TxBh ?`  ZSt+2:(2 vB 4X ND>? pp pB 5X@ HD>? pp vB 6X ND>? pB 7X@ HD>? vB 8X ND>? p p pB 9X@ HD>? p p H X 0޽h ? ̙33   `-@P  (  P^ 6P 6? P `@^ )P 6?@P @  *P TMh?p  sStK:(2  +P TRh? p  uStK+1:(2  ,P TWh?  uStK+2:(2  -P Z]h?  ]S(t+1)K:(2  .P Tah?P   \Pt+1,1:(2  /P Tdeh?P p  ZPt,1:(2  0P Tih? `  ZPt,2:(2  1P T,h ? P  \Pt-1,2:(2  2P Trh ?P 0 ZPt,3:(2  3P TXwh ?P   \Pt-1,3:(2  4P Z{h?0  _ S(t+1)K+1: (2  5P Zh? 0  _ S(t+1)K+2: (2 l P C ԃhP  h l P C h  0 h  P <Ȇh ?@  B Source layer 2  P <h ?  9...(2jB P BD? p jB  P BD?ppp P <h ?@  mto multicast group Gx 2 P <h ?P @  DParity layer 1 2 P <lh ?P   9...(2jB P BD?p pp  P <h ?P @  oto multicast group Gx.1 2 P <h ? @  V Parity layer 2 (delayed 1 block)! 2! P <h ?   9...(2jB P BD? p  P <Уh ? @  oto multicast group Gx.2 2 P <$h ?P @ V Parity layer 3 (delayed 1 block)! 2! P <h ?P  9...(2jB P BD?ppp P <h ?P @ oto multicast group Gx.3 2vB "P ND>?p0 pB #P@ HD>?p0 vB &P ND>? 0 pB 'P@ HD>? 0  8P T h ?@ IK=3*(2pB 9P@ HDo?@ pB :P@ HDo?pP  ;P Th ?@ aW=2 waves (decision epochs)*(2pB P@ HDo? `  @P 0Լh P` |*Delay is blocklength times number of waves+P+ H P 0޽h ? ̙33 m zrp h ( p  hl h C hP  h ^  h 6A ? H h 0޽h ? ̙33  (  l  C hP  h l  C \h h H  0޽h ? 3̙33gD  DDua C( \@d@ `l ` C hP0P  h 98 ` da` ` Nlh?   m # pkts to req(2$lB ` <D? P lB ` <D?P P  ` Nh?  @  b # pkts recvd (2   ` Nh? @ @`  b # pkts recvd (2  B ` <D?P  ,$0 ` 6Lh ?0   50(2l ` < ? @@`  ` 6\h ?@   53(2 ` 6h ? @  54(2 ` Nh? @ `  m # pkts to req(2$lB ` <D?@P P  a NXh?  m # pkts to req(2$ a Nh? @ `  m # pkts to req(2$lB a <D?@ lB a <D?@ lB a <D?@ P lB  a <D?@P   a 6h ? @  50(2lB  a <D?@P lB  a <D?@ P lB  a <D?@ lB a <D?@P P  a 6h ?  51(2 a 6(h ? `  52(2 a 6k ?  53(2 a 6k ?  ` 54(2l a < ? l a < ? @ `lB a <D?  lB a <D? P lB a <D? P  a Nk?   b # pkts recvd (2   a Nk? @ `  b # pkts recvd (2   a Nk? @` b # pkts recvd (2    a Nk?  b # pkts recvd (2   !a Nk?  b # pkts recvd (2   "a Nk? @` b # pkts recvd (2  lB $a <D? P P lB %a <D? P lB &a <D? lB 'a <D? PlB (a <D? P lB )a <D?  P  *a 6 k ?   50(2 +a 6 $k ?0  @ 51(2 ,a 6h'k ?0   52(2 -a 6+k ? 0  50(2 .a 6-k ?  51(2 /a 60k ? p  52(2 0a <@4k ?  52(2 1a <\7k ?0 `  51(2 2a <:k ?0  50(2lB 5a <D?P @P l 6a < ?@@ `` l 7a < ?@ ` l :a < ?@ ` l ;a < ?@@`` l a < ?  l ?a < ?@`lB @a <D?@P Aa 6 @k ?@ 50(2 Ba 6Ck ?@@  51(2 Ca 6Fk ? @  52(2 Da 6$Jk ?@ @  53(2 Ea 6(Mk ? @  54(2lB Ha <D?@lB Ia <D?P@lB Ja <D?P@P lB Ka <D?P@PlB La <D?@P lB Ma <D?P @PlB Na <D? @ lB Oa <D?@ lB Pa <D?P @ lB Qa <D? @PlB Ra <D?P @PlB Sa <D?P @lB Ta <D? @ Ua 6(Sk ?0p0 50(2 Va 6Vk ?0 51(2 Wa 6Yk ? 50(2 Xa 6@]k ?0P 51(2 Ya 6D`k ?p 52(2 Za 6|ck ? P  50(2 [a 6fk ?   51(2 \a 6ljk ?   50(2 ]a 6mk ?0@   51(2 ^a 6Hpk ? `  52(2 _a 6sk ? @ 50(2 `a 6vk ? 51(2 aa 6yk ?` 50(2 ba 6t}k ?` ` 51(2 ca 6k ?`0  52(2l P@ aP@,$D 0xB ea HDԔ?P  ~B fa NDԔ?@ P xB ga HDԔ?@ xB ha HDԔ?@ xB ia HDԔ?@P xB a HDԔ?@ rB a BDԔ? P xB a HDԔ? P rB a BDԔ? xB a HDԔ?P@P xB a HDԔ?P@xB a HDԔ?P@PxB a HDԔ?P @ xB a HDԔ?@ xB a HDԔ? @ xB a HDԔ? @xB a HDԔ?P @H ` 0޽h ? ̙33  (  l  C kP  k l  C Pk k H  0޽h ? 3̙33  (  l  C kP  k l  C Tk0 k H  0޽h ? 3̙33[    B\pw(  \l \ C (kP  k 8 y B\yl \ <A ?yT   "\# p   \ <Hk 3?  71(23r2  \ B 3? T    !\#    \ <,k ?   72(23r2 \ B 3?  T  \# @ ` 0 \ 6k ? E3((2l2 \ < ?T  \# 0  \ 6Lk ? E4((2l2 \ < ?  \ Nv(\kG  3?   B(2  /\ <k ? @ E4((2r2 0\ B ? @T  1\#    2\ 6k ? E3((2l2 3\ < ?}T   4\#    5\ 6\ < k ?0 P  N original RLM& 2 H \ 0޽h ? ̙33  l( \@d@ ll l C kP  k l l C tk k H l 0޽h ? ̙33  d( )pM@ dl d C  P   l d C l 0   H d 0޽h ? ̙330 zr (  X  C ` =  r  S G FW    H  0iq ? ̙33 0 zr0 (  X  C ` =  pr  S pFY   p H  0iq ? ̙33 0  (  @P  X  C ` =  p  S hpFY   p  H  0iq ? ̙33 0 ( P` X  C ` =  y  S xyFY   y  H  0iq ? ̙330 ( P` X  C ` =    S P" FY     H  0iq ? ̙33 0 ]( P` X  C ` =    S f Fd    _Some observations: Bandwidth is conserved. No link carries duplicate packets, no matter how many receivers there are, because packets are copied only as necessary within the network. In particular the sender sends only one copy of each packet, no matter how many receivers there are. In this sense, the sender has no knowledge of the number of receivers, and the same goes for any interior router. As new receivers join in, no new resources are needed at the sender, and the resources needed at any individual router are bounded although they may increase slightly. Hence the system is scalable to an arbitrary number of receivers. Finally, joining and leaving are a form of scalable feedback from the receivers to the sender, which we can take advantage of.H+uH  0iq ? ̙33L0  p( P` X  C ` =  \  S L<\F%   \ If a different receiver now want to unsubscribe to the multicast, it sends a Leave message upstream towards the receiver, and the router deletes the entry from the routing table, and in turn sends a Leave message upstream to the next router, which if it has other downstream receivers on a different link, simply deletes the link in the appropriate entry. This prunes off a branch of the tree.H  0iq ? ̙330 zrP ( P` X  C ` =  \r  S /\FY   \ H  0iq ? ̙330 zr0 ( Pv@M@ X  C ` =  r  S @ FY    H  0iq ? ̙330 zr ( % X  C ` =  r  S  FY    H  0iq ? ̙330 zr` ( Pv@M@ X  C ` =  r  S FY    H  0iq ? ̙330 zr0 ( P` X  C ` =  r  S FY    H  0iq ? ̙330 zr` (  @  X  C ` =  yr  S L\FY   y H  0iq ? ̙330 zrp  ( X@X@  X   C ` =  yr   S pFY   y H   0iq ? ̙33 0 zr$ ( X@X@ $X $ C ` =  yr $ S x#yFY   y H $ 0iq ? ̙330 zr( (   (X ( C ` =  yr ( S spFY   y H ( 0iq ? ̙33#0 zr, ( X@X@ ,X , C ` =  yr , S l^pFY   y H , 0iq ? ̙330 zrP0 (  0X 0 C ` =  yr 0 S pFY   y H 0 0iq ? ̙33$0 zr@4 ( bG 4X 4 C ` =  yr 4 S yFY   y H 4 0iq ? ̙330 zr08 ( j 8X 8 C ` =  pr 8 S @pFY   p H 8 0iq ? ̙33&0 zr < ( X@X@ <X < C ` =  pr < S QpFY   p H < 0iq ? ̙33%0 zr@ ( 4l @X @ C ` =  pr @ S  pFY   p H @ 0iq ? ̙330 zrD ( j DX D C ` =  kr D S  FY   k H D 0iq ? ̙330 zrH ( 4l HX H C ` =  kr H S T[\FY   k H H 0iq ? ̙330 zrL ( X@X@ LX L C ^ ;  kr L S 8\FY   k H L 0iq ? ̙330 zr@P (  PX P C ` =  yr P S ({FY   y H P 0iq ? ̙330 zrT ( j TX T C ` =  yr T S 8FY   y H T 0iq ? ̙33 0 zrX ( X@X@ XX X C ` =  yr X S l FY   y H X 0iq ? ̙33 0 zr\ (  \X \ C ` =  yr \ S yFY   y H \ 0iq ? ̙330 zrh (  hX h C ` =  yr h S 8yFY   y H h 0iq ? ̙33!0 zrt ( 0 tX t C ` =  yr t S wyFY   y H t 0iq ? ̙33"0 zr (  X  C ` =  yr  S  }yFY   y H  0iq ? ̙33'0 ^(  ^ S ` =   # l &e&eFJ   H  0iq ? ̙33xW]lTE>s^vwv?ڲ-GRۢiXly1d */%(M҂ Byb} 1kB41)c| H,[J_Pfwϙ9gfsb+.CFytNaِ@t:v^L!zi Ě{>mJ+o dQpRqvASEM{'?c:;gJvAǬbڮO/:~3P)ߴ=-80u{)E|ʹ \"B@!9(kNK@h` QX *U(C,B,F,A,E-+|!_Gq꿃SfZh:n?uIɎQ2ք(BƑ2nS*\R?)_s˃a]^O?kj`xB7n5~,D|&O溱1uYu;=tq=^'>-*oQy{x&C~gwz,<[s9S26)ϼ 6Rq/R1'AjQ~F>PS/QR_k!ʧԞ樂d.R&{G}i).R;d-ݤ݀nڒ]zvQC?4Dq>?6~y<NzR5{=a}_qZwB/S0/Q^B7}ePN7Ψڟ.TRsd"oQjMρ Y?)ߊM<۴5`;x }Yq9?>Mvp),.n;1X7Z|*2M%;`!`xa|ۓUϜD|{yDuWm0:OϽ5o> x{p7Da^V}"AT6\9whQXxUGTw9hcWc3y5!j-{%&Ɠm3ImK֊2qsݪicNx44Dz}*a:p:l.h#ծ& nȑsԩ5 O9]OVxVMhQvӘMb~"K բPAԨIL%+IiRÂBO+X/= z+Tū"Q Hg{.֍,7fDѓEAV;C9XP+nv u5Ow:0nQtj\N{6_|4Rt\zy012,pg$S*~`RSKXi#[[S-R'S%|H{+7=11~`L+f۵K:ڝʅ)4̬]We.Sv/N,GRw8'pA: T#Iz3'rN^(C\{dwrwи8/N+pYcxU,6 1t- S$DZbgx y-+? ;ne?+ߦ~sSxXMLcU>B P~*@ɌI\n)FR 1ƕ0nLܨh &.4g2;3cbb h=޼01$s}}@@ :UJ׸X*ұ)Gmsg*͹Ygrd2B &!ȹ҉+ƲEoa ,_03IXd]>bgxj 5xnaOg T?\f> 0"KWz˯E=o? tTP-'P[A vP9 . 5zj/IQ@B i!],Nzga8CPkϽi LϬdV3Z"kfұ#r)M:,0|~_Z>PJmԆ+Y|#(^J+[%8a֭FGDi6'jO`.?;'Sln dqd9kR2>hzۨ7]'L{"} ,hA;N{cîL\=.ppTvm)T3=߽j|z|wo7^X.w+[ĸQ·ŷӛ$gs:P?jR~-<Р+>1kzl&J_;`E7-AxD9/9b WOU^jy9B&Nx(׬'dsd /p]ơn+$0paD(۽`a0q SΛi|!  㯍-6瀿>uLq!02ƁSA݀y*ƁZi`@H:זt\m3eZb+eX~;F/U;Y?%v`^-G >c9/FO8xVMhA~3Mڤ4(,=x3TsPl=٪M*HM԰RAz A/"<Ń꽢OJ7ٸlTBe{oRݷh1`4TNp])lcj(vuw0>0a^Л9ݠ&Oz_{x.a(/knM9 (~pO(3pc}** #A?uIQ?1@[[^l1Mzw7A5 x̐מI_Zl_XVVLFD(e}"\%/G,<5y%Pc5  a$"ѿ_HSWY%Bq !Ƞ;LH( $P:ʾ8Ei&N[d9QV;J<8D"KPeYH:5U?viBlNUOU-hx.K"qC;sJvzkb?v[YuOiw4Bޖ"Dg˃vvKxXIA }L5z\E'^~3vaƚ@7ٿ-6 x6y5Zچ:}T!-qQeݳ#gr%Wl6 X{vN X,y?`RiW}&nnA{G"W//(=H`RȌ_5$V2b"(0g qJ+cM:a{-KoTorP`@V]W[ pݼվ# ,5G$ +g!@_Kt^%IG# %&(s*G,\14r6489;=*H6 byJ:hA@kbpugFD d Pz=Multicast Receiver-driven Layered Multicast FEC and Pseudo-ARQ MulticastBMechanism for broadcasting in packet networks: any receiver able to receive broadcast packets by  tuning in to broadcast address Our focus: IP networks Protocols: How to dynamically maintain a multicast routing tree IGMP, DVMRP/PIM/CBT/& How to forward packets along the tree IP Multicastb5& 5& -Packet Forwarding in a Multicast Routing Tree ! Grafting / Joining / Subscribing  !Pruning / Leaving / Unsubscribing   Observations(Bandwidth is conserved. Sender has no knowledge of receivers (likewise any interior router). Scalable: As new receivers join, no new resources (bandwidth, computation) are needed at the sender, and resources needed at any individual router are bounded. Joining and Leaving are a form of feedback. "Growth of Multicast Infrastructure!MBONE has grown from 901 routers in 1994 to 12000 routers in 1998 Commercial routers (e.g., Cisco) have been multicast enabled for last two years ISPs (e.g., UUNET, @HOME) have begun to provide multicast service Intranets are widely multicast enabled Much research and standardization work  Types of Multicast Applications2Reliable Multicast 1-to-M file transfer, distributed software updates, synch. of distributed databases, filesystems must be reliable, but delay is not constrained Real-time Multicast for broadcast of  live or pre-recorded audio/video need not be reliable, but delay is constrainedLcc$h   Reliable MulticastARQ-based error control need to avoid  repeat request implosion protocols use hierarchical re-transmitters (SRM, RMTP, RAMP, RMP, & ) FEC-based error control digital fountain Multiple channels for flow control`n#n# Real-time Multicast Error resilient source coding for error control in MBONE tools (nv), commercial systems FEC-based error control in MBONE tools (RAT), commercial systems fixed amount of redundancy ARQ-based error control commercial systems, LVMR Layered source coding for flow control0(D'0(D'@ dReceiver-driven Layered Multicast (S. McCanne  96)$3" &Code source in layers (base, enh1, enh2, & ) Send each layer to different multicast groupDynamic Joining/Leaving "The Case for FEC 2 )FEC for Receiver-driven Layered MulticastZAmount of redundancy must be receiver-driven to deal with heterogeneity, dynamics Generate FEC in layers, using a systematic rate-compatible code (for each source layer) Send each layer to different multicast group At each receiver, subscribe to number of source layers,  !"#$%&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`acdeghijklmnopqrstuvwxy~Root EntrydO)@.PicturesMCurrent UserIJSummaryInformation( PowerPoint Document(';DocumentSummaryInformation80fb0 :EEquation Equation.30,Microsoft Equation 3.0e0AFEquation Equation.30,Microsoft Equation 3.00BGEquation Equation.30,Microsoft Equation 3.0/ 00DTimes New Roman6|dv 0|( 0DArialNew Roman6|dv 0|( 0" DArial Narrowan6|dv 0|( 0"0DSymbolarrowan6|dv 0|( 0 b(.2  @n?" dd@  @@`` 0eSE   $OI# AA%T(C%" ]} U~JF= B   ,!b"@#L'& 93232/0/.D$<,(:$&<2$"J6bpUC;2$񚻝x?Hhy'Xq2$SW{Yvx $$$2$ϣ'nQ.&%32$O0ρua H$$$2$c ׎I2$\ъo"1:ѱ1zL 0e0e     A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||`3f33@3Z g4KdKdv 0pppp@ <4!d!d` 0,7g4ddddv 0pp' p<4dddd` 0,7uʚ;2Nʚ;<4dddd{ 0h`___PPT9B/ 0&%? %O =,8FEC and Pseudo-ARQ for Receiver-driven Layered MulticasthPhilip A. Chou, Alex Mohr, Albert Wang, Sanjeev Mehrotra (Microsoft, University of Washington, Stanford)i90(1ProblemEfficient and robust broadcast of real-time audio and video over the near-term Internet Best-effort packet loss, jitter, out-of-sequence Heterogeneous transmission rate, loss rate, delay, jitter, receivers Feedback availablevX %7X %7]'ProblemFind ways to multicast real-time audio and video efficiently and robustly over the near-term Internet Best-effort packet loss, jitter, out-of-sequence Heterogeneous transmission rate, loss rate, delay, jitter, receiver capacity Dynamic Influence design of network services in longer termf %?4f %?  4Outline>Multicast Receiver-driven Layered Multicast FEC and Pseudo-ARQ MulticastBMechanism for broadcasting in packet networks: any receiver able to receive broadcast packets by  tuning in to broadcast address Our focus: IP networks Protocols: How to dynamically maintain a multicast routing tree IGMP, DVMRP/PIM/CBT/& How to forward packets along the tree IP Multicastb5& 5& -Packet Forwarding in a Multicast Routing Tree ! Grafting / Joining / Subscribing  !Pruning / Leaving / Unsubscribing   Observations(Bandwidth is conserved. Sender has no knowledge of receivers (likewise any interior router). Scalable: As new receivers join, no new resources (bandwidth, computation) are needed at the sender, and resources needed at any individual router are bounded. Joining and Leaving are a form of feedback. "Growth of Multicast Infrastructure!MBONE has grown from 901 routers in 1994 to 12000 routers in 1998 Commercial routers (e.g., Cisco) have been multicast enabled for last two years ISPs (e.g., UUNET, @HOME) have begun to provide multicast service Intranets are widely multicast enabled Much research and standardization work  Types of Multicast Applications2Reliable Multicast 1-to-M file transfer, distributed software updates, synch. of distributed databases, filesystems must be reliable, but delay is not constrained Real-time Multicast for broadcast of  live or pre-recorded audio/video need not be reliable, but delay is constrainedLcc$h   Reliable MulticastARQ-based error control need to avoid  repeat request implosion protocols use hierarchical re-transmitters (SRM, RMTP, RAMP, RMP, & ) FEC-based error control digital fountain Multiple channels for flow control`n#n# Real-time Multicast Error resilient source coding for error control in MBONE tools (nv), commercial systems FEC-based error control in MBONE tools (RAT), commercial systems fixed amount of redundancy ARQ-based error control commercial systems, LVMR Layered source coding for flow control0(D'0(D'@ dReceiver-driven Layered Multicast (S. McCanne  96)$3" &Code source in layers (base, enh1, enh2, & ) Send each layer to different multicast groupDynamic Joining/Leaving "The Case for FEC 2 )FEC for Receiver-driven Layered MulticastZAmount of redundancy must be receiver-driven to deal with heterogeneity, dynamics Generate FEC in layers, using a systematic rate-compatible code (for each source layer) Send each layer to different multicast group At each receiver, subscribe to number of source layers, number of parity layers for each source layer, to optimize received quality[Z[Generation of Parity PacketsBlock each source layer into K packets per block Apply systematic Reed-Solomon type code to packets (bytewise) to produce N-K parity packetse 3!Optimization at Each Receiver6Measure transmission rate and loss probability For this transmission rate and loss probability, minimize expected distortion (over number of source layers, and number of parity layers for each source layer) Subscribe to optimal number of source layers, and optimal number of parity layers for each source layer7"Expected Distortion and Rate C#Lagrangian Optimization  Unequal Error Protection  The Case for ARQFEC does not achieve capacity C = 1-p ARQ makes optimal use of forward channel Adapts to loss (erasure) probability p Used extensively for data transmission (e.g., TCP) and media transmission (e.g., VOD) Must avoid  repeat-request implosion Observe: for broadcast of real-time media, delay (number of repeat-requests) is boundedRJO0Pseudo-ARQ for Receiver-driven Layered MulticastSender transmits delayed versions of source Receivers  request repeats by subscribing and unsubscribing to delayed versions[ Hybrid FEC & Pseudo-ARQSender delays parity packets  Repeated info is actually parity infoEPEReduction in Network Traffic D$Markov Decision Process=Finite-state stochastic process in which a decision can be made at each step to influence the transition probabilities, in order to maximize an expected reward Sequence of decision rules is a policy Optimal policy, which minimizes expected cost (D+lR) of paths through state space, can be found by dynamic programming6>2EDState Space for FEC/Pseudo-ARQ G&CaveatsNo experiments so far, only analysis no actual network transmissions, no source coding, no channel coding source is modeled as D=s 22-2R channel is modeled as iid 20% packet loss, no packet jitter or resequencing assumed no join or leave latencies Little analysis of aggregate behavior%&%Z o&6& IF%Analyzed Systems- No error protection (original RLM) - Equal error protection, redundancy determined by sender; K=8; N=11,14,17,20 - Unequal error protection, determined by receiver; K=8; Ni=Ni* (RLM w/FEC) - FEC and Pseudo-ARQ; W=1,2,4,8, KW=8%13N23L3&4`A$ Results of Analysis  Issues for Further InvestigationEstimation of channel condition Accommodation for join/leave latency Clustering of channels Study of aggregate (social) behavior ImplementationSummary3FEC & Pseudo-ARQ allow error control when flow control alone is insufficient Layered (rate-compatible) FEC allows receiver-driven approach Pseudo-ARQ is more effective than FEC and uses only standard multicast machinery Hybrid FEC/Pseudo-ARQ enhances scalability Many issues remain for further investigation/&'()*+,-./ 0 1 I J KLMNOPQRSTUVWXYZ[\^ 0 zr ( P` X  C ` =  r  S f FY    H  0iq ? ̙330 zrp ( P` X  C ` =  \r  S L<\FY   \ H  0iq ? ̙33rt+ c t%^s@(O %H  ^6BEquation  !"#$%&'()*+,-./123456789:;<=>?@ABCDEFGHJOh+'0 px  8D d p | 9FEC and Pseudo-ARQ for Receiver-driven Layered Multicast\Philip A. ChouACC:\Program Files\Microsoft Office\Templates\Blank Presentation.potPhilip A. Chous61lMicrosoft PowerPointoso@P@`I@ $Е@.yG g  N& &&#TNPP2OMi & TNPP &&TNPP    --- !---&G&w@ zww0- &Gy& --iyHH-- @Times New Romanzww0- 3.2 FEC and Pseudo%'!. 3. 2 ]-. 3. 2 pARQ*'+. 3.2 for Receiver'. 3. 2 -. 3.2 0driven. 3.!2 4 Layered Multicast#4.--QH-- 3@Times New Romanzww0- .'2 Philip A. Chou, Alex       . . 2 iMohr&. . 2 , . .2  Albert Wang,   ) . .2 Sanjeev Mehrotra  ' .@Times New Romanzww0- .N2 0~/(Microsoft, University of Washington, Stanford)             .--"System 0-&TNPP & number of parity layers for each source layer, to optimize received quality[Z[Generation of Parity PacketsBlock each source layer into K packets per block Apply systematic Reed-Solomon type code to packets (bytewise) to produce N-K parity packetse 3!Optimization at Each Receiver6Measure transmission rate and loss probability For this transmission rate and loss probability, minimize expected distortion (over number of source layers, and number of parity layers for each source layer) Subscribe to optimal number of source layers, and optimal number of parity layers for each source layer7"Expected Distortion and Rate C#Lagrangian Optimization  Unequal Error Protection  The Case for ARQFEC does not achieve capacity C = 1-p ARQ makes optimal use of forward channel Adapts to loss (erasure) probability p Used extensively for data transmission (e.g., TCP) and media transmission (e.g., VOD) Must avoid  repeat-request implosion Observe: for broadcast of real-time media, delay (number of repeat-requests) is boundedRJO0Pseudo-ARQ for Receiver-driven Layered MulticastSender transmits delayed versions of source Receivers  request repeats by subscribing and unsubscribing to delayed versions[ Hybrid FEC & Pseudo-ARQSender delays parity packets  Repeated info is actually parity infoEPEReduction in Network Traffic D$Markov Decision Process=Finite-state stochastic process in which a decision can be made at each step to influence the transition probabilities, in order to maximize an expected reward Sequence of decision rules is a policy Optimal policy, which minimizes expected cost (D+lR) of paths through state space, can be found by dynamic programming6>2EDState Space for FEC/Pseudo-ARQ G&CaveatsNo experiments so far, only analysis no actual network transmissions, no source coding, no channel coding source is modeled as D=s 22-2R channel is modeled as iid 20% packet loss, no packet jitter or resequencing assumed no join or leave latencies Little analysis of aggregate behavior%&%Z o&6& IF%Analyzed Systems- No error protection (original RLM) - Equal error protection, redundancy determined by sender; K=8; N=11,14,17,20 - Unequal error protection, determined by receiver; K=8; Ni=Ni* (RLM w/FEC) - FEC and Pseudo-ARQ; W=1,2,4,8, KW=8%13N23L3&4`A$ Results of Analysis  Issues for Further InvestigationEstimation of channel condition Accommodation for join/leave latency Clustering of channels Study of aggregate (social) behavior ImplementationSummary3FEC & Pseudo-ARQ allow error control when flow control alone is insufficient Layered (rate-compatible) FEC allows receiver-driven approach Pseudo-ARQ is more effective than FEC and uses only standard multicast machinery Hybrid FEC/Pseudo-ARQ enhances scalability Many issues remain for further investigation/&'()*+,-./ 0 1 I J KLMNOPQRSTUVWXYZ[\^ re A^s@(O %H  ^6BEquation Equation.30,Microsoft Equation 3.00 :EEquation Equation.30,Microsoft Equation 3.0e0AFEquation Equation.30,Microsoft Equation 3.00BGEquation Equation.30,Microsoft Equation 3.0/ 00DTimes New Roman6|dv 0|( 0DArialNew Roman6|dv 0|( 0" DArial Narrowan6|dv 0|( 0"0DSymbolarrowan6|dv 0|( 0 b(.2  @n?" dd@  @@`` 0eSE   $OI# AA%T(C%" ]} U~JF= B   ,!b"@#L'& 93232/0/.D$<,(:$&<2$"J6bpUC;2$񚻝x?Hhy'Xq2$SW{Yvx $$$2$ϣ'nQ.&%32$O0ρua H$$$2$c ׎I2$\ъo"1:ѱ1zL 0e0e     A@  A5% 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||`3f33@3Z g4KdKdv 0p,ppp@ <4!d!d` 0,7g4ddddv 0pp' p<4dddd` 0,7)uʚ;2Nʚ;<4dddd{ 0h`___PPT9B/ 0&%? %O =,8FEC and Pseudo-ARQ for Receiver-driven Layered MulticasthPhilip A. Chou, Alex Mohr, Albert Wang, Sanjeev Mehrotra (Microsoft, University of Washington, Stanford)i90(1ProblemEfficient and robust broadcast of real-time audio and video over the near-term Internet Best-effort packet loss, jitter, out-of-sequence Heterogeneous transmission rate, loss rate, delay, jitter, receivers Feedback availablevX %7X %7]'ProblemFind ways to multicast real-time audio and video efficiently and robustly over the near-term Internet Best-effort packet loss, jitter, out-of-sequence Heterogeneous transmission rate, loss rate, delay, jitter, receiver capacity Dynamic Influence design of network services in longer termf %?4f %?  4Outline>Multicast Receiver-driven Layered Multicast FEC and Pseudo-ARQ MulticastBMechanism for broadcasting in packet networks: any receiver able to receive broadcast packets by  tuning in to broadcast address Our focus: IP networks Protocols: How to dynamically maintain a multicast routing tree IGMP, DVMRP/PIM/CBT/& How to forward packets along the tree IP Multicastb5& 5& -Packet Forwarding in a Multicast Routing Tree ! Grafting / Joining / Subscribing  !Pruning / Leaving / Unsubscribing   Observations(Bandwidth is conserved. Sender has no knowledge of receivers (likewise any interior router). Scalable: As new receivers join, no new resources (bandwidth, computation) are needed at the sender, and resources needed at any individual router are bounded. Joining and Leaving are a form of feedback. "Growth of Multicast Infrastructure!MBONE has grown from 901 routers in 1994 to 12000 routers in 1998 Commercial routers (e.g., Cisco) have been multicast enabled for last two years ISPs (e.g., UUNET, @HOME) have begun to provide multicast service Intranets are widely multicast enabled Much research and standardization work  Types of Multicast Applications2Reliable Multicast 1-to-M file transfer, distributed software updates, synch. of distributed databases, filesystems must be reliable, but delay is not constrained Real-time Multicast for broadcast of  live or pre-recorded audio/video need not be reliable, but delay is constrainedLcc$h   Reliable MulticastARQ-based error control need to avoid  repeat request implosion protocols use hierarchical re-transmitters (SRM, RMTP, RAMP, RMP, & ) FEC-based error control digital fountain Multiple channels for flow control`n#n# Real-time Multicast Error resilient source coding for error control in MBONE tools (nv), commercial systems FEC-based error control in MBONE tools (RAT), commercial systems fixed amount of redundancy ARQ-based error control commercial systems, LVMR Layered source coding for flow control0(D'0(D'@ dReceiver-driven Layered Multicast (S. McCanne  96)$3" &Code source in layers (base, enh1, enh2, & ) Send each layer to different multicast groupDynamic Joining/Leaving "The Case for FEC 2 )FEC for Receiver-driven Layered MulticastZAmount of redundancy must be receiver-driven to deal with heterogeneity, dynamics Generate FEC in layers, using a systematic rate-compatible code (for each source layer) Send each layer to different multicast group At each receiver, subscribe to number of source layers, number of parity layers for each source layer, to optimize received quality[Z[Generation of Parity PacketsBlock each source layer into K packets per block Apply systematic Reed-Solomon type code to packets (bytewise) to produce N-K parity packetse 3!Optimization at Each Receiver6Measure transmission rate and loss probability For this transmission rate and loss probability, minimize expected distortion (over number of source layers, and number of parity layers for each source layer) Subscribe to optimal number of source layers, and optimal number of parity layers for each source layer7"Expected Distortion and Rate C#Lagrangian Optimization  Unequal Error Protection  The Case for ARQFEC does not achieve capacity C = 1-p ARQ makes optimal use of forward channel Adapts to loss (erasure) probability p Used extensively for data transmission (e.g., TCP) and media transmission (e.g., VOD) Must avoid  repeat-request implosion Observe: for broadcast of real-time media, delay (number of repeat-requests) is boundedRJO0Pseudo-ARQ for Receiver-driven Layered MulticastSender transmits delayed versions of source Receivers  request repeats by subscribing and unsubscribing to delayed versions[ Hybrid FEC & Pseudo-ARQSender delays parity packets  Repeated info is actually parity infoEPEReduction in Network Traffic D$Markov Decision Process=Finite-state stochastic process in which a decision can be made at each step to influence the transition probabilities, in order to maximize an expected reward Sequence of decision rules is a policy Optimal policy, which minimizes expected cost (D+lR) of paths through state space, can be found by dynamic programming6>2EDState Space for FEC/Pseudo-ARQ G&CaveatsNo experiments so far, only analysis no actual network transmissions, no source coding, no channel coding source is modeled as D=s 22-2R channel is modeled as iid 20% packet loss, no packet jitter or resequencing assumed no join or leave latencies Little analysis of aggregate behavior%&%Z o&6& IF%Analyzed Systems- No error protection (original RLM) - Equal error protection, redundancy determined by sender; K=8; N=11,14,17,20 - Unequal error protection, determined by receiver; K=8; Ni=Ni* (RLM w/FEC) - FEC and Pseudo-ARQ; W=1,2,4,8, KW=8%13N23L3&4`A$ Results of Analysis  Issues for Further InvestigationEstimation of channel condition Accommodation for join/leave latency Clustering of channels Study of aggregate (social) behavior ImplementationSummary3FEC & Pseudo-ARQ allow error control when flow control alone is insufficient Layered (rate-compatible) FEC allows receiver-driven approach Pseudo-ARQ is more effective than FEC and uses only standard multicast machinery Hybrid FEC/Pseudo-ARQ enhances scalability Many issues remain for further investigation/&'()*+,-./ 0 1 I J KLMNOPQRSTUVWXYZ[\^ r; :^s