Peer-To-Peer-Netzwerke/Mündliche Prüfung SoSe 07

Die Prüfung dauerte 30 Minuten.

Fragen während der Prüfungsvorbereitung (letzte Übung)

• Wie funktioniert Datenreplikation bei Chord?
• Wodurch stellt Splitstream sicher, dass die verschiedenen Bäume

möglichst disjunkte Mengen von inneren Knoten haben?

• Was soll mit sicherem Routing erreicht werden? Mit welchen Maßnahmen

wird es erreicht?

• Wie wird bei den Pastry Routing Tabellen die Lokalität berücksichtigt?
• Nenne ein Beispiel ür einen Eintrag, der in einer Pastry Routing

Tabelle in Zeile 3, Spalte 4 steht (jeweils von 0 gezählt). Die Routing Tabelle gehört zum Knoten 728321 zur Basis 16. Was steht an gleicher Stelle in der beschränkten Routing-Tabelle?

• Was ist der Unterschied von normalem zu konsistentem Hashing?
• Wann wird bei der Lastverteilung nach Ganeson welche Operation ausgelöst?
• Was ist der Hauptunterschied zwischen Pastry und Tapestry? Erkläre

beide Lösungen.

• Nenne möglichst viele Konzepte, die ein P2P-System charakterisieren.
• Welche Kanten hat ein Viceroy-Knoten und wohin zeigen sie?
• Nenne Techniken zur Lastbalancierung in DHTs.
• Welche Auswirkungen hat die Power-Law-Struktur von Gnutella auf die

Robustheit des Netzes?

• Welche Einträge hat ein Chord-Knoten in seiner Routing-Tabelle?
• Wie kommt die Power-Law-Struktur von Gnutella vermutliche zustande?

(* Erkläre Small-World-Netzwerke. <- Frage kam nicht explizit dran, wurde aber angedeutet)

• Welche Probleme würden sich ohne den optimistic Unchoke in BitTorrent

ergeben?

• Wie ist Stress und Stretch in Bezug auf den Application Layer

Multicast definiert?

• Mit welchen Operationen auf BitStrings wird ein DeBruijn-Graph

erstellt und wie können diese Operationen numerisch interpretiert werden?

• Wie hängt der Grad mit dem Durchmesser eines Netzwerkes zusammen?
• Unter welchen Bedingungen sorgen DHTs für eine gute Lastverteilung?
• Beschreibe das Bootstrapping eines neuen Chord-Knotens.

Protokoll 1, 31. Juli 2007

Prüfung war Teil meiner Schwerpunktprüfung und 30min. Die Zeitslots (1 Prüfung pro Stunde) sind leider so großzügig gewählt gewesen, dass ich keine anderen Prüflinge getroffen habe.

Prüfungs-Fragen (ohne Anspruch auf Vollständigkeit):

• Was ist P2P? (Definitionen, Prinzipien)
• Vorteile/Nachteile Vergleich von strukturierten und unstrukturierten P2P Netzwerken
• Entweder Pastry oder Tapestry erklären - ich habe Pastry gewählt und Aufbau des Netzes sowie der Routing Tabellen erklärt, inkl. Lokalität/PNS
• Distance Halving erklären: Netzaufbau, wie und warum das Routing funktioniert, Vorteil von Distance Halving gegenüber anderen Netzen wie Chord,Pastry,etc (-> Grad-Optimiertheit)
• Splitstream erklären (Aufbau, Funktionsweise, Join), sowie Frage: Wann kann es passieren, dass ein innerer Knoten eines Stripes nicht das gleiche Präfix/erste Ziffer wie die grpID des Stripes hat?
• Sicherheit: Definition "Sicheres Routing", wodurch wird sicheres Routing hergestellt, Wie funktioniert der Algorithmus für sicheres Routing (der mit den 2 Routing-Tabellen)
• Prinzip der mehrfachen Auswahl: Beweis für die Bereichsgrößen es sicheren Routings
• Innerhalb welcher Grenzen sind die ID-Bereichsgrößen ohne Verwendung des Prinzips d. mehrfachen Auswahl, Beweis hierfür
• Wie hängt die Anzahl der Pointer in Chord-Fingertable mit den Größen d. ID-Bereich zusammen

Die Fragen zu den Beweisen waren der "1.0er Test", sprich sie waren bewusst etwas schwieriger gewählt.

Protokoll 2, 31. Juli 2007

• Welche P2P-Netzwerke wurden in der Vorlesung behandelt?

• Was sind Super-Peer Netzwerke? Wie funktioniert bei Ihnen das Routing? (Im Prinzip beliebig. Die Super-Peer Knoten könnten untereinander auch ein Chord oder Pastry Netzwerk aufbauen)

• Was ist konsistentes Hashing?

• Wie groß/klein werden die ID-Bereiche bei Chord? (O(1/N^2) bzw. O(N*log(N))
  • Wie kann man dies verhindern? Prinzip der mehrfachen Auswahl => nur noch konstante Abweichungen

• Wie funktioniert das Routing bei Pastry und Tapestry?
  • Wie sehen die Routing-Tabellen aus (Welche Einträge?)?
  • Wie funktioniert das Routing, wenn der Tabelleneintrag an der betreffenden Stelle leer ist? (Bei Pastry übers Leafset. Bei Tapestry Surrogate-Routing)

• Wie wird die Konsistenz der Routing-Tabellen bei Tapestry sichergestellt? (Acknowledged Multicast beim Einfügen eines neuen Knotens)
  • Ab wo wird der Acknowledged Multicast durchgeführt? (Beim ersten Peer, der Surrogate Routing gemacht hat.)

• Was ist Viceroy? Wie ist es aufgebaut?
  • Wieviele Level/Ebenen werden in Viceroy benötigt bei n Knoten? log n
  • Wie findet ein neuer Knoten seine Position/Ebene?
  • Wie funktioniert das Routing in Viceroy?

• Wie funktioniert bei OceanStore die Archivierung?
  • Wie werden aus einer Nachricht die Code-Blöcke generiert? (Stützstellen wählen (z.B. x0=0, x1=1 ...) und dann in das Polynom einsetzen)
  • Wie lässt sich aus den Code-Blöcken die Nachricht wieder herstellen? (Interpolation, es reichen n beliebige der n+k Code-Blöcke)

Zur Prüfung selbst: Lief eigentlich ganz locker. Waren alles faire Fragen. Er gibt Hilfestellungen und bewertet auch sehr fair.

Protokoll 3, 08. August 2007

TODO

Protokoll 4, 08. August 2007

Welche P2P-Netzwerke haben wir in der Vorlesung kennen gelernt und wie kann man diese einteilen?

CAN

       - Wie kann man Lokalität im CAN-Netzwerk berücksichtigen? (auch Landmarks!)

Unter welchen Annahmen funktioniert die Lastverteilung bei einem DHT? Folgefrage: Wie kann man für ähnlich große ID-Bereiche sorgen? (mehrfache Auswahl)

Viceroy

       - Wie ist das Netz aufgebaut/Grundidee?
       - log(N)-Schätzung (unter welchen Bedingungen gilt das?)

OceanStore

       - wie funktioniert die dauerhafte Archivierung (Erasure-Codes)?
       - wie (Grundidee, High-Level) errechnet man die zus. Blöcke?

Sicherheit

       - Welche Attacken kann man gegen P2P-Netzwerke ausführen?

Chord-Bereichsgrenzen:

       - Grundidee des Beweises für die obere Schranke

Protokoll 5, 08. August 2007

• Was für P2P-Netze gibt es? (systematisch, Beispiele)
  • Unterschiede strukturierte / unstrukturierte Netze
• Gnutella, Pareto-Eigenschaft erklären + wie kommt sie zustande
• Pastry: Aufbau der Routingtabelle + insgesamt einmal Pastry erklären.
  • Wie kommt die Lokalität in Pastry zustande?
• Scribe: Aufbau, Join-Algorithmus
  • Nachteile von Scribe -> Splitstream: Funktionsweise + wie kann es sein, dass ein innerer Knoten mit falschen Präfix existiert?

Protokoll 5, 08. August 2007

• Welche P2P-Netzwerke
• Can
  • Routing, Aufwand
  • Verbesserungen: PRS, PNS, Realitäten, Dimensionen
    • Vor und Nachteile
• P-Grid
  • Idee: Tries
  • Aufbau, IDs, Verbindungsstruktur, Bildung (Parallel Join)
  • Routing, Wieso log n?
• Tapestry
  • Unterschied zu Pastry
  • Wie wird Konsistenz sichergestellt
  • Join Protokoll erläutern
• Chord
  • Routinggeschwindigkeit, Wieso log n?
  • Anzahl Finger-Pointer (Skiziert)
• BitTorrent
  • Idee: tit for tat
  • Umsetzung 3 + 1 verbindung
  • warum 1 extra
• Sicherheit
  • Welche Angriffe gibt es
  • Sicheres routing (sichere ids und routing-tabellen gegeben)
    • sichere weiterleitung
    • fehlertest
    • durchführung sicheres routing