TU Darmstadt / ULB / tuprints

Peer-to-Peer Location-based Search: Engineering a Novel Peer-to-Peer Overlay Network

Kovacevic, Aleksandra :
Peer-to-Peer Location-based Search: Engineering a Novel Peer-to-Peer Overlay Network.
TU Darmstadt
[Ph.D. Thesis], (2009)

[img]
Preview
PDF
FB18_AleksandraKovacevic-Thesis_2009.09.02.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives.

Download (9Mb) | Preview
Item Type: Ph.D. Thesis
Title: Peer-to-Peer Location-based Search: Engineering a Novel Peer-to-Peer Overlay Network
Language: English
Abstract:

Personalization of Internet services is a significant feature and exploiting the users’ location brings the most value to it. Location-based services have a wide application range – from emergency, tracking, and navigation services to informational and entertainment services. In existing centrally managed solutions, the results of location-based search are often incomplete or outdated. Additional information about the searched object (e.g. the menu, facilities, prices) is usually not available, as such a huge amount of data and frequent updates (e.g. the number of free places in restaurant) would overload the server. In a peer-to-peer solution, each peer is responsible for the information about the object it represents, therefore, updating and publishing information is done directly without a single point of failure. It is available to a wide community to join and publish their services, as peer-to-peer systems operate at low costs. The main goal of this thesis is to prove the feasibility of engineering a peer-to-peer solution for fully retrievable location-based search. Following an engineering approach, we first examine the most used and referred overlays of different types (unstructured, structured, and hybrid). Comparative evaluation identifies the influence of their design decisions on quality aspects such as efficiency, scalability, robustness, and stability. The foundation for the design of our solution is based on the findings from this study. The resulting overlay, Globase.KOM is a structured superpeer-based overlay in the form of a tree enhanced with interconnections. Superpeers are chosen from publicly reachable, static peers with more capacity, spare bandwidth, and good network connectivity. The world projection is divided into rectangular zones, which do not overlap. Each zone is assigned to a superpeer, located inside this zone. It is responsible for all peers in the zone. Superpeers form the tree, which is based on the subset-relation of their zones. Further contribution is the clear methodology for evaluating peer-to-peer search overlays, by defining metrics and various workloads that address all crucial quality properties. Additionally, in order to model realistic workloads, we discuss the difference between user behavior in popular file-sharing applications and VoIP applications such as Skype. As an evaluation tool, we select the simulation framework PeerfactSim.KOM and extend it to support various geographical distribution of peers on a world map and a location-aware churn model. The evaluation results prove the efficiency, good load balancing, scalability, robustness, and stability of the system. Query resolution is significantly faster than in related solutions. Additionally, the location-awareness of the overlay results in an efficient mapping of the logical overlay to the physical underlay which reduced total transmission delay and unnecessary underlay traffic. Although uneven load distribution seems to be an issue due to the tree structure of the overlay, we prove very good load balance due to interconnections and a careful zone formation, which together diminish a higher expected overload of superpeers in the higher tree levels. Our solution scales logarithmically with growing network size. It proves to be robust and stable under simultaneous failures of superpeers in higher tree levels, or in the same branch of the tree, and in the case of frequent querying. The biggest influence on the quality of our solution is the choice of identifier space, its management, and interconnections. A peer identifier contains the information responsibility and its location. That allows smart selection of interconnections and efficient greedy routing. Interconnections enable bypassing of the superpeers in higher levels of the tree and therefore allow equal load distribution among the superpeers. A fast recovery time and small performance variation under extreme churn and critical failures is to be credited to the various maintenance strategies used in combination. The simulation results are confirmed by a prototype and its applicability is shown in the examples of distributed multimedia communication and future peer-to-peer based collaborative applications.

Alternative Abstract:
Alternative AbstractLanguage
Durch Personalisierung bringen Internetdienste einen großen Mehrwert, insbesondere wenn dabei der Aufenthaltsort des Nutzers einbezogen wird. Lokationsbasierte Dienste haben ein weites Anwendungsfeld - von Notruf-, Verfolgungs- und Navigationsdiensten zu informierenden und unterhaltenden Diensten. Die Ergebnisse einer lokationsbasierten Suche existierender zentraler Lösungen sind oft unvollständig und veraltet. Zusätzliche Informationen über das gesuchte Objekt (beispielweise eine Speisekarte, die Ausstattung oder Preise) sind selten verfügbar, da solch große Datenmengen und häufige Aktualisierungen (z.B. die Anzahl freier Plätze in einem Restaurant) einen Server überladen würden. In einer Peer-to-Peer-basierten Lösung ist jeder Peer für Informationen über das repräsentierte Objekt verantwortlich. Informationen werden direkt aktualisiert und angeboten, ohne auf eine zentrale Stelle angewiesen zu sein, bei deren Ausfall das System zusammenbricht. Die niedrigen Betriebskosten von Peer-to-Peer-Systemen machen sie für eine große Nutzerschaft verfügbar. Das Hauptziel dieser Dissertation ist zu beweisen, dass das Engineering einer Peer-to-Peer-basierten Lösung für lokationsbasierte vollständige Suche machbar ist. Als erster Schritt der Engineering-Vorgehensweise, untersuchen wir die am meisten benutzten und referenzierten Overlay-Netzwerktypen (unstrukturiert, strukturiert und hybrid). Durch vergleichende Evaluationen identifizieren wir den Einfluss von deren Designentscheidungen auf Qualitätsaspekte wie Effizienz, Skalierbarkeit, Robustheit und Stabilität. Die Grundlage für das Design unserer Lösung basiert auf dieser Studie. Das resultierende Overlay-Netzwerk, Globase.KOM, ist ein strukturiertes Superpeer-basiertes Overlay-Netzwerk in Form eines durch Zwischenverbindungen erweiterten Baumes. Die Superpeers werden unter öffentlich erreichbaren, statischen Peers mit höherer Kapazität, unbenutzter Bandbreite und guter Netzanbindung gewählt. Die Projektion der Weltkarte ist in rechteckige, überlappungsfreie Zonen aufgeteilt. Jede Zone ist einem Superpeer zugeteilt, der sich selbst innerhalb dieser Zone befindet. Dieser ist für alle Peers in der Zone verantwortlich. Die Superpeers formen einen Baum, welcher aus den Teilmengenbeziehungen der Zonen besteht. Ein weiterer Beitrag dieser Dissertation ist eine klare Evaluationsmethodik zur Untersuchung von Peer-to-Peer-basierten Suchoverlaynetzen, durch die Definition von Metriken und verschiedenen Lastmodellen – die entscheidende Qualitätskriterien adressieren. Für realistische Lastmodelle analysieren wir das Verhalten der Nutzern von VoIP-Anwendungen wie Skype, das sich stark von dem Nutzungsverhalten populärer Dateitauschbörsen unterscheidet. Als Evaluationswerkzeug nutzen wir das Simulationsrahmenwerk PeerfactSim.KOM und erweiteren es, um verschiedene geographische Verteilungen von Peers auf einer Weltkarte und lokationsbewusstes Churn unter diesen zu ermöglichen. Die Evaluationsergebnisse bestätigen unserem System gute Effizienz, Lastverteilung, Skalierbarkeit, Robustheit und Stabilität. Die Beantwortung von Suchanfragen ist entscheidend schneller als in verwandten Lösungen. Zusätzlich ist durch das Lokationsbewusstsein das Overlay-Netz effizient auf das physikalische Underlay-Netzwerk abgebildet, wodurch Übertragungsverzögerungen und unnötiger Datenverkehr im Underlay-Netz reduziert werden. Obwohl es scheint, als würde die Baumstruktur eine ungleiche Lastverteilung zur Folge haben können, widerlegen unsere Untersuchungen dies. Zwischenverbindungen und ein sorgfältiges Formen von Zonen vermindern eine erhöhte Last auf Superpeers höherer Baumebenen. Unsere Lösung skaliert logarithmisch mit wachsender Netzwerkgröße. Sie erweist sich unter gleichzeitigem Ausfall von Superpeers im gleichen Zweig oder in höheren Ebenen des Baumes, selbst bei häufigen Suchanfragen, als robust und stabil. Den größten Einfluss auf die Qualität unserer Lösung hat die Wahl des Adressbereichs, dessen Verwaltung und die Zwischenverbindungen. Dem Identifikator eines Peers kann man dessen Lage und den zuständigen Bereich entnehmen. Dies ermöglicht eine elegante Wahl von Zwischenverbindungen und effizientes ’greedy Routing’. Die Zwischenverbindungen erlauben die Superpeers in den höheren Baumebenen zu umgehen und ermöglichen dadurch eine gleichmäßige Lastverteilung unter den Superpeers. Die kurze Wiederherstellungszeit nach Peer-ausfällen und die geringe Variation der Leistung unter extrem hohem Churn und kritischen Ausfällen ist den diversen Wartungsstrategien zuzuschreiben, die kombiniert benutzt werden. Die Simulationsergebnisse wurden durch einen Prototypen bestätigt. Die Anwendbarkeit unser Lösung zeigen wir beispielhaft für verteilte multimediale Kommunikation und zukünftige Peer-to-Peer-basierte, kollaborative Anwendungen.German
Classification DDC: 600 Technik, Medizin, angewandte Wissenschaften > 620 Ingenieurwissenschaften
Divisions: Fachbereich Elektrotechnik und Informationstechnik > Multimedia Kommunikation
Date Deposited: 09 Sep 2009 09:55
Last Modified: 07 Dec 2012 11:55
URN: urn:nbn:de:tuda-tuprints-18931
License: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0
Referees: Steinmetz, Prof. Dr.- Ralf and Wehrle, Prof. Dr.- Klaus
Refereed: 17 August 2009
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/1893
Export:

Actions (login required)

View Item View Item