Seite 1 von 1

Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 4. Dez 2010 14:19
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!

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 4. Dez 2010 20:00
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

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 4. Dez 2010 23:42
von BadTaste
Korrekt, sehr gut erklärt :D

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 5. Dez 2010 12:37
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.)

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 5. Dez 2010 13:12
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.

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 17. Dez 2010 10:19
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

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 17. Dez 2010 11:09
von olg
norm. graphviz, aber da spinnte die neue version in dem moment rum, daher hab ich's in omnigraffle (mac) gezeichnet

Re: Vorlesung 30.11.2010: Greedy-Routing in CHORD

Verfasst: 17. Dez 2010 11:12
von BadTaste
Ja, OmniGraffle rockt, das nehme ich auch immer für Graphen (z.B. für die Vorlesungsfolien und die Übung :mrgreen:)