Chord - Revision history

79.228.114.127: /* Einfache Suche */

2013-01-28T19:39:35Z

Einfache Suche

← Older revision		Revision as of 19:39, 28 January 2013
Line 36:		Line 36:
	\|+ '''Pseudo Code für eine einfache Suche'''		\|+ '''Pseudo Code für eine einfache Suche'''
	\|}		\|}
	Diese Form der Suche ist zwar nicht besonders effizient, da die Länge des Suchpfades linear zur Anzahl der Knoten im System wächst. Aber sie kann jederzeit als Fallback-Variante dienen. Die minimale ~~Vorraussetzung~~ für die lineare Suche, dass jeder Knoten seinen Nachfolgeknoten kennt, ist damit auch die minimale Vorraussetzung für die Korrektheit des Chord Protokolls.		Diese Form der Suche ist zwar nicht besonders effizient, da die Länge des Suchpfades linear zur Anzahl der Knoten im System wächst. Aber sie kann jederzeit als Fallback-Variante dienen. Die minimale Voraussetzung für die lineare Suche, dass jeder Knoten seinen Nachfolgeknoten kennt, ist damit auch die minimale Vorraussetzung für die Korrektheit des Chord Protokolls.
	\|\|[[Image:ChordLinearSearch.jpg\|thumb\|250px\|Einfache Suche im Chord Ring]]		\|\|[[Image:ChordLinearSearch.jpg\|thumb\|250px\|Einfache Suche im Chord Ring]]
	\|}		\|}

92.231.86.232: typo

2012-12-03T14:09:43Z

typo

← Older revision		Revision as of 14:09, 3 December 2012
Line 175:		Line 175:

	==Chord#==		==Chord#==
	[http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#] ist eine Weiterentwicklung des Chord Protokolls, an der am [http://www.zib.de Zuse Institut Berlin] gearbeitet wird. Die Gleichverteilung der Schlüssel auf Knoten in einem Chord-Ring mittels einer Basis-Hash-Funktion verhindert die Suche nach Intervallen von Schlüsselwerten, da diese auf logisch benachbarten Knoten ~~geseichert~~ werden müssten. ''Chord#'' eliminiert die Hashfunktion unter Beibehaltung der Perfomance von Chord und ermöglicht damit Bereichsabfragen.		[http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#] ist eine Weiterentwicklung des Chord Protokolls, an der am [http://www.zib.de Zuse Institut Berlin] gearbeitet wird. Die Gleichverteilung der Schlüssel auf Knoten in einem Chord-Ring mittels einer Basis-Hash-Funktion verhindert die Suche nach Intervallen von Schlüsselwerten, da diese auf logisch benachbarten Knoten gespeichert werden müssten. ''Chord#'' eliminiert die Hashfunktion unter Beibehaltung der Perfomance von Chord und ermöglicht damit Bereichsabfragen.

	= Anwendungen =		= Anwendungen =

Mrfluxi: /* Stabilisierung */ kleiner fehler korrigiert

2009-01-29T20:58:05Z

Stabilisierung: kleiner fehler korrigiert

← Older revision		Revision as of 20:58, 29 January 2009
Line 126:		Line 126:
	Das Stabilisierungsprotokoll von Chord sorgt dafür, dass neue Knoten im restlichen Netzwerk bekannt werden, dass die Fingertable aktualisiert wird und dass die Struktur des Rings erhalten bleibt. Dazu wird zusätzlich zum Successor Pointer und der Fingertable noch ein Zeiger auf den direkten Vorgänger Knoten (''Predecessor'') gespeichert. In Regelmässigen Abständen (z.B. 30 Sekunden) werden dann die Stabilisierungs Routinen ''fix_fingers()'' und ''stabilize()'' gerufen.		Das Stabilisierungsprotokoll von Chord sorgt dafür, dass neue Knoten im restlichen Netzwerk bekannt werden, dass die Fingertable aktualisiert wird und dass die Struktur des Rings erhalten bleibt. Dazu wird zusätzlich zum Successor Pointer und der Fingertable noch ein Zeiger auf den direkten Vorgänger Knoten (''Predecessor'') gespeichert. In Regelmässigen Abständen (z.B. 30 Sekunden) werden dann die Stabilisierungs Routinen ''fix_fingers()'' und ''stabilize()'' gerufen.

	'''fix_fingers()''' setzt für jeden Eintrag der Fingertable eine Suche nach dessen ''Start''-Wert ab und trägt den zuständigen Knoten in die Tabelle ein. Dabei gibt es verschiedene Strategien, wieviele Einträge bei einem Aufruf bearbeitet werden. Es kann bei jedem Aufruf die ganze Tabelle aktualisiert werden, allerdings bedeutet das einiges an Netzwerklast. Es kann aber z.B. auch bei jedem Durchlauf ein zufällig ausgewählter Eintrag erneuert werden. Da die Korrektheit der Fingertable nur für die Performance der Suche, nicht aber für die Korrektheit des Suchergebnisses ausschlaggebend ist, kann man eine ganz aktuelle Fingertable eine gewisse zeit lang tollerieren.		'''fix_fingers()''' setzt für jeden Eintrag der Fingertable eine Suche nach dessen ''Start''-Wert ab und trägt den zuständigen Knoten in die Tabelle ein. Dabei gibt es verschiedene Strategien, wieviele Einträge bei einem Aufruf bearbeitet werden. Es kann bei jedem Aufruf die ganze Tabelle aktualisiert werden, allerdings bedeutet das einiges an Netzwerklast. Es kann aber z.B. auch bei jedem Durchlauf ein zufällig ausgewählter Eintrag erneuert werden. Da die Korrektheit der Fingertable nur für die Performance der Suche, nicht aber für die Korrektheit des Suchergebnisses ausschlaggebend ist, kann man eine nicht ganz aktuelle Fingertable eine gewisse zeit lang tollerieren.

	'''stabilize()''' holt sich den ''Predecessor'' des Nachfolgeknoten. Im Normalfall sollte das der Knoten, an dem die Funktion gerufen wird, selbst sein. Falls allerdings die ID dieses Knotens zwischen der eigenen und des Successors liegt, hat sich offensichtlich die Ringstruktur geändert. In diesem Fall wird der Überprüfte Knoten zum neuen Successor. In jedem Fall aber, wird dem Successor durch den Aufruf der ''notifiy()'' Funktion mitgeteilt, dass der rufende Knoten sich als Predeccessor versteht. Beim Aufruf von '''notifiy()''' überprüft der Knoten an dem die Funktion gerufen wird, ob der bisherige Predecessor entweder nicht verfügbar ist oder die ID des rufenden Knoten zwischen der des bisherigen Predecessors und der eigenen liegt. In diesen beiden Fällen, wird der rufende Knoten als neuer Predecessor eingetragen.		'''stabilize()''' holt sich den ''Predecessor'' des Nachfolgeknoten. Im Normalfall sollte das der Knoten, an dem die Funktion gerufen wird, selbst sein. Falls allerdings die ID dieses Knotens zwischen der eigenen und des Successors liegt, hat sich offensichtlich die Ringstruktur geändert. In diesem Fall wird der Überprüfte Knoten zum neuen Successor. In jedem Fall aber, wird dem Successor durch den Aufruf der ''notifiy()'' Funktion mitgeteilt, dass der rufende Knoten sich als Predeccessor versteht. Beim Aufruf von '''notifiy()''' überprüft der Knoten an dem die Funktion gerufen wird, ob der bisherige Predecessor entweder nicht verfügbar ist oder die ID des rufenden Knoten zwischen der des bisherigen Predecessors und der eigenen liegt. In diesen beiden Fällen, wird der rufende Knoten als neuer Predecessor eingetragen.

T.janetzki: /* Anpassung an Strukturänderungen */

2008-04-04T20:47:55Z

Anpassung an Strukturänderungen

← Older revision		Revision as of 20:47, 4 April 2008
Line 103:		Line 103:

	== Anpassung an Strukturänderungen ==		== Anpassung an Strukturänderungen ==
	Bislang wurde einem bereits bestehenden Chord-Ring ausgegangen, dessen Struktur sich nicht ändert. In realen Anwendungen verhält sich das aber völlig anders. Chord muss mit neu hinzukommenden Knoten genauso fertig werden wie mit Knoten, die spontan ausfallen oder das System ordnungsgemäss verlassen. Dazu bietet Chord ein robustes Stabilisierungsprotokoll, das auf solche Ereignisse reagiert und die Struktur des Chord-Rings wahrt. Die Anforderungen für ein korrektes Funktionieren des Systems ist minimal: Chord funktioniert so lange korrekt, so lange jeder Knoten seinen Successor erreichen kann. Selbst wenn es nicht der richtige Successor ist, wirkt sich das zwar auf die Länge des Suchpfades aus, da die Suche evtl. einmal um den Ring weitergereicht wird, ein korrektes Auffinden des Knotens ist aber trotzdem sehr wahrscheinlich, da die Stabilisierung in regelmässigen Abständen läuft und diesen Fehler korrigiert. Bei falschen oder fehlenden Finger-Einträgen kann auf die [[#Einfache Suche \| einfache Suche]] zurückgegriffen werden. Damit ist die Korrektheit der Fingertable nur für die Perfomance ausschlaggebend. Es kann sogar gezeigt werden: <cite>Wenn zu einem Netzwerk mit N Knoten weitere N Knoten, ohne Fingertable aber mit korrekten Successor Zeigern, hinzukommen, liegt die Anzahl der Hops für eine Suche mit hoher Wahrscheinlichkeit nach wie vor bei O(log N).</cite> Daraus ergibt sich auch die Eigenschaft von Chord, dass selbst während des Stabilisierungsvorgangs Suchanfragen nicht nur korrekt, sondern auch mit sehr geringem Performanceverlust möglich sind.		Bislang wurde von einem bereits bestehenden Chord-Ring ausgegangen, dessen Struktur sich nicht ändert. In realen Anwendungen verhält sich das aber völlig anders. Chord muss mit neu hinzukommenden Knoten genauso fertig werden wie mit Knoten, die spontan ausfallen oder das System ordnungsgemäss verlassen. Dazu bietet Chord ein robustes Stabilisierungsprotokoll, das auf solche Ereignisse reagiert und die Struktur des Chord-Rings wahrt. Die Anforderungen für ein korrektes Funktionieren des Systems ist minimal: Chord funktioniert so lange korrekt, so lange jeder Knoten seinen Successor erreichen kann. Selbst wenn es nicht der richtige Successor ist, wirkt sich das zwar auf die Länge des Suchpfades aus, da die Suche evtl. einmal um den Ring weitergereicht wird, ein korrektes Auffinden des Knotens ist aber trotzdem sehr wahrscheinlich, da die Stabilisierung in regelmässigen Abständen läuft und diesen Fehler korrigiert. Bei falschen oder fehlenden Finger-Einträgen kann auf die [[#Einfache Suche \| einfache Suche]] zurückgegriffen werden. Damit ist die Korrektheit der Fingertable nur für die Perfomance ausschlaggebend. Es kann sogar gezeigt werden: <cite>Wenn zu einem Netzwerk mit N Knoten weitere N Knoten, ohne Fingertable aber mit korrekten Successor Zeigern, hinzukommen, liegt die Anzahl der Hops für eine Suche mit hoher Wahrscheinlichkeit nach wie vor bei O(log N).</cite> Daraus ergibt sich auch die Eigenschaft von Chord, dass selbst während des Stabilisierungsvorgangs Suchanfragen nicht nur korrekt, sondern auch mit sehr geringem Performanceverlust möglich sind.

	=== Stabilisierung ===		=== Stabilisierung ===

Uhermann: /* Anwendungen */

2006-03-29T09:22:09Z

Anwendungen

← Older revision		Revision as of 09:22, 29 March 2006
Line 177:		Line 177:
	[http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#] ist eine Weiterentwicklung des Chord Protokolls, an der am [http://www.zib.de Zuse Institut Berlin] gearbeitet wird. Die Gleichverteilung der Schlüssel auf Knoten in einem Chord-Ring mittels einer Basis-Hash-Funktion verhindert die Suche nach Intervallen von Schlüsselwerten, da diese auf logisch benachbarten Knoten geseichert werden müssten. ''Chord#'' eliminiert die Hashfunktion unter Beibehaltung der Perfomance von Chord und ermöglicht damit Bereichsabfragen.		[http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#] ist eine Weiterentwicklung des Chord Protokolls, an der am [http://www.zib.de Zuse Institut Berlin] gearbeitet wird. Die Gleichverteilung der Schlüssel auf Knoten in einem Chord-Ring mittels einer Basis-Hash-Funktion verhindert die Suche nach Intervallen von Schlüsselwerten, da diese auf logisch benachbarten Knoten geseichert werden müssten. ''Chord#'' eliminiert die Hashfunktion unter Beibehaltung der Perfomance von Chord und ermöglicht damit Bereichsabfragen.

	= Anwendungen =		= Anwendungen =
			==Das Cooperative File System==
			Das Cooperative File System (CFS) ist eine Dateisystem-Schicht die auf dem Chord-Protokoll aufbaut. Dateisystem-Blöcke werden an den Knoten gespeichert, denen das Chord-Protokoll ihre Schlüssel zuordnet. Damit erbt CFS die Performance, Robust heit und Load-Balancing-Eigenschaften in Bezug auf Referenzierung der Daten von Chord. Um die Robustheit auch in Bezug auf die Integrität der Daten zu sichern wird zusätzlich ein Replikationsmechanismus benutzt. Als weitere Performance-Optimierungen sind ebenfalls ein Caching-Schema, ähnlich wie bei Freenet, und "Server Selection" implementiert. Server Selection sorgt dafür, dass Anfragen im Chord-Ring nicht nur andhand der optimalen Finger-Zeiger, sondern auch Anhand von Eigenschaften des physischen Netzes geroutet werden. Führt also der momentan optimale Finger-Zeiger über einen Knoten dessen Netzwerkverbindung eine hohe Latenz aufweist, so kann mittels Server Selection auch der vorige Finger zum Weiterreichen der Anfrage benutzt werden, selbst wenn sich dadurch die Anzahl der Hops erhöht.

	= Siehe Auch =		= Siehe Auch =

Uhermann: /* Idealisierte Darstellung für "volle" Ringe */

2006-03-29T08:58:29Z

Idealisierte Darstellung für "volle" Ringe

← Older revision		Revision as of 08:58, 29 March 2006
Line 161:		Line 161:

	===Einbettung in den Chord Ring===		===Einbettung in den Chord Ring===
	====Idealisierte Darstellung für "volle" Ringe==== [[Image:DiminishedChordEinbettung.png\|left\|thumb\|350px\|Einbettung in den Chord-Ring, aus [http://iptps04.cs.ucsd.edu/papers/karger-subgroup.pdf Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks (pdf)], Seite 4]]		====Idealisierte Darstellung für "volle" Ringe==== [[Image:DiminishedChordEinbettung.png\|left\|thumb\|350px\|Einbettung in den Chord-Ring, aus [http://iptps04.cs.ucsd.edu/papers/karger-subgroup.pdf David R. Karger, Matthias Ruhl, Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks (pdf)], Seite 4]]
	Die Adressen des Chord Ringes werden für diesen Zweck als Gleitkomma-Zahlen im Intervall <math>[0,1]</math> interpretiert. Alle arithmetischen Operationen sind daher "modulo 1" zu verstehen. Außerdem gehe ich idealisierend davon aus, dass alle Adressen im Chord-Ring mit Knoten belegt sind.		Die Adressen des Chord Ringes werden für diesen Zweck als Gleitkomma-Zahlen im Intervall <math>[0,1]</math> interpretiert. Alle arithmetischen Operationen sind daher "modulo 1" zu verstehen. Außerdem gehe ich idealisierend davon aus, dass alle Adressen im Chord-Ring mit Knoten belegt sind.
	Für jede Untergruppe wird eine Startadresse <math>a_0</math> gewählt. Die Chord-Adresse jedes Knotens wird nun wiederum - für jede Gruppe - als ein Paar <math><a,b></math> ausgedrückt. Für a, b und die Chord-Adresse C des Knotens gilt dabei: <math>C = (a_0 + b/2^a)</math>. Als linkes Kind eines Knotens <math><a,b></math> wird nun der Knoten <math><a+1, 2b-1></math>, als rechtes Kind der Knoten <math><a+1, 2b></math> eingesetzt. Dabei fällt auf, dass die Adresse des rechten Kindes immer gleich der Adresse des Elternknotens ist - jeder Elternknoten ist sein eigenes rechtes Kind - und die Adresse des linken Kindes den Adressraum zwischen dem Elternknoten und dessen Geschwister in zwei gleiche Hälften teilt. Zudem überbrücken Referenzen von (linken) Kinder- auf Eltern-Knoten Zweierpotenzen im Adressraum und sind somit, unter der Annahme, dass alle Adressen mit Knoten belegt sind, Finger im Chord-Ring. Zudem kann ein Kindknoten C allein aus der Startaddresse <math>a_0</math> und seiner eigenen Adresse die Adresse seines Elternknotens berechnen, da es in dem durch die m Bits der Chord-Adresse begrenzten Zahlenraum genau ein Paar <math><a,b></math> gibt, so dass <math>C = a_0 + b/2^a</math> gilt. Aus der so gewonnenen Gruppen-Adresse lässt sich leicht der Elternknoten bestimmen, indem entweder <math><a,b> = <0,0></math> gilt und C schon der Wurzelknoten ist, oder <math><a-1, (b+1)/2></math> den nächsten ("echten") Elternknoten darstellt.		Für jede Untergruppe wird eine Startadresse <math>a_0</math> gewählt. Die Chord-Adresse jedes Knotens wird nun wiederum - für jede Gruppe - als ein Paar <math><a,b></math> ausgedrückt. Für a, b und die Chord-Adresse C des Knotens gilt dabei: <math>C = (a_0 + b/2^a)</math>. Als linkes Kind eines Knotens <math><a,b></math> wird nun der Knoten <math><a+1, 2b-1></math>, als rechtes Kind der Knoten <math><a+1, 2b></math> eingesetzt. Dabei fällt auf, dass die Adresse des rechten Kindes immer gleich der Adresse des Elternknotens ist - jeder Elternknoten ist sein eigenes rechtes Kind - und die Adresse des linken Kindes den Adressraum zwischen dem Elternknoten und dessen Geschwister in zwei gleiche Hälften teilt. Zudem überbrücken Referenzen von (linken) Kinder- auf Eltern-Knoten Zweierpotenzen im Adressraum und sind somit, unter der Annahme, dass alle Adressen mit Knoten belegt sind, Finger im Chord-Ring. Zudem kann ein Kindknoten C allein aus der Startaddresse <math>a_0</math> und seiner eigenen Adresse die Adresse seines Elternknotens berechnen, da es in dem durch die m Bits der Chord-Adresse begrenzten Zahlenraum genau ein Paar <math><a,b></math> gibt, so dass <math>C = a_0 + b/2^a</math> gilt. Aus der so gewonnenen Gruppen-Adresse lässt sich leicht der Elternknoten bestimmen, indem entweder <math><a,b> = <0,0></math> gilt und C schon der Wurzelknoten ist, oder <math><a-1, (b+1)/2></math> den nächsten ("echten") Elternknoten darstellt.

Uhermann: /* Siehe Auch */

2006-03-29T08:56:34Z

Siehe Auch

← Older revision		Revision as of 08:56, 29 March 2006
Line 184:		Line 184:
	* [http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#: Structured Overlay Network for Non-Uniform Load Distribution (pdf)]		* [http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#: Structured Overlay Network for Non-Uniform Load Distribution (pdf)]
	* [http://iptps04.cs.ucsd.edu/papers/karger-subgroup.pdf Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks (pdf)]		* [http://iptps04.cs.ucsd.edu/papers/karger-subgroup.pdf Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks (pdf)]
			* [http://pdos.csail.mit.edu/papers/cfs:sosp01/cfs_sosp.pdf Wide-area cooperative storage with CFS (pdf)]

Uhermann: /* Idealisierte Darstellung für "volle" Ringe */

2006-03-29T08:52:36Z

Idealisierte Darstellung für "volle" Ringe

← Older revision		Revision as of 08:52, 29 March 2006
Line 161:		Line 161:

	===Einbettung in den Chord Ring===		===Einbettung in den Chord Ring===
	====Idealisierte Darstellung für "volle" Ringe==== [[Image:DiminishedChordEinbettung.png\|left\|350px\|Einbettung in den Chord Ring]]		====Idealisierte Darstellung für "volle" Ringe==== [[Image:DiminishedChordEinbettung.png\|left\|thumb\|350px\|Einbettung in den Chord-Ring, aus [http://iptps04.cs.ucsd.edu/papers/karger-subgroup.pdf Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks (pdf)], Seite 4]]
	Die Adressen des Chord Ringes werden für diesen Zweck als Gleitkomma-Zahlen im Intervall <math>[0,1]</math> interpretiert. Alle arithmetischen Operationen sind daher "modulo 1" zu verstehen. Außerdem gehe ich idealisierend davon aus, dass alle Adressen im Chord-Ring mit Knoten belegt sind.		Die Adressen des Chord Ringes werden für diesen Zweck als Gleitkomma-Zahlen im Intervall <math>[0,1]</math> interpretiert. Alle arithmetischen Operationen sind daher "modulo 1" zu verstehen. Außerdem gehe ich idealisierend davon aus, dass alle Adressen im Chord-Ring mit Knoten belegt sind.
	Für jede Untergruppe wird eine Startadresse <math>a_0</math> gewählt. Die Chord-Adresse jedes Knotens wird nun wiederum - für jede Gruppe - als ein Paar <math><a,b></math> ausgedrückt. Für a, b und die Chord-Adresse C des Knotens gilt dabei: <math>C = (a_0 + b/2^a)</math>. Als linkes Kind eines Knotens <math><a,b></math> wird nun der Knoten <math><a+1, 2b-1></math>, als rechtes Kind der Knoten <math><a+1, 2b></math> eingesetzt. Dabei fällt auf, dass die Adresse des rechten Kindes immer gleich der Adresse des Elternknotens ist - jeder Elternknoten ist sein eigenes rechtes Kind - und die Adresse des linken Kindes den Adressraum zwischen dem Elternknoten und dessen Geschwister in zwei gleiche Hälften teilt. Zudem überbrücken Referenzen von (linken) Kinder- auf Eltern-Knoten Zweierpotenzen im Adressraum und sind somit, unter der Annahme, dass alle Adressen mit Knoten belegt sind, Finger im Chord-Ring. Zudem kann ein Kindknoten C allein aus der Startaddresse <math>a_0</math> und seiner eigenen Adresse die Adresse seines Elternknotens berechnen, da es in dem durch die m Bits der Chord-Adresse begrenzten Zahlenraum genau ein Paar <math><a,b></math> gibt, so dass <math>C = a_0 + b/2^a</math> gilt. Aus der so gewonnenen Gruppen-Adresse lässt sich leicht der Elternknoten bestimmen, indem entweder <math><a,b> = <0,0></math> gilt und C schon der Wurzelknoten ist, oder <math><a-1, (b+1)/2></math> den nächsten ("echten") Elternknoten darstellt.		Für jede Untergruppe wird eine Startadresse <math>a_0</math> gewählt. Die Chord-Adresse jedes Knotens wird nun wiederum - für jede Gruppe - als ein Paar <math><a,b></math> ausgedrückt. Für a, b und die Chord-Adresse C des Knotens gilt dabei: <math>C = (a_0 + b/2^a)</math>. Als linkes Kind eines Knotens <math><a,b></math> wird nun der Knoten <math><a+1, 2b-1></math>, als rechtes Kind der Knoten <math><a+1, 2b></math> eingesetzt. Dabei fällt auf, dass die Adresse des rechten Kindes immer gleich der Adresse des Elternknotens ist - jeder Elternknoten ist sein eigenes rechtes Kind - und die Adresse des linken Kindes den Adressraum zwischen dem Elternknoten und dessen Geschwister in zwei gleiche Hälften teilt. Zudem überbrücken Referenzen von (linken) Kinder- auf Eltern-Knoten Zweierpotenzen im Adressraum und sind somit, unter der Annahme, dass alle Adressen mit Knoten belegt sind, Finger im Chord-Ring. Zudem kann ein Kindknoten C allein aus der Startaddresse <math>a_0</math> und seiner eigenen Adresse die Adresse seines Elternknotens berechnen, da es in dem durch die m Bits der Chord-Adresse begrenzten Zahlenraum genau ein Paar <math><a,b></math> gibt, so dass <math>C = a_0 + b/2^a</math> gilt. Aus der so gewonnenen Gruppen-Adresse lässt sich leicht der Elternknoten bestimmen, indem entweder <math><a,b> = <0,0></math> gilt und C schon der Wurzelknoten ist, oder <math><a-1, (b+1)/2></math> den nächsten ("echten") Elternknoten darstellt.

Uhermann: /* Diminished Chord */

2006-03-27T12:57:34Z

Diminished Chord

@@ Line 147: / Line 147: @@
 = Erweiterungen =
 ==Diminished Chord==
 ==Chord#==
 [http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#] ist eine Weiterentwicklung des Chord Protokolls, an der am [http://www.zib.de Zuse Institut Berlin] gearbeitet wird. Die Gleichverteilung der Schlüssel auf Knoten in einem Chord-Ring mittels einer Basis-Hash-Funktion verhindert die Suche nach Intervallen von Schlüsselwerten, da diese auf logisch benachbarten Knoten geseichert werden müssten. ''Chord#'' eliminiert die Hashfunktion unter Beibehaltung der Perfomance von Chord und ermöglicht damit Bereichsabfragen.

Tuschl: /* Siehe Auch */

2006-03-06T17:10:20Z

Siehe Auch

← Older revision		Revision as of 17:10, 6 March 2006
Line 153:		Line 153:

	= Siehe Auch =		= Siehe Auch =
	* [http://pdos.lcs.mit.edu/chord Chord]		* [http://pdos.lcs.mit.edu/chord Official Chord Homepage]
			* [http://www.pdos.lcs.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications (pdf)]
	* [http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#]		* [http://www.zib.de/CSR/Publications/2005-schuett-zr0540.pdf Chord#: Structured Overlay Network for Non-Uniform Load Distribution (pdf)]
			* [http://iptps04.cs.ucsd.edu/papers/karger-subgroup.pdf Diminished Chord: A Protocol for Heterogeneous Subgroup Formation in Peer-to-Peer Networks (pdf)]