Tapestry (DHT)

Gobeläng
Skrivet i	C++
Typ	peer-to-peer
Hemsida	nuvarande .cs .ucsb .edu /projects /chimera /

Tapestry är ett peer-to-peer- överlagringsnätverk som tillhandahåller en distribuerad hashtabell , routing och multicasting- infrastruktur för distribuerade applikationer. Tapestry peer-to-peer- systemet erbjuder effektiv, skalbar, självreparerande, platsmedveten routing till närliggande resurser.

Introduktion

Den första generationen av peer-to-peer-applikationer, inklusive Napster , Gnutella , hade begränsande begränsningar som en central katalog för Napster och omfångade sändningsfrågor för Gnutella som begränsar skalbarheten. För att lösa dessa problem utvecklades en andra generation av P2P-applikationer inklusive Tapestry, Chord , Pastry och CAN . Dessa överlägg implementerar en grundläggande nyckelbaserad routingmekanism. Detta möjliggör deterministisk dirigering av meddelanden och anpassning till nodfel i överlagringsnätverket. Av de namngivna nätverken ligger Pastry väldigt nära Tapestry eftersom de båda använder samma routingalgoritm av Plaxton et al.

Tapestry är en utbyggbar infrastruktur som tillhandahåller decentraliserad objektplacering och routing med fokus på effektivitet och minimera meddelandefördröjning. Detta uppnås eftersom Tapestry konstruerar lokalt optimala routingtabeller från initiering och underhåller dem för att minska routingsträckningen. Dessutom tillåter Tapestry bestämning av objektfördelning enligt behoven för en given applikation. På liknande sätt tillåter Tapestry applikationer att implementera multicasting i överläggsnätverket.

Algoritm

API

Varje nod tilldelas ett unikt nodID likformigt fördelat i ett stort identifierarutrymme. Tapestry använder SHA-1 för att skapa ett 160-bitars identifierarutrymme representerat av en 40-siffrig sexkantnyckel. Applikationsspecifika slutpunkter GUID:er tilldelas på liknande sätt unika identifierare. NodID och GUID är ungefär jämnt fördelade i överlagringsnätverket med varje nod som lagrar flera olika ID:n. Från experiment har det visat sig att Tapestry-effektiviteten ökar med nätverksstorleken, så flera applikationer som delar samma överläggsnätverk ökar effektiviteten. För att skilja mellan applikationer används en unik applikationsidentifierare. Tapestry använder sitt bästa för att publicera och dirigera objekt.

PublishObject
UnPublishObject
RouteToObject
RouteToNode (till exakt matchning istället för närmast matchning)

Routing

Ledningsnät

Varje identifierare mappas till en levande nod som kallas roten. Om en nods nod-ID är G så är det roten annars använd routingtabellens nod-ID och IP-adresser för att hitta nodernas grannar. Vid varje hopp dirigeras ett meddelande progressivt närmare G genom inkrementell suffixdirigering. Varje grannkarta har flera nivåer där varje nivå innehåller länkar till noder som matchar upp till en viss sifferposition i ID:t. Den primära i: ^te posten i den j: ^te nivån är ID och platsen för den närmaste noden som börjar med prefixet (N, j-1)+i. Det betyder att nivå 1 har länkar till noder som inte har något gemensamt, nivå 2 har den första siffran gemensam, etc. På grund av detta tar routing ungefär $\log _{B}N$ hoppar in ett nätverk av storlek N och ID för bas B (hex: B=16). Om ett exakt ID inte kan hittas kommer routingtabellen att dirigera till närmaste matchande nod. För feltolerans behåller noder $c$ sekundära länkar så att routingtabellen har storlek $c*B*\log _{B}N$ .

Objektpublicering och plats

Deltagare i nätverket kan publicera objekt genom att regelbundet dirigera ett publiceringsmeddelande mot rotnoden. Varje nod längs vägen lagrar en pekare som kartlägger objektet. Flera servrar kan publicera pekare till samma objekt. De redundanta länkarna prioriteras efter latens och/eller lokalitet.

Objekt lokaliseras genom att dirigera ett meddelande mot objektets rot. Varje nod längs vägen kontrollerar mappningen och omdirigerar begäran på lämpligt sätt. Effekten av routing är konvergens av närliggande vägar på väg till samma destination....

Dynamiska noder

Nod infogning

Den nya noden blir roten till dess nodID. Roten hittar längden på det längsta prefixet för det ID som den delar. Sedan skickar den ett multicast-meddelande som når alla befintliga noder som delar samma prefix. Dessa noder lägger sedan till den nya noden i sina routingtabeller. Den nya noden kan ta över att vara roten för några av rotens objekt. Noderna kommer att kontakta den nya noden för att tillhandahålla en tillfällig grannskapslista. Den nya noden utför sedan en iterativ närmaste grannesökning för att fylla alla nivåer i sin routingtabell.

Nodavgång

För att lämna nätverket sänder en nod sin avsikt att lämna och sänder ersättningsnoden för varje nivå i routningstabellerna för de andra noderna. Objekt vid den lämnande noden omdistribueras eller fylls på från redundanta kopior.

Nodfel

Oväntade nodfel hanteras genom redundans i nätverket och backuppekare för att återupprätta skadade länkar.

Ansökningar

Tapestry tillhandahåller ett överläggsroutingnätverk som är stabilt under en mängd olika nätverksförhållanden. Detta ger en idealisk infrastruktur för distribuerade applikationer och tjänster. Applikationer baserade på gobeläng är:

OceanStore − Distribuerat lagringsverktyg på PlanetLab
Mnemosyne − Steganografiskt filsystem
Bayeux − Självorganiserande multicastingapplikation
Spamwatch − Decentraliserat spamfilter

Utvecklare

Tapestry utvecklades av Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph och John D. Kubiatowicz.

Se även

^ Zhao, Ben Y.; Huang, Ling; Stribling, Jeremy; Rhea, Sean C.; Joseph, Anthony D.; Kubiatowicz, John D. (2004). "Tapestry: A Resilient Global-scale Overlay for Service Deployment" (PDF) . IEEE Journal om utvalda områden inom kommunikation . 22 (1): 41–53. CiteSeerX 10.1.1.71.2718 . doi : 10.1109/JSAC.2003.818784 . Hämtad 13 januari 2015 .

externa länkar

Chimera Project en implementering av Tapestry (ca 2007)

[1] Zhao, Ben Y.; Huang, Ling; Stribling, Jeremy; Rhea, Sean C.; Joseph, Anthony D.; Kubiatowicz, John D. (2004). "Tapestry: A Resilient Global-scale Overlay for Service Deployment" (PDF) . IEEE Journal om utvalda områden inom kommunikation . 22 (1): 41–53. CiteSeerX 10.1.1.71.2718 . doi : 10.1109/JSAC.2003.818784 . Hämtad 13 januari 2015 .