Peer model based and actor model based frameworks for search algorithms in unstructured peer-to-peer networks

Abstract

Aufgrund der Fähigkeit verschiedene Ressourcen zu teilen, sind P2P Netzwerke seit Jahrzehnten im Fokus der Forschung. Vor allem die Umsetzung von Suchalgorithmen, um verteilte Ressourcen in unstrukturierten P2P Netzwerken zu finden, ist von spezieller Wichtigkeit, da keine zentrale Sicht auf das Netzwerk existiert. Diese Arbeit geht die Notwendigkeit zur Evaluierung und dem Vergleichen von Suchalgorithmen für unstrukturierte P2P Netzwerke, unter der Verwendung von Standardmetriken, an. Sie liefert zwei Umsetzungen eines Frameworks für systematische Benchmark-Tests von Suchalgorithmen in unstrukturierten P2P Netzwerken und ermöglicht deren Vergleich. Das Framework wird dabei einmal mit dem Actor Model und einmal mit dem auf koordinationsbasiertem Programmiermodel Peer Model umgesetzt. Beide Umsetzungen unterstützen dabei die leichte Austauschbarkeit von Suchalgorithmen. Das zweite Ziel dieser Arbeit ist das Erstellen eines voll verteilten Suchalgorithmus für unstrukturierte P2P Netzwerke, basierend auf dem kollektiven Futtersuchverhalten von Borkenkäfern. Des Weiteren wird ein bereits bestehender Algorithmus basierend auf dem Physarum Polycephalum Schleimpilz an die Bedürfnisse von voll verteilter Suche in unstrukturierten P2P Netzwerken angepasst. Um diese Ziele zu erreichen wird folgende methodische Vorgehensweise angewendet. Nach ausführlicher Literaturrecherche werden die Frameworks zunächst entworfen und anschließend umgesetzt. Als nächstes werden die beiden neuen Suchalgorithmen entwickelt und in die Frameworks eingebunden. Abschließend werden beide Algorithmen kompetitiv gemessen, evaluiert und mit vier bekannten Suchalgorithmen verglichen: Gnutella Flooding, k-Walker, AntNet für P2P und SMP2P. Bark Beetle und der angepasste Physarum Polycephalum Algorithmus zeigen beide insgesamt sehr gute Ergebnisse hinsichtlich der Skalierbarkeit in Bezug auf Netzwerkgröße und -last. Hinsichtlich absoluter Zeit zeigen beide Algorithmen sehr vielversprechende Ergebnisse, wobei lediglich k-Walker etwas bessere Ergebnisse bei Netzwerken mit vielen Replikaten erzielt. In puncto Erfolgsrate zeigt Bark Beetle beinahe so gute Ergebnisse wie Gnutella Flooding, ohne dessen wesentliche Mängel aufzuweisen. Obwohl die Erfolgsrate für die Physarum Polycephalum Anpassung sehr niedrig für Netzwerke mit wenig Replikaten ist, wird diese signifikant besser für Netzwerke mit vielen Replikaten.

Through its ability to share various resources, P2P networks have been in the focus of research for the last decades. Especially the utilization of search algorithms to retrieve the distributed resources in unstructured P2P networks is of major importance, since no global view of the network exists. This thesis addresses the need to evaluate and compare search algorithms for unstructured P2P networks with each other by using standard metrics. It provides two frameworks for systematic benchmarking and comparison of search algorithms in unstructured P2P networks. The first framework is implemented based on the Actor Model and the second one based on the Peer Model (a coordination based programming model). Both frameworks support easy exchangeability of search algorithms. The second goal of this thesis is to create a fully distributed search algorithm for unstructured P2P networks based on the collective feeding of bark beetles. Additionally, an already existing algorithm from a different domain based on the Physarum Polycephalum slime mold is adapted to fully distributed search for unstructured P2P networks. To achieve these goals the following methodological approach is applied. After an extensive literature research, the frameworks are first designed and afterwards implemented. As the next step, the two new search algorithms are developed and implemented into the frameworks. As the final step, both algorithms are benchmarked, evaluated and compared to four existing search algorithms: Gnutella Flooding, k-Walker, AntNet for P2P and SMP2P. Overall, Bark Beetle and the adapted Physarum Polycephalum algorithm show very good scalability regarding growing network size and load. In terms of absolute time, both algorithms show very promising results with only k-Walker having slightly better results for networks with high replication. In terms of success rate, Bark Beetle shows an almost equal good success rate as Gnutella Flooding, without having the same major drawbacks. Although the success rate for the Physarum Polycephalum adaption is very low for networks with small replication, it is significantly better for networks with high replication.