Small-world Networks
(Bachelor-, Masterarbeit)

Stichworte: Overlay Networks, Peer-to-Peer Systeme

Zielgruppe: Studierende beliebiger Fachrichtungen

Das in unserer Arbeitsgruppe entworfene P2P Grid soll auf einer Internetseite zum Download freigegeben werden. Dazu hat jeder potentielle Teilnehmer die von ihm für die einzelnen Dienste verwendeten Portnummern anzugeben. Zudem bekommt man beim Download eine ID und eine initiale Freundesliste zugewiesen. Bei jedem Connect mit dem P2P Grid soll der Download-Server kontaktiert werden, um gegebenenfalls eine aktualisierte Freundesliste (neue Freunde oder geänderte Portnummern) zu erhalten. Umgekehrt muß es möglich sein, den Download-Server über eine geänderte Wahl der Portnummern zu informieren.

Die Schwierigkeit besteht darin, durch die Freundeslisten ein skalenfreies Netz zu implementieren, in dem einige wenige Knoten (sogenannte Hubs) außerordentlich viele Verbindungen aufweisen, während der Großteil der Knoten relativ wenige Verbindungen zu anderen Knoten hat.



Zufällig generierte Netzwerke verfügen jedoch nicht über diese günstige Eigenschaft skalenfreier Netzwerke, welche deren Robustheit gegenüber dem Ausfall von Knoten sicherstellt, sofern es sich dabei nicht um die Hubs handelt. Darüberhinaus soll das durch die Freundesliste implementierte Netzwerk von der Beschaffenheit sogenannter Small-World Netzwerke sein, die durch zwei weitere Eigenschaften charakterisiert sind:



• Eine hohe Wahrscheinlichkeit dafür, daß zwei Knoten, die jeweils eine Kante zu einem dritten Knoten haben, auch untereinander verbunden sind (Transitivität).
• Eine Nachricht, die jeweils von einem Knoten über eine Kante zu allen seinen Nachbarknoten weitergereicht wird, kann über nur sehr wenige Kanten alle Knoten im Netzwerk erreichen (geringer Durchmesser).

Der geringe Durchmesser garantiert das schnelle Auffinden von Ressourcen in einem P2P System.

Zunächst wird der erste Peer lediglich den Download-Server in seiner Freundesliste haben. Mit zunehmender Beteiligung müssen die ersten Freundeslisten aktualisiert werden. Der Download-Server soll im Netzwerk als Hub fungieren. Mit weiter zunehmender Beteiligung müssen jedoch zusätzliche Hubs in das System integriert werden, die ihrerseits eventuell auch als Download-Server fungieren.

Die Arbeit sollte, wenn möglich, in enger Kooperation mit der Arbeit Peer-to-Peer Strategien für Ad-hoc Grids ausgeführt werden.

Last modified: Thu Feb 05 20:33:00 CET 2009