Papnet: An order-preserving and latency-aware P2P Overlay and its Applications

Papnet: Ein Ordnungserhaltendes und Latenzberücksichtigendes P2P Netz und seine Anwendungen

  • 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 garantDiese 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.show moreshow less
  • 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 laThis 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.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author: Martin Raack
URN:urn:nbn:de:kobv:83-opus-33970
Advisor:Prof. Dr. Odej Kao
Document Type:Doctoral Thesis
Language:English
Date of Publication (online):2012/01/20
Publishing Institution:Technische Universität Berlin
Granting Institution:Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Date of final exam:2012/01/12
Release Date:2012/01/20
Tag:Ausfallsicherheit; Bereichsanfragen; Latenz; Multidimensional; P2P
Fault Tolerance; Latency; Multidimensionality; P2P; Range Queries
Institutes:Institut für Telekommunikationssysteme
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht mit Print on Demand (u.a. für Dissertationen empfohlen)