ࡱ> `!!_؛0{ ŵ @xcdd``~ @c112BYL%bpu3@0&dT20< 01d++&1~-bF: pi#&L@%o  '8Y@ 9乇L;-;|d31a {\a<= ×"40Th l0 Ma(w Hq%? L2\ p{A|83Db8`Sl?G}`sm S vr$%̍LLJ% 1.,#c3X]`!s9{ӀWjp" Ew /kxZk\E7Vэd`KEbA-M $l`@z(x B^ ^D z*}g^XJv}wfn}ǜy,;p?Vgŵ+Zm}/)nGثhَ=%uMy0?g?n& $|(NF9' ċ6r*7N.9qsIRmTn4)砅Ή<AM=7νtN3E8e5 5gXK$%ad{||EX^R^_Z=&V9Ernľ:0#밂熉s,No1hNߢ8?<γ7[%MՉ,[2j",?Ss=[ೖ<9|KwDǕ]?[8N}0m1wkvqBYzd&wXWvf}ztKTSD/V}8}2SuLjcꋶTn49 .2}N]*.E/RS8 5}N՝1H/RFYTݍ#~Ƥ-80!qp^GΫSΎN>6giS#{kUjе>&(/-E2kj}diy=4X*NdpP՜rYBeU8b|p]\5ϣLcէlQq\Zk} LiS8(p &z"ʓ6 r*7甁U0LiF*nF &4i;qu8 =/wKc̩h8Qk%js[_§m rqQDէQtqo} j킜ʍ9eDQWuo} v킜=7Nu[֗/D1g;h3tF`!6򸸠[ʸ.`m !`4` xڝ]hUvL#6M55t1 E,kF(k &JA<VE_|?Җ십 P;T[1)6܏9H9?wܝՈI^17MW[xTɑFuJ[*lП GA֣`↼Nׇf92"#3*Ml 7[s@m#eQ"lleQ6#l:-߭la3K ۘqYͲqWپ+'2ߒ}%S?;mlʦw)[W.&%*~twdbrTujl/= F#ў 3/9m.)Nk3#~2#${{}$[p~`;0OC80 1>ܤ4DHf`,.Yx· 0a|\%a k؟Qz׵b79t_˥,vdg(lu-U}zk3yW1u`f$+nիB{v_w0ɻ:c|N\%i ^"-܌_{jg0?މ|}al~ [U}Y&x5_A [+,[AliC6 0Mos̘99ì5wt NM}Tl =ux#,pe͝t.dwףqvm2㫤-ϗ6ĶZ1ꄺ7t ImƄ #S0/ħN~}_4'|vM+A -`?DlaAed`sL})Dz5\<}e$dgVUKr=8=hXǐ ~h>Bo ñU~ +M|CwGKv8& 1|Ą#G,iW$BZ{ 8c9TTP-pK]Ʋv_^qWO"q}\_sM|A)ן=/ ^pQCj\QCj\uE_\s,n4Q׍\7j\7ZzEZC"qCq۹YWia8"%;Bz2}߫+cfx6;O[EjZݫ'Y{>٬g 4&~Nuz[%s϶byNBgWY#o&qПjSxC?*́]፫-x}ܠ_|_P32ZgjYagfb{݈~` /I7ׅOnQ\Rb 7˔w^ؚQ`Ĕxc3q>`#QC&%YmȔ #Sc0†P CS$ 8THF7!,VX);'JێU(p&V:iy-dM>?m_O56䧿h܍%NiSLHY4Y; +uRȎXVC~[5~[-joo~[,.I-X>C~4~,goo~{,{Y DZ`c/ƴB ~I61*f/FIVX< _X=9U9a/V!b*NBX<Zr-4!BZX:"Br}CWu"׽`u/sM|}Ӧ\{\ ח ?^듆\Ը>i듆\Ը>i7-rL׿aq]냆\Ը>h냆\Ը>h> >Y\WFِff \7rݬql뽆\~+'v..g+EjuNkuEaEvq>VrP5,F:nu\:c, YDr}GatbM?rM w?bg7#5|oVڹY%cգo ,mo$-M4it >rx>ՠ,'?mSO4VYi!wmwmk3in >27Nj}&>b1ͧc|276霡OO|vǼqXM|*0iT >2V&O~ħ5>|ZtyG3:ȇ/L61ӻ_xdS~~ӡ>fxhb_=jeV%oeӶnO>۫V^111:7>MtN8c.&8>ᱝ M[N\~ mupYlojؖ{,'W{r/eFVَ2kؘ֌?wϥ%, wd厹:/:Yn_]Ov+VIv Rᕢ?3j)ws@=d3w0%~yv,;&};~޳+YZmD,$dD78|Q*H- +w='TU %6U0T,TKłVzt TX.ZRrfS&p J/h./G-z<lγ9|ll"abπ݂BnņkT \QY?&2`Ʀ;M7n66ltE¦ŦbQ~Tڇ{i.FjQ\?gklԢPyyF~P~v+!J, t$Bu FPW.6B'"!P"3BMl5jb#@HmȌv `#lnТ2{5Ck[ bpL2]Fxh'nP'<%Uc1O5Y<!ܷq{;1,އ邗Wp8 b+e.yJÙ~I" 3Z/>I=A5j R 6s>![ 9J1: nľldf{$7ʽӴe[C6ڝV"]wrw(!F;ӤC<؉SLW-PV?ڞtzѪ[*bE+O`B%beg)ڇ{i.Fj>[s-9[ qO F(P~|6BS"!$|Y.x_`?g@ER< (} %:FtlN:@4GBUu FPG6BGB耏Pef@h=lFHmeFh 6FhC lPB 6BQ"PZ#TnjX{$Hwpqm\勷\q^Q͈vp抹̚NR|I727mT s2-1-,Jq-Գ-p}lP:pma_>->xG@)w Xxi(\qgIl W0-|J#ӓ(6dR\ JJjQe[x(`!ܳ>~v9&g;Գ\w-g 9u4v>@lg{a 0٭=?z~3`!=EcIZ @_xcdd``eb``baV d,FYzP1n:&! KA?H1 < zjx|K2B* R KXB2sSRsxC1X r8W!nf%? ׇ8@| 8߇U7F<= s#ws FP{3|g@vGf=Hb8@e58{84 &K`IG_G?2c 9 b(GPDnddbR ,.Ite`! Jnz΍b߿E*l? @/ x[]h\ݝݽԑb 6R`UZ "JE/5T* UvYIț .Jhb8/!Oi?$dj'!%l~&`%sܝ٫9( »g|9goJbB% 1>@mSLO͟^lk=4K~x_EW[NYo,k<'*mBwH 1(L6夞DZ."ՈCil26MEa9lD٦F+h~qM`rb)LZG`)**? "!;Jh'pYMQLV*E˙'[ K(Dd؊ҫ3<ғA>A@)X*Ho9zf1N~&" cvUc}DN`UWK*nUWK<҄TQ/:Tu"dala|uGyez}PeLӝ}%#Xcͫ,,Y`nJA 8%X~& J;cE,y9Λ)qDugv^xg?v?N?r?xgKT7,{')g;}>zOs=e~Kȝ>;ჿ^]ˈzj7d`r'zYݮֹ~~[}t7jpo`ds|pE6PwުY:_ z]Nw;lB5ui!'nMQcKé7s]s=|~N~@iƖ 9B574% %6jl rksNsZE~N~--DiƖ 9˩7sSsH~N~EiƖ 9i-ik295o4S[|TKD5W{j I|0^5Y6k %>~$zMfM&1ݥaSN {K63z.,EGnL5x@dl˧E_E\U}uHm }pZ ] eczPBW\˞O8χ=o>#6vCYHpfx|`6䄚3ssɚX8|Y3<>U{6cArSo<Ĝf:2_ cf[sg5._ cf"Nwߡoً_4€ջT /g:(X  D   2Document Word.Document.80.Microsoft Word DocumentDocument Word.Document.80.Microsoft Word DocumentEquation Equation.30,Microsoft Equation 3.0Equation Equation.30,Microsoft Equation 3.0Equation Equation.30,Microsoft Equation 3.0/ 0DTimes New Roman(0(z[ 0 DCourier Newman(0(z[ 0 1 DUnivers (W1)an(0(z[ 0 0DSymbol (W1)an(0(z[ 0 @DComic Sans MSn(0(z[ 0 BPDMonotype Corsiva0(z[ 0 B@ .@  @@``  @n?" dd@  @@``   X $*  0/34 &%'"-   : *O=;#&T'T#:;!? ) ? 7=$%&'()*+, o2$!_؛0{ ŵ2$s9{ӀWjp2$6򸸠[ʸ.`md2$ l$Ưܘ]. 2$=EcIZ=$$$$$$$$$$$$$$$$2$Jnz΍b߿E*  0e0e    A A1 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||@333f@fdg4KdKd@z[ 0ppp@  <4!d!dl< 0<4BdBdl< 0g4CdCd@z[ 0p, p^ ʚ;2Nʚ;<4ddddl|- 0Xr0___PPT10 2___PPT9/ 0?  O =%-New Models and Algorithms for Active Networks 7The Active Bell-Labs EngineAn adjunct active engine to any COTS router Only some packets are diverted to the AE Packet Delay depends on whether it passes thru the AE. Processing time in the AE may depend on data in the packet. soft state in the AE.N*7k*OAddressing ModesExplicit - sent directly to a known AE. efficient Oblivious - sent along a path, and intercepted by the first AE en-route. topology learning robustf( I33 @6 What is the right model to analyze algorithmic solutions? How to compare the strength of AN architectures? Are active networks efficient?.9$O8Standard Asynchronous ModelCommunication is between neighbors A message arrivals triggers computation at a node A single bound on the delay of a communication + computation cycle What does O(n log n) mean?N ; The RS Model 2 (Two bounds on the delay: C thru the FF. P(k) thru the EE. Forwarding is done according to the destination addr. No assumptions on the routing. We use P(k) = P k |#i$' l5<DARPA Model vs. The RS Model( =Performance MeasuresCommunication (Message) complexity - hops traveled by messages Time complexity - time to mission completion. processing complexity - CPU time used.*m%333n.)An Application Example: Route ExplorationIn the model - a node is only aware of its local neighbors. A node wishes to learn the route to some destination. Abstraction of the traceroute program. &    9A nave Solution$ EThe source query nodes sequentially. O(n2) messages. O(n2C+nP) time. 6F( PA nave Solution$ EThe source query nodes sequentially. O(n2) messages. O(n2C+nP) time. fF(  >report-en-routeuA query process advances sequentially. Reports are sent to the source for each query. O(n2) messages. O(nC+nP) time. $vYf ?collect-en-routeA query process advances sequentially. Information is collected in the forward direction, and sent by the destination to the source. O(n) messages. O(nC+n2P) time. $ Rcollect-en-route 3&Route Exploration@Report-every-l& OObtain the route length. Initiate collect-en-route in n/l segments of length l.HP"SReport-every-l& Complexities: message O(n2/l) time O(nC+(n+l2)P) alg. at the ith segment starts after (i-1)(C+P)l segment time cmplx: For l=n2/3: message O(n4/3); time O(nC+ n4/3 P)#F %             P2 /& A Collect-rec  Optimal up to a log factor ! Obtain the route length. Partition the route to two segments. Send results from the second segment using the FF. Perform recursively. Complexities: message O(n log n); time O(nC+nP) $  KCollect-rec (2)6 JTCollect-rec complexity:  `&  We can count messages/time per iteration. Alternative approach: TC(n) TC(n/2) + 4n(P+C) MC(n) 2MC(n/2) + 4n2@.@(m INMessage DisseminationA message for a large number of receivers. No notion of group. Ad-hoc. Processing time is linear in the recipient size. Example: a full binary tree(GMUNave solution esend a message to each recipient Complexity for a full binary tree time: nP+log n C message: n log n vC#C IVNave solution esend a message to each recipient Complexity for a full binary tree time: nP+log n C message: n log n vC#C IMMail Distribution (2) W Multicast  lWe assume a multicast group exist Aim: build the best tree In general: NP-hard We will look at the line case$mG$l XPrevious Solutions Unicast: time complexity: O(nP+C) message complexity: O(n2) message dissemination: time complexity: O(n(P+C)) message complexity: O(n)  34 $hYBetter solution 3Embed a tree in the line What should be its arrity?&, ZComplexity of a tree scheme  [Optimum ;x / log x achieves optimum at 3 when restricted to integers.<2; BOther Basic ProblemsBottleneck detection - computation along a route. Message dissemination to an ad-hoc group. Topology discovery. Computation of a global function. CSummaryA new model to analyze active network applications. Can be used for Other domains Peer2Peer application layer multicast Can be used to compare strength of architectures by comparing lower bounds.JR&L G&L/x      ` ̙33` 3` 3333f` 999MMM` f` f3` 3>?" dd@,|?" dd@   " @ `"  n?" dd@   @@``PR    @ ` ` p>> (    Z|9zgֳgֳ ?P z T Click to edit Master title style! !:  T1?0   =managerB  ` ZDo? 0 @ B  ` ZDo? 0 @ B  ` ZDo?@0 @`pB ` HDo?  |B ` TDo?  B ` ZDo?  B ` ZDo?  B ` ZDo? v2 ` N1? pB ` HD1?  2 ` TD1?P`pp C session 1  2 ` TtJ1?Pp C session 2  pB ` HD1?p0 pB ` HD1?pp` H ` 0޽h ? ̙33!  K0   >>> (    ZSxaxa?`` : 2   3 rTxaxa ?P     3 rSxaxa ?n  z $\l   $\l ,$ 0N $   $ N T  T   `\xaxa1?TD : 2     `DYxaxa1?Tc : 2 f2   61?gzf   61?_~f2   61?;~B   NԔ?2  Zdxaxa1? : 2 f2  61?g f2  61? l  <1?T,;l2  <1?$ N $l  $lN 4T<  4T<   `,ixaxa1?4T : 2    `mxaxa1?4< : 2 f2  61?{ f  61??d%f2  61?w~B  NԔ?k2  ZXqxaxa1?# : 2 f2  61?Ggf2  61?l  <1?4`l2  <1?$lN 4$ l    4$ l N dT <  ! dT <  "  `vxaxa1?dT   : 2  #  `0zxaxa1?d <  : 2 f2 $ 61?  f % 61?o % f2 & 61?  ~B ' NԔ?  2 ( Z&xaxa1? #  : 2 f2 ) 61?w  f2 * 61?  l + <1?d  l2 , <1?4$ l xB - H8c?/xB . H8c?xB / H8c?!xB 0B H8c?xB 1B H8c? P xB 2 H8c?R" 0 xB 3 H8c?! xB 4 H8c?xB 5 H8c?rxB 6 H8c?xB 7B H8c?RxB 8 H8c?f2 9 61?$ f2 : 61?t\f2 ; 61?t<f2 < 61?tf2 = 61?f2 > 61? LL H  0޽h ? rswJ 7iWaG  \( w \l \ C P   l \ C   H \ 0޽h ? ̙33  d(  dl d C $P   l d C   H d 0޽h ? ̙33  )p<(  px p c $`   x p c $`    p T1? @ :  p Z1?P pPp  >FF | p T1?p @ p Tp1?pP XExecution Environment (EE)"(2B  p ZDo? B  p ZDo?  B  p ZDo? vB p ND1?  p p H 1? ` p B$ 1? B @Filter 2p2 p H o?` 0 vB p ND1?  vB p ND1?p  pB p HD1?  vB p ND1? vB p ND1?`  p H 1?@`h oracle|B !p TD1? pp@vB "p ND1? 0 vB %p ND1?` 0 vB 'p ND1? 0  (p BX 1? p  H forwarding" vB )p ND1?` P H p 0޽h ? ̙33y___PPT10Y+D=' = @B +  4Nte( ,?lFF | t T1?p @ t T1?pP XExecution Environment (EE)"(2B t ZDo? B  t ZDo?  B !t ZDo? p "t H 1? ` #t Bd 1? B @Filter 2p2 $t H o?` 0 vB %t ND1?  vB &t ND1?p  pB 't HD1?  vB (t ND1? vB )t ND1?`  *t HL1?@`h oracle|B +t TD1? pp@vB ,t ND1? 0 vB -t ND1?` 0 vB .t ND1? 0  /t B 1? p  H forwarding" vB 0t ND1?` P | 1t T1?p 2t T1?I BEE 2"(2| 3t T1?p@  4t T1?@ I BEE 3"(2pB 5t HD1? pB 6t HD1? vB 7t ND1? ` vB 8t@ ND1?` `  Jt T 1?` @g  >IP B Lt ZD1? @ B Mt ZD1? ` |B Nt@ TD1? @ H t 0޽h ? ̙33y___PPT10Y+D=' = @B +  x( (:%:4%A xl x C 4P   l x C   H x 0޽h ? ̙33 K0 ph (    C xxaxa1 ?P     C xxaxa1 ?  ^  61?``  T`xaxa1?Q 645H  0޽h ? rswJ 7iWaGH+  @.9h (  hl h C ,P   l h C \%   pB  h HD1?pB  h HD1?pB  h HD1?00pB  h HD1?P P pB h HD1?|B h TD1?P |B h TD1?pP p|B h TD1?P |B h TD1?0P 0|B h TD1?P |B h TD1?P |B h TD1?PP P|B h TD1?P |B h TD1?P |B h TD1?pP p|B h TD1?P |B h TD1?0 P 0 |B h TD1? P  |B  h TD1? P  |B !h TD1?P P P |B "h TD1? P  |B #h TD1? P  |B $h TD1?p P p |B %h TD1? P  |B &h TD1?0 P 0 |B 'h TD1? P  |B (h TD1? P  |B )h TD1?P P P |B *h TD1? P  |B +h TD1?P |B ,h TD1?pP p|B -h TD1?P |B .h TD1?0P 0B /h ND1?P 0p,$D  0B 0h@ ND1?P 00,$D  0B 2h ND1?P P,$D  0B 3h@ ND1?P p,$D  0l P p  8hP p ,$D  0B 4h ND1?P  ,$D  0B 5hB ND1?P P p ,$D  0l P  9h P ,$D  0~B 6h ND1?P P ~B 7hB ND1?P H h 0޽h ? ̙33`X___PPT108+wYD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(DE' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*/h%(D' =-6B%strips(downRight)*<3<*/hD' =%(DC' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<*0h%(D' =-6B#strips(downLeft)*<3<*0hD' =%(D' =%(DE' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*2h%(D' =-6B%strips(downRight)*<3<*2hD' =%(DC' =4@BBB B%(D' =1:Bvisible*o3>+B#style.visibility<*3h%(D' =-6B#strips(downLeft)*<3<*3hD' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*8h%(D' =-o6Bwipe(up)*<3<*8hD' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*9h%(D' =-o6Bwipe(up)*<3<*9h+  TLP56(   r  S dHP   r  S I   pB  HD1?pB  HD1?pB  HD1?00pB  HD1?P P pB  HD1?|B   TD1?P |B   TD1?pP p|B   TD1?P |B   TD1?0P 0|B   TD1?P |B  TD1?P |B  TD1?PP P|B  TD1?P |B  TD1?P |B  TD1?pP p|B  TD1?P |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B  TD1? P  |B  TD1? P  |B  TD1?p P p |B  TD1? P  |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B   TD1? P  |B ! TD1?P |B " TD1?pP p|B # TD1?P |B $ TD1?0P 0B % ND1?P 0p,$ 0B &@ ND1?P 00,$ 0B ' ND1?P P,$ 0B (@ ND1?P p,$ 0z P p  ) P p ,$ 0B * ND1?P  ,$D  0B +B ND1?P P p ,$D  0z P  ,  P ,$ 0~B - ND1?P P ~B .B ND1?P |B / TDo?0P P |B 0 TDo?P|B 1 TDo?pP P |B 3 TDo? P |B 4 TDo?p P P |B 5 TDo?p00|B 6 TDo?P  H  0޽h ? ̙33h3  ld`7<(  U::A r  S `P   r  S da   pB  HD1?pB  HD1?pB  HD1?00pB  HD1?P P pB  HD1?|B   TD1?P |B   TD1?pP p|B   TD1?P |B   TD1?0P 0|B   TD1?P |B  TD1?P |B  TD1?PP P|B  TD1?P |B  TD1?P |B  TD1?pP p|B  TD1?P |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B  TD1? P  |B  TD1? P  |B  TD1?p P p |B  TD1? P  |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B   TD1? P  |B ! TD1?P |B " TD1?pP p|B # TD1?P |B $ TD1?0P 0vB % ND1?P 0pvB &@ ND1?P 00vB ' ND1?P PvB (@ ND1?P pvB ) ND1?P  vB *@ ND1?P P p vB + ND1? P P vB ,@ ND1? P B 0 TD1?P 0p,$D  0B 1@  `D1??P 0-,$D  0B 3 TD1?00,$D  0l P P :P P,$D  0B 5B  `D1?P PB 6  `D1?6l P P  ;PP  ,$D  0B 7B  `D1?P PpB 8  `D1?PB 9B ZD1?P   < Nv1?\  P,$D  0 H~send Report(id, c+1) to s if id send MSG*(s,d, c+1) to d@ H  0޽h ? ̙33___PPT10|+}ʞD(' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*0%(D' =-o6Bwipe(up)*<3<*0D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*1%(D' =-o6Bwipe(up)*<3<*1D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*3%(D' =-o6Bwipe(up)*<3<*3D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*:%(D' =-o6Bwipe(up)*<3<*:D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*;%(D' =-o6Bwipe(up)*<3<*;D' =%(D+' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*<%(D' =+4 8?dCB2/3*#ppt_wBCB#ppt_wB*Y3>B ppt_w<*<D' =+4 8?dCB2/3*#ppt_hBCB#ppt_hB*Y3>B ppt_h<*<+8+0+< +D+  p::6( @  r  S P   r  S L   pB  HD1?pB  HD1?pB  HD1?00pB  HD1?P P pB  HD1?|B   TD1?P |B   TD1?pP p|B   TD1?P |B   TD1?0P 0|B   TD1?P |B  TD1?P |B  TD1?PP P|B  TD1?P |B  TD1?P |B  TD1?pP p|B  TD1?P |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B  TD1? P  |B  TD1? P  |B  TD1?p P p |B  TD1? P  |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B   TD1? P  |B ! TD1?P |B " TD1?pP p|B # TD1?P |B $ TD1?0P 0vB % ND1?P 0pvB &@ ND1?P 00vB ' ND1?P PvB (@ ND1?P pvB ) ND1?P  vB *@ ND1?P P p vB + ND1? P P vB ,@ ND1? P |B - TD1?P 0pB .@  `D1??P 0-|B / TD1?00B 0@  `D1?P PB 1  `D1?B 2@  `D1?PP pB 3  `D1?PB 4@ ZD1?P  B 5  `D1?P 0p,$D  0B 6  `D1?00,$D  0B 7  `D1?P,$D  0l P p  :pP  ,$D  0B 8  `D1?pB 9B  `D1?P P  H  0޽h ? ̙33F > ___PPT10 +mD ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*5%(D' =-o6Bwipe(up)*<3<*5D ' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*6%(D' =-o6Bwipe(up)*<3<*6D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*7%(D' =-o6Bwipe(up)*<3<*7D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*:%(D' =-o6Bwipe(up)*<3<*:+B   :<( |^  r  S P   pB  HD1?pB  HD1?pB  HD1?00pB  HD1?P P pB  HD1?|B   TD1?P |B   TD1?pP p|B   TD1?P |B   TD1?0P 0|B   TD1?P |B  TD1?P |B  TD1?PP P|B  TD1?P |B  TD1?P |B  TD1?pP p|B  TD1?P |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B  TD1? P  |B  TD1? P  |B  TD1?p P p |B  TD1? P  |B  TD1?0 P 0 |B  TD1? P  |B  TD1? P  |B  TD1?P P P |B   TD1? P  |B ! TD1?P |B " TD1?pP p|B # TD1?P |B $ TD1?0P 0vB % ND1?P 0pvB &@ ND1?P 00vB ' ND1?P PvB (@ ND1?P pvB ) ND1?P  vB *@ ND1?P P p vB + ND1? P P vB ,@ ND1? P |B - TD1?P 0pB .@  `D1??P 0-|B / TD1?00B 0@  `D1?P PB 1  `D1?B 2@  `D1?PP pB 3  `D1?PB 4@ ZD1?P  B 5  `D1?P 0p,$ 0B 6  `D1?00,$ 0B 7  `D1?P,$ 0z P p  8 pP  ,$ 0B 9  `D1?pB :B  `D1?P P   ; H,1?  8Lif i==d send Report(list|i) to s else send MSG*(s,d, list|i) to d M  H  0޽h ? ̙33  qi(  r  S P    0 6A  ?$     T1? r  ACan we do better?H  0޽h ? ̙33  ( x@K@ l  C xP   l  C L  H  0޽h ? ̙33  d\@(  r  S P   r  S   `  c $A ??  `  c $A ??d   H  0޽h ? ̙33  $(  r  S P   r  S   H  0޽h ? ̙33]  C C::B(  BC    txaxa ?P   6 F       ~B  N DV?  r2  B 33?  r2  B 33?  r2  B 33?  2  H 33?   : r2   B 33?  r2   B 33?  r2   B 33? r2   B 33? r2   B 33? r2  B 33? r2  B 33? r2  B 33?  r2  B 33?  r2  B 33?y  r2  B 33?n  r2  B 33?{  r2  B 33?^  2  H ? X ,$D 0z     ,$D 0x2  H ?     v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||cLY@   z ?    ?  ,$D 0x2  H ? " x2  H ?p     v    BCUDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||DaHoU@   W     v    BCUDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||DaHoU@  ?  : z       ,$D 0x2   H ?  x2 ! H ? & x2 " H ?  x2 # H ?G   $  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@     %  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@     &  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    '  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@   2z    (   ,$D 02 ) H ?j  ,$D 02 * H ?   ,$D 02 + H ?  ,$D  02 , H ?  ,$D  02 - H ?  ,$D 02 . H ?\  ,$D 02 / H ? + ,$D 02 0 H ?  ,$D 0 1  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    ,$D 0 2  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@   ,$D  0 3  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@   ,$D  0 4  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    ,$D  0 5  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    ,$D 0 6  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    ,$D 0 7  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    ,$D 0 8  v    BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    ,$D 02 9 HT? [,$D  0 Time: O(nP+nC)( ,? : H?t ,$D  0 Message: O(nlogn)D  H  0޽h ? rswJ 7iWaG|t___PPT10T+D' = @B D' = @BA?%,( < +O%,( < +DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(DX' =%(D' =%(D' =4@BBBB%(E' =1B B`BPB1:Bhidden*3>+B#style.visibility= `B<*D' =1:Bvisible*o3>+B#style.visibility<*%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*9%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*9D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*9D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*:%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*:D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*:+p+0+9 ++0+: +\  DD@99D(    Z|xaxa ?p@ uCollect-rec (2)( 6 F       ~B  N DV?  r2  B 33?  r2  B 33?  r2  B 33?  2  H| 33?   : r2   B 33?  r2   B 33?  r2   B 33? r2   B 33? r2   B 33? r2  B 33? r2  B 33? r2  B 33?  r2  B 33?  r2  B 33?y  r2  B 33?n  r2  B 33?{  r2  B 33?^  N    A3  k ,$D 02  Z ??j  ,$D 02  Z ??   ,$D 02  Z ??  ,$D  02  Z ??  ,$D  02  Z ??  ,$D 02  Z ??\  ,$D 02  Z ?? + ,$D 02  Z ??  ,$D 0        BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@    ,$D 0         BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@   ,$D  0  !      BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@   ,$D  0  "      BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@    ,$D  0  #      BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@    ,$D 0  $      BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@    ,$D 0  %      BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@    ,$D 0  &      BCDEF o 8c8c     ?1 d0u0@Ty2 NP'p<'p?A)BCD|E||-v [n@    ,$D 0j z    'A  { ,$D 02 ( T Ԕ?  2 ) T Ԕ? & 2 * T Ԕ?  2 + T Ԕ?G   ,  v    BCDEF Ԕ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@     -  v    BCDEF Ԕ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@     .  v    BCDEF Ԕ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@    /  v    BCDEF Ԕ 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||-v [n@   z ?   0A M  ,$D 02 1 T p? " 2 2 T p?p   3  v    BCUDEF p 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||DaHoU@   W   4  v    BCUDEF p 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||DaHoU@  ?  z   5A ( ,$D 02 6 T )?   7 #     BCDEF ) 8c8c     ?1 d0u0@Ty2 NP'p<'pA)BCD|E||cLY@   2 8 HȽ|? [,$D  0 Time: O(nP+nC)( ,? 9 H|?t ,$D  0 Message: O(nlogn)D  H  0޽h ? rswJ 7iWaGg____PPT10?+ܝD' = @B Dn' = @BA?%,( < +O%,( < +Dq' =%(D' =%(D' =4@BBBB%(E5' =1B B`BPB,54*3>B ppt_c='`B@BPB<*D' =1:Bvisible*o3>+B#style.visibility<*%(Dq' =%(D' =%(D' =4@BBBB%(E5' =1B B`BPB,54*3>B ppt_c='`B@BPB<*'D' =1:Bvisible*o3>+B#style.visibility<*'%(Dq' =%(D' =%(D' =4@BBBB%(E5' =1B B`BPB,54*3>B ppt_c='`B@BPB<*0D' =1:Bvisible*o3>+B#style.visibility<*0%(D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*5%(D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*8%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*8D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*8D{' =%(D#' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*9%(D' =+4 8?dCB1+#ppt_w/2BCB#ppt_xB*Y3>B ppt_x<*9D' =+4 8?\CB#ppt_yBCB#ppt_yB*Y3>B ppt_y<*9+p+0+8| ++0+9| +  P$(  r  S ,P   r  S |-  H  0޽h ? ̙33y )!P( 6Vg[8Y[   Z|xaxa?`` : 2   ZH|xaxa ? MRoute Exploration (5)  NA ??d X $ 0U 0H  0޽h ? rswJ 7iWaG  K0 x( CP    3 rl3xaxa ?    Z7xaxa?`` : 2   3 r8xaxa ?P   pB  HԔ?,  H  0޽h ? rswJ 7iWaG  ` $(   r   S >P   r   S ?  H   0޽h ? ̙33%   LDp (     0$0N}n#&k3d/a8q0*FyW#^x-u#ހ$y0lFlA؊xy oE\6ňm}bve2OC8 #hL `ys>FcqIq{m0ɷ7o8u0h?!V$3I`F>dzWldN0v+_WEI_%h|Qx`1b>ٙKmsnt8;k-DC oSV;~hJ^*j :ZZ 퓋m,1^W[F@^:}qم o5:L躷ׄ;EKjN?2 Ρ0՝ǐ֣n9mƸ_bh V CXJ~ hƷƄWX nl䭐w ȫ{V*{cxY^_nc[uO8_7Xaڽظ,{0ð/;} 4!e0Î3˖je :øL9|(ܾK1Wcj/c5Y,V -\JkrcHq,p$;_Z.D3¹oReP'W\z5|.DT GXt" " " 1 ogCo 7~3suHpBR)ţN\rqq"럨@T66dZ\3Z^ q.w}A|4213١3?jL`&3cV~-wṣ区Y7);&uZlr5Q-H_rrx3|oLh{hx y!ndK넺^, x̀~G1 uBDu/b-Sۤ{mȉ=I4⟉:2^Z_f'sI? 2^Z_'Yub>f)2^Z_ٺuR9ulLMi^Z_'XnTNjk4aT}az6"m_|M:UןO7w҆Ƕ㴡3>7M?1|Š_kZIAzM8FzsdLOO_K:)E#]x]w:MmY͒>eA]QBĞU=97C%#? υRյvXOL jv;%=~n i۬#!Q^e= h(M^/ٓSʯ>P^Ohtxi}*RNW)J)ϧe4e:L˓^JשWF4//s̓^-KשjWceh27_3_t?38Fۮ1qƔtƔVؿ^[gs=y^(S$\B.D>XƬW<|YRgԕc QWʽ9WPlk׫ePtLۙ'½pgzƷcgUjYD0}FIҵN*ʃiL֗9`:}+<jtxi}'S׃sW4WSf֗9`:Ly0>ՒI+[vcSo,ϟ*WL֗ =S^_=vTSK˜dznvlf)O;)eZL]ڭ /L?UiG5eyi}cL}o]Fmϟ*j]iG sD"-߼o/鷺$ fwvv[aٚX#4xrqka))Wu~Mg( K |Ho?1|H W+ʴN؊ϰ9[!L1[aH䅡~Gz[~BXO8}Mm2,QP9Rv0-g/)[<5K=d|ƶGBg]-lŞU^lW 1騨q.5͈- ފ q9*N5]7"ޏ؃WއɿNz6n\0>14ҒHKi1J4_}; nBA׻~0@ 1feL<a0j[y؇~k%s pWO-3! xnCg՜AVgœި zwY p˂FzJ]0yᓳRd\`6qaXI1Rw=x|3+'Y7ZGA[~Lyw}/=E7]z/k! v b8 OxO-ߒ;{r'brG;'au;s^C|gkrgP-F  ]M;7ԶAnr$D9#mmK[>g' gVAqSίaDADADA\j |RHVஸԖ˥ʿy_(߽sډ'`m)Vv!s4G: :} 8S^q.L='=6gGrl3Jewm)XT?3?h e=tJK=iÛw?|^-Vc q?,Rkƙ Ka1a-taŘZvt:0D'gnk[sDADADA_l/[Bx] p\u{e #we$cL1-7TTHkKym)DNMmLEL~0eC)vSLgɐ!&d&c%,g<{ߟۧw,hќ}w7^S~0S:cqU1ןX⑈PtxY 8:7)4f8R6v!O<bKk/  x6s <xB8.^ |%p#U_^bK3k+W^ |Oֳ.V~8ԡ`LvcIiB~T޾ޝk/~(9aY.LPldwۇ0 yc90P}l]SƑBv?hr7qh9ljmo@a{aK1^ή*tŜVHt<_h_{ų(4f4bp0*|6`1R681of5β)v#,f`W-$ֺݼ&nYp-[Sb~pm[;up>U|nc= |J};9Ia$#7o)3 +]T[䊡 -? ^ҎH5;J3VêȽ~·5zγf-^]\i`PEYFZ* /e>Wrh Vv, ᠢD<16@[>8sa'- qCV25Š΂hWq }^MeSӹ e; %#ҴBYe877W-R/e[ evJ#TccaOW;fZEnT$Dk)zrѳB_gm-fk`sxޗZ/qaZ3=J ,4Jf7i#ٻ3-0X\>r~'Fɕ㼸4yqck!uM/uFW%ByzlO OQtyŽb]6⨖jx_/, jT$ts &nJT-Gj9<8少5Ôàà1r{z{@%noW 9gw { Έ4U*ς쑿y񂂉hCJI[qU1k6Vbto,TNQ9A͓bs²ߝPe:|O=n=ݲRWe:t̓6$5OVJSI*Ӊ8j1ؘ} f4H@0KpeYne'mEXA)`GL]񍜶ff𷬍i)q~EX=sc/SAyџkjPݼl!k}7G 2nmڸr.E8WF[AJ+}P}u)`_M&lavƎ&T9맱ժm !~B K;CN|#1qәb7-QMfFY wIQ(AR^j̏BQFI99fi_Gz>}AL: 6.o_w;u+6JDM_QO%j~(IOCo%}jI[K\&"N 4zbR`Hsp έ9 RX7ZVb;Xz,r گQ:()*/+(۱dXC(#q%(헊6JOpvSg"CiOvcOIS~^/veRŮ*^ ;zBU"(1Jq'XFP6V:͉Z*Bs= j{NΞm7eyf_>[S9"ntwmLʼ#ˌ>eyf_>[߃9"&Y`fIdҌ=o2Ǵ}{6GA46I7e=/2Ǵ}{ .z8u]w^T|x˸}$hd2ܢ;̫)~G멾H G|哩-yU\F${:lc= `n륚JV-<[j>G?sה^_nOy w^99>ī?^,Y\_vgK7|#~cH#đ!a@]a!;{- =o_2 Ր`e%|WF/>l5oF4ct_|p.=7BRz>k3㉋b5;oϘ+67&'zv8y|Fi|3H>-t`2QCnXg1;Xc58<&}(>NYg5xHq O2FYuum[.s\/>$2x0ȼi;2 tk}}rM1Qh k Y`؉N7%jYWd_<Ť1 N7T"}SeWڻt{<]?rvs {p 1z1v4wbD&kslf.wЗM \glrg/v9ڸ}|֞Ν"+8i@^@_g~awȊc!f#zn態ś0l{?`4}3}}1"("("(&7_{E3þCz*(O4}?(~>Iy?U K(k`c=Ll1zw<1F/0Me&c*3 zʹ36:惿\1!_3wlE].w3qSM3Ll-sigMau5cu7nZebۀ–Jl1+v5Bpu%l%\_;g& U*HR_6"("("(I{xWMHTQ>ofD &P񯍄11)ڪ4FxF1E" Ⲗ-۶ k!-Zڢm$VBL{5pwsޛ돖C rrژbAU\\>th٧PDzDsخC;4)2lQ'asy׸h_ݽn٪WjWFg)`B(n23?^Հ?'aE~:'I~\չ#4;+"uYϩusZR2rA JWTȘd-c258N!jV\Ge)_%4=G;akϐۦ&w o4sk$;ܺ夅sJP5HLx( xL|o N3';9꧞欍[lnr_2/ g'Ǯl$:-]ZDmƁ98+a:}[XJxtZ҄iY.ƛ(ήxlxL2xN'Xʄ(6L=hD_FEYKύ2ٛxÎYooh/@o]d:q7<\f7gәxh~Aݩ|%*54f08Ca B 1-X&7 [8V352Z 7]M1 _Ԏ,hՍ`Poha$hx_ _mi1=4ݘ 7$L(دO0zO< /XŭtxWOSAWZZ" !TL XHL8`jj&R*@1%ּ@[UCg` &#A`hWJii7;ݙkåPF@| 6XPWzP(ͅc:RlW{hoدc;4I AHw2GԂcEEZjpfp Ө`>50 nLwrSUL8|Uvne(MU2JϐX"[qP$}{,3ܺɳyj0GSPt;GP7}YzD|癬>=o'1.ҍ>^K.Sd#=6 '@X-&_~mÚCljI@qKp޲o_'< ou8d,CtV3O$ cöSl-,oɢ _i_.j k?+Ox6ųuU:Ib59%c4JGF?4Lˡ JL_{/BӘδ Nh\u7>߅eHAո`-sy.A@49](NcN|30H'es=Ug['J/0za";(ZzyqJ CCT- sKWxX[lTEϜYvvg@[z+VV(^+^6Y@ K`YY5!bZ_O|!؞DPi7A0X}5Q}@#\~H _Fκqau~ȧ(KϧyqPӘl8{g?r? DW>[`5}3b Ջܷ?M #\`E@iؙhFAE Zmy$b>ql9s!: #: "R l#K!.F\T!.G\Xpb9bjDq 7KϸYb6guaKaC1ržB>$kz2~I-6/;>uc0݊Ólv[(;zY"hRV=#VN'p{na:!܄r_2'M$^ {>++9Q%;Шd% YvPz}!!N_tcD^K(ޱ 7ŕF%kRl%*H>.2~@o %*WJTC?3"6s .ۆ|Zz_mg]IӒ#mbٺ~1r~ :_6bn/vԛbrޗUGX\k,Ci9 hjZqf~; WSZx2&%t>U 9-<Qϯ;$/F?uƌbtȯBO6z<j[fe'o%C.m;b k ~_=W-/ʯDMz1=y/Ƿ|>7|2')::d=}>B|ӽ1M}^X[}oO&}. I s7邂m/uwT<1uW JrJ(/N)Ԥ{,n?5WԑR!jqFhq#h#W t!]BMjP+T;=-TXvΛu~OmquKB^>D~52*eFSɌ>su{=c-9>S߮@|=E/YR 07թjɆ۪nf/J @/ $lkM$1bd->KK L쟝Mír?>y1 ޷-˶ϲ,Dw<ҁ<>ZvO+|cG;LV֟ԁ/ ؏?]Syӌ GF ' @˞Gw)xNRRYp<ߞsi(O@y`\fL4L%]< r}m'LMzJHV_eW[(8/kpr@MDo:JuE2 n{nx0mL|~lih/7~ӂ8b0[ApDSpڑ[D$[0oo?HJ$oxI{5}? JYOh+'0 x (4 T ` l x.New models and algorithms for active networksweActive Networksshavitt-E:\MSOffice\Templates\Blank Presentation.potweshavitt84vMicrosoft PowerPoint\Bl@`ߔ@z @2d @+Gxg  44  -- @ !--'@Times New Roman-. 42 eNew Models and Algorithms for ,,6+/."System-@Times New Roman-. 2 $Active Networks+,-.-՜.+,0\    ( Letter Paper (8.5x11 in)A Lucent Bell-Labsx11k!A *Times New Roman Courier New Univers (W1)SymbolComic Sans MSMonotype CorsivaBlank PresentationMicrosoft Word DocumentMicrosoft Equation 3.0.New Models and Algorithms for Active NetworksThe Active Bell-Labs EngineAddressing ModesSlide 4Standard Asynchronous ModelThe RS Model DARPA Model vs. The RS ModelPerformance Measures*An Application Example: Route ExplorationA naïve SolutionA naïve Solutionreport-en-routecollect-en-routecollect-en-routeRoute ExplorationReport-every-lReport-every-l Collect-recCollect-rec (2) Slide 20Collect-rec complexity Slide 22Message DisseminationNaïve solutionNaïve solutionMail Distribution (2) MulticastPrevious SolutionsBetter solutionComplexity of a tree schemeOptimumOther Basic ProblemsSummary  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles!_Jshavittshavitt  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwyz{|}~Root EntrydO)Pictures'Current UserSummaryInformation(xPowerPoint Document(nDocumentSummaryInformation8