Innehållsadresserbart nätverk
Det innehållsadresserbara nätverket ( CAN ) är en distribuerad, decentraliserad P2P- infrastruktur som tillhandahåller hashtabellfunktionalitet i en internetliknande skala. CAN var ett av de ursprungliga fyra fördelade hashtabellsförslagen , som introducerades samtidigt med Chord , Pastry och Tapestry .
Översikt
Precis som andra distribuerade hashtabeller är CAN designad för att vara skalbar , feltolerant och självorganiserande . Den arkitektoniska designen är ett virtuellt flerdimensionellt kartesiskt koordinatutrymme , en typ av överlagringsnätverk, på en multitorus . Detta n-dimensionella koordinatutrymme är en virtuell logisk adress , helt oberoende av nodernas fysiska plats och fysiska anslutningsmöjligheter. Punkter i utrymmet identifieras med koordinater. Hela koordinatutrymmet är dynamiskt uppdelat mellan alla noder i systemet så att varje nod har åtminstone en distinkt zon inom det totala rummet.
Routing
En CAN-nod upprätthåller en routingtabell som innehåller IP-adressen och den virtuella koordinatzonen för var och en av dess grannar. En nod dirigerar ett meddelande till en destinationspunkt i koordinatutrymmet. Noden bestämmer först vilken angränsande zon som ligger närmast destinationspunkten och söker sedan upp den zonens nods IP-adress via routingtabellen.
Nod sammanfogning
För att gå med i en CAN måste en anslutningsnod:
- Hitta en nod som redan finns i överläggsnätverket.
- Identifiera en zon som kan delas
- Uppdatera routingtabellerna för noder som gränsar till den nyligen delade zonen.
För att hitta en nod som redan finns i överlagringsnätverket kan bootstrapping-noder användas för att informera den anslutande noden om IP-adresser till noder som för närvarande är i överlagringsnätverket.
Efter att den anslutande noden har fått en IP-adress för en nod som redan finns i CAN, kan den försöka identifiera en zon för sig själv. Anslutningsnoden väljer slumpmässigt en punkt i koordinatutrymmet och skickar en anslutningsbegäran, riktad till den slumpmässiga punkten, till en av de mottagna IP-adresserna. Noderna som redan finns i överläggsnätverket dirigerar anslutningsbegäran till rätt enhet via sina zon-till-IP-routningstabeller. När noden som hanterar destinationspunktens zon tar emot anslutningsbegäran, kan den uppfylla anslutningsbegäran genom att dela sin zon på mitten, tilldela sig själv den första halvan och tilldela anslutningsnoden den andra halvan. Om den inte respekterar anslutningsbegäran fortsätter anslutningsnoden att välja slumpmässiga punkter i koordinatutrymmet och skicka anslutningsförfrågningar riktade till dessa slumpmässiga punkter tills den framgångsrikt ansluter sig till nätverket.
Efter att zonuppdelningen och allokeringen är klar, uppdateras de närliggande noderna med koordinaterna för de två nya zonerna och motsvarande IP-adresser. Routningstabeller uppdateras och uppdateringar sprids över nätverket.
Noden avgår
För att hantera en nod som avgår måste CAN
- identifiera en nod som avgår
- låta den avgående nodens zon slås samman eller tas över av en angränsande nod
- uppdatera routingtabellerna över nätverket.
Detektering av en nods avgång kan till exempel göras via hjärtslagsmeddelanden som periodiskt sänder routingtabellinformation mellan grannar. Efter en förutbestämd period av tystnad från en granne, fastställs den närliggande noden som misslyckad och anses vara en avgående nod. Alternativt kan en nod som gärna avgår sända ett sådant meddelande till sina grannar.
Efter att en avgående nod har identifierats måste dess zon antingen slås samman eller tas över. Först analyseras den avgående nodens zon för att bestämma huruvida en angränsande nods zon kan slås samman med den avgående nodens zon för att bilda en giltig zon. Till exempel måste en zon i ett 2d-koordinatutrymme vara antingen en kvadrat eller rektangel och kan inte vara L-formad. Valideringstestet kan gå igenom alla närliggande zoner för att avgöra om en lyckad sammanslagning kan inträffa. Om en av de potentiella sammanslagningarna anses vara en giltig sammanslagning, slås zonerna samman. Om ingen av de potentiella sammanslagningarna bedöms vara giltiga tar den angränsande noden med den minsta zonen över kontrollen över den avgående nodens zon. Efter ett övertagande kan övertagandenoden periodiskt försöka slå samman sina ytterligare kontrollerade zoner med respektive angränsande zoner.
Om sammanslagningen lyckas uppdateras routningstabellerna för närliggande zoners noder för att återspegla sammanslagningen. Nätverket kommer att se undersektionen av överlagringsnätverket som en enda zon efter en sammanslagning och behandla all routingbearbetning med detta tänkesätt. För att genomföra ett övertagande uppdaterar övertagandenoden angränsande zoners noders dirigeringstabeller, så att förfrågningar till endera zonen löser sig till övertagandenoden. Och som sådant ser nätverket fortfarande undersektionen av överlagringsnätverket som två separata zoner och behandlar all routingbearbetning med detta tänkesätt.
Utvecklare
Sylvia Ratnasamy , Paul Francis, Mark Handley , Richard Karp , Scott Shenker