ࡱ> $!"#`!ҮӽwUp 4x}tUǟ_΄ɉ`)Ox!e FL9p[n?`Q`,1хz61,XJ ́A1s:|r=={{{cFd*PaJO !(PΜG+w’jrI7 t?/ 0Q3g.2P9dFQdz˭$?Zw/.eH;w͟f=e@ӓ:'=q̢"=n0oJAI>Ƒ^Fy~f1u2H!O@vqA)ߝ:x|SMr7'#(rѻd4v¹|6[OCd<]JkO;ܚ}T3NzJW(cT1M?׬fУ LA^ߗ2Kyy\-:Q?})_:(SFF ԍVE "uSb2~ J)ʖu7!_PC>#d|;!f?)i6KnA1,2/ yKW_eAG#?~E^}Yd_Rߪ"K9!q\w2!࿬~[Տq \_~nw QC7\;2e+[2um)2>c>-cd|tF o92BX12~ ψAV512^*oAoUG+12Mշ?#ϫ?zAe-7zdLM0_U?#/IMtt_9*MS? ?i<c"h!_{u4ʣ>HyE5w蜛K7A7|G<>PI?ѓ~8kˏ'MO u4їF<ڂdjF =\,hYo~Q,wweLVmK2 鷐&K)*嘮'~`R nkddd4[P~Mw4Ƽ0d[i:dg'=+MtBZEj<~Mr^:wo>o>$j`=f&zՠ oEɋA˨#Cm e!ϡ\j+逭$~.uy4٭:aA+UR[CJA+[@k)/^E$~Ƌo#t,^C yF[FM _2nQ."]{v~Fˢ) Z͋$^1/4I=nԃ? ص:kpuQ{J[Kq-ն;WٽTnAR>X\t2.{`TkiosKx-uik:NOh1jnW/i]AMujthuavɵ_H5?LHA68:&94|]ӁTj45*6vAE UܨOw}ɜ?fk,{{O_g=ῼ?/ ^a_-Vǽ!CCC=` npY̒W<!eo6?~%񝭂z̶Ƕ ޳𖝄O|khMĸU Mev>y*{X’sGۃ5J,aA7NDŽFwy0xfM{i q"&\z~(NEl=(cLw=5fdt=cF۝|#ۅE,ᖱ3;SΘ5خFqA?zb#Y#5gPnl$#4 sQ%h*Fùb;bAB7M8n$?{ax-{߉WZ}~RU4wF |SiUm?FOr4& &_SUu_E`/kZ`¹gs=Bb#WeLA6kd L[BѨGBUb/)"%b"ʪVU XRDüb?dm! E$YSđDrIfdnyNY J-dw,AolEl#.HT,PSߛɭ5꺉/yfh(U8-1I|˦7eVo:L4z,L06}wf.6%a ,-c#;gT/xoH\a1^lgWHZ%e?D0F "NSqPjj׊zov+f!d;$6%'PٚL&~RtٌuNwoTKEՕBU#f"@j^&Se ^pr*x:zt?? {`zhyH=㽊nM^waB %EYZDUZ+ ,| tKOxNQF8@Ǿb;͡Dt= fr]%Îæ\j/aOUaM5uYMrķ{LLۏfj۝mF>fov؂MlnS?؄yG ڨ. Wx[^A}ڻ+$Ǻb'ֻgEkXryE*WS8I:9,6 sBo3xoܩUӑ>Km)T}2;yj9cLGlmbaisҘdw=z\ŻJNd]ONЕH]DYdG\c:+1+t?-?"]u:M%T,*\$K'GފJRވdR*JȴZf2;Bi(`$4ao# Nj TT9ڻ`:1N=uީso@*jt젋b݅e)U%nښn)ger'a${^n,[ꪲ.!2NW}tvoMD#D_O|ӝEoJH@ .*'`QPE),^B.(n'<bI%2✎):"vbV_HLˠ*E4P810ng6$@}nڛ.Y-ұ|uF_r]·A.`O sPl'NzS(-A1ڊ[W;bx}Ӕֹxt]f3}wRW-|_=e{YN\eyu>k&JF |u X>kHWYNte s17ӴNݞ"5m˪61LC} Q]5t^vUR_Nwf ,}~=c{NTJ v/ \yPN-d5YƱ;]j&RцxY,w$vV &e g<#NSO<FpM)qKXZOKU3[ɷŧT`gzB<ńtJ,RT XH`* 3l:vb6aGk_\.Svv.m/Maө#~~|< R"Md&Q5uL.PuFџlsѕ\tU\#綨Za#~vV0M{D8@`.'5hJdn&{Q>O}0gd0-Y$Zu.Nn¶k:۩ȵTl, e` !]Q}8>krޜ3)SUY&6tygTʌ&Md)mB,ocWP2 @[0aO&oZw 0{\V5W)qxt/_safdƺ`~'|\2^ZϦg^ڋo>xL(S+"#"WfJDyl"e:)*)ڛ,I!Z&&cPTeeNQ'|~e7_iLHfԬ9I""[ϵmFPҔcdEZ^QtI*.ϫaEY+z :ߑO/\ e LTFOdd3Dn 4[(jDNϿoW &ab'F)b#ŢY-M%ښˢy 7bd"gsؤk`bʭ&erQw5 ΚⒹ'N 9,vm\GlȌLc5fpt_F8qLLe !V4Sf; TueO&h繒;8^E]ϸ%#{cOLy ̔;$!i #<&#uT(8Q.iLJce|f#k"jIIA{?ϝMCqs\'#PF8N/t3}]V/f 5TK'XA &or>6vɷ&?lv_V)CyAAr"A6 ))Bz*٩6 zA 5i64ЊC{ɵEaFS[@M`UT/Л@g (h?lTPj*Q (G4#,NieR!(UF CFPz@=Mh#mi WYmWDCjɈ30* *}eqIi,hJ>wz(I)(ǯecdy-c8&eDZ>l5ԡl"4М՘\ej)M)?l:,XIK`1k'L0Uz¾b}8ٔP>\Kp57Q}7fqb/YZhwvZkve2lٚj6I6#ω2 [cT{^w-ؒڪmG17e7E{Wc~5ngL~>Uo-cjr氮o6'M:Ö9]aЖUuYKMfUmsF؞vUa#;c>8QU9]HPmw5-T[_uT'{-w2wW3kgZݍҙLƭvձ=\쒘x.I*̮n֚niƙi:.媘r.^njn.&.h?l]myӝYa&wOu/tJQ'u$taBe4\qko0_]6M\U7m\2]vݥ7}\<gںo{빛:۪v.h3:pl_2w:HII"T.IqLS.r3"sp3R.{”q]\S0\x6E3]x-y-d54fWˬ^EwĽ^Isܫ`.{5=y5督LDїa&:b<,3`[h{K͟*󀯯x3 oɺl g;˼Nfl}^s̫cr{Z?X۟^Wm< 1'1wy ?1Gf z}1# ׂ5c }w?ŜQG8hʈ=ajͦXoզXaz0Lqܬ.qeœ19 >sGZai&P!`ڈWxvnK&h?l^e]G1M1ӎvMq gXLq,Wjql>ledkGXYBF7\|2[ӕMq^7Aa;!DpЌLg\qfח.8gÖE:z*R>29"SDGe$#cSIj4TB<4@ g?@V6u lBdK-Q(lHdM#+PH^(i<ϓ9H,䓙(LGQej%SPDFƧ,2 啩@eV%sQYb]at m&QCYO%smFgU)9+KRdY#v3)#Ei)LɳQbFqJ0ʬkqm&F\d9&ȑ4SE?iJ{e':*9^#){FQ|L阵e[gfgpB8F14E *}g;]Y&&W2smF$F7v1tQCD هk9F;b3N+(##M ()6&3̟C4NL/y=tGnKrc{b$P~FwQ䘞#}#EX&'2J=[{%Wp}M9.YtgAa_5gT QK&5SW8Ex&BA!Wt>#e 1;gAb{R+֞Ld;!]tHiA&bVVu/FZŸ^0?# i4ܡ|jxCY&ޅqaB;$Hc7CQ΂DvĶxl7g l~j֌Ǵ'<ݧl,S1͂˗^i r7|la #] Lvߏ8Pֻ-woBEJ7P~0l\dS`Z E*ͰHngc[nvq#(gg688f6)vؾZ6h?lX:X&69鱘͊m^,`KuU,c`%kXv󚹌t*v㰧}@~>#lkcD[їA6?fϻv666۠0~m",mScqfd-帿*?a5ۂQv_msϨ0ǧylյG5 [M; en9v/N'p+ٿpu̾0ʠقj3G:c{}n3{-{f|_lZ%\"e\8#|d ڕ;z [=n݅[!\oO1K¥1.{hjMv26:fǨs;6?ͮg6ze7̦~'뮽Ef_Ge/6{(]5*Fs\z8st;XttOwetmWKWs-tEׇ'nN9.YYM>cn>s. wz\zKǺz 9Bqѽ\9Uם]ѵm]g uzۣǹSz1^4#9x#[yz'y\#Uѳ]Q=eӣ]sŋ1ҺUѝe׌cZa]wφ뮌ۍlm#'Iz0#i(WOe9 }\s˫M5uxi5yk 3yL{N1aθޛivNyw &vk>>hN{Gx;axx7{93;6[&h7lѴ7ڛg fc|L0if7ρlmZc1nvly5sfoe=YJ[lMOF0-`"kΚ籅|RܿҌb99 5 >i /ޘh╉#DI) -0kSHE4Xģ"9:FEN@"PN҉DPĤ("YA-W%&hrw #*)Uj1"1#%pqf~e"-gDBF(GoIb:]7SQUٿFR"6[QZ18>llфRԡ UiHEY:'JucQ3)Pfqe'J-{Qfřq(B J|818R2[ /ג`F̢b"]#wяBvюtJ4+9#K4%O&Ǩ"[,=s$̉c3̓\H❘LO+eџNt@tƏ u-ؗtCJ3р4g_ۑ_v?EփwotQJAyJ#TAr/5JF(Wx=蔼N7z._/T {O&='`(viWvdz7V>z6ۼDAa;+X^Nbc.o:\e4+{{(3ۗ2 S[ɬ6ij!M lzdBl[:޶PΆjv 4 hmC:ۮö> U-mmy`5dRC>\.Yl|24f6aY~V5dm@j¯vԷ{v=#n lch2Jg5XED)ؠՖAhS@:_j4 -ΨB6[rښcM([/akpL+By[*s|l9)3f/dfAa!0ÎvUū5n9}Ii@WO0plZq[kxVS vmFƗV} [pu;`]kTXhÖ+`] \f0ݞ)Xr6Wmr':wMr2N-f;];󮆾.r4k}v:쫦Jؾ|:/N⋫c*ụ޹ۨn [mUwDtg1Fx^u3$3̨o_0}PD _ʌv*ˤ#R騾|C'#;uT'{ñv;3]}cy%\j}e7\.}c%O\١M%?7?OzJȏjc"=}Z~8tL3AT]b|BUS=dj<ɭ\e9rWRX"*v>OQuOUGe'N6yj2*YEU YMeA %R2P@YERq^:8B~ <xy}*|A /񹼃.| ɕ^v>Γp\ϗ3װzS &S9ʮyeIl%s`y,;en,ȇ)!? ~8x]FRbFQޅQ,K=/s&(Bdx1'n@t8 ax w10Utc` GH+G'9 "PH !~x+ 胛a#xPY= ,W_B?+?F19uB,3ae]k,Y*t[R:)˛)BɩzǙjƘiZyfLob,31O02* ժ*|=B7 T\SL$E?ŧ^ճޏgë:zWzWP}YY=][YnVG8]azv|2<#~(wut@0ޅqdz;w0*NR**>Jy***ΠBO=SڃIUuXeV'TMuNSW2ujJ(R졶a 5k RTjZUTT7ES=q4O建,$Sy7L.a<CP (T5:jqu#2ڇ tC #nxRCXb?5W؇TT]1j_*¸3cOL0"vŨ8cO/JU*PM/`?^x:v_ϡLOJ!`Ąqͅ,}àٰfq͂?` ظ(9ކf_0?B7 TGE1+La'0X3`]́m R`K5:\X `.CytVUrd px9EW!Ǽ2x,`ͼZ=xuU1tc:sq[ǼS U,bYՌߨ؈x@u3Cĩj=NVp"xǪ68Z Wuqj @\n ]xE5߿R񅚊`|: <Q]h f'x/lcs}P/z bmݞ6G8U/q/~oKpyz|^76|x\1hQo,'CL1bP䐢< 2r,!;)[Q?KثF 9EJ 9?~/ ;+:B ޘoGy?^08j~7YL~$ 6Xfv0kYA~~2p\\4w'&`m OIA 5 teR,X곔dIWo5 L"Q?0rP@kҀS@]JhJYm(W3 Ary@ z.7!(B(2b,!ȅl1[ƺ㲁cT9\_.?z% `! MiƏW#_s%y,i]`Z xZ tUIfH&<34B hA,.lzxUAZXlpWT"{J[Q[d*)G9vcQ3I&MK"MI?o;( 0̉Č?B[q;Fb Q 4,* ܂YR ^c]uߗ-~RC%eΙ9gxNG-\%p}E-&-[80?]s QT}kOonH E"_Y:k7A`vlA#8b-f Vk$.v7[qYmV0G}4JohQF2Ԟqx7`1bw >V:gy&jJu/taI.͓?32NNǞuNkgjʝ)6AxW;{g8xouy%vo+u{䭣LNR|Q}]O9(Z>Hy˞T+kkʯ{cޢ0mdП3lFcKQlՍrh56A6]l*f[R}&uY:uXoO2E-:iHAIv諝$h mZm!R"G[NiBmqK̰M#Jr-!%^5m2ѠOG⌶J[E\p#q"#%Rbܿ#J2zf:S[_vL cL7Q?3YY[~W[FNjyk|̕/+dy}\MҪl(Pr>,U1ǥ3nIar6 }fJ8_y\x{Y$b:_, Ďٹ@,秈ocsQ41C`ŹB;*AQpY7؅2A5OUmPL_} 䣳 Iw#D}04  @ a;,Oap옑{`+|PAu0U, Ca*[QGKq T8Q oD/d$/R TIGh^Pr%#W1#7B E`0r. LvnԸ}AyN}!S/<5Bnj&gQ3,u+ tZc=kxL!˛JF{EbgU$ΣӇב EC$#ӗq%V._ww)8†89Ed)@!‡!!& m2,tʽBx* Xݚ4gy@+Mx(P8o2 zsVZzH:?V8-[\wqXj0;ܭ[f.@U5xQ_}ˊOS8;F t9N}<;LqN'X]O{~7>M_UЌC\sϿNOvв:u0ZOPf=.枣#eX;YQ x i~Ԣ:V&f64-mGXcڰd")Lw9$;NY٣, L,YFРϢ7)gKW0j Kt3C=WI HHػQ5>ZOqQjІd MiOƑh9a?kT1~Qi_7۝- aS'p^ٕg4y>DE6"[fsE7 ]!}hP1%E |?_?7!/A`#3}H`ߦn 2߀O:G|2_Y8r m9,m(tZ1=xaݺloJ[5R,_52{\pƽwׂl20,4u@óFWjC `[0[Z K'0JZsR x +`EP.{;ƾ5W^Ma;}lnV^h"Ck>mDW݋\!F{"; *L) V'<{Wt=WՁVa{pB9i J*&CU [\ mST52 ^8M-vÓS/L 1qzƄTzyLº=`-^9 æLy~MJrؘnhƤyOes.LPAP-$ܢԠ Un,›A5,bvoY"VTĚ'wخ#d+Hro Kԟ*!~VPqA<v?8A;Tj_UW4a :RkU35h]X`558ns\18rQ+5[qIc@)58*XVe8zt~ǟ.ic{~O(Vt9 /A~:LBO>> | =yQy{ڏpU4DGW&a8yˇo9LU[I_LU[ s'TG)O% O`lv)9ix08DPQ>HPT,)+쿛( vvJ4Y+P k?ΏRidl)ky3̼o-@zC+}Ԗ ݄G47BE@y/Z3X@RT#Q'/pD8lH[P݋|:j Ǫ2\\ǽjtE؅!Sz`eWO΀h%D=(@I8ˇdC6JӘeez<1DFI 0pz8= ;=2NFqfiDѽGS} 0ҿEzuyfK:Ouh\3}]he؇;l 6?+πR'`;=V4e|؜9|T~HrOuD/\krX9y(pY|;[߳u[ zM|=l?tݓN׽=cU( {o}F2,Kҟ/Y,K?c韱/ -},(K_^<<67g,}ZYE4s;阒ц%S,;[Jٶ3H/ GC#2ZFt雺d\ kT1|̛U2="a=oNzh\9-+cBn5 < >͢4%ͧjZ ǀ _|:jT;7S ߅,6&-mx ؙntݷBACVKo;J-rRg?Yy3AvВђS-mPee~.Mw CvK~#J~ֻDAeܕBYn]ֿ!;!ё.&l<uFCT`fzݛWm YnvomK[ f?O϶{>cWslhh;b_ҳ9f>z5DtǍT:]wTZ~PGF,?\#z&;b}[. u/n}AxGT,cmyb7H7Bc%Fuܼ. =}X'Җg}p] ]NO{$%!Ev6lj,=1~5L1pGZwdyutn8=ӎ a.c$?RJ*pz#ϝo4Cy3gp= In8=n a}QQpܼO7pSK~OҺ.{S׊rU族h_|eqkN52g <`ԺHZ6 DHAG!!&,}>OG U*$$-|g< ~/ ?_s|8;gXcQGaU uո>g>]T{u^YLsBzo̾wSօ &a0fD|sBaSօ*3?חv[@;ksJe/+o=)߼Yw~;z/1]{&vӆ~Ϙ"jl+m/_:>Sٓ^P^?o5zzΝyg8G|{- F ꊬj;̀рgKw˻ ˕NVP+-Vc[Zhh=ɾ7Ie/+c>'{Dm:y&rɚ#.?cdxwk`8{0gsg #8KE[)ɇv}]˷@Ł"p"oN4&ey*b2ayqX/rJu/jUsc5= 6B&B@'CNw֥#vD]p? }0ÚuiT@[wDy^u0FkkC fX͗<Uqd4N(   7Zhttp://www.cs.berkeley.edu/~ravenben/tapestryZhttp://www.cs.berkeley.edu/~ravenben/tapestry|{0http://lcs.mit.edu/chord0http://lcs.mit.edu/chord}Thttp://research.microsoft.com/~antr/pastryThttp://research.microsoft.com/~antr/pastryJ Chart Excel.Chart.80*Microsoft Excel Chart/ 0DArial San,(0(z[ 0 DGaramondn,(0(z[ 0  DTimes New Roman(0(z[ 0 0DWingdingsRoman(0(z[ 0 @DSymbolgsRoman(0(z[ 0 PDLucida Sans Unicode0(z[ 0 "@0.  @n?" dd@  @@``    @Q)!****21// ..5       .51&7'7,+*#  .E 245 8;;!@ABCDEFGHIJ2$ҮӽwUp 2$,ȫ;GI  N8$$2$MiƏW#_s M?$$2$ǢPS}+XFE K"$]T/Dz KU AA1" pf̙@8 w ʚ;=1ʚ;g4?d?d@z[ 0ppp@  <4ddddl< 0<4BdBdl< 080___PPT10 ?p% November 7, 2003 4ravenben@eecs.berkeley.eduO  =7@Exploiting Route Redundancy via Structured Peer to Peer OverlaysAA.Ben Y. Zhao, Ling Huang, Jeremy Stribling, Anthony D. Joseph, and John D. Kubiatowicz University of California, Berkeley ICNP 2003*PV -, ! / &Challenges Facing Network Applications''&6Network connectivity is not reliable Disconnections frequent in the wide-area Internet IP-level repair is slow Wide-area: BGP 3 mins Local-area: IS-IS 5 seconds Next generation network applications Mostly wide-area Streaming media, VoIP, B2B transactions Low tolerance of delay, jitter and faults Our work: transparent resilient routing infrastructure that adapts to faults in not seconds, but milliseconds%K6%%K %  ,fD  Talk OverviewkMotivation Why structured routing Structured Peer to Peer overlays Mechanisms and policy Evaluation Summaryl a$>Routing in  Mesh-like Networks|Previous work has shown reasons for long convergence [Labovitz00, Labovitz01] MinRouteAdver timer Necessary to aggregate updates from all neighbors Commonly set to 30 seconds Contributes to lower bound of BGP convergence time Internet becoming more mesh-like [Kaat99,labovitz99] Worsens BGP convergence behavior Question Can convergence be faster in context of structured routing?b235! <5 23!!    <  N "% Resilient Overlay Networks (MIT)`Fully connected mesh Allows each node full knowledge of network Fast, independent calculation of routes Nodes can construct any path, maximum flexibility Cost of flexibility Protocol needs to choose the  right route/nodes Per node O(n) state Monitors n - 1 paths O(n2) total path monitoring is expensive@ZZZZEZZ)Z@Z: $F9+Leveraging Structured Peer-to-Peer Overlays,,&Key based routing (IPTPS 03) Large sparse ID space N (160 bits: 0  2160) Nodes in overlay network have nodeIDs N Given some key k N, overlay deterministically maps k to its root node (live node in the network) route message to root (k)$(!3 hH"Proximity Neighbor SelectionPNS = network aware overlay construction Within routing constraints, choose neighbors closest in network distance (latency) Generally reduces # of IP hops Important for routing Reduce latency Reduce susceptibility to faults Less IP links = smaller chance of link/router failure Reduce overall network bandwidth utilization We use Tapestry to demonstrate our design P2P protocol with PNS overlay construction Topology-unaware P2P protocols will likely perform worse)ZrZZ/Z6Z-Z*ZdZ)r/6-  *  d  L$System ArchitectureqLocate nearby overlay proxy Establish overlay path to destination host Overlay traffic routes traffic resilientlyrZr/Traffic Tunneling&Tradeoffs of Tunneling via P2PLLess neighbor paths to monitor per node: O(log(n)) Large reduction in probing bandwidth: O(n) O(log(n)) Increase probing frequency Faster fault detection with low bandwidth consumption Actively maintain path redundancy Manageable for  small # of paths Redirect traffic immediately when a failure is detected Eliminate on-the-fly calculation of new routes Restore redundancy when a path fails End result Fast fault detection + precomputed paths = increased responsiveness to faults Cons Overlay imposes routing stretch (more IP hops), generally < 23ZZ"ZZ ZNZZ>Z) &Q" N  >P))F o(  Some Details`Efficient fault detection Use soft-state to periodically probe log(n) neighbor paths  Small number of routes reduced bandwidth Exponentially weighted moving average in link quality estimation Avoid route flapping due to short term loss artifacts Loss rate Ln = (1 - a) Ln-1 + a p p = instantaneous loss rate, a = hysteresis factor Maintaining backup paths Each hop has flexible routing constraint Create and store backup routes at node insertion Restore redundancy via  intelligent gossip after failures Simple policies to choose among redundant pathstZZZZ)Z1ZkZ%)U@    )1k>?< >%First Reachable Link Selection (FRLS)Use estimated loss results to choose shortest  usable path Sort next hop paths by latency Use shortest path with minimal quality > T Correlated failures Reduce with intelligent topology construction Key is to leverage redundancy available*VV0 Evaluation Metrics for evaluation How much routing resiliency can we exploit? How fast can we adapt to faults? What is the overhead of routing around a failure? Proportional increase in end to end latency Proportional increase in end to end bandwidth used Experimental platforms Event-based simulations on transit stub topologies Data collected over different 5000-node topologies PlanetLab measurements Microbenchmarks on responsiveness Bandwidth measurements from 200+ node overlays Multiple virtual nodes run per physical machineZZ_ZZ3Z3ZZZM2_  33,r rK#!Exploiting Route Redundancy (Sim)}Simulation of Tapestry, 2 backup paths per routing entry Transit-stub topology shown, results from TIER and AS graphs similar~~R)$Responsiveness to Faults (PlanetLab) O&"Link Probing Bandwidth (Planetlab) Q( Related WorkRedirection overlays Detour (IEEE Micro 99) Resilient Overlay Networks (SOSP 01) Internet Indirection Infrastructure (SIGCOMM 02) Secure Overlay Services (SIGCOMM 02) Topology estimation techniques Adaptive probing (IPTPS 03) Peer-based shared estimation (Zhuang 03) Internet tomography (Chen 03) Routing underlay (SIGCOMM 03) Structured peer-to-peer overlays Tapestry, Pastry, Chord, CAN, Kademlia, Skipnet, Viceroy, Symphony, Koorde, Bamboo, X-Ring& PPPP!P\P!\  P3 ConclusionBenefits of structure outweigh costs Structured routing lowers path maintenance costs Allows  caching of backup paths for quick failover Can no longer construct arbitrary paths Structured routing with low redundancy gets very close to ideal in connectivity Incur low routing stretch Fast enough for highly interactive applications 300ms beacon period response time < 700ms On overlay networks of 300 nodes, b/w cost is 7KB/s Future work Deploying a public routing and proxy service on PlanetLab Examine impact of Network aware topology construction Loss sensitive probing techniques"%P1P4P(PjP0P`PP PLPFP%14(j  0J LF   Y5Questions& Related websites: Tapestry http://www.cs.berkeley.edu/~ravenben/tapestry Pastry http://research.microsoft.com/~antr/pastry Chord http://lcs.mit.edu/chord Acknowledgements Thanks to Dennis Geels and Sean Rhea for their work on the BMark benchmark suiteZ Z.ZZ+ZZZZQZoQ\-*#%7U 0H}U 0Pz{U 0/;STUVWXYZ [ P  ` 3333ff3` 3333f33ff3` "3333̙ff3` Kf3̙` &e̙3g3f` f333̙po7` ___f3̙;/f9` ff3Lm` ff3LmNLm>?" dd@*?nAd@q<nAqFLK#M n?" dd@   @@``PR    M`2p>>  (      HD? ?" `  X Click to edit Master title style!!  @   Hܧ? ?"0 `  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S     6 #" `] `}  \*      6г #" ``0`   V*       C @ABCDE FjJ@3"0`B   s *DjJ"0 `0   N`1#"   #  C ICNP 2003 0  H   0޽h ? ___f3̙;/f9___PPT10i.  +D=' = @B + Edge   $(  $ $ H? ?"@  X Click to edit Master title style!!   $ Hp? ?"   [#Click to edit Master subtitle style$$   $ 6  #" `] `}  \*    $ 6t #" `]}   V*     $ 6D #" `] `}  V*     $ C @ABCDE F8c@3"@B $ s *DjJ"  ,$ 0H $ 0޽h ? ___f3̙;/f9___PPT10i.  +ityD=' = @B + 0 P(    Nh\dy˼y˼ .  d n*  a00aa  Nmdy˼y˼ 2 . d p*  a00aad  c $ ?  d4  Ngdy˼y˼ 9 3 d RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S   T0|dy˼y˼ q  d n*  a00aa   T|dy˼y˼ q2  d p*  a00aaH  0ηo~ ? 3380___PPT10.>YG `((    Ndy˼y˼ .  d \* a00aa  Ndy˼y˼ 2 . d ^* a00aa  Tdy˼y˼ q  d \* a00aa  THey˼y˼ q2  d ^* a00aaH  0ηo~ ? 3380___PPT10.>"hG !K0 p$(  r  S $`  r  S Р$   H  0޽h ? ___f3̙;/f9___PPT10i.ɖ:?+D=' = @B + K0 0(  x  c $ '  `  ' x  c $ ' 0 ` ' H  0޽h ? ___f3̙;/f9___PPT10i.̖ ~3+D=' = @B + p^K0 $(  r  S '  `  ' r  S  0 ` ' H  0޽h ? ___f3̙;/f9___PPT10i.rX+D=' = @B + K0 0(  x  c $  `   x  c $X 0 `  H  0޽h ? ___f3̙;/f9___PPT10i.̖0z8+D=' = @B +% K0 NF*-(  x  c $@"'  `  ' x  c $#' 0   ' 2  H$'1" p 0 9S02  H('1"   @ 9D0.l @ $@p,$D  0   <1S" ?`     <1S" ?0 @`    <1S" ?   <1S" ?@@p   <1S" ?  lB  <D1 `lB  <D1  lB  <D1` @ lB  <D10 lB  <D1plB  <D1@@l  @  #p @@,$D 0  <1S" ?@`  <1S" ?  @  <1S" ?   <1S" ? 0   <1S" ?P  fB  6D1p0 P fB  6D1 fB  6D1PfB  6D1@ fB  6D1p fB  6D1@@fB  6D1p fB   6D1  fB ! 6D1` fB "B 6D1Pl   +@ ,$D 0fB % 6D>P  fB &B 6D>B )@ <D> ,$D  0 l @ -,$D  00@   * lB ' <D> lB ( <D>`lB , <D> @H  0޽h ? ___f3̙;/f9@ TIMING$|16.9|3.8|6.7|10.8___PPT10y.̖P8+'dY(DM' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$%(D' =-s6Bwipe(down)*<3<*$D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*+%(D' =-o6Bdissolve*<3<*+D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*#%(D' =-o6Bdissolve*<3<*#Dz' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*-%(D' =-s6Bwipe(down)*<3<*-D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*)%(D' =-o6Bwipe(up)*<3<*)+ K0 `6XQ(  X~ X s *`B'    ' ~ X s *4C' 0   ' R2 X s *  R X s *+AR  X s *0`R X s * 0 R X s *5 5 R X s *  R X s *  R X s *  R X s * @zR X s *py  X <hK'/ 900 "X C BCDEF1\8(`P@  "`P8@ ,$D  0 #X S BCDEF10@p@  "` @ ,$D 0 $X S BCDEF1d|8@  "`  ,$D  0 (X <\P' . ?root(k)0dB )X <D1 p *X <4T' D  9k0dB +X <D1  4X  TBCDEpF0AԔ1_$)*37??AKQ]fl,s@]hz@         c"$`   R X s *0 `  5X NX'1"  L >source0\ 6X Bd' ?"t  ZDistributed Hashtables (DHT) is interface on KBR Key is leveraging underlying routing mesh(1*1* E @`H X 0޽h ? ___f3̙;/f9 & TIMING |53.1m ___PPT10M .d=4+ҺD! ' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*"X%(D' =-o6Bwipe(up)*<3<*"XD' =%(D9' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*#X%(D' =-u6Bwipe(right)*<3<*#XD' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*$X%(D' =-s6Bwipe(down)*<3<*$X+  K0 @$(  r  S t'  `  ' r  S t' 0 ` ' H  0޽h ? ___f3̙;/f9___PPT10i.W5>+D=' = @B +P3 K0 H&@&6:%(  l  <  : < ,$D 0N P0     < B   3 n<'E`FNQ&UVW}))? XX6381-D81^ DS &{'LO^ D+ YL^0L8]T+ YL7Gn2H+IJ7GI:9]T:I:Q= qR&QJ 7JJ >:*;9>:+$.+] x!+] 6381$ 3-D^ D %D^0L8]TH+ YL^0L8]T7G@8Cn2H+IJI:B,= qR&N7#Q7JK J 7J>:8*;9+ +$ x!+ ] x!+$(,`C0*0*ITNT0*0* BCCloudS"?P0  .02   H'1S" ?P `  202   H'1S" ?0 ;v02  HБ'1S" ?P 0  ;v02  H'1S" ?p P  202  H'1S" ?@  ;v02  H'1S" ? `P  ;v02  H<'1S" ?@@   ;v02  H'1S" ? @  ;v02  Hx'1S" ? `@ ;v02  H'1S" ?PP   ;v02  H'1S" ?  ;v02  H'1S" ?  ;v02  H'1S" ?  ;v02  H@'1S" ? P  ;v02  HX'1S" ? @  ;v0fB  6D100 fB  6D10 P fB  6D1  fB B 6D1 fB  6D1P fB   6D1P  fB ! 6D1@PfB " 6D1fB #B 6D1 P fB $ 6D1  fB % 6D1@PP fB & 6D1@ fB ' 6D1P  fB ( 6D1 P @ fB ) 6D1 P fB * 6D1p fB + 6D10 p fB , 6D10 @p fB - 6D1 p fB . 6D1`fB / 6D1 fB 0B 6D1  fB 1B 6D1 fB 2 6D10 p fB 3 6D1P p  8 N'1" g  K O V E R L A Y"0r  S T'  `  ' r  S ' p `0 ' B   b'E`FNQ&UVW}))? XX6381-D81^ DS &{'LO^ D+ YL^0L8]T+ YL7Gn2H+IJ7GI:9]T:I:Q= qR&QJ 7JJ >:*;9>:+$.+] x!+] 6381$ 3-D^ D %D^0L8]TH+ YL^0L8]T7G@8Cn2H+IJI:B,= qR&N7#Q7JK J 7J>:8*;9+ +$ x!+ ] x!+$(,`C0*0*ITNT0*0* BCCloud"@@  .0~  HA ?j0230312",~ @ HA ?j0094889"z 4  BCDEF >Pp   @c"$` ,$D  02 6 Bo" ` ,$D 02 7 Bo" @,$@ 0 9 ND'1"  B  >Internet 0 H  0޽h ? ___f3̙;/f9 6 TIMING|7.2|7.3|27.4R ___PPT102 .AO+\3 D ' = @B D ' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*:%(D' =-o6Bdissolve*<3<*:D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*7%(D' =-o6Bdissolve*<3<*7D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*6%(D' =-o6Bdissolve*<3<*6D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*4%(D' =-s6Bwipe(left)*<3<*4+D  .K0 !0r(  2 / <cU1" @,$@ 0 9B0r  S eU  `  U B   bhUE`FNQ&UVW}))? XX6381-D81^ DS &{'LO^ D+ YL^0L8]T+ YL7Gn2H+IJ7GI:9]T:I:Q= qR&QJ 7JJ >:*;9>:+$.+] x!+] 6381$ 3-D^ D %D^0L8]TH+ YL^0L8]T7G@8Cn2H+IJI:B,= qR&N7#Q7JK J 7J>:8*;9+ +$ x!+ ] x!+$(,`C0*0*ITNT0*0* BCCloud"  .0   6kU` C Legacy Node A0   6^UP C Legacy Node B0B  6pU 0 ;Proxy0B  6`U` ;Proxy0l T `T,$D  0ZB  s *D`  <xUT @register 0 l 0@ 0P,$D  0ZB B s *D@@  <|U0pW @register 0   0U   YStructured Peer to Peer Overlay 0 z P  ! p ,$@  04   BCDEFAA1H@x@  " PP   N`U1" 9   (put (hash(B), P (B))0 2  <U1" @,$D 0 B P (B)0l p`  %p`0 ,$D   0( #  BCDEFAA1@ @H @  " `  $ H̍U1" p \  g get (hash(B))0|l @@@  (p@@ ,$D   0( &  BC`DEFAA1`hx@  " @8@  ' HU1" | @  B P (B)0 , NU1" g V KA, B are IP addresses0 *  BP CDE@F AԔ0  H0H@08  x` p h P @     c"$  p @ ,$D 0z    "  ,$D  0(   B0CDEF1?P(hPhT0@  "`  .  NU1S" ?   (put (hash(A), P (A))0   - NU1" Hh,$D 0 LP (A) = A 0   . NxU1"  Q,$D 0 LP (B) = B 0  0 B8U ?"P `` .Store mapping from end host IP to its proxy s overlay ID Similar to approach in Internet Indirection Infrastructure (I3)"yZP)H  0޽h ? ___f3̙;/f9E&: TIMING|15.1|26.6|18.7%___PPT10%. D+9Z'D_$' = @B D$' = @BA?%,( < +O%,( < +D&' =%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bwipe(up)*<3<*D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*.%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*!%(D' =-o6Bwipe(up)*<3<*!D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bwipe(up)*<3<*D' =%(D' =A@BBBB0B%(D' =1:Bvisible*o3>+B#style.visibility<*-%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*"%(D' =-o6Bwipe(up)*<3<*"D. ' =%(D' =%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*/%(D' =-o6Bdissolve*<3<*/D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*!%(D' =4@BBBB%(D' =1:Bhidden*o3>+B#style.visibility<*"%(D' =%(D3' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%%(D' =-o6Bwipe(up)*<3<*%D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(%(D' =-s6Bwipe(down)*<3<*(D ' =%(D/' =%(D' =A@BBBB0B%(D' =1:Bhidden*o3>+B#style.visibility<*/%(D@' =A@BB BB0B%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<**%(D' =-o6Bdissolve*<3<**D' =%(Ds' =A@BBBB0B%()?)?D' =.7 BBBBBM 0.0 0.0 L 0.01667 0.13308 L 0.125 0.33271 L 0.35 0.3438 L 0.4 0.12199 L 0.45 -0.03328 *3>*B ppt_xB ppt_y=!0BBAAAAAA<*+P+0+/U ++0+/U ++0+U ++0+U ++0+-U ++0+.U + 0=K0 0(  x  c $U  `  U x  c $lU   U H  0޽h ? ___f3̙;/f9___PPT10i.̖p9+D=' = @B + {K0 $(  r  S U  `  U r  S U 0 ` U H  0޽h ? ___f3̙;/f9___PPT10i.P~+D=' = @B +! 3K0 )lZ(  lr l S U  `  U r l S U 0   U 2 l 6(U `  <204602  l 6xU    <111102 l 6U   <228102 l 6LU p  <253002 l 6pU  @ <229902 l 6U @ <227402 l 6% P@ <228602 l 6D%`` <22250dB l <DjJ 0 ^B l 6DjJ  dB l <DjJ  dB l <DjJ@p` dB l <DjJ@ ^B l 6DjJ@ p ^B l 6DjJP dB  l <DjJ@ ^B !l 6DjJ dB "l <DjJ@@ dB #l <DjJP  dB $l <DjJ@ L %l S B0CpDE(FԔ p0H (,0 @   c"$`   ,$D  0L &l S BCDE(FԔ T(Xh`h4 @   c"$` @ ,$D  0B 'l s *D> \0 ,$D 0" (l 3 BXCDE(FԔ P`Xp  @   "`H ,$D  0B )l s *D>  ,$D 0H l 0޽h ? ___f3̙;/f9ID TIMING(|49.4|2.8|2.8|1.9|1.___PPT10.UlA+D' = @B Dd' = @BA?%,( < +O%,( < +D' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*%l%(D' =-s6Bwipe(down)*<3<*%lD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*'l%(D' =-o6Bdissolve*<3<*'lD' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*&l%(D' =-s6Bwipe(down)*<3<*&lD' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*)l%(D' =-o6Bdissolve*<3<*)lD' =%(D' =%(D7' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*(l%(D' =-s6Bwipe(down)*<3<*(l+ uK0 $(  r  S x%  `  % r  S % 0 ` U H  0޽h ? ___f3̙;/f9___PPT10i.`+D=' = @B + K0 P 4(  r  S i  `   r   S j P 0   0  A ?AA1 ? "  z   H  0޽h ? ___f3̙;/f9___PPT10i.8G+D=' = @B +(   K0 G? (  r  S X.%  `  % !  B/% ?"P `0 qResponse time increases linearly with probe period Minimum link quality threshold T = 70%, 20 runs per data pointrr   A1 ? " . %l 0 >  0 > ,$D 0fB B 6D>@* p* fB  6D>0 p   N4%1" W 0 >  ;3000  N8%1" T  ;6600H  0޽h ? ___f3̙;/f9q$ TIMING|33.=___PPT10..+HKD' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(D3' =4@BB BB%(D' =1:Bvisible*o3>+B#style.visibility<*%(D' =-o6Bdissolve*<3<*+@ K0 ?7 (  r  S ?%  `  %    A1 ? " p  %   BA% ?"P `0 oMedium sized routing overlays incur low probing bandwidth Bandwidth increases logarithmically with overlay sizeppH  0޽h ? ___f3̙;/f9___PPT10i.ף;<+D=' = @B +  K0 $(  r  S H%  `  % r  S dI% 0 ` % H  0޽h ? ___f3̙;/f9___PPT10i.9+D=' = @B + pK0  $(   r   S @X%  `  % r   S Y% 0 ` % H   0޽h ? ___f3̙;/f9___PPT10i.J+D=' = @B + AK0 ($(  (r ( S 8i%  `  % r ( S i% 0 ` % H ( 0޽h ? ___f3̙;/f9___PPT10i.'+D=' = @B +X 0 p\h(  \d \ c $   d \ s * d9 3  d RThis is how routing works in a DHT, But we re not using the storage side of it, which is what the DHT does, (refer back to apporx search cost){H \ 0ηo~ ? 3380___PPT10.{/IXo 0   (   X   C    d   S d9 3  d SDistinquish between wide-area and local area, but new net apps are mostly wide-area IH   0ηo~ ? 3380___PPT10.ΤP 0 0$(  $X $ C    d $ S Хd9 3  d ~Do not say n squared, be more high level, can take a long time Unclear what is structured and what is unstructured in internetH $ 0ηo~ ? 3380___PPT10.ΤpfJ 0 @(Z(  (X ( C    d ( S d9 3  d \HSay MIT s resilient overlay networksH ( 0ηo~ ? 3380___PPT10.Ϥ < 0 P,L(  ,X , C    d , S td9 3  d N:Not a unique engineering approach, similar approach at i3 H , 0ηo~ ? 3380___PPT10.Ϥ031 0 `0A(  0X 0 C    d 0 S d9 3  d C/Mention the cost is increased IP hops / latencyH 0 0ηo~ ? 3380___PPT10.Ф* 0 JBp4(  4X 4 C    dB 4 S d9 3  d I haven t drawn all the possible paths in the example This is not perfect because of possible correlated failures, but can leverage existing work on failure independent overlay construction If there s just 1 link, nobody can winH 4 0ηo~ ? 3380___PPT10.Фf=P# 0  8(  8X 8 C    d 8 S 8d9 3  d eSimulation constructs shortest paths to emulate IP routes Now break links, then look at reachability X H 8 0ηo~ ? 3380___PPT10.Ф6H) 0 <X(  <X < C    d < S d9 3  d ZFEnlarge fonts, Highlight 660 and 300 and lines 20 runs for each pointH < 0ηo~ ? 3380___PPT10.Ѥ aP( 0 @`(  @X @ C    d @ S d9 3  d bI3 is more general, targeting generic redirection We have a very simple link quality estimation mechanism We designed these mechanisms with these overlays in mind, applicable to nearly all of these in mind - All have ability to choose from multiple routes, all have log(n) neighbors,  H @ 0ηo~ ? 3380___PPT10.ҤPz x] `E~=3HP c WH!Ь!C"!IXe *^zz .VtXD]I'$ TUUuzֻ!(  Wye)V@+A;^UU%W2áp}pW5Nͩ/rL`>o*) Xz)̄zMSdG:EB[;ibƠ4>_Wq0˟ٌ}:B>cBr(tQ-ci:I/s#"Nk,v/=Fj/؉c]1c_c>)BTaqwK1^10^q$Q鑉D~gZ/9&< & J''?tFvi9[~Z(Vh90:Sb:/1z'k]9;jYp6~\ErtD<4}sSI>={t85)=+),ș]S< r (²eye̒ ҧX!6tfٌ2.E 45C8Qm:jL׆߮}E:{tNi~$>f>XHDuL+_rFvq4je/ׁb zOp񵓢EWU\܃ S"scӵV$j';P*E q(Mq|9jExԬs6z(0`G!6"e{{'Ņj#9/Kgx0Rȴ6 z[9}yUQɲB̅L+ 넔4kűQ;Xs4GJM/7~?{vYKЈ5ҥ3yipL_V&`qPt`P ހ6ek8BAٶ˟~Mj%(n."OX,+];_$fP~~%?5A(n A9I;ZF72uӯ+S0(JaP>)OocUN!Pv[nAY#֘zHMţr㣇mbJbbsT#P7a,gP< Jw>>àlV[KЈUaP>#N:`er &+@Šx'_~@N!PV NYT2(KlWeP&iB@9x| W>*dY!F?ZWaP -#{&(4+A2(7l߷ˠ<#)[pZ*,4b\S1Zmi#eTӖVxp*v 5ĊH̾2dtwN wޭzjU**6pE| 1*giFz7bC&݈jn1NƕU!u扭+p^T% vbWulKUb7PDu-8lƹe3% VtX9T|K(StyOޠ՟~f<}֧5{2:ĵ־}&˛ɝc@0̼ܫЂ5{ 4.+(7G]OD%`IOLEI*($Ctc,EYAkd)TW lAL{W]'A:SLc۸-e{Ux]V/~ay]Wq>O_[6Mbp.9]>=_R 1_2gGG.w٬Bf^vΌף@FiqIzeppb*{ 7ЧH)o}+AV y̕Y!o4BAqǸ MI\^\vj#1r;q~u BA%dd1O_'dS Aɗk0c2"%WSأ K-D yp8NT WoJW^j0煭e{Xsi1>;qGK&|׺/4W>W+_HZlߌ)jH[|cM}tS`l>TGt5a-?/b=Fc|>^죭_+NT孝uMB چ^|>Me@|]scV]V*TC{v!+Y1L=̶*ӊhga p=IAw•Ƿ~܏i3y1L> sUVfGUJ[ IAF+O*U6Te.ٸyMz^1iָ|P Q?ŀ]<` fk<(~ tA4NԋVL'OM'.S׿f;kQ7R6zH>m&f)JE[StDQ-<D{+ }e(A%'E 8瑇)QP ˒KQ","O)z;%sx3E,R<|"YLJV0ڇR>bk۴ƂiW-hkk^m-Y~ۛV%M8hA{{;lkAx{]-h0+{,hWNۂ<3і'v&LD[`h#myc-O{;]6> Y6.蔦ȝhkZcR)z^ďx> ݿyހg"6> 5؎H$rЊ+9k|@QrBet»j"͍Rkȯ\ar &RA %WB͐x#_W'?̆lURS߭W?t]-{"ܯџX,+'7-r*q/0A(EePEePa09 P`QSʫO}|+oi OFjjAL_ZquB@²9*YV(= }2v1(K?vMPDi&A9XJЈU1(r&09I' }3?%!eU)szOyr/v:HMMSQ␠89ZJЈU`Pkar &)@ lL᥽?.raO c1ɠ ?N4uN AI:b^B@%mcsT#P'k#l (@qJP \XXJЈUdPZLK3D.+}}6 PR&Lzq7bbPFɛ>5u. Awtcbĕ#>/bJbՏ0pEF$(.E,%h*@q1(rqear &%"lö?lö?l=Oߧ KKD6ݠ(d~mT+ wm>^m>n)kwb-ITi?38u;;򿪾!]QD.2?ZOzu9! UAL{*KTއ 0Q"MUhRz%fnl]?JGHi@v$Ou(lHˡgprePGN3QB9rAH~0 *  J/%GSGP OlX99la+,ҟB؎9톻a/Ew?|>[yZ( Vy*+`,ЕUs M>ч~QS,lS:݌{J߉8X$` PiD" X$#>E_?~S6cK@ÇqA `tQ#)C}8{w"8}+" W)BLYlc3%﹍'gW á%Ѣd7sѡcנG:8zBU;78"C8*J."=JpQn="=n]ſHߡ%!8 w!c%Z){=VXW[e4kz<"=Yw e6g3*pk}.ǹ,#R3(7fT]:XhQ\VZnF]ml(8`th4fcFsp5r*fcth4JR;,5m)m,Q<y2CQ?.5z]v}C@.5:ˣFJF6v^j4׭c_h4KV(sWկtckX7ֺo7;sr; =p> *;=BN&&$7Hz3AOޠ b{K zd7~A@e ^SiR}οz[ l*('1!Dg8RbK$UXcR;$Hߐu#uS}wCnʵJP䠧7FYD_/E3i3 حˇ*N90H&vO}K!e`_=qwV^sv&zÿJv_HC߱.(-ߥ,kfF$ KG"R19;?)USaTXGXɅCG @{=1[HSaTXXV^Րv}d#]XX+3v)S!jtzX5:=?%oB?qMs;ƅa(ƒK@wh͓9NFU6v^j4׭eh/th4gcF(sWկtckX7?7js# ȿ7S??QD) cq#V:s?ӠQ?,߈%{+l;`r-3~23 lw7V nv9wB!l7ĚVW; sy7<.C;ۊSi_4yQ{zgOwV=<8DsHbJ0d\OAkQo`z7}U`A? [Oh+'0 px  ( 4 @ LX`AExploiting Route Redundancy via Structured Peer to Peer Overlayst Ben Y. ZhaoEdge. Z Ben Y. Zhao97 Microsoft PowerPointnda@P%>@@ɖ@49Grg  1:  -- @ !--'̙-- % J --'̙--%bAb--'@Garamond-. f372  Exploiting Route Redundancy via T;AA%A9 QA?%5 P5@?A@4A55 <4 ."System-@Garamond-. f372 f Structured Peer to Peer Overlays=%+?5%?+5@ H55+ %A G55+ d<5+45/.-@Arial-. 72  Ben Y. Zhao, Ling Huang, Jeremy -%%,)%%%%%%0%%%%"%$9!.-@Arial-. 2  Stribling-%%%.-@Arial-.  2 , .-@Arial-. 62 Anthony D. Joseph, and John D. -%%%%!0"$"%%%%%%"%%$0.-@Arial-. 2  Kubiatowicz,%%%%/"!.-@Arial-. :2 X"University of California, Berkeley0%!%"!%0%%%%-%"%%!.-@Arial-. 2  ICNP 2003c00-%%%%.-՜.+,D՜.+,    On-screen Show Replicus.comw A Arial GaramondTimes New Roman WingdingsSymbolLucida Sans UnicodeEdgeMicrosoft Excel ChartAExploiting Route Redundancy via Structured Peer to Peer Overlays'Challenges Facing Network ApplicationsTalk Overview Routing in Mesh-like Networks!Resilient Overlay Networks (MIT),Leveraging Structured Peer-to-Peer OverlaysProximity Neighbor SelectionSystem ArchitectureTraffic TunnelingTradeoffs of Tunneling via P2P Some Details&First Reachable Link Selection (FRLS) Evaluation"Exploiting Route Redundancy (Sim)%Responsiveness to Faults (PlanetLab)#Link Probing Bandwidth (Planetlab) Related Work Conclusion Questions  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles(PX _PID_HLINKSVersionA.http://www.cs.berkeley.edu/~ravenben/tapestryhttp://lcs.mit.edu/chord+http://research.microsoft.com/~antr/pastry#_㕮 eBen Y. ZhaoBen Y. Zhao  !"#$%&'()*+,-./023456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~     %Root EntrydO)PicturesHaCurrent UserSummaryInformation( PowerPoint Document(1DocumentSummaryInformation8