Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

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

Die Prüfung dauerte 30 Minuten.

Die Vorbereitungsfragen aus der letzten Übung sind auf einer eigenen Seite zu finden.


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

  • Was sind Peer2Peer-Netze?
  • Rückfrage "Ressourcen am Rand des Netzes" -- Welche Probleme gibt es? (Firewalls, NAT)
  • Wie funktioniert Hole Punching (grob)?
  • Was sind Super-Peer-Netze? Wie können Super-Peers untereinander verbunden sein? (auch strukturiert, unstrukturiert)
  • Was bedeutet der Begriff "Small-World-Netz"? (Geringer Durchmesser, hoher Clustering-Koeffizient)
  • Rückfrage: Definition Clustering-Koeffizient (keine Formel, aber "was steht in der Formel" -- Verhältnis vorhandener Kanten zu möglichen Kanten)
  • Chord: Was macht die Operation stabilize() ?
  • Erkläre Routing nach numerischer ID in SkipNet an einem Beispiel.
  • Mini-Skype: Wie wurden direkte Chat-Verbindungen aufgebaut (vor Gruppen-Chat)
  • Definition Sicheres Routing. Welche 3 Schritte gibt es zum sicheren Routing?
  • Chord: Welche Schranken für ID-Bereiche gibt es? Beweis für untere Schranke (1/N^2)

Prüfung war fair, Felix hat bei "ratenden" Antworten genickt und hin und wieder Kommentare gegeben.

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