A coordination-based framework for routing algorithms in unstructured peer-to-peer networks

Abstract

Die Problemstellung der Pfadselektion beim Senden von Daten über mehrere Netzwerkknoten wird durch Routing Algorithmen gelöst und ist von elementarer Relevanz für die Kommunikation in Peer-to-Peer Computer Netzwerken. Für Peer-to-Peer Netzwerke ist das Routing Problem von spezieller Wichtigkeit, da keine zentrale Sicht auf das Netzwerk und keine globale Adresszuordnung existiert. Die Diplomarbeit liefert ein dringend benötigtes Framework für faire und systematische Benchmark-Tests von Routing Algorithmen in unstrukturierten Peer-to-Peer Netzwerken und ermöglich deren Vergleich. Die resultierende Applikation basiert auf dem koordinationsbasierten Programmiermodel Peer Model, erlaubt die leichte Austauschbarkeit von Routing Algorithmen und bietet umfangreiche Konfigurierbarkeit. Ein weiterer Beitrag ist die Adaptierung von zwei vorhandenen schwarm-intelligenten Algorithmen zur Lösung des Routing Problems. BeeNet basiert auf dem Futtersuchverhalten von Honigbienen. SlimeMoldNet hingegen basiert auf dem Lebenzyklus des Dictyostelium discoideum Schleimpilzes. Beide Algorithmen werden kompetitiv gemessen, evaluiert und mit fünf bekannten Routing Algorithmen verglichen: AntNet, BeeHive, Physarum polycephalum Routing Algorithmus, Gnutella Flooding und k-Random Walker. SlimeMoldNet performt ingesamt besser als die anderen Algorithmen bezüglich der durchschnittlichen Datenpaketverzögerung. Dies gilt im Speziellen für größere Netzwerke und große Anzahl von Datenpaketen. BeeNet zeigt ähnlich gute Resultate. Hinsichtlich der Skalierbarkeit performt BeeNet besser als die anderen Algorithmen. Die Ausnahme bildet k-Random Walker in einigen wenigen Fällen, der jedoch dafür in anderen Bereichen wesentliche Mängel aufweist. Die Skalierbarkeit von SlimeMoldNet ist überdurchschnittlich gut und verbessert sich drastisch und proportional zur Netzwerkgröße und Datenverkehr.

The problem of path selection when sending information from one node to another over multiple hops, solved by routing algorithms, is a substantial one in computer networks. Especially in unstructured Peer-to-Peer networks, the topic is of major importance, since no global view on the network or global address mapping exists. This thesis provides a much needed benchmarking framework that allows the fair and systematic benchmarking and comparison of routing algorithms in unstructured Peer-to- Peer networks. The resulting application, based on the Peer Model (a coordination based programming model), supports easy exchangeability of routing algorithms and extensive configurability. Additional contributions are the adaption of existing swarm intelligent algorithms from a different domain to the domain of routing. BeeNet is based on the foraging behavior of honey bees, whereas SlimeMoldNet makes use of the Dictyostelium discoideum slime molds life-cycle. Both algorithms are competitively benchmarked, evaluated and compared to five well known routing algorithms: AntNet, BeeHive, Physarum polycephalum routing algorithm, Gnutella Flooding and k-Random Walker. Overall, SlimeMoldNet outperforms the other algorithms in regards to the average data packet delay. This especially holds for bigger P2P network sizes and data packet traffic levels. BeeNet shows similar good results. In terms of scalability, BeeNet outperforms all other algorithms, beside k-Random Walker at some occasions, without having the same major drawbacks. SlimeMoldNets scalability is above average and improves drastically proportional to the network size and data packet traffic level.