Artifact Content
Not logged in

Artifact 8b94623b18aeb0c540dec4bccba8196223ba719d:

Attachment "2002_xx_xx_Routing_Algorithms_for_DHTs_Some_Open_Questions_by_Sylvia_Ratnasamy_and_Scott_Shenker_and_Ion_Stoica.ps" to wiki page [Attic 001 for Holding Various Files] added by martin_vahi on 2018-01-20 11:59:52.
%!PS-Adobe-2.0
%%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software
%%Title: routing.dvi
%%Pages: 5
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%DocumentFonts: Times-Roman Times-Bold Times-Italic Courier
%%+ Times-BoldItalic
%%EndComments
%DVIPSWebPage: (www.radicaleye.com)
%DVIPSCommandLine: dvips -f routing
%DVIPSParameters: dpi=600, compressed
%DVIPSSource:  TeX output 2002.03.01:1635
%%BeginProcSet: texc.pro
%!
/TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S
N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72
mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0
0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{
landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize
mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[
matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round
exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{
statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0]
N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin
/FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array
/BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2
array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N
df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A
definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get
}B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub}
B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr
1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3
1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx
0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx
sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{
rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp
gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B
/chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{
/cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{
A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy
get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse}
ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp
fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17
{2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add
chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{
1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop}
forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn
/BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put
}if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{
bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A
mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{
SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{
userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X
1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4
index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N
/p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{
/Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT)
(LaserWriter 16/600)]{A length product length le{A length product exch 0
exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse
end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask
grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot}
imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round
exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto
fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p
delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M}
B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{
p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S
rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end

%%EndProcSet
%%BeginProcSet: 8r.enc
% @@psencodingfile@{
%   author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry",
%   version = "0.6",
%   date = "1 July 1998",
%   filename = "8r.enc",
%   email = "tex-fonts@@tug.org",
%   docstring = "Encoding for TrueType or Type 1 fonts
%                to be used with TeX."
% @}
% 
% Idea is to have all the characters normally included in Type 1 fonts
% available for typesetting. This is effectively the characters in Adobe
% Standard Encoding + ISO Latin 1 + extra characters from Lucida.
% 
% Character code assignments were made as follows:
% 
% (1) the Windows ANSI characters are almost all in their Windows ANSI
% positions, because some Windows users cannot easily reencode the
% fonts, and it makes no difference on other systems. The only Windows
% ANSI characters not available are those that make no sense for
% typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen
% (173). quotesingle and grave are moved just because it's such an
% irritation not having them in TeX positions.
% 
% (2) Remaining characters are assigned arbitrarily to the lower part
% of the range, avoiding 0, 10 and 13 in case we meet dumb software.
% 
% (3) Y&Y Lucida Bright includes some extra text characters; in the
% hopes that other PostScript fonts, perhaps created for public
% consumption, will include them, they are included starting at 0x12.
% 
% (4) Remaining positions left undefined are for use in (hopefully)
% upward-compatible revisions, if someday more characters are generally
% available.
% 
% (5) hyphen appears twice for compatibility with both 
% ASCII and Windows.
% 
/TeXBase1Encoding [
% 0x00 (encoded characters from Adobe Standard not in Windows 3.1)
  /.notdef /dotaccent /fi /fl
  /fraction /hungarumlaut /Lslash /lslash
  /ogonek /ring /.notdef
  /breve /minus /.notdef 
% These are the only two remaining unencoded characters, so may as
% well include them.
  /Zcaron /zcaron 
% 0x10
 /caron /dotlessi 
% (unusual TeX characters available in, e.g., Lucida Bright)
 /dotlessj /ff /ffi /ffl 
 /.notdef /.notdef /.notdef /.notdef
 /.notdef /.notdef /.notdef /.notdef
 % very contentious; it's so painful not having quoteleft and quoteright
 % at 96 and 145 that we move the things normally found there to here.
 /grave /quotesingle 
% 0x20 (ASCII begins)
 /space /exclam /quotedbl /numbersign
 /dollar /percent /ampersand /quoteright
 /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash
% 0x30
 /zero /one /two /three /four /five /six /seven
 /eight /nine /colon /semicolon /less /equal /greater /question
% 0x40
 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O
% 0x50
 /P /Q /R /S /T /U /V /W
 /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore
% 0x60
 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o
% 0x70
 /p /q /r /s /t /u /v /w
 /x /y /z /braceleft /bar /braceright /asciitilde
 /.notdef % rubout; ASCII ends
% 0x80
 /.notdef /.notdef /quotesinglbase /florin
 /quotedblbase /ellipsis /dagger /daggerdbl
 /circumflex /perthousand /Scaron /guilsinglleft
 /OE /.notdef /.notdef /.notdef
% 0x90
 /.notdef /.notdef /.notdef /quotedblleft
 /quotedblright /bullet /endash /emdash
 /tilde /trademark /scaron /guilsinglright
 /oe /.notdef /.notdef /Ydieresis
% 0xA0
 /.notdef % nobreakspace
 /exclamdown /cent /sterling
 /currency /yen /brokenbar /section
 /dieresis /copyright /ordfeminine /guillemotleft
 /logicalnot
 /hyphen % Y&Y (also at 45); Windows' softhyphen
 /registered
 /macron
% 0xD0
 /degree /plusminus /twosuperior /threesuperior
 /acute /mu /paragraph /periodcentered
 /cedilla /onesuperior /ordmasculine /guillemotright
 /onequarter /onehalf /threequarters /questiondown
% 0xC0
 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla
 /Egrave /Eacute /Ecircumflex /Edieresis
 /Igrave /Iacute /Icircumflex /Idieresis
% 0xD0
 /Eth /Ntilde /Ograve /Oacute
 /Ocircumflex /Otilde /Odieresis /multiply
 /Oslash /Ugrave /Uacute /Ucircumflex
 /Udieresis /Yacute /Thorn /germandbls
% 0xE0
 /agrave /aacute /acircumflex /atilde
 /adieresis /aring /ae /ccedilla
 /egrave /eacute /ecircumflex /edieresis
 /igrave /iacute /icircumflex /idieresis
% 0xF0
 /eth /ntilde /ograve /oacute
 /ocircumflex /otilde /odieresis /divide
 /oslash /ugrave /uacute /ucircumflex
 /udieresis /yacute /thorn /ydieresis
] def

%%EndProcSet
%%BeginProcSet: texps.pro
%!
TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2
index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{
dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1
roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def
dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def}
if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def}
def end

%%EndProcSet
TeXDict begin 40258431 52099146 1000 600 600 (routing.dvi)
@start /Fa 165[37 43 43 56 1[43 37 33 40 1[33 43 43 53
37 43 23 20 43 43 1[37 43 40 40 43 65[{TeXBase1Encoding ReEncodeFont}23
59.7758 /Times-Roman rf /Fb 134[33 33 50 1[37 21 29 29
1[37 37 37 54 21 33 1[21 37 37 21 33 37 33 37 37 9[62
46 1[42 37 2[46 54 50 62 42 2[25 54 54 46 46 54 50 1[46
8[37 5[37 37 37 21 19 25 3[25 25 25 39[{TeXBase1Encoding ReEncodeFont}
49 74.7198 /Times-Italic rf
%DVIPSBitmapFont: Fc cmmi6 6 1
/Fc 1 101 df<EC03E0EC3FC0A21403A2EC0780A4EC0F00A4EB1F1EEBFF9E3801E0DE38
03807E3807007C48133C121E123E003C5B127CA3485BA215401560903801E0C012781303
393807E180391C1CF300380FF87F3807E03C1B247EA220>100 D
E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fd cmr6 6 1
/Fd 1 50 df<137013F0120712FF12F91201B3A7487EB512E0A213217AA01E>49
D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fe cmsy10 10.95 2
/Fe 2 107 df<126012F812FEEA7F80EA1FE0EA07F8EA01FE38007F80EB1FE0EB07F8EB
01FE9038007F80EC1FE0EC07F8EC01FE9138007F80ED1FE0ED07F8ED01FE9238007F80EE
1FE0EE07F8EE01FE9338007F80EF1FE0EF07F8EF01FCA2EF07F8EF1FE0EF7F80933801FE
00EE07F8EE1FE0EE7F80DB01FEC7FCED07F8ED1FE0ED7F80DA01FEC8FCEC07F8EC1FE0EC
7F80D901FEC9FCEB07F8EB1FE0EB7F80D801FECAFCEA07F8EA1FE0EA7F8000FECBFC12F8
1260CCFCAE007FB812F8B912FCA26C17F8364878B947>21 D<126012F0B3B3B3B3B11260
045B76C319>106 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Ff cmr8 8 1
/Ff 1 51 df<EB7F803801FFF0000713FC380F01FE381C003F0030EB1F800070EB0FC000
7814E000FC13076C14F07E1403A2127E003C1307C7FC15E0A2140F15C0EC1F8015005C14
3E5C5CEB01E0495A495A49C7FC131E5B017013305B485A4848136048C7FC120E001FB512
E05A5AB612C0A31C2C7DAB23>50 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fg cmmi10 10.95 5
/Fg 5 111 df<49B612E0835FD900010180C7FC93C8FC5DA34A5AA44A5AA44A5AA44A5A
A44A5AA44A5AA44AC9FCA4495AA21804180E4948151CA31838495A18781870A2494815F0
EF01E0A217034948EC07C0A2EF0F80173F4948147F933803FF00017F141F007FB8FCB85A
A2373E7DBD3E>76 D<EE3FF00303B5FC92391FC03FC092397E0007E0DA01F8EB01F8DA07
E06D7E4A48147E023FC87E027EED1F804A16C0D903F8150F494816E0495A4948ED07F0A2
494816F849C9FC5B48481603A2484817FCA2485A000F17075B121FA25B123F19F8484816
0FA44848EE1FF0A3F03FE0A390CAEA7FC0A2F0FF80A219004D5A1703604D5A6C7E4D5A4D
5A003F5F4D5A6C6C4BC7FC17FE6C6C4A5A4C5A6C6CEC07E06C6CEC1FC06C6C4A5A6C6C02
FEC8FC90393F8003F890390FE01FE00103B5C9FC9038007FF03E427BBF45>79
D<EE07E0ED03FFA3ED000F17C0A4EE1F80A4EE3F00A4167EA45EA2EC1F80ECFFE0903903
F071F8903807C03990381F001D013E130D017EEB0FF0491307485A1203495C1207485AA2
001F4A5A5B123FA24848495AA448C748C7FCA492387E0180481503A3007E9138FC0700A2
1401003E1303003F0107130E6CEB0E7C6C011C5B390780783C3A03C1E01C383A01FFC00F
F03A007F0007C02B407DBE2F>100 D<EB01F813FFA313035CA4495AA4495AA4495AA449
C9FCA216FCED03FE017EEB0F0792381C0F80ED301FED603F49EBC07FEC0180EC03000206
EB3F00484848131C4A90C7FC5C5C3803F1C0EBF38001FEC9FC7F4813F0EBE3FEEBE07FEC
1F8048486C7E6E7E6E7EA2D81F801406160EA3484848485AA35E007E1303163016700201
5B48903800E1C0007CEC7F800038023EC7FC29407CBE2F>107 D<D801F0EB1FE0D807FC
EB7FF83A0E1E01E07C3A0C0F03803E001C90388E001F0038139C02B81480007013F0A25C
48485AA25CA24848C7EA3F001200A3017E147EA35E5BA24B5AA248481503923803F007A2
ED07E04848150EA2EEC01CA24848153817301770030313E04848903801C3C00007913800
FF006C48147E30297DA737>110 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fh cmr10 10.95 15
/Fh 15 112 df<1430147014E0EB01C0EB0380EB07005B130E5B133C5BA25BA2485A1203
5B1207A25B120FA348C7FCA35A123EA3127EA4127CA212FCB2127CA2127EA4123EA3123F
7EA36C7EA312077FA212037F12016C7EA21378A27F131C7F130F7FEB0380EB01C0EB00E0
14701430145A77C323>40 D<124012E012707E7E7E120F7E6C7E7F6C7EA26C7EA2137813
7C133C133EA2131E131FA3EB0F80A314C01307A314E0A41303A214F0B214E0A21307A414
C0A3130F1480A3EB1F00A3131E133EA2133C137C13785BA2485AA2485A5B48C7FC5A120E
5A5A5A5A1240145A7BC323>I<EB01FE90380FFFC090383F03F090387C00F849137C4848
7F48487F4848EB0F80A2000F15C04848EB07E0A3003F15F0A290C712034815F8A64815FC
B3A26C15F8A56C6CEB07F0A3001F15E0A36C6CEB0FC0A26C6CEB1F80000315006C6C133E
6C6C5B017C5B90383F03F090380FFFC0D901FEC7FC263F7DBC2D>48
D<EB01C013031307131F137FEA07FFB5FC139FEAF81F1200B3B3ACEB7FF0B612F8A31D3D
78BC2D>I<EB07FC90383FFF8090B512E03901F01FF03903C003FC48C66C7E000E6D7E48
EC7F805AED3FC05A16E0007F141F487E16F07FA46C5A6CC7FC120CC813E0153FA216C015
7F168016005D4A5A5D4A5A5D4A5A4A5A4A5A92C7FC143E5C14F0495A495A5C49C8FC010E
14705B5B5B4914E0485A5B48C8FC00061401000FB6FC5A5A4815C0B7FCA3243D7CBC2D>
I<EB07FC90383FFF809038F80FE03901E003F839038001FC48C77E000E80481580D81F80
137F486C14C07FA56C5A6C481480C8FC15FF1600A25D4A5A5D4A5A4A5A4A5A023FC7FCEB
1FFCECFF809038000FE0EC03F0EC01FC816E7EED7F80A216C0A2ED3FE0A216F0A2120C12
3F487E487EA316E05B157F6CC713C012706C1580003CECFF006C5C6C495A3907C003F839
03F80FF0C6B512C0013F5BD907F8C7FC243F7CBC2D>I<00061403D80780131F01F813FE
90B55A5D5D5D5D92C7FC14FCEB3FE090C9FCACEB01FE90380FFF8090383E03E090387001
F09038C0007849137C90C77E153F0006EC1F80C8FC16C0A2ED0FE0A316F0A3120C123E12
7F487EA316E090C7FC48141F007C15C0127016806C143F003C1500001C147E6C5C6C495A
3903C003F03901F80FE06CB55A013F90C7FCEB07F8243F7CBC2D>53
D<EC1FE0ECFFF8903803F03C903807C00E90381F0007013E148049131F49EB3FC0000114
7F5B1203485AED3F80000FEC1F004990C7FC121FA2123FA25B127FA214FE903883FF8090
388707E039FF8C01F090389800F801B0137C01E0137E8116805BED1FC0A216E05BA216F0
A4127FA5123FA216E07F121F16C0000F143F16806C6C14005D6C6C137E00015C3900FC01
F890387E07F090383FFFC0010F5BD903FCC7FC243F7CBC2D>I<1238123C123F90B612FC
A316F84815F0A216E00078C7EA01C00070EC0380A2ED0700150E5A5D5DA2C85A5DA24A5A
4A5A140792C7FC5C140E141E5CA2147C147814F8A213015CA21303A21307A3495AA4131F
A5133FA96D5AA20107C8FC26407BBD2D>I<EB03FC90381FFF8090383C07E09038F000F0
D801C0137C48487F0007141E48C7121FED0F80121EED07C0A2123EA3123FA26DEB0F80A2
D81FE014006D5B6C6C131E01FE5B6C6C5B6CEBC0F06CEBE1E06CEBFF806D48C7FC6D7E01
0F7F15E0497F017813FC9038F03FFE3901C01FFF3803800700076D138048C713C0001E14
7F003EEC1FE0003C140F007C140716F0481403A21501A516E0127CED03C07EED07807E6C
6CEB0F006C6C133ED803F05B3901FC03F039007FFFE0011F1380D903FCC7FC243F7CBC2D
>I<EB03FCEB1FFF90383E07C09038F801E048486C7E0003804848137C4848137E153E00
1F143F123F491480127FED1FC0A212FF16E0A616F0A4127FA2153F123FA26C7E157F120F
6C7E000314DF3901F0019F3900F8031FD97E0E13E0EB1FFCEB07F090C7FCA216C0153FA2
1680A21600D80F805B486C137E487E5DA24A5A01C05B6C48485A391E0007C06CEB1F8026
07C07FC7FC3803FFFC6C5B38003FC0243F7CBC2D>I<007FB912E0BA12F0A26C18E0CDFC
AE007FB912E0BA12F0A26C18E03C167BA147>61 D<167C903903F801FE90391FFF078F90
3A7E0FCE1F809038F803F83901F001F03B03E000F80F000007ECFC0693C7FC4848137EA2
001F147FA6000F147EA26C6C5BA200035C6C6C485A6D485A39037E0FC0D91FFFC8FC3807
03F80006CAFC120EA3120FA27F6C7E90B512E015FE6C6E7E6C15E06C810003813A07C000
1FFC001FC71201003EEC007E003C153E007C153F4881A6007C153E003C153C6C5D6C5DD8
07C0EB03E0D803F0EB0FC0D800FE017FC7FC90383FFFFC010313C0293D7EA82D>103
D<EA01FC12FFA3120712031201B3B3B1487EB512F8A3153F7DBE1A>108
D<14FF010713E090381F81F890387E007E01F8131F4848EB0F804848EB07C04848EB03E0
000F15F04848EB01F8A2003F15FCA248C812FEA44815FFA96C15FEA36C6CEB01FCA3001F
15F86C6CEB03F0A26C6CEB07E06C6CEB0FC06C6CEB1F80D8007EEB7E0090383F81FC9038
0FFFF0010090C7FC282A7EA82D>111 D E
%EndDVIPSBitmapFont
/Fi 139[25 7[25 6[40 3[45 50[23 46[{TeXBase1Encoding ReEncodeFont}5
90.9091 /Times-BoldItalic rf /Fj 134[45 45 2[51 30 35
40 1[51 45 51 76 25 2[25 51 45 1[40 51 40 51 45 12[61
51 66 71 56 1[66 1[61 4[71 3[66 1[66 6[30 45 45 45 45
45 45 45 45 45 45 48[{TeXBase1Encoding ReEncodeFont}40
90.9091 /Times-Bold rf /Fk 134[45 3[45 45 3[45 45 2[45
45 3[45 1[45 59[45 45 40[{TeXBase1Encoding ReEncodeFont}11
74.7198 /Courier rf /Fl 105[37 28[37 37 54 37 37 21 29
25 37 37 37 37 58 21 37 21 21 37 37 25 33 37 33 37 33
3[25 1[25 46 54 1[71 1[54 46 42 50 1[42 54 54 66 46 54
29 25 54 54 42 46 54 50 50 54 5[21 21 37 37 37 37 37
37 37 37 37 37 21 19 25 19 2[25 25 25 36[42 2[{
TeXBase1Encoding ReEncodeFont}71 74.7198 /Times-Roman
rf /Fm 203[25 25 25 25 49[{TeXBase1Encoding ReEncodeFont}4
49.8132 /Times-Roman rf /Fn 203[33 33 33 33 49[{
TeXBase1Encoding ReEncodeFont}4 66.4176 /Times-Roman
rf /Fo 134[55 3[55 55 3[55 55 2[55 55 3[55 1[55 59[55
55 40[{TeXBase1Encoding ReEncodeFont}11 90.9091 /Courier
rf /Fp 133[35 40 40 61 40 45 25 35 35 45 45 45 45 66
25 40 1[25 45 45 25 40 45 40 45 45 9[76 2[51 45 2[56
3[51 2[30 66 3[66 61 1[56 1[45 15[25 23 30 23 2[30 30
37[45 2[{TeXBase1Encoding ReEncodeFont}43 90.9091 /Times-Italic
rf /Fq 105[45 1[40 40 24[40 45 45 66 45 45 25 35 30 45
45 45 45 71 25 45 25 25 45 45 30 40 45 40 45 40 3[30
1[30 3[86 66 66 56 51 61 1[51 66 66 81 56 2[30 66 66
51 56 66 61 61 66 1[40 3[25 25 45 45 45 45 45 45 45 45
45 45 25 23 30 23 2[30 30 30 35[51 51 2[{TeXBase1Encoding ReEncodeFont}
73 90.9091 /Times-Roman rf /Fr 134[60 60 86 60 66 40
47 53 1[66 60 66 100 33 2[33 66 60 40 53 66 53 1[60 12[80
66 86 8[47 93 93 73 80 3[86 9[60 60 60 60 60 60 60 3[40
42[66 2[{TeXBase1Encoding ReEncodeFont}39 119.552 /Times-Bold
rf /Fs 134[50 2[50 50 28 39 33 2[50 50 78 28 50 1[28
50 2[44 50 44 50 44 13[55 66 8[33 8[92 17[25 4[33 33
40[{TeXBase1Encoding ReEncodeFont}25 99.6264 /Times-Roman
rf /Ft 138[72 40 56 48 1[72 72 72 112 40 2[40 72 72 48
64 16[88 80 96 104 1[104 6[104 3[104 2[104 6[40 58[{
TeXBase1Encoding ReEncodeFont}23 143.462 /Times-Roman
rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop 396 364 a Ft(Routing)34 b(Algorithms)f(for)i(DHTs:)43
b(Some)35 b(Open)g(Questions)272 617 y Fs(Sylvia)25 b(Ratnasamy)113
733 y(\(sylviar@cs.berk)o(ele)o(y)-6 b(.edu\))1678 617
y(Scott)25 b(Shenk)o(er)1389 733 y(\(shenk)o(er@icsi.berk)o(ele)o(y)-6
b(.edu\))3069 617 y(Ion)24 b(Stoica)2758 733 y(\(istoica@cs.berk)o(ele)
o(y)-6 b(.edu\))-150 1095 y Fr(1)119 b(Intr)n(oduction)-150
1308 y Fq(Ev)o(en)40 b(though)h(the)o(y)g(were)f(introduced)j(only)d(a)
g(fe)n(w)f(years)-150 1421 y(ago,)20 b(peer)n(-to-peer)j(\(P2P\))18
b(\002lesharing)j(systems)f(are)f(no)n(w)g(one)-150 1533
y(of)28 b(the)h(most)f(popular)j(Internet)f(applications)i(and)d(ha)n
(v)o(e)g(be-)-150 1646 y(come)f(a)g(major)g(source)h(of)f(Internet)i
(traf)n(\002c.)42 b(Thus,)29 b(it)e(is)h(e)o(x-)-150
1759 y(tremely)i(important)h(that)f(these)g(systems)g(be)f(scalable.)48
b(Un-)-150 1872 y(fortunately)-6 b(,)22 b(the)d(initial)h(designs)h
(for)d(P2P)g(systems)h(ha)n(v)o(e)h(sig-)-150 1985 y(ni\002cant)33
b(scaling)h(problems;)39 b(for)32 b(e)o(xample,)j(Napster)e(has)g(a)
-150 2098 y(centralized)k(directory)f(service,)i(and)c(Gnutella)h
(emplo)o(ys)h(a)-150 2211 y(\003ooding-based)41 b(search)d(mechanism)g
(that)g(is)f(not)g(suitable)-150 2324 y(for)24 b(lar)n(ge)h(systems.)
-59 2439 y(In)41 b(response)i(to)d(these)i(scaling)h(problems,)j(se)n
(v)o(eral)c(re-)-150 2552 y(search)i(groups)h(ha)n(v)o(e)f
(\(independently\))k(proposed)d(a)e(ne)n(w)-150 2665
y(generation)32 b(of)d(scalable)j(P2P)c(systems)i(that)g(support)h(a)e
Fp(dis-)-150 2778 y(trib)n(uted)35 b(hash)e(table)g Fq(\(DHT\))e
(functionality;)41 b(among)33 b(them)-150 2891 y(are)26
b(T)-7 b(apestry)26 b([15)q(],)f(P)o(astry)h([6)q(],)f(Chord)h([14)q
(],)f(and)h(Content-)-150 3004 y(Addressable)33 b(Netw)o(orks)e
(\(CAN\))f([10)q(].)49 b(In)31 b(these)g(systems,)-150
3117 y(which)36 b(we)f(will)g(call)h(DHTs,)h(\002les)e(are)h
(associated)i(with)e(a)-150 3230 y(k)o(e)o(y)29 b(\(produced,)j(for)d
(instance,)j(by)c(hashing)j(the)e(\002le)f(name\))-150
3343 y(and)i(each)g(node)g(in)g(the)g(system)g(is)f(responsible)k(for)c
(storing)-150 3456 y(a)24 b(certain)i(range)f(of)g(k)o(e)o(ys.)31
b(There)25 b(is)f(one)h(basic)g(operation)i(in)-150 3568
y(these)19 b(DHT)e(systems,)j Fo(lookup\(key\))p Fq(,)13
b(which)19 b(returns)h(the)-150 3681 y(identity)j(\()p
Fp(e)o(.g)o(.)p Fq(,)c(the)i(IP)f(address\))i(of)f(the)f(node)i
(storing)g(the)f(ob-)-150 3794 y(ject)27 b(with)f(that)g(k)o(e)o(y)-6
b(.)37 b(This)26 b(operation)j(allo)n(ws)d(nodes)h(to)f
Fo(put)-150 3907 y Fq(and)20 b Fo(get)e Fq(\002les)h(based)i(on)f
(their)g(k)o(e)o(y)-6 b(,)21 b(thereby)g(supporting)i(the)-150
4020 y(hash-table-lik)o(e)28 b(interf)o(ace.)749 3987
y Fn(1)-59 4136 y Fq(This)48 b(DHT)e(functionality)51
b(has)e(pro)o(v)o(ed)f(to)g(be)g(a)g(use-)-150 4249 y(ful)39
b(substrate)i(for)d(lar)n(ge)i(distrib)n(uted)i(systems;)47
b(a)38 b(number)-150 4361 y(of)45 b(projects)i(are)f(proposing)i(to)d
(b)n(uild)i(Internet-scale)i(f)o(a-)-150 4474 y(cilities)33
b(layered)g(abo)o(v)o(e)e(DHTs,)h(including)h(distrib)n(uted)i(\002le)
-150 4587 y(systems)d([5,)e(7,)g(4],)i(application-layer)j(multicast)d
([11)r(,)d(16)q(],)-150 4700 y(e)n(v)o(ent)d(noti\002cation)i(services)
g([3,)d(1],)g(and)i(chat)f(services)h([2)q(].)-150 4813
y(W)l(ith)f(so)f(man)o(y)g(applications)k(being)d(de)n(v)o(eloped)i(in)
d(so)g(short)-150 4926 y(a)h(time,)h(we)e(e)o(xpect)j(the)f(DHT)d
(functionality)30 b(to)d(become)g(an)-150 5039 y(inte)o(gral)e(part)f
(of)g(the)f(future)i(P2P)e(landscape.)-59 5154 y(The)38
b(core)i(of)f(these)h(DHT)d(systems)j(is)f(the)g(routing)i(al-)p
-150 5226 800 4 v -45 5282 a Fm(1)-16 5314 y Fl(The)34
b(interf)o(aces)h(of)e(these)i(systems)f(are)g(not)g(all)f(identical;)
41 b(some)-150 5405 y(re)n(v)o(eal)34 b(only)h(the)f
Fk(put)g Fl(and)h Fk(get)e Fl(interf)o(ace)i(while)f(others)g(re)n(v)o
(eal)h(the)-150 5496 y Fk(lookup\(key\))21 b Fl(function)j(directly)-5
b(.)36 b(Ho)n(we)n(v)o(er)m(,)25 b(the)e(abo)o(v)o(e)i(discussion)-150
5587 y(refers)18 b(to)f(the)h(underlying)h(functionality)g(and)f(not)g
(the)g(details)f(of)h(the)g(API.)2050 1095 y Fq(gorithm.)82
b(The)40 b(DHT)f(nodes)j(form)e(an)h(o)o(v)o(erlay)h(netw)o(ork)2050
1208 y(with)18 b(each)h(node)g(ha)n(ving)h(se)n(v)o(eral)g(other)f
(nodes)h(as)e(neighbors.)2050 1321 y(When)23 b(a)f Fo(lookup\(key\))17
b Fq(is)23 b(issued,)h(the)f(lookup)h(is)f(routed)2050
1434 y(through)g(the)e(o)o(v)o(erlay)h(netw)o(ork)g(to)f(the)g(node)h
(responsible)i(for)2050 1547 y(that)19 b(k)o(e)o(y)-6
b(.)27 b(The)18 b(scalability)k(of)c(these)h(DHT)e(algorithms)j(is)f
(tied)2050 1660 y(directly)25 b(to)f(the)g(ef)n(\002cienc)o(y)g(of)g
(their)g(routing)h(algorithms.)2141 1802 y(Each)35 b(of)g(the)h
(proposed)i(DHT)33 b(systems)j(listed)h(abo)o(v)o(e)f(\226)2050
1915 y(T)-7 b(apestry)h(,)37 b(P)o(astry)-6 b(,)36 b(Chord,)h(and)d
(CAN)e(\226)h(emplo)o(y)i(a)e(dif)n(fer)n(-)2050 2028
y(ent)21 b(routing)i(algorithm.)30 b(Usually)22 b(discussion)i(of)d
(DHT)e(rout-)2050 2141 y(ing)26 b(issues)i(is)d(in)h(the)h(conte)o(xt)g
(of)f(one)g(particular)j(algorithm.)2050 2254 y(And,)37
b(when)e(more)f(than)i(one)f(is)f(mentioned,)39 b(the)o(y)c(are)g(of-)
2050 2367 y(ten)23 b(compared)h(in)e(competiti)n(v)o(e)j(terms)d(in)h
(an)f(ef)n(fort)h(to)g(deter)n(-)2050 2480 y(mine)35
b(which)g(is)f(\223best\224.)64 b(W)-7 b(e)34 b(think)i(both)f(of)g
(these)h(trends)2050 2593 y(are)k(wrong.)76 b(The)39
b(algorithms)j(ha)n(v)o(e)e(more)f(commonality)2050 2706
y(than)g(dif)n(ferences,)44 b(and)39 b(each)f(algorithm)i(embodies)g
(some)2050 2819 y(insights)25 b(about)e(routing)i(in)d(o)o(v)o(erlay)i
(netw)o(orks.)29 b(Rather)23 b(than)2050 2932 y(al)o(w)o(ays)38
b(w)o(orking)g(in)f(the)g(conte)o(xt)i(of)e(a)f(single)j(algorithm,)
2050 3044 y(or)26 b(comparing)i(the)f(algorithms)h(competiti)n(v)o(ely)
-6 b(,)30 b(a)c(more)g(ap-)2050 3157 y(propriate)i(goal)e(w)o(ould)f
(be)g(to)h(combine)g(these)g(insights,)i(and)2050 3270
y(seek)20 b(ne)n(w)f(insights,)j(to)d(produce)j(e)n(v)o(en)d(better)i
(algorithms.)29 b(In)2050 3383 y(that)i(spirit)h(we)d(describe)k(some)d
(issues)i(rele)n(v)n(ant)g(to)e(routing)2050 3496 y(algorithms)f(and)f
(identify)i(some)d(open)h(research)i(questions.)2050
3609 y(Of)k(course,)39 b(our)d(list)f(of)g(questions)j(is)d(not)h
(intended)h(to)e(be)2050 3722 y(e)o(xhausti)n(v)o(e,)25
b(merely)f(illustrati)n(v)o(e.)2141 3864 y(As)30 b(should)i(be)f(clear)
g(by)g(our)g(description,)k(this)d(paper)f(is)2050 3977
y(not)24 b(about)h(\002nished)g(w)o(ork,)f(b)n(ut)g(instead)i(is)e
(about)h(a)e(research)2050 4090 y(agenda)e(for)e(future)i(w)o(ork)e
(\(by)h(us)f(and)h(others\).)29 b(W)-7 b(e)18 b(hope)j(that)2050
4203 y(presenting)31 b(such)e(a)e(discussion)k(to)d(this)h(audience)h
(will)e(pro-)2050 4316 y(mote)d(syner)n(gy)j(between)e(research)h
(groups)f(in)f(this)h(area)g(and)2050 4429 y(help)j(clarify)g(some)f
(of)g(the)h(underlying)i(issues.)43 b(W)-7 b(e)28 b(should)2050
4542 y(note)38 b(that)f(there)h(are)f(man)o(y)g(other)h(interesting)i
(issues)f(that)2050 4655 y(remain)33 b(to)f(be)h(resolv)o(ed)h(in)f
(these)g(DHT)d(systems,)36 b(such)d(as)2050 4768 y(security)i(and)f
(rob)n(ustness)i(to)d(attacks,)k(system)d(monitoring)2050
4881 y(and)39 b(maintenance,)45 b(and)39 b(inde)o(xing)h(and)f(k)o(e)o
(yw)o(ord)h(search-)2050 4993 y(ing.)28 b(These)21 b(issues)h(will)e
(doubtless)k(be)c(discussed)k(else)n(where)2050 5106
y(in)32 b(this)h(w)o(orkshop.)58 b(Our)32 b(focus)h(on)g(routing)h
(algorithms)g(is)2050 5219 y(not)24 b(intended)i(to)d(imply)h(that)g
(these)h(other)f(issues)h(are)f(of)g(sec-)2050 5332 y(ondary)h
(importance.)2141 5475 y(W)-7 b(e)26 b(\002rst)h(\(v)o(ery\))h
(brie\003y)g(re)n(vie)n(w)f(the)h(routing)h(algorithms)2050
5587 y(used)21 b(in)f(the)h(v)n(arious)g(DHT)e(systems)i(in)f(Section)h
(2.)27 b(W)-7 b(e)20 b(then,)p eop
%%Page: 2 2
2 1 bop -150 91 a Fq(in)35 b(the)f(follo)n(wing)j(sections,)i(discuss)d
(v)n(arious)g(issues)g(rele-)-150 204 y(v)n(ant)d(to)g(routing:)49
b(state-ef)n(\002cienc)o(y)36 b(tradeof)n(f,)g(resilience)f(to)-150
317 y(f)o(ailures,)g(routing)d(hotspots,)j(geography)-6
b(,)35 b(and)d(heterogene-)-150 430 y(ity)-6 b(.)-150
732 y Fr(2)119 b(Re)n(view)31 b(of)f(Existing)f(Algorithms)-150
942 y Fq(In)g(this)i(section)g(we)e(re)n(vie)n(w)g(some)h(of)f(the)h(e)
o(xisting)h(routing)-150 1055 y(algorithms.)80 b(All)39
b(of)h(them)g(tak)o(e,)k(as)c(input,)45 b(a)39 b Fo(key)f
Fq(and,)-150 1168 y(in)d(response,)41 b(route)36 b(a)g(message)g(to)g
(the)f(node)i(responsible)-150 1280 y(for)h(that)h(k)o(e)o(y)-6
b(.)73 b(The)37 b(k)o(e)o(ys)i(are)f(strings)i(of)e(digits)h(of)f(some)
-150 1393 y(length.)72 b(Nodes)37 b(ha)n(v)o(e)h(identi\002ers,)43
b(tak)o(en)38 b(from)g(the)f(same)-150 1506 y(space)c(as)f(the)h(k)o(e)
o(ys)g(\()p Fp(i.e)o(.)p Fq(,)g(same)f(number)h(of)f(digits\).)56
b(Each)-150 1619 y(node)40 b(maintains)h(a)e(routing)i(table)g
(consisting)h(of)d(a)g(small)-150 1732 y(subset)27 b(of)f(nodes)h(in)f
(the)g(system.)36 b(When)26 b(a)f(node)i(recei)n(v)o(es)g(a)-150
1845 y(query)d(for)e(a)g(k)o(e)o(y)h(for)f(which)h(it)f(is)g(not)h
(responsible,)j(the)c(node)-150 1958 y(routes)35 b(the)g(query)g(to)f
(the)g(neighbor)j(node)e(that)f(mak)o(es)h(the)-150 2071
y(most)29 b(\223progress\224)j(to)n(w)o(ards)e(resolving)h(the)f(query)
-6 b(.)46 b(The)29 b(no-)-150 2184 y(tion)20 b(of)f(progress)i(dif)n
(fers)g(from)e(algorithm)i(to)e(algorithm,)j(b)n(ut)-150
2297 y(in)g(general)i(is)e(de\002ned)h(in)f(terms)g(of)h(some)f
(distance)i(between)-150 2410 y(the)34 b(identi\002er)h(of)e(the)h
(current)h(node)f(and)g(the)f(identi\002er)i(of)-150
2522 y(the)24 b(queried)h(k)o(e)o(y)-6 b(.)-150 2699
y Fj(Plaxton)33 b Fi(et)g(al.)p Fj(:)92 b Fq(Plaxton)34
b Fp(et)f(al.)g Fq([9])g(de)n(v)o(eloped)i(perhaps)-150
2812 y(the)c(\002rst)g(routing)i(algorithm)g(that)f(could)g(be)f
(scalably)i(used)-150 2925 y(by)28 b(DHTs.)40 b(While)28
b(not)h(intended)h(for)e(use)g(in)g(P2P)e(systems,)-150
3038 y(because)31 b(it)e(assumes)h(a)f(relati)n(v)o(ely)i(static)f
(node)g(population,)-150 3151 y(it)h(does)g(pro)o(vide)i(v)o(ery)e(ef)n
(\002cient)h(routing)g(of)f(lookups.)53 b(The)-150 3264
y(routing)31 b(algorithm)g(w)o(orks)e(by)h(\223correcting\224)i(a)d
(single)h(digit)-150 3377 y(at)40 b(a)f(time:)62 b(if)39
b(node)i(number)g Fh(36278)g Fq(recei)n(v)o(ed)g(a)e(lookup)-150
3490 y(query)24 b(with)f(k)o(e)o(y)g Fh(36912)p Fq(,)h(which)f(matches)
h(the)f(\002rst)f(tw)o(o)h(dig-)-150 3603 y(its,)41 b(then)d(the)g
(routing)h(algorithm)g(forw)o(ards)g(the)f(query)g(to)-150
3715 y(a)30 b(node)h(which)g(matches)h(the)e(\002rst)g(three)i(digits)f
(\()p Fp(e)o(.g)o(.)p Fq(,)g(node)-150 3828 y Fh(36955)p
Fq(\).)67 b(T)-7 b(o)35 b(do)h(this,)k(a)35 b(node)i(needs)g(to)f(ha)n
(v)o(e,)j(as)d(neigh-)-150 3941 y(bors,)j(nodes)e(that)g(match)f(each)h
(pre\002x)f(of)f(its)h(o)n(wn)g(identi-)-150 4054 y(\002er)41
b(b)n(ut)h(dif)n(fer)h(in)e(the)h(ne)o(xt)g(digit.)84
b(F)o(or)40 b(a)i(system)g(of)f Fg(n)-150 4167 y Fq(nodes,)33
b(each)f(node)f(has)g(on)g(the)f(order)i(of)e Fg(O)s
Fh(\(log)17 b Fg(n)p Fh(\))30 b Fq(neigh-)-150 4280 y(bors.)f(Since)22
b(one)g(digit)g(is)g(corrected)i(each)e(time)g(the)g(query)g(is)-150
4393 y(forw)o(arded,)i(the)f(routing)h(path)f(is)f(at)g(most)g
Fg(O)s Fh(\(log)17 b Fg(n)p Fh(\))k Fq(o)o(v)o(erlay)-150
4506 y(\(or)j(application-le)n(v)o(el\))k(hops.)-59 4620
y(This)c(algorithm)i(has)e(the)h(additional)i(property)f(that)f(if)f
(the)-150 4733 y Fg(n)-95 4700 y Ff(2)-13 4733 y Fq(node-node)46
b(latencies)f(\(or)f(\223distances\224)i(according)g(to)-150
4846 y(some)24 b(metric\))g(are)h(kno)n(wn,)f(the)g(routing)h(tables)g
(can)g(be)e(cho-)-150 4959 y(sen)31 b(to)g(minimize)h(the)f(e)o
(xpected)i(path)f(latenc)o(y)g(and,)h(more-)-150 5072
y(o)o(v)o(er)l(,)22 b(the)g(latenc)o(y)g(of)g(the)g(o)o(v)o(erlay)g
(path)g(between)h(tw)o(o)e(nodes)-150 5185 y(is)32 b(within)g(a)g
(constant)i(f)o(actor)f(of)f(the)g(latenc)o(y)h(of)f(the)g(direct)-150
5298 y(underlying)27 b(netw)o(ork)d(path)h(between)f(them.)-150
5475 y Fj(T)-8 b(apestry:)92 b Fq(T)-7 b(apestry)26 b([15)q(])e(uses)h
(a)f(v)n(ariant)h(of)g(the)f(Plaxton)-150 5587 y Fp(et)30
b(al.)49 b Fq(algorithm.)h(The)30 b(modi\002cations)i(are)f(to)f
(ensure)i(that)2050 91 y(the)26 b(design,)i(originally)g(intended)g
(for)e(static)h(en)l(vironments,)2050 204 y(can)k(adapt)g(to)f(a)g
(dynamic)i(node)f(population.)52 b(The)30 b(modi\002-)2050
317 y(cations)23 b(are)f(too)g(in)l(v)n(olv)o(ed)i(to)e(describe)h(in)f
(this)g(short)g(re)n(vie)n(w)-6 b(.)2050 430 y(Ho)n(we)n(v)o(er)l(,)19
b(the)g(algorithm)h(maintains)h(the)d(properties)k(of)c(ha)n(v-)2050
543 y(ing)h Fg(O)s Fh(\(log)e Fg(n)p Fh(\))h Fq(neighbors)k(and)d
(routing)i(with)e(path)g(lengths)i(of)2050 656 y Fg(O)s
Fh(\(log)c Fg(n)p Fh(\))22 b Fq(hops.)2050 841 y Fj(P)o(astry:)93
b Fq(In)27 b(P)o(astry)h([6)q(],)g(nodes)h(are)f(responsible)j(for)d(k)
o(e)o(ys)2050 954 y(that)22 b(are)f(the)h(closest)h(numerically)h
(\(with)d(the)h(k)o(e)o(yspace)h(con-)2050 1067 y(sidered)h(as)f(a)f
(circle\).)30 b(The)22 b(neighbors)k(consist)e(of)f(a)f
Fp(Leaf)h(Set)2050 1180 y Fg(L)g Fq(which)h(is)g(the)g(set)g(of)g
Fe(j)p Fg(L)p Fe(j)f Fq(closest)i(nodes)g(\(half)g(lar)n(ger)l(,)h
(half)2050 1293 y(smaller\).)35 b(Correct,)26 b(not)g(necessarily)i(ef)
n(\002cient,)f(routing)g(can)2050 1406 y(be)21 b(achie)n(v)o(ed)i(with)
e(this)h(leaf)g(set.)28 b(T)-7 b(o)21 b(achie)n(v)o(e)h(more)f(ef)n
(\002cient)2050 1519 y(routing,)29 b(P)o(astry)d(has)h(another)i(set)d
(of)h(neighbors)i(spread)f(out)2050 1632 y(in)f(the)h(k)o(e)o(y)f
(space)i(\(in)e(a)g(manner)h(we)e(don')n(t)j(describe)h(here\).)2050
1745 y(Routing)e(consists)h(of)e(forw)o(arding)i(the)e(query)h(to)f
(the)g(neigh-)2050 1858 y(boring)h(node)g(that)f(has)g(the)g(longest)h
(shared)h(pre\002x)d(with)h(the)2050 1970 y(k)o(e)o(y)f(\(and,)h(in)e
(the)h(case)h(of)e(ties,)i(to)f(the)g(node)g(with)g(identi\002er)2050
2083 y(closest)38 b(numerically)g(to)e(the)h(k)o(e)o(y\).)67
b(P)o(astry)36 b(has)g Fg(O)s Fh(\(log)17 b Fg(n)p Fh(\))2050
2196 y Fq(neighbors)26 b(and)e(routes)h(within)f Fg(O)s
Fh(\(log)17 b Fg(n)p Fh(\))23 b Fq(hops.)2050 2382 y
Fj(Chord:)91 b Fq(Chord)30 b([14)q(])f(also)i(uses)f(a)g
(one-dimensional)k(cir)n(-)2050 2495 y(cular)h(k)o(e)o(y)f(space.)62
b(The)33 b(node)i(responsible)j(for)c(the)g(k)o(e)o(y)g(is)2050
2608 y(the)27 b(node)g(whose)h(identi\002er)g(most)e(closely)j(follo)n
(ws)e(the)g(k)o(e)o(y)2050 2720 y(\(numerically\);)37
b(that)32 b(node)f(is)g(called)g(the)g(k)o(e)o(y')-5
b(s)32 b Fp(successor)p Fq(.)2050 2833 y(Chord)43 b(maintains)g(tw)o(o)
f(sets)h(of)f(neighbors.)87 b(Each)42 b(node)2050 2946
y(has)36 b(a)f Fp(successor)k(list)d Fq(of)f Fg(k)j Fq(nodes)f(that)f
(immediately)i(fol-)2050 3059 y(lo)n(w)21 b(it)h(in)g(the)h(k)o(e)o(y)f
(space.)29 b(Routing)23 b(correctness)j(is)c(achie)n(v)o(ed)2050
3172 y(with)38 b(these)g(lists.)73 b(Routing)39 b(ef)n(\002cienc)o(y)f
(is)g(achie)n(v)o(ed)h(with)2050 3285 y(the)31 b Fp(\002ng)o(er)h(list)
f Fq(of)f Fg(O)s Fh(\(log)17 b Fg(n)p Fh(\))30 b Fq(nodes)h(spaced)h(e)
o(xponentially)2050 3398 y(around)g(the)e(k)o(e)o(y)g(space.)50
b(Routing)31 b(consists)h(of)e(forw)o(arding)2050 3511
y(to)i(the)g(node)g(closest,)k(b)n(ut)c(not)g(past,)i(the)e(k)o(e)o(y;)
37 b(pathlengths)2050 3624 y(are)24 b Fg(O)s Fh(\(log)17
b Fg(n)p Fh(\))22 b Fq(hops.)2050 3809 y Fj(CAN:)90 b
Fq(CAN)34 b(chooses)39 b(its)d(k)o(e)o(ys)h(from)f(a)g
Fg(d)p Fq(-dimensional)2050 3922 y(toroidal)d(space.)53
b(Each)31 b(node)h(is)f(associated)i(with)e(a)g(hyper)n(-)2050
4035 y(cubal)23 b(re)o(gion)g(of)g(this)f(k)o(e)o(y)h(space,)g(and)f
(its)h(neighbors)i(are)d(the)2050 4148 y(nodes)29 b(that)g(\223o)n
(wn\224)f(the)g(contiguous)j(hypercubes.)45 b(Routing)2050
4261 y(consists)23 b(of)e(forw)o(arding)j(to)d(a)f(neighbor)k(that)d
(is)g(closer)i(to)e(the)2050 4374 y(k)o(e)o(y)-6 b(.)41
b(CAN)25 b(has)j(a)f(dif)n(ferent)i(performance)h(pro\002le)e(than)g
(the)2050 4487 y(other)23 b(algorithms;)j(nodes)d(ha)n(v)o(e)h
Fg(O)s Fh(\()p Fg(d)p Fh(\))e Fq(neighbors)j(and)e(path-)2050
4613 y(lengths)37 b(are)e Fg(O)s Fh(\()p Fg(dn)2712 4550
y Fd(1)p 2711 4562 33 4 v 2711 4603 a Fc(d)2757 4613
y Fh(\))f Fq(hops.)64 b(Note,)38 b(ho)n(we)n(v)o(er)l(,)g(that)d(when)
2050 4726 y Fg(d)30 b Fh(=)f(log)17 b Fg(n)p Fq(,)25
b(CAN)e(has)k Fg(O)s Fh(\(log)16 b Fg(n)p Fh(\))25 b
Fq(neighbors)k(and)d Fg(O)s Fh(\(log)17 b Fg(n)p Fh(\))2050
4839 y Fq(pathlengths)27 b(lik)o(e)d(the)g(other)g(algorithms.)2050
5149 y Fr(3)119 b(State-Ef\002ciency)31 b(T)-9 b(radeoff)2050
5362 y Fq(The)36 b(most)h(ob)o(vious)i(measure)f(of)e(the)i(ef)n
(\002cienc)o(y)f(of)g(these)2050 5475 y(routing)k(algorithms)g(is)e
(the)g(resulting)i(pathlength.)78 b(Most)2050 5587 y(of)35
b(the)f(algorithms)j(ha)n(v)o(e)e(pathlengths)j(of)d
Fg(O)s Fh(\(log)17 b Fg(n)p Fh(\))34 b Fq(hops,)p eop
%%Page: 3 3
3 2 bop -150 95 a Fq(while)25 b(CAN)e(has)i(longer)h(paths)g(of)e
Fg(O)s Fh(\()p Fg(dn)1228 32 y Fd(1)p 1227 44 33 4 v
1227 85 a Fc(d)1273 95 y Fh(\))p Fq(.)32 b(The)24 b(most)h(ob-)-150
208 y(vious)g(measure)g(of)e(the)i(o)o(v)o(erhead)g(associated)i(with)c
(k)o(eeping)-150 321 y(routing)36 b(tables)g(is)f(the)f(number)i(of)e
(neighbors.)65 b(This)34 b(isn')n(t)-150 434 y(just)g(a)g(measure)h(of)
f(the)g(state)g(required)i(to)e(do)g(routing)i(b)n(ut)-150
547 y(it)27 b(is)h(also)g(a)f(measure)i(of)e(ho)n(w)g(much)h(state)g
(needs)h(to)e(be)h(ad-)-150 660 y(justed)h(when)e(nodes)i(join)f(or)g
(lea)n(v)o(e.)41 b(Gi)n(v)o(en)27 b(the)h(pre)n(v)n(alence)-150
773 y(of)37 b(ine)o(xpensi)n(v)o(e)i(memory)e(and)h(the)f(highly)h
(transient)i(user)-150 885 y(populations)31 b(in)d(P2P)e(systems,)j
(this)g(second)g(issue)f(is)g(lik)o(ely)-150 998 y(to)h(be)f(much)h
(more)g(important)i(than)e(the)g(\002rst.)44 b(Most)29
b(of)g(the)-150 1111 y(algorithms)e(require)g Fg(O)s
Fh(\(log)17 b Fg(n)p Fh(\))25 b Fq(neighbors,)j(while)e(CAN)d(re-)-150
1224 y(quires)i(only)f Fg(O)s Fh(\()p Fg(d)p Fh(\))g
Fq(neighbors.)-59 1337 y(Ideally)-6 b(,)30 b(one)e(w)o(ould)g(lik)o(e)h
(to)e(combine)i(the)f(best)h(of)e(these)-150 1450 y(tw)o(o)45
b(classes)j(of)d(algorithms)j(in)e(hybrid)h(algorithms)h(that)-150
1563 y(achie)n(v)o(e)22 b(short)f(pathlengths)j(with)c(a)g(\002x)o(ed)g
(number)h(of)g(neigh-)-150 1676 y(bors.)-150 1839 y Fj(Question)i(1)46
b Fp(Can)24 b(one)g(ac)o(hie)o(ve)h Fg(O)s Fh(\(log)17
b Fg(n)p Fh(\))23 b Fp(pathlengths)k(\(or)-150 1951 y(better\))e(with)e
Fg(O)s Fh(\(1\))h Fp(neighbor)o(s?)-150 2114 y Fq(One)g(w)o(ould)h(e)o
(xpect)h(that,)f(if)g(this)g(were)f(possible,)j(that)e(some)-150
2227 y(other)g(aspects)g(of)e(routing)j(w)o(ould)e(get)g(w)o(orse.)-150
2366 y Fj(Question)f(2)46 b Fp(If)35 b(so,)i(ar)m(e)d(ther)m(e)i(other)
f(pr)l(operties)j(\(suc)o(h)d(as)-150 2479 y(those)21
b(described)h(in)d(the)h(following)h(sections\))h(that)f(ar)m(e)e(made)
-150 2592 y(wor)o(se)24 b(in)f(these)i(hybrid)g(r)l(outing)g
(algorithms?)-150 2910 y Fr(4)119 b(Resilience)32 b(to)d(F)m(ailur)n
(es)-150 3117 y Fq(The)d(abo)o(v)o(e)h(routing)h(results)g(refer)g(to)e
(a)g(perfectly)j(function-)-150 3230 y(ing)j(system)h(with)f(all)g
(nodes)h(operational.)57 b(Ho)n(we)n(v)o(er)l(,)33 b(P2P)-150
3343 y(nodes)43 b(are)e(notoriously)k(transient)e(and)f(the)f
(resilience)j(of)-150 3455 y(routing)d(to)e(f)o(ailures)i(is)e(a)f(v)o
(ery)i(important)g(consideration.)-150 3568 y(There)24
b(are)f(\(at)h(least\))h(three)f(dif)n(ferent)i(aspects)f(to)e
(resilience.)-59 3681 y(First,)f(one)g(needs)h(to)f(e)n(v)n(aluate)i
(whether)e(routing)i(can)e(con-)-150 3794 y(tinue)36
b(to)e(function)j(\(and)f(with)f(what)f(ef)n(\002cienc)o(y\))i(as)f
(nodes)-150 3907 y(f)o(ail)27 b(without)g(an)o(y)g(time)f(for)g(other)i
(nodes)f(to)f(establish)j(other)-150 4020 y(neighbors)d(to)d
(compensate;)j(that)e(is)f(the)g(neighboring)k(nodes)-150
4133 y(kno)n(w)20 b(that)g(a)f(node)h(has)g(f)o(ailed,)i(b)n(ut)e(the)o
(y)g(don')n(t)h(establish)h(an)o(y)-150 4246 y(ne)n(w)28
b(neighbor)j(relations)g(with)e(other)h(nodes.)45 b(W)-7
b(e)28 b(will)h(call)-150 4359 y(this)c Fp(static)g(r)m(esilience)h
Fq(and)f(measure)g(it)f(in)g(terms)g(of)g(the)g(per)n(-)-150
4472 y(centage)k(of)f(reachable)h(k)o(e)o(y)f(locations)i(and)e(of)f
(the)h(resulting)-150 4585 y(a)n(v)o(erage)e(path)f(length.)-150
4747 y Fj(Question)f(3)46 b Fp(Can)30 b(one)g(c)o(har)o(acterize)j(the)
d(static)h(r)m(esilience)-150 4860 y(of)24 b(the)h(various)i
(algorithms?)34 b(What)25 b(aspects)h(of)f(these)g(algo-)-150
4973 y(rithms)f(lead)g(to)g(good)g(r)m(esilience?)-59
5136 y Fq(Second,)60 b(one)53 b(can)g(in)l(v)o(estigate)i(the)d
(resilience)j(when)-150 5249 y(nodes)33 b(ha)n(v)o(e)g(a)e(chance)i(to)
f(establish)i(some)e(neighbors,)37 b(b)n(ut)-150 5362
y(not)k(all.)80 b(That)40 b(is,)45 b(when)c(nodes)g(ha)n(v)o(e)h
(certain)g(\223special\224)-150 5475 y(neighbors,)f(such)c(as)f(the)g
Fp(successor)i(list)f Fq(or)e(the)i Fp(Leaf)e(Set)p Fq(,)-150
5587 y(and)24 b(these)h(are)f(re-established)k(after)d(a)e(f)o(ailure,)
j(b)n(ut)e(no)g(other)2050 91 y(neighbors)43 b(are)e(re-established)j
(\(such)d(as)g(the)f Fp(\002ng)o(er)i(set)p Fq(\).)2050
204 y(The)34 b(presence)i(of)e(these)h(special)g(neighbors)i(allo)n(w)d
(one)g(to)2050 317 y(pro)o(v)o(e)19 b(the)f(correctness)k(of)c
(routing,)j(b)n(ut)e(the)f(follo)n(wing)i(ques-)2050
430 y(tion)k(remains:)2050 638 y Fj(Question)f(4)46 b
Fp(T)-8 b(o)56 b(what)i(e)n(xtent)h(ar)m(e)e(the)h(observed)h(path)2050
751 y(lengths)33 b(better)f(than)g(the)g(r)o(ather)g(pessimistic)i
(bounds)f(pr)l(o-)2050 864 y(vided)25 b(by)e(the)h(pr)m(esence)h(of)f
(these)g(special)i(neighbor)o(s?)2141 1065 y Fq(Finally)-6
b(,)30 b(one)f(can)g(ask)g(ho)n(w)g(long)g(it)f(tak)o(es)i(v)n(arious)g
(algo-)2050 1178 y(rithms)g(to)g(fully)h(reco)o(v)o(er)g(their)g
(routing)g(state,)h(and)f(at)e(what)2050 1291 y(cost)j(\(measured,)j
(for)d(e)o(xample,)i(by)d(the)h(number)h(of)e(nodes)2050
1404 y(participating)k(in)d(the)f(reco)o(v)o(ery)i(or)f(the)g(number)g
(of)f(control)2050 1517 y(messages)25 b(generated)h(for)e(reco)o(v)o
(ery\).)2050 1694 y Fj(Question)f(5)46 b Fp(How)29 b(long)i(does)h(it)e
(tak)o(e)o(,)i(on)f(aver)o(a)o(g)o(e)o(,)i(to)d(r)m(e-)2050
1807 y(co)o(ver)h(complete)g(r)l(outing)g(state?)49 b(And)30
b(what)f(is)h(the)g(cost)g(of)2050 1920 y(doing)25 b(so?)2050
2090 y Fq(A)d(related)j(question)h(is:)2050 2267 y Fj(Question)d(6)46
b Fp(Can)28 b(one)i(identify)g(design)g(rules)g(that)f(lead)g(to)2050
2380 y(shorter)c(and/or)h(c)o(heaper)f(r)m(eco)o(veries?)2050
2551 y Fq(F)o(or)c(instance,)i(is)f(symmetry)g(\(where)g(the)g(node)g
(neighbor)i(re-)2050 2663 y(lation)g(is)e(symmetric\))i(important)g(in)
e(restoring)j(state)f(easily?)2050 2776 y(One)32 b(could)i(also)g(ar)n
(gue)g(that)f(in)g(the)g(f)o(ace)h(of)e(node)i(f)o(ailure,)2050
2889 y(ha)n(ving)c(the)f(routing)h(automatically)i(send)d(messages)h
(to)f(the)2050 3002 y(correct)f(alternate)g(node)f(\()p
Fp(i.e)o(.)36 b Fq(the)26 b(node)h(that)g(tak)o(es)g(o)o(v)o(er)f(the)
2050 3115 y(range)21 b(of)g(the)f(identi\002er)i(space)f(that)g(w)o(as)
f(pre)n(viously)j(held)e(by)2050 3228 y(the)j(f)o(ailed)h(node\))f
(leads)h(to)e(quick)o(er)j(reco)o(v)o(ery)-6 b(.)2050
3558 y Fr(5)119 b(Routing)31 b(Hot)f(Spots)2050 3777
y Fq(When)37 b(there)h(is)f(a)g(hotspot)i(in)e(the)h(query)g(pattern,)k
(with)37 b(a)2050 3890 y(certain)e(k)o(e)o(y)f(being)i(requested)g(e)o
(xtremely)f(often,)i(then)e(the)2050 4003 y(node)20 b(holding)i(that)e
(k)o(e)o(y)g(may)f(become)i(o)o(v)o(erloaded.)29 b(V)-10
b(arious)2050 4116 y(caching)23 b(and)f(replication)j(schemes)e(ha)n(v)
o(e)f(been)g(proposed)i(to)2050 4229 y(o)o(v)o(ercome)f(this)g
Fp(query)h(hotspot)g Fq(problem;)h(the)d(ef)n(fecti)n(v)o(eness)2050
4341 y(of)31 b(these)i(schemes)g(may)e(v)n(ary)h(between)g(algorithms)i
(based)2050 4454 y(on)40 b(the)g(f)o(an-in)i(at)d(the)i(node)f(and)h
(other)g(f)o(actors,)k(b)n(ut)c(this)2050 4567 y(seems)24
b(to)g(be)g(a)f(manageable)j(problem.)31 b(More)24 b(problematic,)2050
4680 y(ho)n(we)n(v)o(er)l(,)f(is)g(if)g(a)g(node)h(is)e(o)o(v)o
(erloaded)k(with)d(too)g(much)g(rout-)2050 4793 y(ing)35
b(traf)n(\002c.)62 b(These)34 b Fp(r)l(outing)j(hotspots)g
Fq(are)d(harder)i(to)f(deal)2050 4906 y(with)26 b(since)i(there)g(is)e
(no)h(local)g(action)h(the)f(node)h(can)f(tak)o(e)g(to)2050
5019 y(redirect)32 b(the)e(routing)h(load.)48 b(Some)29
b(of)h(the)g Fp(pr)l(oximity)h Fq(tech-)2050 5132 y(niques)h(we)d
(describe)j(belo)n(w)e(might)g(be)g(used)h(to)f(help)h(here,)2050
5245 y(b)n(ut)24 b(otherwise)h(this)f(remains)h(an)e(open)i(problem.)
2050 5422 y Fj(Question)e(7)46 b Fp(Do)33 b(r)l(outing)h(hotspots)i(e)n
(xist)e(and,)h(if)e(so,)i(how)2050 5534 y(can)24 b(one)g(deal)g(with)g
(them?)p eop
%%Page: 4 4
4 3 bop -150 91 a Fr(6)119 b(Incor)o(porating)30 b(Geograph)n(y)-150
308 y Fq(The)d(ef)n(\002cienc)o(y)i(measure)g(used)f(abo)o(v)o(e)g(w)o
(as)g(the)g(number)g(of)-150 421 y(application-le)n(v)o(el)i(hops)d
(tak)o(en)g(on)f(the)g(path.)37 b(Ho)n(we)n(v)o(er)l(,)26
b(the)-150 534 y(true)f(ef)n(\002cienc)o(y)g(measure)g(is)f(the)h
(end-to-end)i(latenc)o(y)f(of)e(the)-150 647 y(path.)51
b(Because)32 b(the)f(nodes)h(could)h(be)d(geographically)36
b(dis-)-150 760 y(persed,)c(some)e(of)g(these)g(application-le)n(v)o
(el)35 b(hops)30 b(could)h(in-)-150 872 y(v)n(olv)o(e)43
b(transcontinental)k(links,)h(and)43 b(others)g(merely)g(trips)-150
985 y(across)c(a)e(LAN;)f(routing)j(algorithms)g(that)f(ignore)h(the)f
(la-)-150 1098 y(tencies)c(of)e(indi)n(vidual)i(hops)f(are)g(lik)o(ely)
g(to)f(result)h(in)f(high-)-150 1211 y(latenc)o(y)d(paths.)44
b(While)28 b(the)g(original)i(\223v)n(anilla\224)g(v)o(ersions)g(of)
-150 1324 y(some)22 b(of)f(these)i(routing)h(algorithms)f(did)f(not)h
(tak)o(e)f(these)h(hop)-150 1437 y(latencies)29 b(into)e(account,)i
(almost)e(all)g(of)f(the)h(\223full\224)g(v)o(ersions)-150
1550 y(of)k(the)g(algorithms)h(mak)o(e)f(some)g(attempt)h(to)e(deal)h
(with)g(the)-150 1663 y(geographic)43 b(proximity)f(of)d(nodes.)79
b(There)40 b(are)g(\(at)g(least\))-150 1776 y(three)24
b(w)o(ays)g(of)g(coping)h(with)e(geography)-6 b(.)-150
1972 y Fj(Pr)n(oximity)39 b(Routing:)91 b Fq(Proximity)39
b(routing)g(is)e(when)h(the)-150 2085 y(routing)21 b(choice)g(is)e
(based)h(not)f(just)h(which)g(neighboring)i(node)-150
2198 y(mak)o(es)27 b(the)f(\223most\224)h(progress)h(to)n(w)o(ards)f
(the)g(k)o(e)o(y)-6 b(,)27 b(b)n(ut)g(is)f(also)-150
2311 y(based)39 b(on)e(which)h(neighboring)j(node)d(is)g
(\223closest\224)i(in)d(the)-150 2424 y(sense)32 b(of)e(latenc)o(y)-6
b(.)51 b(V)-10 b(arious)31 b(algorithms)i(implement)e(prox-)-150
2537 y(imity)36 b(routing)j(dif)n(ferently)-6 b(,)41
b(b)n(ut)c(the)o(y)g(all)f(adopt)i(the)e(same)-150 2650
y(basic)24 b(approach)i(of)d(weighing)i(progress)g(in)e(identi\002er)i
(space)-150 2762 y(against)43 b(cost)g(in)e(latenc)o(y)i(\(or)f
(geography\).)87 b(Simulations)-150 2875 y(ha)n(v)o(e)28
b(sho)n(wn)g(this)g(to)f(be)g(a)g(v)o(ery)h(ef)n(fecti)n(v)o(e)h(tool)f
(in)f(reducing)-150 2988 y(the)d(a)n(v)o(erage)h(path)f(latenc)o(y)-6
b(.)-150 3158 y Fj(Question)23 b(8)46 b Fp(Can)37 b(one)i(formally)f(c)
o(har)o(acterize)j(the)d(ef)n(fec-)-150 3271 y(tiveness)26
b(of)d(these)i(pr)l(oximity)g(r)l(outing)g(appr)l(oac)o(hes?)-150
3515 y Fj(Pr)n(oximity)34 b(Neighbor)e(Selection:)93
b Fq(This)33 b(is)f(a)g(v)n(ariant)i(of)-150 3627 y(the)e(idea)g(abo)o
(v)o(e,)h(b)n(ut)f(no)n(w)f(the)h(proximity)h(criterion)h(is)d(ap-)-150
3740 y(plied)22 b(when)e(choosing)j(neighbors,)h(not)d(just)g(when)g
(choosing)-150 3853 y(the)j(ne)o(xt)g(hop.)-150 4023
y Fj(Question)f(9)46 b Fp(Can)25 b(one)h(show)g(that)g(pr)l(oximity)h
(neighbor)h(se-)-150 4136 y(lection)g(is)e(always)h(better)h(than)f(pr)
l(oximity)h(r)l(outing?)39 b(Is)27 b(this)-150 4249 y(dif)n(fer)m(ence)
f(signi\002cant?)-59 4414 y Fq(As)60 b(mentioned)i(earlier)l(,)72
b(if)60 b(the)h Fg(n)1207 4381 y Ff(2)1306 4414 y Fq(node-pair)i(dis-)
-150 4527 y(tances)34 b(\(as)e(measured)i(by)e(latenc)o(y\))i(are)f
(kno)n(wn,)i(the)d(Plax-)-150 4639 y(ton/T)-7 b(apestry)30
b(algorithm)g(can)e(choose)i(the)e(neighbors)i(so)e(as)-150
4752 y(to)f(minimize)h(the)g(e)o(xpected)i(o)o(v)o(erlay)e(path)g
(latenc)o(y)-6 b(.)42 b(This)27 b(is)-150 4865 y(an)d(e)o(xtremely)i
(important)f(property)-6 b(,)27 b(that)d(is)g(\(so)g(f)o(ar\))h(the)f
(e)o(x-)-150 4978 y(clusi)n(v)o(e)h(domain)f(of)g(the)g(Plaxton/T)-7
b(apestry)26 b(algorithms.)31 b(W)-7 b(e)-150 5091 y(don')n(t)37
b(whether)g(other)g(algorithms)g(can)g(adopt)f(similar)h(ap-)-150
5204 y(proaches.)-150 5374 y Fj(Question)23 b(10)47 b
Fp(If)40 b(one)h(had)h(the)f(full)g Fg(n)1168 5341 y
Ff(2)1247 5374 y Fp(distance)i(matrix,)-150 5487 y(could)28
b(one)f(do)g(optimal)h(neighbor)h(selection)g(in)e(algorithms)-150
5600 y(other)e(than)f(Plaxton/T)-8 b(apestry?)2050 91
y Fj(Geographic)32 b(Lay)n(out:)92 b Fq(In)32 b(most)f(of)h(the)f
(algorithms,)36 b(the)2050 204 y(node)c(identi\002ers)g(are)g(chosen)g
(randomly)h(\()p Fp(e)o(.g)o(.)49 b Fq(hash)32 b(func-)2050
317 y(tions)26 b(of)e(the)h(IP)f(address,)i(etc.\))33
b(and)25 b(the)g(neighbor)i(relations)2050 430 y(are)32
b(established)k(based)d(solely)h(on)e(these)h(node)h(identi\002ers.)
2050 543 y(One)j(could)h(instead)g(attempt)g(to)f(choose)i(node)e
(identi\002ers)2050 656 y(in)e(a)g(geographically)k(informed)e(manner)
-5 b(.)3461 623 y Fn(2)3562 656 y Fq(An)35 b(initial)h(at-)2050
769 y(tempt)28 b(to)g(do)h(so)f(in)g(the)g(conte)o(xt)i(of)e(CAN)e(w)o
(as)i(reported)i(on)2050 882 y(in)36 b([12)q(];)42 b(this)37
b(approach)i(w)o(as)d(quite)h(successful)i(in)d(reduc-)2050
995 y(ing)29 b(the)g(latenc)o(y)h(of)e(paths.)45 b(There)29
b(w)o(as)f(little)h(in)g(the)g(layout)2050 1108 y(method)20
b(speci\002c)h(to)e(CAN,)e(b)n(ut)j(the)g(high-dimensionality)25
b(of)2050 1220 y(the)19 b(k)o(e)o(y)g(space)h(may)e(ha)n(v)o(e)h
(played)i(an)d(important)j(role;)g(recent)2050 1333 y(w)o(ork)31
b([8)q(])f(suggests)j(that)e(latencies)i(in)e(the)f(Internet)j(can)e
(be)2050 1446 y(reasonably)c(modeled)f(by)e(a)f Fg(d)p
Fq(-dimension)k(geometric)f(space)2050 1559 y(with)31
b Fg(d)41 b Fe(\025)f Fh(2)p Fq(.)53 b(This)31 b(raises)i(the)f
(question)i(of)e(whether)h(sys-)2050 1672 y(tems)23 b(that)g(use)g(a)f
(one-dimensional)27 b(k)o(e)o(y)22 b(set)h(can)g(adequately)2050
1785 y(mimic)g(the)h(geographic)j(layout)e(of)e(the)h(nodes.)2050
1933 y Fj(Question)f(11)47 b Fp(Can)53 b(one)h(c)o(hoose)i
(identi\002er)o(s)g(in)e(a)f(one-)2050 2046 y(dimensional)28
b(k)o(e)m(y)d(space)h(that)g(will)e(adequately)k(captur)m(e)f(the)2050
2158 y(g)o(eo)o(gr)o(aphic)g(layout)e(of)e(nodes?)2141
2306 y Fq(Ho)n(we)n(v)o(er)l(,)c(this)g(may)f(not)g(matter)h(because)h
(the)f(geographic)2050 2419 y(layout)h(may)e(not)g(of)n(fer)h
(signi\002cant)i(adv)n(antages)g(o)o(v)o(er)d(the)h(tw)o(o)2050
2532 y(proximity)25 b(methods.)2050 2679 y Fj(Question)e(12)47
b Fp(Can)20 b(the)h(two)f Fq(local)i Fp(tec)o(hniques)h(of)e(pr)l
(oximity)2050 2792 y(r)l(outing)29 b(and)f(pr)l(oximity)g(neighbor)i
(selection)f(ac)o(hie)o(ve)f(most)2050 2905 y(of)23 b(the)h(bene\002t)h
(of)f Fq(global)h Fp(g)o(eo)o(gr)o(aphic)h(layout?)2050
3052 y Fq(Moreo)o(v)o(er)l(,)g(these)f(geographically-in)q(for)q(med)30
b(layout)c(meth-)2050 3165 y(ods)44 b(may)g(interfere)h(with)f(the)g
(rob)n(ustness,)51 b(hotspot,)g(and)2050 3278 y(other)25
b(properties)h(mentioned)f(in)f(pre)n(vious)h(sections.)2050
3426 y Fj(Question)e(13)47 b Fp(Does)32 b(g)o(eo)o(gr)o(aphic)j(layout)
f(have)f(an)g(impact)2050 3539 y(on)41 b(r)m(esilience)o(,)47
b(hotspots,)g(and)42 b(other)g(aspects)g(of)f(perfor)n(-)2050
3652 y(mance?)2050 3981 y Fr(7)119 b(Extr)n(eme)29 b(Heter)n(ogeneity)
2050 4188 y Fq(All)i(of)h(the)g(algorithms)h(start)g(by)f(assuming)h
(that)f(all)g(nodes)2050 4301 y(ha)n(v)o(e)f(the)f(same)g(capacity)i
(to)e(process)i(messages)f(and)g(then,)2050 4414 y(only)36
b(later)l(,)i(add)d(on)g(techniques)j(for)d(coping)h(with)f(hetero-)
2050 4527 y(geneity)-6 b(.)2332 4494 y Fn(3)2415 4527
y Fq(Ho)n(we)n(v)o(er)l(,)30 b(the)f(heterogeneity)j(observ)o(ed)f(in)d
(cur)n(-)2050 4640 y(rent)37 b(P2P)e(populations)40 b([13)q(])35
b(is)i(quite)g(e)o(xtreme,)j(with)c(dif-)2050 4753 y(ferences)c(of)e
(se)n(v)o(eral)h(orders)g(of)f(magnitude)i(in)d(bandwidth.)2050
4866 y(One)20 b(can)g(ask)g(whether)i(the)e(routing)i(algorithms,)g
(rather)f(than)2050 4979 y(merely)35 b Fp(coping)i Fq(with)d
(heterogeneity)-6 b(,)41 b(should)36 b(instead)h(use)p
2050 5042 800 4 v 2155 5097 a Fm(2)2184 5129 y Fl(Note)16
b(that)g(geographic)h(layout)f(dif)n(fers)g(from)g(the)f(tw)o(o)h(abo)o
(v)o(e)h Fb(pr)m(oxim-)2050 5220 y(ity)j Fl(methods)h(in)f(that)g(here)
g(there)h(is)e(an)i(attempt)f(to)g(af)n(fect)g(the)g(global)h(lay-)2050
5312 y(out)h(of)g(the)g(node)h(identi\002ers,)f(whereas)h(the)f
(proximity)h(methods)g(merely)2050 5403 y(af)n(fect)c(the)g(local)g
(choices)h(of)e(neighbors)j(and)e(forw)o(arding)h(nodes.)2155
5464 y Fm(3)2184 5496 y Fl(The)e(authors)f(of)h([13])f(deserv)o(e)h
(credit)f(for)g(bringing)h(the)f(issue)h(of)f(het-)2050
5587 y(erogeneity)j(to)f(our)g(attention.)p eop
%%Page: 5 5
5 4 bop -150 91 a Fq(it)31 b(to)h(their)g Fp(advanta)o(g)o(e)p
Fq(.)57 b(At)30 b(the)i(e)o(xtreme,)i(a)e(star)g(topology)-150
204 y(with)26 b(all)g(queries)i(passing)g(through)g(a)e(single)h(hub)g
(node)g(and)-150 317 y(then)f(routed)i(to)d(their)i(destination)i(w)o
(ould)d(be)g(e)o(xtremely)h(ef-)-150 430 y(\002cient,)42
b(b)n(ut)d(w)o(ould)g(require)i(a)d(v)o(ery)g(highly)i(capable)h(nub)
-150 543 y(node)35 b(\(and)g(w)o(ould)f(ha)n(v)o(e)h(a)f(single)h
(point)g(of)f(f)o(ailure\).)63 b(But)-150 656 y(perhaps)36
b(one)f(could)h(use)f(the)g(v)o(ery)g(highly)h(capable)g(nodes)-150
769 y(as)e(mini-hubs)i(to)d(impro)o(v)o(e)i(routing.)61
b(In)34 b(another)i(position)-150 882 y(paper)27 b(here,)g(some)f(of)g
(us)g(ar)n(gue)h(that)g(heterogeneity)j(can)c(be)-150
995 y(used)d(to)f(mak)o(e)h(Gnutella-lik)o(e)i(systems)e(more)f
(scalable.)31 b(The)-150 1108 y(question)24 b(is)d(whether)h(one)g
(could)g(similarly)h(modify)f(the)f(cur)n(-)-150 1220
y(rent)31 b(DHT)e(routing)j(algorithms)h(to)d(e)o(xploit)i
(heterogeneity:)-150 1466 y Fj(Question)23 b(14)47 b
Fp(Can)52 b(one)g(r)m(edesign)j(these)e(r)l(outing)h(algo-)-150
1578 y(rithms)24 b(to)g(e)n(xploit)h(heter)l(o)o(g)o(eneity?)-59
1711 y Fq(It)44 b(may)g(be)g(that)g(no)h(sophisticated)j
(modi\002cations)e(are)-150 1824 y(needed)e(to)f(le)n(v)o(erage)h
(heterogeneity)-6 b(.)91 b(Perhaps)43 b(the)g(sim-)-150
1936 y(plest)23 b(technique)i(to)d(cope)h(with)e(heterogeneity)-6
b(,)27 b(one)22 b(that)h(has)-150 2049 y(already)42 b(been)e(mentioned)
i(in)e(the)g(literature,)46 b(is)39 b(to)h Fp(clone)-150
2162 y Fq(highly)26 b(capable)h(nodes)f(so)f(that)g(the)o(y)g(could)h
(serv)o(e)f(as)g(multi-)-150 2275 y(ple)f(nodes;)g Fp(i.e)o(.)p
Fq(,)e(a)h(node)h(that)g(w)o(as)f Fh(10)g Fq(times)h(more)f(po)n
(werful)-150 2388 y(than)34 b(other)h(nodes)g(could)g(function)h(as)e
Fh(10)g Fq(virtual)h(nodes.)1811 2355 y Fn(4)-150 2501
y Fq(When)d(combined)i(with)e(proximity)i(routing)f(and)g(neighbor)-150
2614 y(selection,)c(cloning)f(w)o(ould)e(allo)n(w)g(nodes)i(to)e(route)
h(to)f(them-)-150 2727 y(selv)o(es)20 b(and)f(thereby)i(\223jump\224)f
(in)f(k)o(e)o(y)g(space)h(without)g(an)o(y)g(for)n(-)-150
2840 y(w)o(arding)25 b(hops.)-150 2994 y Fj(Question)e(15)47
b Fp(Does)28 b(cloning)i(plus)f(pr)l(oximity)h(r)l(outing)g(and)-150
3107 y(neighbor)35 b(selection)f(lead)f(to)g(signi\002cantly)j(impr)l
(o)o(ved)d(per)n(-)-150 3220 y(formance)23 b(when)f(the)g(node)g
(capabilities)j(ar)m(e)d(e)n(xtr)m(emely)h(het-)-150
3333 y(er)l(o)o(g)o(eneous?)-150 3639 y Fr(Refer)n(ences)-113
3808 y Fl([1])48 b(A)t(.)41 b(R)q Fa(O)r(W)t(S)t(T)t(R)r(O)t(N)t
Fl(,)j(A)t(-)t(M)t(.)d(K)t Fa(E)t(R)t(M)t(A)t(R)t(R)t(E)t(C)t
Fl(,)i(M)t(.)e(C)t(.)t(,)46 b Fa(A)t(N)t(D)41 b Fl(D)t
Fa(R)t Fl(-)22 3899 y Fa(U)t(S)t(C)t(H)t(E)t(L)t Fl(,)31
b(P)l(.)57 b(Scribe:)41 b(The)28 b(design)h(of)f(a)g(lar)o(ge-scale)g
(e)n(v)o(ent)g(no-)20 3991 y(ti\002cation)23 b(infrastructure.)43
b(In)23 b Fb(Pr)m(oceedings)i(of)f(NGC)f(2001)i Fl(\(No)o(v)-5
b(.)20 4082 y(2001\).)-113 4201 y([2])48 b Fa(B)r(A)t(S)t(E)t(D)21
b Fl(C)t Fa(H)t(A)m(T)o Fl(,)g(C)t(.)28 b(http://jxme.jxta.or)o
(g/demo.html,)18 b(2001.)-113 4320 y([3])48 b(C)t Fa(A)t(B)t(R)t(E)t(R)
t(A)t Fl(,)16 b(L)t(.)h(F)n(.)t(,)g(J)t Fa(O)t(N)t(E)t(S)t
Fl(,)g(M)t(.)h(B)t(.)t(,)g Fa(A)t(N)t(D)g Fl(T)t Fa(H)t(E)t(I)t(M)t(E)t
(R)t Fl(,)d(M)t(.)k(Herald:)20 4412 y(Achie)n(ving)h(a)f(global)g(e)n
(v)o(ent)h(noti\002cation)f(service.)27 b(In)19 b Fb(Pr)m(oceedings)20
4503 y(of)c(the)g(8th)g(IEEE)f(W)-7 b(orkshop)16 b(on)g(Hot)f(T)-7
b(opics)15 b(in)g(Oper)o(ating)g(Systems)20 4594 y(\(HotOS-VIII\))j
Fl(\(Elmau/Oberbayern,)i(German)o(y,)f(May)h(2001\).)-113
4714 y([4])48 b(D)q Fa(A)t(B)t(E)t(K)t Fl(,)19 b(F)n(.)t(,)g(K)t
Fa(A)t(A)t(S)t(H)t(O)t(E)t(K)t Fl(,)f(M)t(.)i(F)n(.)t(,)f(K)t
Fa(A)t(R)t(G)t(E)t(R)t Fl(,)e(D)t(.)t(,)j(M)t Fa(O)t(R)t(R)t(I)t(S)t
Fl(,)f(R)t(.)t(,)22 4805 y Fa(A)t(N)t(D)30 b Fl(S)t Fa(T)s(O)t(I)t(C)t
(A)t Fl(,)g(I)t(.)54 b(W)m(ide-area)27 b(cooperati)n(v)o(e)i(storage)f
(with)e(CFS.)20 4896 y(In)k Fb(Pr)m(oceedings)h(of)f(the)g(18th)h(A)n
(CM)e(Symposium)i(on)g(Oper)o(ating)20 4988 y(Systems)f(Principles)f
(\(SOSP)g('01\))h Fl(\(T)-6 b(o)29 b(appear;)35 b(Banf)n(f,)c(Canada,)
20 5079 y(Oct.)18 b(2001\).)p -150 5135 800 4 v -45 5190
a Fm(4)-16 5222 y Fl(This)j(technique)i(has)e(already)h(been)g
(suggested)h(for)e(some)h(of)f(the)g(al-)-150 5314 y(gorithms,)28
b(and)f(could)g(easily)g(be)f(applied)h(to)f(the)h(others.)45
b(Ho)n(we)n(v)o(er)m(,)29 b(in)-150 5405 y(some)h(algorithms)g(it)e(w)o
(ould)j(require)e(alteration)h(in)f(the)g(w)o(ay)h(the)g(node)-150
5496 y(identi\002ers)17 b(were)g(chosen)h(so)f(that)g(the)o(y)g(weren')
o(t)g(tied)g(to)g(the)g(IP)f(address)i(of)-150 5587 y(the)h(node.)2087
91 y([5])48 b(D)t Fa(R)r(U)t(S)t(C)t(H)t(E)t(L)t Fl(,)27
b(P)l(.)t(,)i Fa(A)t(N)t(D)g Fl(R)q Fa(O)r(W)t(S)t(T)t(R)r(O)t(N)t
Fl(,)g(A)t(.)50 b(P)o(ast:)36 b(Persistent)25 b(and)2220
183 y(anon)o(ymous)40 b(storage)f(in)e(a)h(peer)o(-to-peer)h(netw)o
(orking)g(en)m(viron-)2220 274 y(ment.)30 b(In)20 b Fb(Pr)m(oceedings)g
(of)g(the)g(8th)g(IEEE)e(W)-7 b(orkshop)22 b(on)e(Hot)g(T)-7
b(op-)2220 365 y(ics)22 b(in)g(Oper)o(ating)h(Systems)f(\(HotOS)h
(2001\))g Fl(\(Elmau/Oberbayern,)2220 457 y(German)o(y)-5
b(,)19 b(May)h(2001\),)g(pp.)f(65\22670.)2087 581 y([6])48
b(D)t Fa(R)r(U)t(S)t(C)t(H)t(E)t(L)t Fl(,)22 b(P)l(.)t(,)h
Fa(A)t(N)t(D)i Fl(R)q Fa(O)r(W)t(S)t(T)t(R)r(O)t(N)t
Fl(,)e(A)t(.)36 b(P)o(astry:)27 b(Scalable,)22 b(dis-)2220
672 y(trib)o(uted)30 b(object)g(location)g(and)h(routing)f(for)g(lar)o
(ge-scale)g(peer)o(-to-)2220 764 y(peer)20 b(systems.)31
b(In)20 b Fb(Pr)m(oceedings)h(of)f(the)g(18th)h(IFIP/A)n(CM)d(Interna-)
2220 855 y(tional)g(Confer)m(ence)i(on)f(Distrib)o(uted)e(Systems)i
(Platforms)f(\(Middle-)2220 946 y(war)m(e)h(2001\)W)26
b Fl(\(No)o(v)19 b(2001\).)2087 1071 y([7])48 b(K)t Fa(U)t(B)t(I)t(A)m
(T)s(O)r(W)t(I)t(C)t(Z)t Fl(,)42 b(J)t(.)t(,)j(B)t Fa(I)t(N)t(D)t(E)t
(L)t Fl(,)e(D)t(.)t(,)i(C)t Fa(H)t(E)t(N)t Fl(,)f(Y)-6
b(.)t(,)46 b(C)t Fa(Z)t(E)t(R)q(W)t(I)t(N)t Fl(-)2222
1162 y Fa(S)t(K)t(I)t Fl(,)37 b(S)t(.)t(,)g(E)t Fa(A)m(T)s(O)t(N)t
Fl(,)g(P)l(.)t(,)f(G)t Fa(E)t(E)t(L)t(S)t Fl(,)f(D)t(.)t(,)i(G)t
Fa(U)t(M)t(M)t(A)t(D)t(I)t Fl(,)g(R)t(.)t(,)g(R)t Fa(H)t(E)t(A)t
Fl(,)2222 1254 y(S)t(.)t(,)26 b(W)t Fa(E)t(A)m(T)t(H)t(E)t(R)t(S)t(P)t
(O)t(O)t(N)t Fl(,)d(H)t(.)t(,)k(W)t Fa(E)t(I)t(M)t(E)t(R)t
Fl(,)d(W)m(.)t(,)j(W)t Fa(E)t(L)t(L)t(S)t Fl(,)d(C)t(.)t(,)i
Fa(A)t(N)t(D)2222 1345 y Fl(Z)t Fa(H)t(A)q(O)t Fl(,)d(B)t(.)35
b(OceanStore:)27 b(An)21 b(architecture)h(for)e(global-scale)i(per)o(-)
2220 1436 y(sistent)29 b(storage.)60 b(In)29 b Fb(Pr)m(oceeedings)h(of)
f(the)h(Ninth)f(international)2220 1528 y(Confer)m(ence)c(on)f(Ar)m(c)o
(hitectur)o(al)g(Support)i(for)d(Pr)m(o)o(gr)o(amming)i(Lan-)2220
1619 y(gua)o(g)o(es)18 b(and)e(Oper)o(ating)h(Systems)f(\(ASPLOS)f
(2000\))i Fl(\(Boston,)g(MA,)2220 1710 y(No)o(v)o(ember)j(2000\),)f
(pp.)h(190\226201.)2087 1835 y([8])48 b(N)t Fa(G)t Fl(,)24
b(E)t(.)t(,)f Fa(A)t(N)t(D)i Fl(Z)t Fa(H)t(A)t(N)t(G)t
Fl(,)e(H)t(.)34 b(T)-6 b(o)n(w)o(ards)22 b(global)g(netw)o(ork)f
(position-)2220 1926 y(ing.)50 b(In)26 b Fb(Pr)m(oceedings)h(of)f(A)n
(CM)g(SIGCOMM)g(Internet)g(Measur)m(e-)2220 2017 y(ment)19
b(W)-7 b(orkshop)21 b(2001)f Fl(\(No)o(v)-5 b(.)19 b(2001\).)2087
2142 y([9])48 b(P)t Fa(L)t(A)t(X)t(T)s(O)t(N)t Fl(,)23
b(C)t(.)t(,)i(R)t Fa(A)t(JA)t(R)t(A)t(M)t(A)t(N)t Fl(,)f(R)t(.)t(,)h
Fa(A)t(N)t(D)g Fl(R)t Fa(I)t(C)t(H)t(A)t Fl(,)g(A)t(.)38
b(Access-)2220 2233 y(ing)24 b(nearby)h(copies)f(of)g(replicated)g
(objects)g(in)g(a)g(distrib)o(uted)f(en)m(vi-)2220 2325
y(ronment.)28 b(In)19 b Fb(Pr)m(oceedings)h(of)f(the)g(A)n(CM)f(SP)-7
b(AA)19 b Fl(\(Ne)n(wport,)g(Rhode)2220 2416 y(Island,)g(June)h
(1997\),)f(pp.)g(311\226320.)2050 2540 y([10])48 b(R)t
Fa(A)m(T)t(N)r(A)t(S)t(A)t(M)t(Y)-5 b Fl(,)26 b(S)t(.)t(,)g(F)t
Fa(R)t(A)t(N)t(C)t(I)t(S)t Fl(,)g(P)l(.)t(,)g(H)t Fa(A)t(N)t(D)t(L)t(E)
t(Y)-5 b Fl(,)25 b(M)t(.)t(,)i(K)t Fa(A)t(R)t(P)m Fl(,)g(R)t(.)t(,)2222
2632 y Fa(A)t(N)t(D)d Fl(S)t Fa(H)t(E)t(N)t(K)t(E)t(R)t
Fl(,)e(S)t(.)35 b(A)20 b(scalable)i(content-addressable)h(netw)o(ork.)
2220 2723 y(In)29 b Fb(Pr)m(oc.)g(A)n(CM)g(SIGCOMM)j
Fl(\(San)d(Die)o(go,)j(CA,)d(August)h(2001\),)2220 2814
y(pp.)19 b(161\226172.)2050 2939 y([11])48 b(R)t Fa(A)m(T)t(N)r(A)t(S)t
(A)t(M)t(Y)-5 b Fl(,)72 b(S)t(.)t(,)g(H)t Fa(A)t(N)t(D)t(L)t(E)t(Y)-5
b Fl(,)71 b(M)t(.)t(,)i(K)t Fa(A)t(R)t(P)m Fl(,)f(R)t(.)t(,)g
Fa(A)t(N)t(D)2222 3030 y Fl(S)t Fa(H)t(E)t(N)t(K)t(E)t(R)t
Fl(,)36 b(S)t(.)72 b(Application-le)n(v)o(el)33 b(Multicast)g(using)g
(Content-)2220 3122 y(Addressable)26 b(Netw)o(orks.)46
b(In)24 b Fb(Pr)m(oceedings)i(of)f(NGC)f(2001)i Fl(\(No)o(v)-5
b(.)2220 3213 y(2001\).)2050 3337 y([12])48 b(R)t Fa(A)m(T)t(N)r(A)t(S)
t(A)t(M)t(Y)-5 b Fl(,)44 b(S)t(.)t(,)h(H)t Fa(A)t(N)t(D)t(L)t(E)t(Y)-5
b Fl(,)44 b(M)t(.)t(,)i(R)t Fa(I)t(C)t(H)t(A)t(R)t(D)t
Fl(K)t Fa(A)t(R)t(P)m Fl(,)c Fa(A)t(N)t(D)2222 3429 y
Fl(S)t Fa(H)t(E)t(N)t(K)t(E)t(R)t Fl(,)21 b(S)t(.)34
b(T)-6 b(opologically-a)o(w)o(are)23 b(o)o(v)o(erlay)e(construction)h
(and)2220 3520 y(serv)o(er)36 b(selection.)79 b(In)36
b Fb(Pr)m(oceedings)g(of)g(Infocom)g('2002)g Fl(\(Mar)l(.)2220
3611 y(2002\).)2050 3736 y([13])48 b(S)t Fa(A)t(R)r(O)t(I)t(U)t
Fl(,)19 b(S)t(.)t(,)i(G)t Fa(U)t(M)t(M)t(A)t(D)t(I)t
Fl(,)f(K)t(.)t(,)h Fa(A)t(N)t(D)h Fl(G)t Fa(R)t(I)t(B)t(B)t(L)t(E)t
Fl(,)d(S)t(.)27 b(A)18 b(measure-)2220 3827 y(ment)k(study)h(of)f(peer)
o(-to-peer)g(\002le)g(sharing)g(systems.)37 b(In)23 b
Fb(Pr)m(oceed-)2220 3919 y(ings)f(of)h(Multimedia)f(Confer)m(encing)i
(and)f(Networking)g Fl(\(San)f(Jose,)2220 4010 y(Jan.)d(2002\).)2050
4134 y([14])48 b(S)t Fa(T)s(O)t(I)t(C)t(A)t Fl(,)17 b(I)t(.)t(,)i(M)t
Fa(O)t(R)t(R)t(I)t(S)t Fl(,)g(R)t(.)t(,)g(K)t Fa(A)t(R)t(G)t(E)t(R)t
Fl(,)e(D)t(.)t(,)i(K)t Fa(A)t(A)t(S)t(H)t(O)t(E)t(K)t
Fl(,)f(M)t(.)i(F)n(.)t(,)2222 4226 y Fa(A)t(N)t(D)30
b Fl(B)r Fa(A)t(L)t(A)t(K)t(R)t(I)t(S)t(H)t(N)r(A)t(N)t
Fl(,)f(H)t(.)53 b(Chord:)40 b(A)26 b(scalable)h(peer)o(-to-peer)2220
4317 y(lookup)j(service)e(for)g(internet)h(applications.)57
b(In)29 b Fb(Pr)m(oceedings)g(of)2220 4408 y(the)20 b(A)n(CM)f(SIGCOMM)
i('01)f(Confer)m(ence)h Fl(\(San)f(Die)o(go,)g(California,)2220
4500 y(August)f(2001\).)2050 4624 y([15])48 b(Z)t Fa(H)t(A)q(O)t
Fl(,)18 b(B)t(.)g(Y)-6 b(.)t(,)19 b(K)t Fa(U)t(B)t(I)t(A)m(T)s(O)r(W)t
(I)t(C)t(Z)t Fl(,)c(J)t(.)t(,)k Fa(A)t(N)t(D)g Fl(J)t
Fa(O)t(S)t(E)t(P)t(H)t Fl(,)e(A)t(.)k(T)-6 b(apestry:)2220
4716 y(An)36 b(infrastructure)h(for)f(f)o(ault-tolerant)h(wide-area)f
(location)h(and)2220 4807 y(routing.)49 b(T)-5 b(ech.)26
b(Rep.)f(UCB/CSD-01-1141,)j(Uni)n(v)o(ersity)e(of)f(Cal-)2220
4898 y(ifornia)19 b(at)f(Berk)o(ele)o(y)-5 b(,)20 b(Computer)f(Science)
g(Department,)h(2001.)2050 5023 y([16])48 b(Z)t Fa(H)t(U)r(A)t(N)t(G)t
Fl(,)18 b(S)t(.)t(,)h(Z)t Fa(H)t(A)q(O)t Fl(,)f(B)t(.)t(,)h(J)t
Fa(O)t(S)t(E)t(P)t(H)t Fl(,)f(A)t(.)h(D)t(.)t(,)g(K)t
Fa(A)m(T)t(Z)t Fl(,)g(R)t(.)f(H)t(.)t(,)h Fa(A)t(N)t(D)2222
5114 y Fl(K)t Fa(U)t(B)t(I)t(A)m(T)s(O)r(W)t(I)t(C)t(Z)t
Fl(,)28 b(J)t(.)52 b(Bayeux:)39 b(An)27 b(architecture)f(for)h
(wide-area,)2220 5205 y(f)o(ault-tolerant)g(data)h(dissemination.)54
b(In)27 b Fb(Pr)m(oceedings)h(of)g(NOSS-)2220 5297 y(D)m(A)-8
b(V'01)19 b Fl(\(Port)f(Jef)n(ferson,)h(NY)-10 b(,)19
b(June)h(2001\).)p eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF