Chord

Chord er et rutingsystem for datanett. Det er utviklet ved Massachusetts Institute of Technology (MIT) og er primært påtenkt ruting i peer-to-peer datanett («P2P-nett»), der ressurser skal lokaliseres til en eller flere likeverdige noder. Målet er å få spredt belastningen rettferdig og samtidig oppnå en adekvat ytelse og pålitelighet.

Chord's ansvar er å få avgjort hvilken node som skal stå som representant for en gitt ressurs i et P2P-nett, samt styre alle henvendelser om ressursen, til nettopp denne noden. Alle noder som er påkoblet P2P-nettet har en unik 128-bits identitet (basert på en hash av for eksempel IP-adressen), og står som ansvarlig for alle henvendelser i et avgrenset adresseområde rundt sin egen identitet. I tillegg kjenner noden til den identitet som innehas av neste node (suksessor). Ansvarsområdet er da det rommet mellom seg selv og neste.

Enhver henvendelse O vil først få en 128-bit hashverdi beregnet, H=h(O). Det er i utgangspunktet ukjent hvor den ansvarlige er lokalisert, så når en applikasjon ber om en ressurs (åpne en fil, lagre endringer, stenge en fil), må henvendelsen styres til korrekt sted. Chord videresender henvendelsen til sin suksessor, hvis den ikke da selv ser at den står som ansvarlig. Dette kan i uheldigste fall, der den ansvarlige står umiddelbart foran startpunktet, medføre at henvendelsen hopper N ganger før den når den ansvarlige.

For å påskynde leveransen, har Chord også en rutingtabell (finger table) som peker til fornuftige deler av adresserommet, slik at noden kan videresende direkte til det som vil være den nærmeste representant (men ikke nødvendigvis den endelige ansvarlige). Uansett, når den ansvarlige mottar henvendelsen, vil den avbryte videresendingen og utføre arbeidet som ønskes gjort. For å sikre at ressurser spres jevnt over klientene, brukes en hashfunksjon som sikrer konsistent hashing.

Et viktig mål er å redusere antall slike hopp henvendelsene må gjennom, før arbeidet blir gjort; i dag er dette i snitt, log₂N, der N er antall noder i P2P-nettet. Med en million noder, ikke utenkelig dagens Internett, gir dette 20 hopp. Med store rutingtabeller i hver node, vil man få færre hopp, men dette blir da en avveiningssak mellom plassbehov og oppslagstid; i dag er rutingtabellen utstyrt med log₂N adresser.

Når en node forlater P2P-nettet er det viktig at dens ansvarsområde blir plassert til andre, før noden forsvinner og dens ressurser blir utilgjengelige. Filer skal da kopieres til de som tar over ansvaret. Likens, når en node tilkommer, er det viktig at den får en identitet og ansvar for et utsnitt av de ressurser som skal forvaltes. Filer skal da kopieres over fra de noder der den nye overtar ansvaret. Der det er hyppige endringer i medlemskapet (churn) er det usikkert i hvor stor grad Chord vil kunne unngå thrashing, altså unngå å bruke vesentlige deler av produksjonskapasiteten til administrasjon (flytting av filer til og fra nye og utflyttede noder). Chord fungerer i dag som rutingsystem for filsystemet CFS (Cooperative File System), utviklet ved MIT.