Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3089
Main Title: Papnet: An order-preserving and latency-aware P2P Overlay and its Applications
Translated Title: Papnet: Ein Ordnungserhaltendes und Latenzberücksichtigendes P2P Netz und seine Anwendungen
Author(s): Raack, Martin
Advisor(s): Kao, Odej
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Diese Dissertation entwickelt ein neues P2P Overlay Netzwerk namens Papnet, welches die einzelnen Vorzüge 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ärschlüssel speichern. Dies ermoglicht sowohl effiziente Bereichsanfragen als auch die Implementierung einer Lastbalancierungs-Technik welche ein konstantes Lastungleichgewicht garantiert. Papnet berücksichtigt Nachrichtenlaufzeiten und ist bei globaler Gleichverteilung der Latenzen in der Lage die zuständigen Knoten zu beliebigen Objektschlüsseln unabhängig von der Größe des Netzwerks in circa zweifacher direkter Laufzeit zu erreichen. Wir zeigen, dass Papnet im Unterschied zu bestehenden P2P Lösungen hierbei eine schnelle Konvergenz zu einem Laufzeit-Optimum garantiert. Als direkte Anwendung von Papnet stellen wir einen neuen Algorithmus zur verteilten Bearbeitung von geospatialen Daten vor. Dieser ermöglicht eine praktisch lineare Skalierung mit zunehmender Anfragelast und erfordert im Gegensatz zu existierenden Lösungen nicht den Aufbau und die Pflege einer speziellen verteilten räumlichen Datenstruktur.
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 object keys in a sorted manner. This enables the efficient 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 asymptotically linear with the total query load. In contrast to existing solutions, the construction and maintenance of an explicit distributed spatial structure is not required.
URI: urn:nbn:de:kobv:83-opus-33970
http://depositonce.tu-berlin.de/handle/11303/3386
http://dx.doi.org/10.14279/depositonce-3089
Exam Date: 12-Jan-2012
Issue Date: 20-Jan-2012
Date Available: 20-Jan-2012
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Ausfallsicherheit
Bereichsanfragen
Latenz
Multidimensional
P2P
Fault Tolerance
Latency
Multidimensionality
P2P
Range Queries
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Telekommunikationssysteme » Publications

Files in This Item:
File Description SizeFormat 
Dokument_6.pdf6,91 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.