ࡱ> o'( N/ 0|DTimes New Roman(0(z[ 0 DArialNew Roman(0(z[ 0  DWingdingsRoman(0(z[ 0 0DTahomagsRoman(0(z[ 0 "@DSymbolgsRoman(0(z[ 0  C0.  @n?" dd@  @@`` t0  21 // ,,    IJLPR!UWX6^:bhf 0AA0 @8*#+$ R ʚ;no8ʚ;g4DdDd@z[ 0ppp@ <4!d!dl 0v<4ddddl 0v<4BdBdl 0v80___PPT10 ?%"February 20, 2003 IPTPS 2003 ravenben@eecs.berkeley.eduO  =:*Towards A Common API for Structured Peer-to-Peer Overlays;;.Frank Dabek, Ben Y. Zhao, Peter Druschel, John Kubiatowicz, Ion Stoica MIT, U. C. Berkeley, and Rice * Conducted under the IRIS project (NSF)XP  / )>J7+State of the Art|Lots and lots of peer to peer applications Decentralized file systems, archival backup Group communication / coordination Routing layers for anonymity, attack resilience Scalable content distribution Built on scalable, self-organizing overlays E.g. CAN, Chord, Pastry, Tapestry, Kademlia, etc& Semantic differences Store/get data, locate objects, multicast / anycast How do these functional layers relate? What is the smallest common denominator?+ZZ,Z2ZZZ+,2  ,HQ-"Some AbstractionsVDistributed Hash Tables (DHT) Simple store and retrieve of values with a key Values can be of any type Decentralized Object Location and Routing (DOLR) Decentralized directory service for endpoints/objects Route messages to nearest available endpoint Multicast / Anycast (CAST) Scalable group communication Decentralized membership managementI1cAI1HA  I@4Tier 1 InterfacesStructured P2P OverlaysD7The Common DenominatorKey-based Routing layer (Tier 0) Large sparse Id space N (160 bits: 0  2160 represented as base b) Nodes in overlay network have nodeIds N Given k N, overlay deterministically maps k to its root node (a live node in the network) Goal: Standardize API at this layer Main routing call route (key, msg, [node]) Route message to node currently responsible for key Supplementary calls Flexible upcall interface for customized routing Accessing and managing the ID-space v!PP6PNPPVP! (! "65V  >\G1&Flexible Routing via Upcalls(hDeliver(key, msg) Delivers a message to application at the destination Forward(&key, &msg, &nextHopNode) Synchronous upcall with normal next hop node Applications can override messages Update(node, boolean joined) Upcall invoked to inform application of a node joining or leaving the local node s neighborSetP5P"PPPP_P5"P  _   7  >  M KBR API (managing ID space)(Expose local routing table nextHopSet = local_lookup (key, num, safe) Query the ID space nodehandle[ ] = neighborSet (max_rank) nodehandle[ ] = replicaSet (key, num) boolean = range (node, rank, lkey, rkey)+v+&%)t  5    ";0Caching DHT Illustrated 4)Caching DHT Implementation&Interface put (key, value) value = get (key) Implementation (source S, client C, root R) Put: route(key, [PUT,value,S]) Forward upcall: store value Deliver upcall: store value Get: route(key, [GET,C]) Forward upcall: if cached, route(C, [value]), FIN Deliver upcall: if found, route(C, [value])V #, #,    ^       /$ Ongoing WorkWhat s next Better understanding of DOLR vs. CAST Decentralized endpoint management Policies in placement of indirection points APIs and semantics for Tier 1: (DHT/DOLR/CAST) KBR API implementation in current protocols See paper for additional details Implementation of Tier 1 interfaces on KBR KBR API support on selected P2P systems &N[!S &N[!S/6 ` fff33` 3KI3ff` 33ff` /p` 3%*3|` Jy3fff3f` 3ff3̙` 33ff33` DDyq3f` ̙3n` w3ff` }ff>?" dd@,?nKd@ P nA@F`d n?" dd@   @@``PR"   @ ` `2p>>   <L (  < < 6 #" ``    b*0  T X < "X < N$d#" `P <   < 6d#" `U :   < S "UY H"0   < c $,"YW H"0    < c $"YU H"0    < c $" H"0    < S #" `SV :    < S D*"Y H"0    < c $*"X H"0   < <* #" `  `0 * T Click to edit Master title style! !$ < 00 * " ` * RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S < 6 #" `T ` * d* 0  H < 0޽h ? }ff80___PPT10. 07  Pixel  # I A @ (  @T  @ " @ T$,d #"   <   @ c $D, "9)e  :  b e  @# "e  @ S ,"ie  :   @ S ,"9) :   @ S T,"0 :    @ S <,"?e  :    @ S  ,") :    @ S ,"?G :    @ S t,"oG :    @ S 4,"9G :   @ S ,"iA :   @ S ,"A? :   @ 0d1 "P   , T Click to edit Master title style! ! @ 01 " P  1 W#Click to edit Master subtitle style$ $H @ 0޽h ? }ff80___PPT10. 07# 0 zr@t (  t t 0C1 P   1 P*   t 0dH1    1 R*  d t c $ ?  1 t 0C1  0 1 RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S t 6N1 _P  1 P*   t 64U1 _  1 R*  H t 0޽h ? 3380___PPT10.Uy$ 00(  x  c $1@P M  1 x  c $ 1@  P 1 H  0޽h ? ̙33y___PPT10Y+D=' = @B +} # $(  r  S H1<  `0  1 r  S 1< ` 1 H  0޽h ? }ff___PPT10i. w+D=' = @B +} # H$(  Hr H S L1<  `0  1 r H S  1<  1 H H 0޽h ? }ff___PPT10i.ɺPn+D=' = @B +N # e] g(  r  S 1<  `0  1 C p g #""p 1Y  B1?p p 'multicast (msg, gId) anycast (msg, gId)((b  @`$  B1?p p sendToObj (msg, objectId, [n])6  @`  BD1?p p _value = get (key) @`   Bt1? p  leave (groupId) @`   B1? p  unpublish (objectId)$  @`   BD9? p  Z remove (key)   @`   B 9?p  ~join (groupId) @`   B9?p  publish (objectId)  @`  B9?p  ]put (key, data) @`  B%9?p Multicast / Anycast (CAST)  @`  BL9?p x.Decentralized Object Location / Routing (DOLR)// @`  B79?p gDistributed Hash Tables (DHT) @``B  0o ?ZB  s *1 ?ppZB  s *1 ?  ZB  s *1 ?p p `B  0o ?pp`B  0o ?pZB  s *1 ?pZB  s *1 ?p`B  0o ?pH  0޽h ? }ff___PPT10i.%+D=' = @B + # B:p/(  x  c $ '9<  `0  9   6D9C"?` CKey-based Routing ^ @ 6o X ^  6o (X ^ @ 6o X XB  0Do  XB  0Do  <J9@ P` 6Tier 0   <|s0 PP  6Tier 1   <0P9 P 6Tier 2   6 T9C"?@ 5CFS   6W9C"?@@ 6PAST   6[9C"? @ W SplitStream      6_9C"?P@ 4i3    6c9C"?@ V OceanStore    ^ " 6o@(` ^ # 6o@ (` ^ %@ 6o@` ^ & 6o@ ` ^ ' 6o@xX  * 6hi9C"? 0@ RBayeux ^ + 6o@ `   6m9S"`?` P  6CAST   6k9S"`?`   5DHT   60u9S"`?` P   6DOLR ^ /@ 6o@ ` H  0޽h ?@  "#! %#&%'(*+**/ y___PPT10Y+D=' = @B +} # `$(  r  S {9<  `0  9 r  S |9< ` 9 H  0޽h ? }ff___PPT10i.+D=' = @B + #   `#(  `r ` S |9<@ ` 9 r ` S 9<  `0  9 &8 O\  `& " ` Z<9))?C"?1O D0 " ` ZȚ9))?C"?1O D0 `B ` 0D1 ` B|9( Umsg0`B ` 0D3 ` B9 X Adeliver0 ` <9q\ C KBR Layer 0  ` <09zV^* E Application 0 8 ~ Lpb ` " ` Z!*))?C"? OJ D0 "  ` Z$9))?C"? JO D0 `B ` 0D~   ` B̳9 ,  Umsg0 ` C B`C@DEFAA`@0 P0`@  3! ` C B`C@DEF`@0 P0`@  K3 ` B9 T Aforward0`B ` 0Dtp ` B9, Umsg0 ` <<9'b C KBR Layer 0  ` <9L  E Application 0 H ` 0޽h ? }ff___PPT10i.+D=' = @B + # h<(  h~ h s *,9<  `0  9 ~ h s *9< ` 9 H h 0޽h ? y___PPT10Y+D=' = @B +A #K0 H%@%)9T$(  2  Z8 >?p 2  C RBbENGI Q >? Nbb`TNbb`T `Tb`T `T t 2  C 8BYENG? )Y/Y`T)Y/Y`T`T/Y`T`T 5 B   `D>?1QB   `D>?Q5 vB    `D>? @ B    `D>? q B    `D>? a  B    `D>? f B    `D>? p 2  C YCIENGGJIQ >? 8`TD)`TI8`TD)`TIID)`TII    2  C 7BYENG!`IUQ >? Y+Y`TY+Y`TU`T+Y`TU`TFB   `D>?Ve6B  ZD>?Uco  2  C C9QENG嵵J9QQ >? `T`T9Q`T`T9Q9Q`T9Q9Q<e2  # BPENHYQ >? `TP;`TP;`TP;`T F tF !  !2  c 9Myd&o?z3s3M p < 2  S X9Ԩ\d&o?Ԩ!@\ `  < 2  S 9Ԩ\d&o?Ԩ!@\\ +  < 2  S 9Ԩ\d&o?Ԩ!@\L[ < 2  S T9Ԩ\d&o?Ԩ!@\ + < 2  S 9Ԩ\d&o?Ԩ!@\ 0@ p < 2  S DԨ\d&o?Ԩ!@\K  < 2  S Ԩ\d&o?Ԩ!@\|  < 2  S Ԩ\d&o?Ԩ!@\ ; < 2  S PԨ\d&o?Ԩ!@\\[ < 2  S 9Ԩ\d&o?Ԩ!@\  L+  < 2   S Ԩ\d&o?Ԩ!@\ B  < 2 ! S Ԩ\d&o?Ԩ!@\k < 2 " S XԨ\d&o?Ԩ!@\ P  < 2 # S Ԩ\d&o?Ԩ!@\!1  < 2 $ S Ԩ\d&o?Ԩ!@\\; < 2 % S X#Ԩ\d&o?Ԩ!@\   <  3 H$ <"` `    + No?C"? 00,$D 0 7 No?C"? @  ,$D 0 6 s *C"?@@0 0,$D 0 9 No?C"? P,$D  0 5 No?C"? P,$D 0H  0޽h ?p 3f^___PPT10>+VdD"' = @B D' = @BA?%,( < +O%,( < +D' =%(D' =%(Dc' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*+%(D' =-o6Bdissolve*<3<*+DW ' =%(Du' =%(D' =4@BBBB%()?)?Dq' =.97 BBBBBKM 0.0 1.95054E-6 L -0.30417 -0.2385 *3>*B ppt_xB ppt_y=@0BBAApBBB9<*+D' =%(Dc' =4@BB BB%()))D' =1:Bvisible*o3>+B#style.visibility<*7%(D' =-o6Bdissolve*<3<*7Du' =%( D' =4@BBBB%()?)?Dq' =.97 BBBBBKM 0.00417 0.00556 L -0.075 -0.22222 *3>*B ppt_xB ppt_y=@0BBAApBB"""B><*7D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*5%(D^' =%(D' =4@BBBB%()?)?DZ' =."7 BBBBB[M -6.66667E-6 5.55556E-6 L 0.14999 -0.04444 *3>*B ppt_xB ppt_y=0BBAA<*5D4' =%(D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*6%(D^' =%(D' =%(D' =4@BBBB%()?)?D ' =.7 BBBBB M 1.94444E-6 -2.59259E-6 C -0.01406 -0.06018 -0.02795 -0.12013 -0.01667 -0.2 C -0.00538 -0.27986 0.03142 -0.37986 0.06823 -0.47986 *3>*B ppt_xB ppt_y=0BB aaA<*6D' =%(D' =4@BBBB%(D' =1:Bvisible*o3>+B#style.visibility<*9%(D ' =%(D' =4@BBBB%()?)?D' =.7 BBBBBM -1.94444E-6 2.59259E-6 C -0.03698 0.09468 -0.07379 0.18959 -0.0849 0.26875 C -0.09601 0.34792 -0.08142 0.41158 -0.06667 0.47546 *3>*B ppt_xB ppt_y=0BB aaA<*9+} # Pl$(  lr l S 9<  `0  9 r l S *< ` 9 H l 0޽h ? }ff___PPT10i. KŘ+D=' = @B +} # X$(  Xr X S ع,<  `0  , r X S ,< ` , H X 0޽h ? }ff___PPT10i.@騹+D=' = @B +` 0 pp(  X  C t   1  S Le1t 0  1 rChange motivation to, everyone s using these, but nobody understands what they re using& let s break down the pieces, so that we can remove the commonality and examine the differences. Change presentation to top down from bottom up. Fill in explanation of DOLR implementation on API, absorb anycast into DOLR. Write out names of systems onto DOLR (tapestry=pastry+scribe), DHT (can=Chord+DHash)>$<  H  0޽h ? 3380___PPT10.rxIcC* w'8-O/K1x46 {L;@QDu$? 8DOh+'0! hp  PowerPoint PresentationowePixeloi Ben Y. Zhao170Microsoft PowerPointon@`V"x@@@8q2 Gg  C  y-- @ !y--'--- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x ---- @ !x ---- @ !x ---- @ !x ---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x---- @ !x ---- @ !x!---- @ !x"---- @ !x#---- @ !x$---- @ !x%---- @ !x&---- @ !x'---- @ !x(---- @ !x)---- @ !x*---- @ !x+---- @ !x,---- @ !x----- @ !x.---- @ !x/---- @ !x1---- @ !x2---- @ !x3---- @ !x4---- @ !x7---- @ !x;---'}-- @ !,--'-- @ ! > --'-- @ ! --'-- @ ! '--'}-- @ ! >--'-- @ ! '--'-- @ ! (--'}-- @ ! (--'-- @ ! (--'-- @ ! 3 --'-- @ ! 3--'@Arial-. "2 +6*Towards A Common  ."System-@Arial-. $2 76API for Structured .-@Arial-.  2 D6Peer.-@Arial-.  2 DL-.-@Arial-.  2 DOto.-@Arial-.  2 DX-.-@Arial-. 2 D[ Peer Overlays.-@Arial-. 2 P7Frank .-@Arial-. 2 PIDabek .-@Arial-.  2 PZ, .-@Arial-. 2 P^ Ben Y. Zhaoy.-@Arial-.  2 P,.-@Arial-. 2 V7Peter .-@Arial-. 2 VGDruschel.-@Arial-. %2 V`, John Kubiatowicz, .-@Arial-.  2 [7Ion .-@Arial-. 2 [BStoica.-@Arial-. 32 f7MIT, U. C. Berkeley, and Rice.-@Arial-. C2 m7(* Conducted under the IRIS project (NSF).-՜.+,0    On-screen Shown-sn A Times New RomanArial WingdingsTahomaSymbolPixel;*Towards A Common API for Structured Peer-to-Peer OverlaysState of the ArtSome AbstractionsTier 1 InterfacesStructured P2P OverlaysThe Common DenominatorFlexible Routing via UpcallsKBR API (managing ID space)Caching DHT IllustratedCaching DHT Implementation Ongoing Work  Fonts UsedDesign Template Slide Titles #_ Ben Y. ZhaoBen Y. Zhao  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklnopqrstuvwxyz{|}Root EntrydO)Current UserSummaryInformation(mD!PowerPoint Document(DocumentSummaryInformation8~