Loading…
Papnet: An order-preserving and latency-aware P2P Overlay and its Applications
Raack, Martin
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.
