Verteilte Algorithmen und Datenstrukturen Kapitel 7: Dynamische Netzwerke für Routing Christian Scheideler WS 2009

Verteilte Algorithmen und Datenstrukturen

Kapitel 7: Dynamische Netzwerke für Routing

Christian Scheideler

WS 2009

Übersicht

Problem: wie erhalten wir dynamische Netzwerke, in denen zeit- und speicher-effizient (d.h. idealerweise in logarithmischer Zeit ohne Verwendung von Routingtabellen) geroutet werden kann?

Zwei grundlegende Methoden:• Lokal-konsistente Methode• Kontinuierlich-diskrete Methode

Grundlegende Methoden

Lokal-konsistente Methode:• reaktive Methode zur Stabilisierung von Netzen• geeignet für Netze mit relativen Regeln• Beispiel: sortierte Liste, in der jeder Knoten mit nächstem

Vorgänger und Nachfolger verbunden sein soll

Kontinuierlich-diskrete Methode:• proaktive Methode zur Erhaltung von Netzen• geeignet für Netze mit absoluten Regeln• Beispiel: de Bruijn Graph, in der jeder Knoten x∈[0,1] mit

Knoten an Positionen x/2 und (1+x)/2 verbunden sein soll (mehr Details folgen)

Lokal-konsistente Methode

Selbststabilisierende Liste:

5

12

20

2

8

2 5 8 12 20


Regel für die Liste: Linearisierung

Jeder Knoten macht das folgende:

12853 14 16

12853 14 16

temporär

stabil (d.h. lokal konsistent)


Probleme:• Liste zu fragil für verteilte Systeme• Durchmesser sehr hoch

Alternativen:• Selbststabilisierender Kreis• Delaunay Graphen• De Bruijn Graphen• Skip Graphen


Selbststabilisierender Kreis:• Linearisierung wie gehabt.• Hat Knoten v keinen linken (bzw. rechten) Nachbarn, hält

v zusätzlich Verbindung zum entferntesten rechten (bzw. linken) Nachbarn und erzeugt eine markierte Rückwärtskante zu sich.

• Hat Knoten w eine markierte Rückwärtskante zu einem Knoten v mit v<w (bzw. v>w) und einen Nachbarn w´>w (bzw. w´<w), schickt w v den am weitesten entfernten solchen Nachbarn w´ zu. Markierte Kanten werden sonst in der Lineari-sierung behandelt wie alle anderen Kanten auch.





Delaunay Graph:

A

B

Delaunay Graph

Gegeben: beliebige Punktmenge V∈ℝ2

Verbindungsregel: verbinde alle Paare v,w∈V, für die es einen Kreis K durch v und w gibt, für den kein Punkt in V innerhalb von K ist (aber Punkte dürfen auf K liegen!)

Beispiele:

v

w

Kante {v,w} nicht in E

v

w

Kante {v,w} in E

Delaunay Graph

Spezialfälle:

Delaunay Graph

V nichtdegeneriert:• keine drei Punkte auf einer Linie• keine vier Punkte auf einem Kreis

Beobachtung: Für nichtdegenerierte Punktmengen V ist der Delaunay Graph eine planare Triangulierung von V.

Delaunay Graph

Einfache Berechnung des Delaunay Graphen für eine Knotenmenge V∈ℝ2 :

1. Für alle Knotenpaare {u,v} aus V:falls der (eindeutige) Kreis durch u und v mit Durchmesser ||u,v|| keinen anderen Knoten aus V enthält, dann füge die Kante {u,v} hinzu

2. Für alle Knotentripel {u,v,w} aus V, die nicht auf einer Gerade liegen: falls der (eindeutige) Kreis durch u, v und w keinen anderen Knoten aus V enthält, dann füge die Kanten {u,v}, {v,w} und {w,u} hinzu

Delaunay Graph

Test für 1.:

Knoten w innerhalb genau dann, wenn

||u,w||2+||w,v||2 < ||u,v||2.

uv

w

Delaunay Graph

Test für 2.:

Knoten z innerhalb genau dann, wenn

uv

w

z

det

xu yu xu2+yu

2 1

xv yv xv2+yv

2 1

xw yw xw2+yw

2 1

xz yz xz2+yz

2 1

> 0

Delaunay Graph

Effiziente Berechnung des Delaunay Graphen für eine

Knotenmenge V∈ℝ2 : divide-and-conquer• sortiere die Punkte in V aufsteigend gemäß ihrer x-Koordinate (und bei gleicher

x-Koordinate nach y-Koordinate)• rufe createDT(V) auf

Algorithmus createDT(V):• falls |V|≤3 dann return trivialDT(V)• L:= linke Hälfte der Knoten in V• R:= rechte Hälfte der Knoten in V• DT1:=createDT(L); DT2:=createDT(R)• return stitchDT(DT1,DT2)

Details z.B. in „Geoff Leach. Improving worst-case optimal Delaunay triangulation algorithms, 4th Canadian Conf. on Computational Geometry, 1992“.

Delaunay Graph

• ||u,v||: Euklidische Distanz zwischen u und v

Definition 7.1: Ein Graph G=(V,E) über einer Punktmenge heißt Euklidischer Spanner, falls es eine Konstante c gibt und für jedes Paar v,w einen Weg p=(v=u1,u2,...,uk=w) von v nach w in G gibt mit

||p|| = Si ||ui,ui+1|| ≤ c||v,w||

Theorem 7.2: Der Delaunay Graph zu V ist ein Euklidischer Spanner mit c≤2,42.

Beweis: recht aufwändig und daher nicht Teil der Vorlesung

Delaunay Graph

Problem: wie finde ich einen guten Pfad von s nach t in beliebigen Delaunay Graphen?

Greedy Strategien:• Distanz Routing: Knoten v bewegt Packet

P zu dem Knoten w∈N(v) mit minimaler Distanz ||w,t||

v

w

t

Delaunay Graph


Greedy Strategien:• Kompass Routing: Knoten v bewegt

Packet P zu dem Knoten w∈N(v) mit minimalem Winkel a=∡tvw

v

w ta

Delaunay Graph


Greedy Strategien:• Distanz Kompass Routing: Knoten v bestimmt zunächst

die Knoten w,w´∈N(v) mit kleinstem Winkel mit und gegen den Uhrzeigersinn zu t und routet Packet P zu dem Knoten w´´∈{w,w´} mit minimaler Distanz ||w´´,t||

v

w

t

w´

Delaunay Graph

Definition 7.3: Eine Routingstrategie ist c-kompetitiv für einen Graph G, falls es für jedes Paar v,w einen Weg p=(v=u1,u2,...,uk=w) von v nach w in G gibt mit

||p|| = Si ||ui,ui+1|| ≤ cdG(v,w)

wobei dG(v,w) die Euklidische Länge eines kürzesten Weges von v und w in G ist.

Theorem 7.4:• Distanz Routing und Kompass Routing finden einen Pfad zum Ziel für

beliebige Delaunay Graphen, aber nicht für beliebige planare Triangulierungen.

• Distanz Kompass Routing findet einen Pfad zum Ziel für beliebige planare Triangulierungen.

• Distanz Routing und Kompass Routing sind in Delaunay Graphen im Allgemeinen nicht c-kompetitiv für beliebige Konstanten c.

Delaunay Graph

Offenes Problem: gibt es einen Greedy Algorithmus, der c-kompetitiv für beliebige Delaunay Graphen ist?

Es gibt alternative c-kompetitive Routing Strategien, aber diese sind „unschön“, da sie manchmal den Graph (über Kreise oder Backtracking) explorieren müssen.

Weiterhin zu lösen: wie erhalte ich einen Delaunay Graphen aus einem beliebigen Graphen.

Dynamischer Delaunay Graph

Stabilisierungsregel:

v

temporär

stabil

Weiterleitung wie im Distanz Kompass Routing


N(v): aktuelle Nachbarschaft von Knoten v (inklusive v)

Stabilisierungsregel:• v berechnet Delaunay Graph G=(N(v),E(v)) zu N(v)• Alle Knoten w mit (v,w)∈E(v): stabil• D(v): Menge der stabilen Nachbarn• v schlägt alle Kanten (u,w)∈E(v) vor mit u,w∈{v}∪D(v).• Für alle w∈N(v)\D(v): v gibt Kante (v,w) an denjenigen Knoten u∈D(v)

weiter, der beim Distanz Kompass Routing für die Nachbarschaft D(v) und Zielknoten w verwendet würde (bei Knoten u und u´ mit gleicher minimaler Distanz wird ein beliebiger von diesen beiden gewählt)

Verallgemeinert Linearisierungsregel zu 2 Dimensionen.


Theorem 7.5: Für eine beliebige Punktmenge V∈ℝ2 und einen beliebigen schwach zusammenhängenden Anfangsgraphen G=(V,E) benötigt die Stabilisierungsregel maximal O(n3) Kommunikationsrunden, bis der Delaunay Graph erreicht ist.

Beweis:• Es ist nicht schwer einzusehen, dass der Delaunay Graph ein stabiler

Graph für unsere Regel ist.• Über alle Triangulierungen ist nur der Delaunay Graph stabil.• Weiterhin gefährdet die Regel nicht den (schwachen) Zusammenhang.• Beweis der Konvergenz: über Potenzialfunktion F, die die Anzahl der

Knoten w∉N(v) zählt, die die aktuelle Delaunay Nachbarschaft N(v) von v verbessern würden.

• Der gesamte Beweis ist recht aufwändig und wird hier nicht beschrieben.


Anwendung: Systeme, in denen ein Knoten einfach und schnell seine geographisch nächsten Nachbarn erreichen können soll.

Delaunay Graphen auch anwendbar für ℝ3: statt Kreisen werden dann Kugeln für die Verbindung von Knoten verwendet.




De Bruijn Graph

• Knoten: (x1,…,xd) {0,1}d

• Kanten: (x1,…,xd) (0,x1,…,xd-1) (1,x2,…,xd-1)

00

01

10

11 000

100 110

111

001

010 101

011

De Bruijn Graph

Routing im de Bruijn Graph: Bitanpassung

Anzahl Hops: maximal log n bei n Knoten.

Dynamischer de Bruijn Graph:• Weise jedem Knoten v einen zufälligen Punkt

in [0,1) zu.• Damit ist bei beliebiger Join-Leave Folge (die

unabhängig von den gewählten Punkten ist) die Punktmenge V gleichverteilt über [0,1).

Dynamischer de Bruijn Graph

Klassischer d-dim. de Bruijn Graph G=(V,E):• V = {0,1}d

• E = { {x,y} | x=(x1,…,xd), y=(b,x1,…,xd-1), b∈{0,1} beliebig}

• Betrachte (x1,…,xd) als 0.x1 x2…xd ∈ [0,1), d.h. 0.101 = 1(1/2) + 0(1/4) + 1(1/8)

• Setze d


Klassischer d-dim. de Bruijn Graph G=(V,E)• V = {0,1}d

• E = { {x,y} | x=(x1,…,xd), y=(b,x1,…,xd-1), b∈{0,1} beliebig}

Ergebnis für d:• V = [0,1)• E = { {x,y}∈[0,1)2 | y=x/2, y=(1+x)/2 }


Kontinuierlicher de Bruijn Graph:• V = [0,1)• E = { {x,y}∈[0,1)2 | y=x/2, y=(1+x)/2 }

Verwendung für lokal-konsistente Methode:• Jeder Knoten v simuliert drei Knoten mit Punkten v,

v/2 und (1+v)/2.• Jeder Knoten v führt eine erweiterte Lineari-

sierungsregel mit diesen drei Punkten durch, um eine sortierte Liste über all diese Punkte zu formen.


Erweiterte Linearisierungsregel:• Knoten v verwaltet drei Punkte v, v/2 und (1+v)/2 mit

unabhängigen Nachbarschaften, auf die v die Linearisierungsregel anwendet.

• Sollte ein Punkt x∈{v,v/2,(1+v)/2} keinen linken bzw. rechten Nachbarn kennen, der aber einem anderen Punkt bekannt ist, dann wird sich x zusätzlich mit dem nächsten dieser Nachbarn verbinden.

vv/2y vv/2y

x





vv/2 y

x

y´ vv/2 y

x

y´





vv/2

x

vv/2

x

keineNachbarn


Theorem 7.6: Die erweiterte Linearisierungs-regel transformiert jeden schwach zusam-menhängenden Graphen in O(n2) Runden in eine doppelt verkettete sortierte Liste über alle Punkte.

Beweis: ähnlich zum einfachen Linearisierungs-beweis.

Vermutung: Konvergenzzeit viel schneller (z.B. mit zusätzlicher Regel, dass ein Nachbar w immer an den nächstliegenden der Punkte {v,v/2,(1+v)/2} zur Linearisierung verwiesen wird)

Problem: wie können wir in so einer Liste effizienter als in Zeit O(n) routen?


Routing im klassischen de Bruijn Graph:(x1,...,xd) (yd,x1,...,xd-1) (yd-1,yd,x1,...,xd-2) ... (y1,...,yd)

Routing im dynamischen de Bruijn Graph:• (x1,x2,...) (yd,x1,x2,...) möglich, ohne den Knoten zu wechseln, da

(yd,x1,x2,...) entweder x/2 oder (1+x)/2 ist.

• Dann aber Wechsel auf Knoten notwendig mit Originalpunkt (yd,x1,x2,...). Dazu reicht die Suche entlang der linearen Liste.

x

x

simulierter KnotenOriginalknoten

falls Idealpunkt rechts



Routing im dynamischen de Bruijn Graph:• (x1,x2,...) (yd,x1,x2,...) möglich, ohne den Knoten zu wechseln, da

(yd,x1,x2,...) entweder x/2 oder (1+x)/2 ist.

• Dann aber Wechsel auf Knoten notwendig mit Originalpunkt (yd,x1,x2,...). Dazu reicht die Suche entlang der linearen Liste.

x

x

simulierter KnotenOriginalknoten

falls Idealpunkt links


Beispiel:• klassisch:

• dynamischer de Bruijn Graph:0 1Start

0 1Start

Idealpunkte für Routing imdynamischen de Bruijn Graph



Routing im dynamischen de Bruijn Graph:• für jeden Schritt im klassischen de Bruijn Graphen zwei Phasen:

(1) ein virtueller Schritt und (2) Suche nach nächstem Originalknoten in Richtung der Idealposition

• am Ende (d.h. nach d Phasen), Suche nach Zielknoten entlang Liste

Lemma 7.7: Die Anzahl der Suchschritte pro Phase ist erwartungs-gemäß konstant.

Beweis: Übung.

Theorem 7.8: Das Routing im dynamischen de Bruijn Graph benötigt erwartungsgemäß O(log n) Schritte, um von einem Startknoten zu einem beliebigen Zielknoten zu gelangen (sofern die Knoten eine konstante Approximation von n haben).



Routing im dynamischen de Bruijn Graph:• für jeden Schritt im klassischen de Bruijn Graphen zwei Phasen:

(1) ein virtueller Schritt und (2) Suche nach nächstem Originalknoten in Richtung der Idealposition

• am Ende (d.h. nach d Phasen), Suche nach Zielknoten entlang Liste

Lemma 7.7: Die Anzahl der Suchschritte pro Phase ist erwartungs-gemäß konstant.

Beweis: Übung.

Theorem 7.8: Das Routing im dynamischen de Bruijn Graph benötigt erwartungsgemäß O(log n) Schritte, um von einem Startknoten zu einem beliebigen Zielknoten zu gelangen (sofern die Knoten eine konstante Approximation von n haben).

Problem: Wie kann d(=log n) ermittelt werden?


Problem: finde gute Abschätzung d´ von d=log n, wobei n die aktuelle Anzahl der Peers im System ist.

Idee: Startknoten s betrachtet nächsten Nachfolger v entlang der sortierten Liste.

Man kann zeigen, dass für alle Startknoten s gilt: • |s-v|∈[1/n3,3(log n)/n] mit Wahrscheinlichkeit mindestens 1-

1/n. • In diesem Fall ist -log|s-v|∈[3log n, (log n)/2]• Setzen wir also d´=-2log|s-v|, dann ist d´≥log n und d

´=Q(log n), was für unser Routing reicht. D.h. wir können d´ für die Simulation des klassischen de Bruijn Routings im dynamischen de Bruijn Graph verwenden.


Anwendung: Peer-to-Peer DNS System• Jeder Peer v hat Namen name(v)• Pseudozufälliger Punkt des Peers in [0,1):

h(name(v)), wobei h eine pseudozufällige (z.B. kryptographische) Hashfunktion ist

• Damit Lookup(name) effizient realisierbar, das für einen Benutzernamen die IP-Adresse zurückliefert, indem eine Anfrage zu h(name) geschickt wird.




Skip Graph

• Jeder Knoten v hat einen beliebigen eindeutigen Namen v.id und eine zufällige Bitkette v.rs

• prei(v): erste i Bits von v.rs

Skip Graph Regel:

Für jeden Knoten v und jedes iIN0:• v hat eine Kante zum nächsten Nachfolger

und Vorgänger w (bezüglich .id ) mit prei(w) = prei(v)

Skip Graph

Knoten v mit v.rs=0…

Knoten v mit v.rs=1…

max .idmin .id

Skip Graph

Hierarchische Sicht: sortierte Listen von Knoten mit gemeinsamem Präfix.

0 1

00 01 10 11

000 001

(log n) Grad, (log n) Durchmesser, (1) Expansion mit hoher Wkeit

Skip Graph

Problem: Original Skip Graph erlaubt keine lokale Überprüfung der korrekten Topologie.

Aus Sicht von v und w sind Skip Graph Regeln erfüllt.

10..00.. 01.. 11..11..11..10.. 00..

wv

01.. 10..

Skip+ Graph

Problem: Original Skip Graph erlaubt keine lokale Überprüfung der korrekten Topologie

Lösung: erweitere Verbindungen

Für jeden Knoten v sei• succi(v,b), b{0,1}: nächster Nachfolger von v mit Präfix

prei(v)b• predi(v,b), b{0,1}: nächster Vorgänger von v mit Präfix prei(v)b• rangei(v)=[minb predi(v,b), maxb succi(v,b)]

v hat Kanten zu allen Knoten wrangei(v) mit prei(w) = prei(v)

Resultat: SKIP+

Skip Graph: rangei(v)=[predi(v),succi(v)] Skip Graph: rangei(v)=[predi(v),succi(v)]

Skip+ Graph

(log n) Grad, (log n) Durchmesser, (1) Expansion mit hoher Wkeit

Dynamischer Skip+ Graph

• Kante (u,v) stabil: SKIP+ Kante aus der Sicht von u

• sonst heißt (u,v) temporär• flag F(v): Indikator in u, ob (u,v) stabil

Regel 1a: erzeuge Rückwärtskanten

u v

stabil

u v


Regel 1b/c: erzeuge neue stabile Kanten

Bedingungen:• u muss periodisch Ranges seiner Nachbarn

erfragen, damit 1b/c durchführbar ist.

uv

w

w.id rangei(v)

uv

w

b c


Regel 2: leite temporäre Kanten weiter

Bedingungen:• Es gibt kein i mit prei(u)=prei(v) und

v∈rangei(u).

• Sei i der maximale Wert, für den prei(u)=prei(v). Dann muss prei+1(w)=prei+1(v) für den Knoten w sein, an den v weitergeleitet wird. So ein Knoten w existiert immer, da v∉rangei(u).

uv

w (längerer Präfix Match)

temp

stabil

uv

w


Regel 3a: erzeuge allesWenn u seine stabile Nachbarschaft verändert (d.h. eine vorher stabile Kante zu einem Knoten v ist jetzt temporär, was über F(v) erkennbar ist), dann initiiert u insert(v,w) für alle Nachbarn v,w von u

u

v1 v2 v3 vk

…

u

v1 v2 v3 vk

…

Knoten formen Clique


Regel 3b: linearisiereu verbindet alle stabilen Nachbarn in jeder Ebene i zu einer sortierten Liste.

u

v1 v2 v3 vk

stabil

…

u

v1 v2 v3 vk

stabl

…

stabil


Jeder Knoten u befolgt 6 Regeln:• Regel 1a: erzeuge Rückwärtskanten zu u• Regeln 1b und 1c: führe stabile Kanten

zwischen Nachbarn von u ein• Regel 2: leite temporäre Kanten weiter• Regel 3a: erzeuge Kanten zwischen allen

Nachbarpaaren, wenn sich stabile Nachbarschaft verändert

• Regel 3b: linearisiere stabile Nachbarschaft


Theorem 7.9: Für jeden schwach zusammen-hängenden Graph etablierenden die Regeln den Skip+ Graph in O(log2 n) Runden m.h.W.

Beweis: SEHR aufwändig

Theorem 7.10: Eine Join oder Leave Operation im perfekten SKIP+ Graph erfordert maximal O(log4 n) Arbeit.

Beweis: aufwändig


Beweis von Theorem 7.9:• Bottom-up Phase: Zusammenhangskom-

ponenten formen sich für jeden Präfix

0 1

00 01 10 11

000 001


Beweis von Theorem 7.9:• Top-down Phase: Komp. werden sortiert


Beweis von Theorem 7.10:

Join Ereignis: neuer Knoten u mit Kante (u,v)• Regel 1a: Kante (v,u)• Regel 2: u wird weitergeleitet• Regeln 1abc und 3ab: integrieren u an richtiger Position

Leave Ereignis: Knoten u verlässt Skip+• nur alte Nachbarn von u müssen stabile Nachbarschaft

anpassen• das geschieht über Regeln 1abc und 3ab.

Vermutung: Regel 3a nicht notwendig.


Fazit:• Kann zu Regeln für selbststabilisierende

Netzwerke führen.• Nicht für alle Netzwerke anwendbar, da

manche nicht lokal auf korrekte Topologie überprüfbar sind (z.B. Skip Graphen)

Übersicht

Problem: wie erhalten wir dynamische Netzwerke, in denen zeit- und speicher-effizient (d.h. idealerweise in logarithmischer Zeit ohne Verwendung von Routingtabellen) geroutet werden kann?

Zwei grundlegende Methoden:• Lokal-konsistente Methode• Kontinuierlich-diskrete Methode

Übersicht

Kontinuierlich-diskrete Methode:• Grundlegendes Prinzip• Moderierte Netze vs. Peer-to-Peer Netze

• Selbststabilisierung

Moderator

Kontinuierlich-diskrete Methode

• V: Menge der Peers, U: virtueller Raum• Jedem v∈V sei eine Region ∅≠R(v)⊆U zugewiesen• Sei F eine Familie von Funktionen f:UU• {v,w} Kante ⇔ [R(v)∪F(R(v))]∩[R(w)∪F(R(w))]≠∅

Kanten beidseitig gerichtet da symmetrisch


• V: Menge der Peers, U: virtueller Raum• Jedem v∈V sei eine Region ∅≠R(v)⊆U zugewiesen• Sei F eine Familie von Funktionen f:UU• Sei EF={ {x,y} | x,y∈U, ∃f∈F: y=f(x)}

• Sei EF(V)={ {v,w} | v,w∈V mit [R(v)∪F(R(v))]∩[R(w)∪F(R(w))]≠∅}

• Für S⊆U sei N(S)={ y∈U\S | ∃x∈S: {x,y}∈EF }

• (U,EF) ist zusammenhängend, falls für alle S⊂U N(S)≠∅ ist.

Lemma 7.10: Falls (U, EF) zusammenhängend ist und Uv

R(v)=U, dann ist auch (V,EF(V)) zusammenhängend.


Lemma 7.10: Falls (U, EF) zusammenhängend ist und Uv R(v)=U, dann ist auch (V,EF(V)) zusammenhängend.

Beweis:• Angenommen, (U, EF) ist zusammenhängend und Uv R(v)=U, aber

(V,EF(V)) ist nicht zusammenhängend.• Dann gibt es eine Menge V´⊂V, so dass keine Kante V´ verlässt. • Sei R´= Uv∈V´R(v) und R´´=Uv∈V\V´ R(v).• Ist R´=U, dann ist R´´⊆R´, d.h. es muss ein v∈V´ und w∈V\V´ geben

mit R(v)∩R(w)≠∅. Damit wäre aber {v,w}∈EF(V), ein Widerspruch.• Ist R´⊂U, dann ist N(R´)≠∅ und N(R´)⊆R´´, d.h. es muss ein v∈V´

und w∈V\V´ geben mit F(R(v))∩R(w)≠∅. Damit wäre aber {v,w}∈EF(V), was auch zum Widerspruch führt.


Routingstrategie: simuliere Routing im kontinuierlichen Graphen im diskreten Graphen

Konkret:• Sei p=(x1,x2,...,xk) Pfad in (U,EF) mit xi+1=f(xi) für

ein f∈F.• Für jedes i gibt es ein vi∈V, so dass xi∈R(vi).

• Wegen der Verbindungsregel ist damit q=(v1,v2,...,vk) ein Pfad in (V,EF(V)).


Grundlegende Fragen:• Wie bilde ich Peers auf Regionen ab?• Welche Familie F sollte ich wählen?


• Nimm eine klassische Netzwerkfamilie(Hypercube, de Bruijn graph,…)

• Konvertiere sie in eine kontinuierliche Form durch Umwandlung der Knotenmenge in U und der Kantenmenge in eine Funktions-menge F

• Bilde dann die Peers auf Regionen in U ab, um mit den Regeln oben einen diskreten Graphen zu erhalten.

Hypercube

Klassischer Hypercube:• V: Knoten mit Labeln (x1,…,xd)∈{0,1}d

• E: i: (x1,…,xd)(x1,..,1-xi,..,xd)

Kontinuierliche Version des Hypercube:• Interpretiere (x1,…,xd) als z=i xi/2i

• d: U=[0,1)• Familie F: i>0 sei

fi+(x) = x+1/2i, fi

-(x) = x-1/2i (mod 1)

Hypercube

Kontinuierlicher Hypercube:• U=[0,1)• F: i>0 sei fi

+(x) = x+1/2i, fi-(x) = x-1/2i

(mod 1)

Routingstrategie für zwei Punkte x,y∈[0,1):

(x1,x2,x3,…) (y1,x2,x3,…) (y1,y2,x3,…) (y1,y2,y3,x4,…) …

Hypercube

Routingstrategie für zwei Punkte x,y∈[0,1): (x1,x2,x3,…) (y1,x2,x3,…) (y1,y2,x3,…) (y1,y2,y3,x4,…) …

Resultat: • in k Schritten bis auf 1/2k Abstand am Ziel• Sind (y1,…,yk,xk+1,…) und y beide in der

Region R(v) eines Knotens v, terminiert das Routing im diskreten Fall

De Bruijn Graph

Klassischer de Bruijn graph:• V: Knoten mit Labeln (x1,…,xd)∈{0,1}d

• E: (x1,…,xd) (0,x1,…,xd-1), (1,x1,…,xd-1)

Kontinuierlicher de Bruijn graph:• Interpretiere (x1,…,xd) as z=i xi/2i

• d: U=[0,1)• F: f0(x) = x/2, f1(x) = (1+x)/2

De Bruijn Graph

Kontinuierlicher de Bruijn graph:• U=[0,1)• F: f0(x) = x/2, f1(x) = (1+x)/2

Routingstrategie für zwei Punkte x,y∈[0,1): (x1,x2,x3,…) (z1,x1,x2,…) (z2,z1,x1,…) (z3,z2,z1,x1,…) … (z3,z2,z1,y1,…) (z2,z1,y1,…) (z1,y1,y2,…) (y1,y2,y3,…)für ein geeignetes Zwischenziel z∈[0,1)(zufällig gewählt: ähnlich zu Valiants Trick)

Zur Erinnerung: Kanten sind beidseitig gerichtet, also Vor- und Zurückrouting möglich.

Gabber-Galil Graph

Klassischer Gabber-Galil Graph:• V: Knoten mit Labeln (x,y)∈{0,…,n-1}2

• E: (x,y) (x,x+y),(x,x+y+1), (x+y,y), (x+y+1,y) (mod n)

Kontinuierlicher Gabber-Galil Graph:• N: U=[0,1)2

• F: f1(x,y)=(x,x+y), f2(x,y)=(x+y,y) (mod 1)

Regionsabbildung

• Moderierte Netzwerke:wir beschränken uns aufU=[0,1)d für ein festes d rekursives Labeling + hierarchische Dekomposition

• Peer-to-Peer Netzwerke:Beschränkung auf U=[0,1) konsistentes Hashing

Moderator

Moderierte Netzwerke

• Moderator dirigiert alle Join und Leave Anfragen.

• Alle anderen Operationen werden durch Peers gehandhabt.

Moderator


• Moderator dirigiert alle Join und Leave Anfragen.

• Alle anderen Operationen werden durch Peers gehandhabt.

Anforderungen:• Moderator speichert nur polylog Information

über das System.• Join und Leave Operationen mit konstanter

Arbeit und Zeit für Moderator.


Grundlegender Ansatz:• Platziere Peers auf Punkten des [0,1)-Rings• Verbinde benachbarte Peers des Rings

01

Rekursives Labeling

• Vergib Labels an Peers in folgender Ordnung:0 1 01 11 001 011 101 111 0001 0011 …

• Interpretiere sie als Binärkodierung einer reellen Zahl in [0,1): xv = i bi/2i

0

1

0111

001

011101

111

Rekursives Labeling

Join & Leave ähnlich zur Cut&Paste Strategie:• Peer initiiert Join (n Knoten im System):

bekommt (n+1)-ten Label in der Liste• Peer v initiiert Leave:

Peer mit n-tem Label bekommt v‘s Position

Verwaltung eines Kreises

• v: Peer mit n-tem Label• Moderator: speichert pred(v), v, succ(v),

succ(succ(v))• Join und Leave Operationen:

Siehe Subj-Ring.cpp


Join Operation für Knoten u:• Der Moderator stellt u succ(v) und

succ(succ(v)) vor und umgekehrt, damit sich u zwischen succ(v) und succ(succ(v)) in den Kreis integrieren kann.

• Der Moderator fragt gleichzeitig succ(succ(v)) nach dessen Nachfolger, um seine Verbindungen zu aktualisieren.

Anzahl Kommunikationsrunden: konstant


Leave Operation für Knoten u:• u informiert den Moderator und teilt ihm pred(u) und succ(u)

mit.• Der Morator stellt v pred(u) und succ(u) vor und umgekehrt,

um v an die Stelle von u zu setzen.• Gleichzeitig stellt der Moderator pred(v) succ(v) vor und

umgekehrt, um die Lücke bei v zu schließen.• Außerdem erfragt der Moderator von pred(v) den Vorgänger

w=pred(pred(v)) und von w dessen Vorgänger pred(w). Damit kann der Moderator seine Verbindungen mit w als neuem Knoten v mit größtem Label aktualisieren.

Anzahl Kommunikationsrunden: konstant

Hierarchische Dekomposition

• Betrachte beliebigen Raum U=[0,1)d

• Hierarchischer Dekompositions-baum zu U:

U


0 10 001 01 1 11


Lemma 7.11:• Volumina der Regionen unterscheiden

sich höchstens um Faktor 2.• Regionen sind paarweise disjunkt.• Die Vereinigung der Regionen ergibt U.

Beweis: Induktion

Kombiniere dies mit einer beliebigen Familie F von Funktionen.

Join Operation

0 10 001 01 10 11

u v

Join Operation

0 10 001 01 10 11

• Verbindungsregel: {v,w}∈EF(V) ⇔ [R(v)∪F(R(v))]∩[R(w)∪F(R(w))]≠∅ • R(v)⊆Ralt(u)• Also ist [R(v)∪F(R(v))]⊆[Ralt(u)∪F(Ralt (u))] und damit N(v)⊆Nalt(u)• v muss also lediglich u kontaktieren, um alle Verbindungen zu erhalten.

u v

Leave Operation

0 10 001 01 10 11

u v

Leave Operation

0 10 001 01 10 11

u v

• Verbindungsregel: {v,w}∈EF(V) ⇔ [R(v)∪F(R(v))]∩[R(w)∪F(R(w))]≠∅ • Rneu(u)=Ralt(u) ∪R(v)• Also ist Nneu(u)=Nalt(u)∪N(v)• u muss also lediglich Kanten von v übernehmen, um alle Verbindungen

zu erhalten.


Spezialfall dynamischer Baum: Realisiere Dekompositionsbaum als Baum auf dem geordneten Kreis. 0

1

01 11

001 011 101 111

0001 0011 0101 0111


Spezialfall dynamischer Baum:

Join: neuer Knoten muss lediglich mit Nachfolger oder Vorgänger im Kreis verbunden werden

0

1

0111

001

011101

111

Subj-Tree.cpp


Theorem 7.12: Für jedes moderierte Netz-werk basierend auf dem kontinuierlich-diskreten Ansatz:

• Moderator muss nur konstant viele Verbindungen zum Netzwerk halten.

• Join/Leave kann in konstanter Zeit und Arbeit für Moderator durchgeführt werden.

• Join/Leave kann in konstanter Zeit für Peers durchgeführt werden


Schnellere Integration von Peers:• Moderator verwaltet Verbindungen zu nächsten 2k

Vorgängern und k+1 Nachfolgern von Knoten v mit höchstem Label.

• Jeder Peer hat Verbindung zum direkten und dem k-ten Vorgänger und Nachfolger.

v


Fehlertoleranz:• Region eines Peers ist sein Label – k Bits

k=2 reicht fürAusfall voneinem Peer

Label 011

Region R(v)

v


Sybil Attacke: Join Anfragen einer Schwemme von gegeneri-schen Peers

Resistenz gegen Sybil Attacken:• Peers behalten ihre alten Verbindungen bei. Damit Grad nur

logarithmisch größer als alter Grad. (Übung)• Dann ist oberer Teil des Netzes imun gegenüber Veränderungen

unten.

001 10

001 011 101 111

1

0001 1111....

Gegnerische Peers

Regionsabbildung

• Moderierte Netzwerke:wir beschränken uns aufU=[0,1)d für ein festes d rekursives Labeling + hierarchische Dekomposition

• Peer-to-Peer Netzwerke:Beschränkung auf U=[0,1) konsistentes Hashing

Moderator

Peer-to-Peer Netzwerk

Wir beschränken uns auf U=[0,1).Jeder Peer hat zufälligen Punkt in [0,1).

• Peer v besitzt Region [v,succ(v)).

Punktzuweisungsstrategien:• Chord: kryptographische Hashfunktion• CAN: zufällige Nummer

0 1

Join Operation

• Neuer Knoten u wählt zufällige Position x.• Route zum Knoten v, der x besitzt.

• Da R(u)⊆Ralt(v), kann v alle Verbindungen zu u transferieren, die u braucht.

0 1uv

Leave Operation

• Ein Knoten, der das Netzwerk verlässt, transferiert seine Verbindungen zum Vorgänger.

• Robustheit gegenüber Ausfällen: wende kontinuierlich-diskrete Methode auf Rk(v) an mit Rk(v) := Vereinigung von R(v) und den Regionen der k nächsten Nachfolger von v

0 1

Kontinuierlich-Diskrete Methode

Effiziente Umsetzung von Join & Leave:• Peers verwalten zusätzlich zu den Verbindun-

gen bzgl. F einen sortierten Basiskreis, so dass Vorgänger und Nachfolger einfach zu ermitteln sind.

1 0


Kontinuierlicher de Bruijn Graph:• V = [0,1)• E = { {x,y}∈[0,1)2 | y=x/2, y=(1+x)/2 }

0 1

Seien f0(x)=x/2 und f1(x)=(1+x)/2.Betrachte R0(v)=f0(R(v)) und R1(v)=f1(R(v)).

R1(v)R(v)R0(v)


Verknüpfungsregel:• Kreiskanten: Peer v verbindet sich mit pred(v) und

succ(v) in [0,1)• De Bruijn Kanten: Peer v verbindet sich mit allen Peers

w, für die sich R(v)∪R0(v)∪R1(v) mit R(w)∪R0(w)∪R1(w) überlappt.

Theorem 7.13: Das dynamische de Bruijn Netzwerk hat Grad O(log n) und Durchmesser O(log n) m.h.W.

Beweis:• Grad: der erwartete Grad eines Knotens ist O(1).• Stochastische Methoden: max. Grad O(log n) m.h.W.


Theorem 7.13: Das dynamische de Bruijn Netzwerk hat Grad O(log n) und Durchmesser O(log n) m.h.W.

Beweis (Fortsetzung):• Durchmesser: simuliere Routing im kontinuierlichen de

Bruijn Graph im diskreten de Bruijn Graph:

(x1,x2,x3,…) (z1,x1,x2,…) (z2,z1,x1,…) (z3,z2,z1,x1,…) … (z2,z1,y1,…) (z1,y1,y2,…) (y1,y2,y3,…)

• Nach O(log n) Schritten sind m.h.W. (zk,…,z1,x1,…) und (zk,…,z1,y1,…) in derselben Region oder benachbarten Regionen auf dem Kreis, d.h. das Routing benötigt max. 2k+1 Schritte

Verteilte Hashtabelle

0 1

Daten

Peers

Verwende konsistentes Hashing:

(pseudo-)zufällige Hashfunktion


Neuer Knoten u mit Position x:• Route zum Knoten v, der x besitzt.

• Da R(u)⊆Ralt(v), kann v alle Verbindungen und Daten zu u transferieren, die u braucht.

0 1uv


Alter Knoten v verlässt das System:• v transferiert alle Verbindungen und Daten

zum Vorgänger w.

• Robustheit gegenüber Ausfällen: wende kontinuierlich-diskrete Methode auf Rk(v) an mit Rk(v) := Vereinigung von R(v) und den Regionen der k nächsten Nachfolger von v

0 1

vw

Übersicht

Kontinuierlich-diskrete Methode:• Grundlegendes Prinzip• Moderierte Netze vs. Peer-to-Peer Netze

• Selbststabilisierung

Moderator

Selbststabilisierung

• Moderierte Netze und Peer-to-Peer Netze basieren beide auf geordnetem Kreis.

• Kann der Kreis wiedergewonnen werden, sind die Regionen korrekt.

Moderator

Protokoll für selbststabilisierenden Kreis!

Selbststabilisierung

• Moderierte Netze und Peer-to-Peer Netze basieren beide auf geordnetem Kreis.

• Jeder Knoten v sucht dann entlang Kreis nach Knoten w: [R(v)∪F(R(v))]∩[R(w)∪F(R(w))]≠∅

Moderator

Effiziente Suche möglich über F

Selbsterhaltung

Neben selbststabilisierenden brauchen wir auch selbsterhaltende Netzwerke.

Forderungen:• Skalierbarkeit: Durchmesser und Grad sind klein

(maximal polylogarithmisch)• Robustheit: Auch bei einer großen Anzahl gegne-rischer

Peers bleiben die ehrlichen Peers in einer Zusammenhangskomponente

Angriffe:• Join/Leave Attacken, Sybil Attacken, DoS Attacken, …

Join-Leave Attacken

Einsicht: Für die lokal-konsistente und kontinuierlich-diskrete Methode ist eine gute Streuung der Knoten von zentraler Bedeutung.

Gute Streuung bzgl. der Knotenordnung:

Dann reicht es, sich mit k nächsten Nachbarn zu verbinden, damit alle ehrlichen Peers ( ) in einer Zusammenhangskomponente sind.

Join-Leave Attacken

Peers formen einen Kreis

gegnerische Peersehrliche Peers

Zustände dem System nicht bekannt!

Join-Leave Attacken

Gegnerische Peers gut verteilt:Forme lokale Quoren

Verbingungen zu k nächstenNachbarn reichen

Join-Leave Attacken

Statische Menge von Peers:

Wähle zufällige Permutation für gute Streuung

Join-Leave Attacken

Dynamische Menge von Peers:

Zwei Operationen: Join und Leave

Join-Leave Attacken

Problem: finde zustandslose Join und Leave Operationen, so dass für jede (selbst adaptive) Join-Leave Sequenz gegnerischer Peers die gegnerischen Peers im Kreis gut verteilt sind.

Join-Leave Attacken

Modell:• n ehrliche Peers• n gegnerische Peers, <1• Zeit unterteilt in Runden• In jeder Runde kann Gegner Join oder Leave

Operation für einen gegnerischen Peer aufrufen

Ziel: finde Join und Leave Operationen, so dass für alle Folgen F von c log n Peers auf Kreis gilt:

Mehrheitsbedingung: die ehrlichen Peers in F sind in der Mehrheit.

120

Wie hält man Peers gemischt?

Kartenmischen [Diaconis & Shahshahani 81]:

zufällige Transposition

Q(n log n) Transpositionen: zuf. Permutation

Q(log n) Transpositionen pro join Operation??

Join-Leave Attacken

Join-Operation, die funktioniert:k-Rotation:- neuer Peer zunächst positionslos- vertausche (k-1)-mal hintereinander posi-

tionslosen mit zufälligem Peer im Kreis

- füge positionslosen Peer zufällig ein

Join-Leave Attacken

Theorem 7.14: Solange < 1-2/k ist, gilt die Mehrheitsbedingung für poly viele Runden m.h.W. für jede gegn. Join/Leave Folge.

Join-Leave Attacken

Problem: in kontinuierlich-diskreter Methode sind Peers im virtuellen Raum verteilt

Join-Leave Attacken

Problem: in kontinuierlich-diskreter Methode sind Peers im virtuellen Raum verteilt

Einfachster virtueller Raum: [0,1)-Intervall

0 1

Join-Leave Robustheit

• n ehrliche Peers, n gegn. Peers, <1• Jeder Peer hat Punkt in [0,1)

0 1

Join-Leave Robustheit

Ziel: Für jedes Interval I⊆[0,1) der Größe (c log n)/n, c konstant, gilt:

• Balancierung: (log n) Peers in I• Mehrheit: ehrliche Peers in Mehrheit in I

0 1I

Wie sind Bedingungen zu erfüllen?

Chord: verwendet kryptographische Hashfunktion, um Peers Punkte in [0,1) zuzuweisen

• zufällige Verteilung der ehrlichen Peers• keine zufällige Verteilung der gegnerischen Peers


CAN: weist den Peers zufällige Punkte in [0,1) zu


Group Spreading [AS04]:• Weise Peers zufällige Punkte in [0,1) zu• Begrenze die Lebenszeit der Peers

Zu teuer!


• Regel, die funktioniert: Kuckuck-Regel

leere k/n-Region

n ehrlich n gegnerisch

< 1-1/k

Rejoin: leave und join über Kuckuck-Regel

Grenzen der Kuckuck-Regel

• Funktioniert nur für rejoin Sequenzen von gegnerischen Peers.

k-flip&cuckoo Regel [AS07]

• Join: wie zuvor (k-Kuckuck-Regel)• Leave: wähle zufällige k/n-Region unter benachbarten c

log n k/n-Regionen, leere & vertausche sie mit zufälliger

k/n-Region

n honest n adversarial

Tauschjoin

Zufallszahlen

Kritische Komponente:Robuster verteilter Zufallszahlengenerator

Lösung [Awerbuch&S 2006]:• sehr einfach (keine fehlerkorr. Codes)• funktioniert für öffentliche Kanäle• selbst wenn konstanter Bruchteil GegnerTrick: generiere Gruppe von Zufallszahlen

Noch Fragen?

Analysis of k-cuckoo rule

• k-region: region of size k/n starting at integer multiple of k/n

• R: fixed set of c log n consec. k-regions• New node: not yet replaced after joining• >0: small constant

Lemma: R has at most c log n new nodes.

Lemma: Sum of ages of k-regions in R in (1 § ) (c log n)n/k, w.h.p.

Analyis of k-cuckoo rule

• R: fixed set of c log n consecutive k-regions• T=(/)log3 n• >0: small constant

Lemma: In any time interval of size T, (1§)kT honest nodes and (1§)kT adv. nodes evicted, w.h.p.

Lemma: R has (1§ )(c log n)k old honest and <(1+)(c log n)k old adv. nodes, w.h.p.

Analysis of k-cuckoo rule

# honest nodes in R: >(1-)(c log n)k

# adversarial nodes in R:<(1+)(c log n)k + (c log n)

Theorem: When using the k-cuckoo rule with <1-1/k, the balancing and majority conditions are satisfied for poly many adversarial rejoin requests, w.h.p.

Documents

Verteilte Algorithmen und Datenstrukturen Kapitel 7: Dynamische Netzwerke für Routing Christian Scheideler WS 2009