Papnet: An order-preserving and latency-aware P2P Overlay and its Applications [Elektronische Ressource] / Martin Raack. Betreuer: Odej Kao

Sujets

• Informatik

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2012
• Nombre de lectures: 34
• Langue: Deutsch
• Poids de l'ouvrage: 6 Mo

Extrait

Papnet: An order-preserving and
latency-aware P2P Overlay and its
Applications
vorgelegt von
Martin Raack, MSc
aus Cottbus
Von der Fakult at IV - Elektrotechnik und Informatik
der Technischen Universit at Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
- Dr. rer. nat. -
genehmigte Dissertation
Promotionaausschuss:
Vorsitzender: Prof. Dr. Volker Markl
Gutachter: Prof. Dr. Odej Kao
Prof. Dr. J org Nolte
Tag der wissenschaftlichen Aussprache: 12. Januar 2012
Berlin 2012
D83Danksagung (Acknowledgement)
Ich m ochte mich zuvorderst bei meinem Betreuer Odej Kao bedanken, der mir
ub er die letzten Jahre stets mit guten Ratschagenl unterstutzend zur Seite stand,
hervorragende Arbeitsbedingungen bot und hiermit letztlich diese Dissertation erst
erm oglicht hat. Weiterer Dank gebuhrt J org Nolte, der sich zur Begutachtung
bereit erkl arte, wie auch dem Vorsitzenden des Prufungsaussc huss Volker Markl.
Des Weiteren danke ich den Kollegen des CIT mit denen ich ub er die vergangen
Jahre arbeiten, diskutieren und auch viele erfreuliche ausserdienstliche Abende
verbringen durfte, insbesondere Felix Heine, Dominic Battre, Andre H oing, Philipp
Berndt, Bj orn Lohrmann, Matthias Hovestadt, Alexander Stanik, Mareike Struwing,
Andreas Kliem sowie meinem Teilzeit-Buro-P artner Daniel Warneke. Auch danke
ich Christian Wurtz und Stefan Menzel, die mich bei meiner Forschung unterstutzten
und deren Abschlussarbeiten ich betreuen durfte.
Ich danke meinen Eltern Siegfried und Irene Raack, die mich schon sehr fruh mit
der Informatik in Beruh rung gebracht, begeistert und gef ordert sowie blockierte
Telefonleitungen und die damit verbundenen Kosten ertragen haben. Weiterhin
schulde ich meinen lieben Geschwistern Thomas, Andrea und Wolfgang grossen
Dank.
Nicht zuletzt m ochte ich auch den Menschen danken, die mich ub er die Jahre
begleitet und gepr agt haben, namentlich Martin Sabransky, Axel Vick, Robert
und Anika Schuppenies, Jacky Weinert, Dr.Ste en Pepper, Stephanie Schneider,
Kati Finzel, Maik Donath, Maria Gosdschan, Marlen Kaletka, David Geier, Chris-
tian Loos, Eric Werner, Frank Sche el sowie Cindy Mentzel und Anne-Katrin
Fischer.
IIIAbstract
This thesis describes the development of a new P2P Overlay called Papnet, which
combines the advantages of Distributed Hash Tables with those of Order-Preserving
P2P Overlays. Papnet does not require any hashing and is thus able to store ob-
ject keys in a sorted manner. This enables the e cient processing of range queries
as well as the implementation of a load balancing technique that guarantees a
constant global load imbalance ratio.
Papnet is latency-aware. Given a uniform distribution of latencies it is able to
route between arbitrary nodes within only twice their direct latency, independent
of the actual network size. We show, that in contrast to other Overlays Papnet is
able to guarantee a fast convergence towards latency-optimal routing links.
As a direct application of Papnet we present a new algorithm to process window-
and k-nearest-neighbor queries on spatial point data, which is able to scale asymp-
totically linear with the total query load. In contrast to existing solutions, the
construction and maintenance of an explicit distributed spatial structure is not
required.
VZusammenfassung
Diese Dissertation entwickelt ein neues P2P Overlay Netzwerk namens Papnet,
welches die einzelnen Vorzuge bestehender Typen von P2P Overlays vereint und
erweitert. Im Unterschied zu den meisten der existierenden P2P Overlays erfordert
Papnet kein Hashing und kann somit einzelne Datenelemente sortiert nach einem
Prim arschlussel speichern. Dies erm oglicht sowohl e ziente Bereichsanfragen als
auch die Implementierung einer Lastbalancierungs-Technik welche ein konstantes
Lastungleichgewicht garantiert.
Papnet beruc ksichtigt Nachrichtenlaufzeiten und ist bei globaler Gleichverteilung
der Latenzen in der Lage die zust andigen Knoten zu beliebigen Objektschlusseln
unabh angig von der Gr o e des Netzwerks in circa zweifacher direkter Laufzeit zu
erreichen. Wir zeigen, dass Papnet im Unterschied zu bestehenden P2P L osungen
hierbei eine schnelle Konvergenz zu einem Laufzeit-Optimum garantiert.
Als direkte Anwendung von Papnet stellen wir einen neuen Algorithmus zur verteil-
ten Bearbeitung von geospatialen Daten vor. Dieser erm oglicht eine praktisch
lineare Skalierung mit zunehmender Anfragelast und erfordert im Gegensatz zu
existierenden L osungen nicht den Aufbau und die P ege einer speziellen verteilten
aumlicr hen Datenstruktur.
VIIContents
1 Introduction 1
1.1 Problem De nition and Contribution . . . . . . . . . . . . . . . . . 4
2 Peer-to-Peer Basics 7
2.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Classi cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Pastry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 SkipNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Ganesan Online Load Balancing . . . . . . . . . . . . . . . . . . . 22
2.7 Distributed RDF Stores . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Enabling DHT Range Queries 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Alphanumerical Extension . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 The Papnet Overlay 43
4.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Papnet in a nutshell . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Formal Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.4 Arrivals, Departures, Maintenance . . . . . . . . . . . . . . . . . . 51
4.5 Latency Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
IXContents
5 Discovery of Proximate Peers 63
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3 Papnet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Papnet Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6 Scalable spatial data processing with Papnet 79
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3 Spatial Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7 Conclusion 101
Bibliography 103
X