English

Peer-to-peer networks belong to the class of overlay networks, i.e. the network is built on top of a physical network (e.g. the Internet) which is used to realize the communication between the nodes (peers) of the overlay. In contrast to the nodes in a client server architecture, peers have symmetric functionality: every peer acts as a server as well as a client. This property bears the potential of excellent resilience to network failures, since a faulty peer can be replaced by every other peer in the network. Studies of real world peer-to-peer networks reveal that these are highly dynamic. Thus, it is of major importance to take advantage of the potential robustness when designing a peer-to-peer network and it is reasonable to choose a simple network structure that can be maintained in case of strong dynamics and therefore guarantees the functionality of the network. This criterion is met by random networks. In this thesis we present local graph transformations to build and maintain random networks without central coordination mechanisms. They especially allow to maintain properties such as logarithmic diameter and expansion by local ``handshake'' operations only and are able to recover from any worst case situation. To overcome the lack of efficient query algorithms for random networks, we describe how to use random networks as a building block of a structured peer-to-peer network. For this, we cleverly combine random networks, search trees, and distributed hash tables to overcome their individual shortcomings while keeping their individual strength. The resulting network, called 3nuts, is self-stabilizing and load-balanced, supports range queries, and allows routing with small latency by adapting the structure of the overlay to the underlying physical network.

Deutsch

Peer-to-Peer Netzwerke gehören zur Klasse der Overlay-Netzwerke, d.h. für die Kommunikation zwischen den Netzwerkteilnehmern (Peers) wird ein darunter liegendes, physikalisches Netzwerk (zumeist das Internet) verwendet. Eine besondere Eigenschaft ist die symmetrische Funktionalität der Peers, d.h. jeder Peer agiert sowohl als Server als auch als Client. Diese Eigenschaft bietet das Potenzial für sehr hohe Robustheit, da ein ausgefallener Peer durch jeden anderen ersetzt werden kann. Es ist wichtig diese potenziell vorhandene Robustheit auch tatsächlich beim Entwurf von Peer-to-Peer Netzwerken zu nutzen, da Untersuchungen zeigen, dass Peer-to-Peer Netzwerke einer sehr starken Dynamik unterliegen. Somit ist es sinnvoll eine einfache Netzwerkstruktur zu wählen, die auch bei starker Dynamik aufrechterhalten werden kann und die Funktionalität des Netzwerks garantiert. Dieses Kriterium wird z.B. von Zufallsnetzwerken erfüllt. In dieser Arbeit stellen wir lokale Graph-Transformationen zum Aufbau und der Aufrechterhaltung von Zufallsnetzwerken ohne zentrale Koordination vor. Diese erlauben es auch im Fall starker Dynamik Eigenschaften wie logarithmischen Durchmesser und Expansionseigenschaft durch lokale Handshake-Operationen mit minimalen Kommunikationskosten aufrecht zu erhalten. Um das Problem der effizienten Suche in Zufallsnetzwerken zu umgehen, setzen wir Zufallsnetzwerke als Baustein für ein strukturiertes Peer-to-Peer Netzwerk ein. Im 3nuts Netzwerk werden Zufallsnetzwerke, Such-Bäume und verteilte Hash-Tabellen auf geschickte Art und Weise kombiniert um ihre jeweiligen Stärken zu erhalten und die jeweiligen Schwächen zu umgehen. Die resultierende Netzwerkarchitektur ist selbst-stabilisierend, Last-balanciert, unterstützt Bereichsanfragen und erlaubt Routing mit niedrigen Latenzen durch Anpassung der Overlay-Struktur an das physikalische Netzwerk.