|
Structures and Algorithms for Peer-to-Peer Cooperation
Steiner, Moritz
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)  Vorschau |
|
PDF
SteinerDiss2.pdf
- Veröffentlichte Version
Download (3MB)
|
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/2149
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-21493
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2009
|
|
Titel einer Zeitschrift oder einer Reihe:
|
None
|
|
Verlag:
|
Universität Mannheim
|
|
Gutachter:
|
Effelsberg, Wolfgang
|
|
Datum der mündl. Prüfung:
|
8 Dezember 2008
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Praktische Informatik IV (Effelsberg 1989-2017)
|
|
Fachgebiet:
|
004 Informatik
|
|
Normierte Schlagwörter (SWD):
|
Peer-to-Peer-Netz , Overlay-Netz
|
|
Freie Schlagwörter (Englisch):
|
p2p , performance , measurement , nve , overlay
|
|
Abstract:
|
Peer-to-peer overlay networks are distributed systems, without any hierarchical organization or centralized control. Peers form self-organizing overlay networks that are on top of the Internet. Both parts of this thesis deal with peer-to-peer overlay networks, the first part with unstructured ones used to build a large scale Networked Virtual Environment. The second part gives insights on how the users of a real life structured peer-to-peer network behave, and how well the proposed algorithms for publishing and retrieving data work. Moreover we analyze the security (holes) in such a system. Networked virtual environments (NVEs), also known as distributed virtual environments, are computer-generated, synthetic worlds that allow simultaneous interactions of multiple participants. Many efforts have been made to allow people to interact in realistic virtual environments, resulting in the recent boom of Massively Multiplayer Online Games. In the first part of the thesis, we present a complete study of an augmented Delaunay-based overlay for peer-to-peer shared virtual worlds. We design an overlay network matching the Delaunay triangulation of the participating peers in a generalized d-dimensional space. Especially, we describe the self-organizing algorithms for peer insertion and deletion. To reduce the delay penalty of overlay routing, we propose to augment each node of the Delaunay-based overlay with a limited number of carefully selected shortcut links creating a small-world. We show that a small number of shortcuts is sufficient to significantly decrease the delay of routing in the space. We present a distributed algorithm for the clustering of peers. The algorithm is dynamic in the sense that whenever a peer joins or leaves the NVE, the clustering will be adapted if necessary by either splitting a cluster or merging clusters. The main idea of the algorithm is to classify links between adjacent peers into short intracluster and long inter-cluster links. In a structured system, the neighbor relationship between peers and data locations is strictly defined. Searching in such systems is therefore determined by the particular network architecture. Among the strictly structured systems, some implement a distributed hash table (DHT) using different data structures. DHTs have been actively studied in the literature and many different proposals have been made on how to organize peers in a DHT. However, very few DHTs have been implemented in real systems and deployed on a large scale. One exception is KAD, a DHT based on Kademlia, which is part of eDonkey, a peer-to-peer file sharing system with several million simultaneous users. In the second part of this thesis we give a detailed background on KAD, the organization of the peers, the search and the publish operations, and we describe our measurement methodology. We have been crawling KAD continuously for more than a year. We obtained information about geographical distribution of peers, session times, peer availability, and peer lifetime. We found that session times are Weibull distributed and show how this information can be exploited to make the publishing mechanism much more efficient. As we have been studying KAD over the course of the last two years we have been both, fascinated and frightened by the possibilities KAD offers. We show that mounting a Sybil attack is very easy in KAD and allows to compromise the privacy of KAD users, to compromise the correct operation of the key lookup and to mount distributed denial-of-service attacks with very little resources.
|
|
Übersetzter Titel:
|
Strukturen und Algorithmen für Peer-to-Peer Zusammenarbeit
(Deutsch)
|
|
Übersetzung des Abstracts:
|
Peer-to-peer Overlay Netzwerke sind verteilte Systeme ohne jede hierarchische Organisation oder zentrale Kontrolle. Die Teilnehmer bilden auf Anwendungsebene sich selbst organisierende Overlay-Netzwerke, die über das unterliegende Netzwerk, das Internet, paarweise miteinander Verbindungen aufbauen können. Beide Teile dieser Dissertation behandeln Peer-to-Peer Overlay-Netze. Der erste Teil beschäftigt sich mit unstrukturierten Overlays, die unter anderem benutzt werden können, um virtuelle Welten im großen Maßstab aufzubauen. Der zweite Teil gewährt Einblicke darüber, wie sich die Benutzer eines real existierenden strukturierten Peer-to-Peer Netzwerkes verhalten und wie gut die vorgeschlagenen Algorithmen für die Publikation und Suche von Daten funktionieren. Darüber hinaus wird die Sicherheit eines solchen Systems analysiert. Networked virtual environments, auch bekannt als verteilte virtuelle Umgebungen, sind computer-generierte synthetische Welten, die es mehreren Teilnehmern ermöglichen, gleichzeitig zu agieren. Es wurden viele Anstrengungen unternommen, um Nutzern die Interaktion in möglichst realistischen virtuellen Umgebungen zu ermöglichen. Dadurch wurde der Boom von Massively Multiplayer Online Games in den letzten Jahren erst ermöglicht. Im ersten Teil dieser Dissertation stellen wir eine komplette Studie eines delaunaybasierten Peer-to-Peer Overlays für verteilte virtuelle Welten vor. Wir entwerfen ein Overlay-Netz, das mit der Delaunay-Triangulierung der teilnehmenden Peers in einem d-dimensionalen Raum übereinstimmt. Vor allem beschreiben wir die sich selbst organisierenden Algorithmen für das Einfügen und Entfernen eines Peers. Um die erhöhte Laufzeit, die durch das Routing im Overlay entsteht, zu reduzieren, schlagen wir vor, jeden Knoten im delaunaybasierten Overlay mit einigen sorgfältig ausgewählten Abkürzungen anzureichern, so dass eine sogenannte smallworld entsteht. Anschließend zeigen wir, dass eine kleine Anzahl von Abkürzungen ausreichend ist, um die Laufzeit einer Nachricht im Overlay signifikant zu reduzieren. Wir präsentieren einen verteilten Algorithmus zum Clustern von Peers. Der Algorithmus ist adaptativ in dem Sinne, dass jedesmal, wenn ein Peer dem NVE beitritt oder es verlässt, das Clustering wenn nötig angepasst wird, indem ein Cluster aufgeteilt wird oder Cluster zusammengeschlossen werden. Die zentrale Idee des Algorithmus ist es, die Verbindungen zwischen benachbarten Peers in kurze intra-cluster- und lange inter-cluster-Verbindungen aufzuteilen. In einem strukturierten Peer-to-Peer System ist die Nachbarschaftsbeziehung zwischen Peers sowie der Ort für die Datenspeicherung strikt festgelegt. Die Suche in einem solchen System ist daher durch die spezielle Netzwerkarchitektur bestimmt. Unter den strukturierten Systemen implementieren einige eine verteilte Hash-Tabelle (Distributed Hash Table, DHT). DHTs sind in der Literatur ausführlich untersucht worden, und es sind viele verschiedene Vorschläge für die Organisation der Peers gemacht worden. Dennoch sind nur sehr wenige DHTs in einem realen System implementiert worden und im großen Maßstab zur Anwendung gekommen. Eine Ausnahme ist KAD, eine auf Kademlia basierende DHT, die Teil von eDonkey ist, einem Peer-to-Peer Netz, das von mehreren Millionen Nutzern gleichzeitig benutzt wird. Im zweiten Teil dieser Dissertation stellen wir die Funktionsweise von KAD vor, seine Organisation der Peers, sowie seine Publikations- und Suchoperation. Um ein System dieser Größenordnung zu untersuchen, haben wir unsere eigene, skalierbare und robuste Meßmethodologie entwickelt. Auf diese Weise war es uns möglich, KAD ohne Unterbrechungen während eines gesamten Jahres zu vermessen und eine Vielzahl von Informationen zu erhalten. So haben wir Daten über die geographische Verteilung, die Sitzungszeiten, die Verfügbarkeit, sowie die Lebenszeit der Peers gewonnen. Ein besonders interessantes Ergebnis ist, dass die Sitzungszeiten Weibull-verteilt sind. Wir zeigen, wie diese Information dazu genutzt werden kann, den Publikationsmechanismus effizienter zu gestalten. Während wir in den vergangenen zwei Jahren mit den Funktionsweisen von KAD immer vertrauter wurden, haben uns die Möglichkeiten, die KAD bietet, sowohl fasziniert als auch erschreckt. KAD erlaubt es einem einzelnen Benutzer ohne große Mühe, viele verschiedene Identitäten anzunehmen. Diese können dazu benutzt werden, spezifische Daten über Nutzer zu sammeln, die korrekte Funktionsweise der Suche zu unterbinden und verteilte Denial-of-Service Angriffe mit sehr wenigen Ressourcen durchzuführen.
(Deutsch)
|
|
Zusätzliche Informationen:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
