Vorlesung 30.11.2010: Greedy-Routing in CHORD

Moderator: Peer-to-peer und Grid Computing

Benutzeravatar
blackcomb
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 1. Okt 2007 15:48
Wohnort: Darmstadt

Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von blackcomb »

Hallo,

ich konnte am 30.11. nicht in der Vorlesung sein. Prof. Strufe hat, wie in der Aufzeichnung zu hören, bei Folie 14 an der Tafel ein Beispiel dazu gegeben, warum CHORD nicht immer den kürzesten Pfad findet. Hat vielleicht jemand mitgeschrieben und könnte das Beispiel kurz skizzieren? (Oder auch ein analoges eigenes Beispiel...)

Danke schön!

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von olg »

Hab mal schnell das Beispiel von der Tafel (nur aus dem Gedächtnis, glaube aber es passt so) nachgeplottet. (Fingereinträge = grüne Pfeile) Zur Vereinfachung sind die Nodes als 1-6 bezeichnet. In diesem Beispiel
wären die Finger natürlich viel zahlreicher, aber gehen wir mal davon aus dass genau diese Finger vorliegen


Bild


Wenn Node 1 zu 6 routen will, nimmt es die nächstmögliche Node zu 6. Er routet also über seinen Finger nach 4. Von Node 4 kann er dann nur über 5 nach 6 routen, also insgesamt drei Schritte.

Wenn Node 1 stattdessen nach 3 routen würde, käme es in zwei Schritten zu 6.

Viele Grüße,
Oliver
Zuletzt geändert von olg am 5. Dez 2010 09:31, insgesamt 1-mal geändert.
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

Benutzeravatar
BadTaste
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 181
Registriert: 18. Apr 2005 16:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von BadTaste »

Korrekt, sehr gut erklärt :D

Benutzeravatar
blackcomb
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 1. Okt 2007 15:48
Wohnort: Darmstadt

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von blackcomb »

Ok, vielen Dank!

Dann entspricht die Nummerierung der Knoten hier aber nicht ihrer ID im Chord-ID-Space, oder? Sonst müsste 1 doch eigentlich einen Finger zu Knoten 5 (dem viertnächsten Knoten), aber nicht zu Knoten 4 besitzen...

Mit folgendem Beispiel konnte ich mir aber erklären, dass das Routing auch mit "korrekten" IDs nicht optimal ist:
  • ID-Space [0, 7]
    Knoten bei 0, 1, 4, 5, 7
    Routing von 1 nach 0: 1 --> 5 --> 7 --> 0
    besser wäre: 1 --> 4 --> 0 (Der Link 1 --> 4 existiert, weil Knoten 3 nicht existiert und deshalb succ(3) = 4.)

Benutzeravatar
BadTaste
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 181
Registriert: 18. Apr 2005 16:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von BadTaste »

Hi,
das angegebene Beispiel hatte ja auch für einige Knoten keine Finger angegeben, es sollte also kein perfektes / korrektes Beispiel sein.
Es ging in dem Beispiel nur darum, sich klar zu machen, dass der Weg, der von einem Routing Verfahren gefunden wird, hier das unidirectional Greedy Routing in Chord, nicht immer optimal ist. Die "optimalen" (in unserem Fall kürzesten = wenigste Hops) Pfade sind eben meist nur zu finden, wenn man globales Wissen annimmt.

Benutzeravatar
aiQon
Windoof-User
Windoof-User
Beiträge: 32
Registriert: 9. Dez 2010 18:23
Wohnort: Darmstadt

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von aiQon »

olg hat geschrieben:Hab mal schnell das Beispiel von der Tafel (nur aus dem Gedächtnis, glaube aber es passt so) nachgeplottet. (Fingereinträge = grüne Pfeile) Zur Vereinfachung sind die Nodes als 1-6 bezeichnet. In diesem Beispiel
wären die Finger natürlich viel zahlreicher, aber gehen wir mal davon aus dass genau diese Finger vorliegen


Bild


Wenn Node 1 zu 6 routen will, nimmt es die nächstmögliche Node zu 6. Er routet also über seinen Finger nach 4. Von Node 4 kann er dann nur über 5 nach 6 routen, also insgesamt drei Schritte.

Wenn Node 1 stattdessen nach 3 routen würde, käme es in zwei Schritten zu 6.

Viele Grüße,
Oliver
was hast du denn zum plotten genommen? sieht gut aus :D
weeks of coding can save hours of planing

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von olg »

norm. graphviz, aber da spinnte die neue version in dem moment rum, daher hab ich's in omnigraffle (mac) gezeichnet
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

Benutzeravatar
BadTaste
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 181
Registriert: 18. Apr 2005 16:40
Wohnort: Darmstadt
Kontaktdaten:

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Beitrag von BadTaste »

Ja, OmniGraffle rockt, das nehme ich auch immer für Graphen (z.B. für die Vorlesungsfolien und die Übung :mrgreen:)

Antworten

Zurück zu „Peer-to-Peer und Grid Computing“