Chord


Chord

Chord ist ein strukturiertes Peer-to-Peer-System, welches im Gegensatz zu den meisten unstrukturierten Systemen eine effiziente Suche nach Inhalten ermöglicht. Wie auch Gnutella ist Chord keine konkrete Implementierung, sondern ein Protokollsystem. Es wird am MIT entwickelt und der Quelltext der aktuellen Version steht unter der MIT-Lizenz zum freien Herunterladen und Benutzen zur Verfügung.

Strukturiertes Overlaynetzwerk

Über der eigentlichen Transportschicht (TCP/IP) bilden Peer-to-Peer-Systeme ein sogenanntes Overlay-Netzwerk. Dieses Overlay-Netzwerk beschreibt die Netzwerktopologie der einzelnen Peers, die über das Peer-to-Peer-System verbunden sind. Die zentrale Frage stellt sich beim Hinzufügen und Entfernen neuer Peers (Netzwerkknoten): Mit wem soll der neue Knoten verbunden werden? Genauso beim Löschen: War der Knoten eventuell eine Verbindung zwischen zwei anderen, sodass das Entfernen des Knotens eine Verschlechterung der Qualität des Overlaynetzwerks darstellt?

Bei Gnutella werden diese Fragen nicht gestellt, neue Knoten verbinden sich wahllos mit den Knoten, die sie durch Flooding des Netzwerkes ermitteln können. Bei Chord hingegen wird ein sogenannter Chord-Ring aufgebaut: Alle Netzwerkknoten werden in einer Ringstruktur angeordnet, wobei jeder Knoten Verbindungen zu seinem Vorgänger, Nachfolger sowie bestimmten anderen Knoten im Netzwerk hat. Diese Ringstruktur ermöglicht (mit Hilfe einer Verteilten Hashtabelle) eine binäre Suche, was im Allgemeinen Suchkosten von O(log(n)) bei der Suche nach Inhalten im Netzwerk verursacht. (Im Gegensatz dazu verursacht Gnutella z. B. immense Suchkosten, – etwa 70 % der Netzwerklast in Gnutella-Netzwerken entsteht durch Suchen.) Der Nachteil liegt natürlich in der komplexeren Handhabung der Ringstruktur – beim Hinzufügen und Entfernen von Netzwerkknoten ist jeweils immer darauf zu achten, dass die Ringstruktur und die Querverweise erhalten bleiben.

Inhaltsverteilung

Chord-Fingertabelleneinträge auf weiterführende Knoten

Nur mit Hilfe der Ringstruktur ist natürlich keine binäre Suche möglich: Im naiven Ansatz müsste – zur Suche von Inhalten – der Ring einmal in aufsteigender Reihenfolge der GUIDs durchlaufen werden, um einen „exact match“, d. h. eine präzise Antwort auf eine Suchanfrage zu bekommen. Das ist zwar besser als die Suche in einem unstrukturierten Netz, aber immer noch relativ „teuer“.

Um Daten, also den eigentlichen zu verbreitenden Inhalt des Netzwerkes, korrekt zu identifizieren, wird eine globale Hash-Funktion benötigt. Diese weist jedem Datensatz (z. B. Dateien im Fall von Filesharing) eine eindeutige ID zu, die durch die Verwendung der SHA-1-Hashfunktion zustande kommt (160-Bit-Schlüssel). Jeder Knoten verwaltet nun einen bestimmten Teil der globalen Hashtabelle, der durch ein Intervall des Schlüssels repräsentiert wird. Jeder Knoten weiß jetzt also für einen Teil der Daten, auf welchen anderen Knoten bzw. Intervallen sich diese jeweils befinden.

Das Chord-Netzwerk benutzt zur Suche und Durchquerung des Ringes Verweise auf entfernte Knoten, eine sogenannte Fingertabelle. Die Einträge werden wie folgt erstellt: der i-te Finger (i beginnt hier mit einer 0) verweist auf den Knoten, der für den Hashwert x+2(-i) zuständig ist. Dadurch ist gesichert, dass man viel schneller als mit linearer Suche zu den gesuchten Element gelangen kann.

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • chord — chord·ed; chord; clav·i·chord; clav·i·chord·ist; har·mon·i·chord; harp·si·chord; harp·si·chord·ist; hep·ta·chord; hex·a·chord; lyri·chord; mono·chord; neu·ro·chord; no·to·chord; no·va·chord; oc·ta·chord; pen·ta·chord; peri·chord; poly·chord;… …   English syllables

  • Chord — may refer to: Chord (music), an aggregate of musical pitches sounded simultaneously. Chord (guitar) an aggregate of musical pitches played simultaneously on a guitar Chord (geometry), a line segment joining two points on a curve Chord (astronomy) …   Wikipedia

  • Chord — (k[^o]rd), n. [L chorda a gut, a string made of a gut, Gr. chordh . In the sense of a string or small rope, in general, it is written cord. See {Cord}.] 1. The string of a musical instrument. Milton. [1913 Webster] 2. (Mus.) A combination of… …   The Collaborative International Dictionary of English

  • chord — [ko:d US ko:rd] n [Sense: 1; Date: 1400 1500; Origin: accord] [Sense: 2 3; Date: 1500 1600; Origin: cord; influenced by Latin chorda ( CORD) (] [Sense: 2; Date: (17 19 centuries); Origin: chord string of a musical instrument )] …   Dictionary of contemporary English

  • chord — Ⅰ. chord [1] ► NOUN ▪ a group of three or more notes sounded together in harmony. DERIVATIVES chordal adjective. ORIGIN from ACCORD(Cf. ↑accord); the spelling was influenced by CHORD(Cf. ↑chord …   English terms dictionary

  • chord — chord, cord 1. Although we are dealing here with three English words, their histories are very much intertwined, and their ultimate origin is in the Latin word chorda which has several meanings. To begin with, there are two distinct words spelt… …   Modern English usage

  • Chord — es un protocolo sencillo y escalable de búsqueda distribuida en redes P2P que relaciona claves (keys) con nodos. Está diseñado para funcionar en redes descentralizadas (es decir, sin nodos privilegiados), y su funcionamiento permite concluir con… …   Wikipedia Español

  • chord — [ kɔrd ] noun count * 1. ) two or more musical notes played together a ) a particular position of the fingers on the guitar, producing a particular sound 2. ) TECHNICAL a straight line that connects two points in a circle or curved line… …   Usage of the words and phrases in modern English

  • Chord — Chord, v. i. (Mus.) To accord; to harmonize together; as, this note chords with that. [1913 Webster] || …   The Collaborative International Dictionary of English

  • Chord — Chord, v. t. [imp. & p. p. {Chorded}; p. pr. & vb. n. {Chording}.] To provide with musical chords or strings; to string; to tune. [1913 Webster] When Jubal struck the chorded shell. Dryden. [1913 Webster] Even the solitary old pine tree chords… …   The Collaborative International Dictionary of English


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.