Routing-Optimierung für verteilte Datenverwaltung und Prozessausführung auf Mobilgeräten mit OSIRIS-SR (Bachelor Thesis, Finished)

Author

Lukas Probst

Description

Peer Overlay-Netzwerke wie beispielsweise Chord ermöglichen die effiziente und dezentralisierte Verwaltung von Daten in verteilten Peer-to-Peer (P2P) Systemen. Wenn ein Chord-Netzwerk über heterogenen Knoten gebildet wird, die sich in Bezug auf ihre Latenzzeit unterscheiden, dann ist der von Standard-Chord gewählte Routing-Pfad jedoch meist nicht der optimale. Oft können Abweichungen der Standard-Routen zu kürzeren Routingzeiten führen.

In dieser Bachelorarbeit präsentieren wir ein Konzept zur Routenoptimierung durch global optimierte Routinginformationen in Form von Routing-Intervallen. Die global optimierten Routing-Intervalle werden dabei nach einer geschickten Initialisierung iterativ berechnet. Dazu findet in jeder Iteration eine Kommunikation mit den Standard-Chord-Next-Hops (Finger-Table-Einträge) statt, bei der sowohl die direkte Latenzzeit gemessen, als auch die Routinginformationen des Next-Hops erlangt werden. Mit Hilfe der direkten Latenzzeit und der globalen Routinginformationen des Next-Hop kann der Knoten die eigenen Routing-informationen durch Aggregation aktuallisieren. Evaluationen zur Laufzeitkomplexität und Konvergenzrate der dafür benötigten Algorithmen zeigen eine gute Skalierbarkeit für realistische praxisrelevante Szenarien.

Anschließend präsentieren wir einen optimierten Routingalgorithmus, welcher die global optimierten Routing-Intervalle verwendet und trotzdem die vom Standard-Chord-Algorithmus garantierte Korrektheit erhält.

Außerdem präsentieren wir eine um diese Routenoptimierung erweiterte Version von OSIRIS, deren Korrektheit wir durch Evaluationen bestätigen konnten.

Die abschließende Evaluation zeigt, dass wir die Routingzeiten, durch die beim Routen verwendeten gobal optimierten Routinginformationen immens verringern konnten. Zudem weist diese Evaluation darauf hin, dass die Routenoptimierung in jeder (also auch in homogenen) Umgebungen bedenkenlos eingesetzt werden kann, sofern keine starken Latenzschwankungen zu erwarten sind.

Start / End Dates

2012/04/01 - 2012/07/31

Supervisors

Research Topics