PlanetenWachHundNetzPlanetenWachHundNetz

Instrumenting Infrastructure for PlanetLab

Instrumenting Infrastructure for PlanetLab

2

OutlineOutline

◊ Motivation◊ Hindernisse◊ Bekannte Ansätze◊ Unsere Lösung◊ Evaluation◊ Zusammenfassung

◊ Motivation◊ Hindernisse◊ Bekannte Ansätze◊ Unsere Lösung◊ Evaluation◊ Zusammenfassung

3

MotivationMotivation

◊ Context: Verteilte Anwendung• P2P (File-sharing), PlanetLab, SETI ...

◊ Monitoring• Statistics• Log collection

◊ Context: Verteilte Anwendung• P2P (File-sharing), PlanetLab, SETI ...

◊ Monitoring• Statistics• Log collection

4

Probleme und AuswegeProbleme und Auswege

◊ “Central warehousing” nicht scalierbar• “Push”: logs alle 5 min werden an

zentralen Server geschickt• “Pull”: nur auf Anfrage

Daten müssen “en-route” reduziert werden• Reduction-tree• Distributed parallel prefix (MapReduce)

◊ “Central warehousing” nicht scalierbar• “Push”: logs alle 5 min werden an

zentralen Server geschickt• “Pull”: nur auf Anfrage

Daten müssen “en-route” reduziert werden• Reduction-tree• Distributed parallel prefix (MapReduce)

5

Andere LösungenAndere Lösungen

◊ Reduction-Trees auf P2P◊ Basieren auf “structured overlays”1) Finger-table based Tree (FTT)

• Unregelmäßig

2) Key-based Tree (KBT)• Nur ein globaler Tree

Beide nicht locality-aware

◊ Reduction-Trees auf P2P◊ Basieren auf “structured overlays”1) Finger-table based Tree (FTT)

• Unregelmäßig

2) Key-based Tree (KBT)• Nur ein globaler Tree

Beide nicht locality-aware

6

Structured Overlay (DHT)Structured Overlay (DHT)

◊ Key-based routing (KBR)• Vergebe lange bit strings (keys/IDs)• Nodes teilen key-space unter sich auf• Garantiertes routing zum “Besitzer” in

log(n)◊ Durch Route zu “näherer” Node

◊ Distributed Hashtable (DHT)• Put, Get (Hashtable Semantik)• Bucket beim Besitzer des Hash

◊ Key-based routing (KBR)• Vergebe lange bit strings (keys/IDs)• Nodes teilen key-space unter sich auf• Garantiertes routing zum “Besitzer” in

log(n)◊ Durch Route zu “näherer” Node

◊ Distributed Hashtable (DHT)• Put, Get (Hashtable Semantik)• Bucket beim Besitzer des Hash

7

DHT Beispiel: ChordDHT Beispiel: Chord

◊ 160 bit Ids, representiert in einem Kreis

◊ Fingertables speichern Zeiger

◊ 160 bit Ids, representiert in einem Kreis

◊ Fingertables speichern Zeiger

8

Chord: LookupChord: Lookup

◊ Benutze fingertable um zur nahsten bekannten node zu springen

◊ Benutze fingertable um zur nahsten bekannten node zu springen

9

Finger-table based Tree (FTT)Finger-table based Tree (FTT)◊ Vereinigung aller

Wege zu einer bestimmten ID• Abhängig von allen

Fingertables Braucht

Benachrichtigung in jedem Hop

◊ Vereinigung aller Wege zu einer bestimmten ID• Abhängig von allen

Fingertables Braucht

Benachrichtigung in jedem Hop

10

Key-based Tree (KBT)Key-based Tree (KBT)

◊ Tree auf Key-space gemappt• “virtuelle” interne Nodes

representieren prefixes• “physikalische” nodes

sind Blätter• Subtree enthält alle

Teilnehmer, die prefix entsprechen

• Algorithmus entscheidet, wer Vater wird

◊ Tree auf Key-space gemappt• “virtuelle” interne Nodes

representieren prefixes• “physikalische” nodes

sind Blätter• Subtree enthält alle

Teilnehmer, die prefix entsprechen

• Algorithmus entscheidet, wer Vater wird

11

Unser AnsatzUnser Ansatz

◊ Hybrid zwischen FTT und KBT KBT mit “root” node

o Ein Tree pro queryo Stochastisch balancierto Root-ID legt Tree eindeutig fest

• Coral für Ortsinformationo Bildet “cluster”

◊ Hybrid zwischen FTT und KBT KBT mit “root” node

o Ein Tree pro queryo Stochastisch balancierto Root-ID legt Tree eindeutig fest

• Coral für Ortsinformationo Bildet “cluster”

12

Key-based MapReduce (KMR)Key-based MapReduce (KMR)

◊ Phys. Root node◊ In jedem level

genaues Bit des root negiert

◊ Phys. Root node◊ In jedem level

genaues Bit des root negiert

13

KMR: AnwendungKMR: Anwendung

◊ “Down”: Interne nodes senden eine Nachricht an jeden Bruder

◊ “Up”: Nur eine Nachricht an Vater

◊ Nachricht landet bei “nahster” node

◊ “Down”: Interne nodes senden eine Nachricht an jeden Bruder

◊ “Up”: Nur eine Nachricht an Vater

◊ Nachricht landet bei “nahster” node

14

EvaluationEvaluation

◊ PlanetenWachHundNetz (PWHN)• Application-level monitoring software• Service für PlanetLab• Testet KMR und FFT• auf Coral und (Free-) Pastry

• Reduzierung durch 3 Executables von User :• Eingabe (Init)• Reduzieren (Update)• Ausgabe (Eval)

◊ PlanetenWachHundNetz (PWHN)• Application-level monitoring software• Service für PlanetLab• Testet KMR und FFT• auf Coral und (Free-) Pastry

• Reduzierung durch 3 Executables von User :• Eingabe (Init)• Reduzieren (Update)• Ausgabe (Eval)

15

ZusammenfassungZusammenfassung

◊ Context: Verteilte Anwendung◊ Motivation: Logging, monitoring◊ Problem: Hot-spots, dynamisches p2p◊ FTT/KBT: Lösungen auf DHTs nicht

scalierbar◊ KMR: Hybrid zwischen FTT und KBT◊ PWHN: Evaluation auf PlanetLab

◊ Context: Verteilte Anwendung◊ Motivation: Logging, monitoring◊ Problem: Hot-spots, dynamisches p2p◊ FTT/KBT: Lösungen auf DHTs nicht

scalierbar◊ KMR: Hybrid zwischen FTT und KBT◊ PWHN: Evaluation auf PlanetLab

Fragen ?Fragen ?