Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Peer-to-peer location based search [Elektronische Ressource] : engineering a novel peer-to-peer overlay network / von Aleksandra Kovačevič

De
225 pages
Ajouté le : 01 janvier 2009
Lecture(s) : 37
Signaler un abus

PEER-TO-PEER LOCATION-BASED SEARCH:
ENGINEERING A NOVEL PEER-TO-PEER OVERLAY
NETWORK
Dissertationsschrift
in englischer Sprache
vorgelegt und genehmigt
am Fachbereich 18
Elektrotechnik und Informationstechnik
der Technischen Universität Darmstadt von
ˇ ´dipl.-ing. aleksandra kovacevic
geboren am 21. Juni 1980 in Belgrad, Serbien
zur Erlangung des akademischen Grades
eines Doktor-Ingenieurs (Dr.-Ing.)
Erstreferent: Prof. Dr.-Ing. Ralf Steinmetz
Korreferent: Prof. Dr.-Ing. Klaus WehrleTag der Einreichung: 14.07.2009
Tag der Disputation: 17.08.2009
Hochschulkennziffer D17
Darmstadt 2009
Dieses Dokument wird bereitgestellt von tuprints, E-Publishing-Service der
Technischen Universität Darmstadt.
http://tuprints.ulb.tu-darmstadt.de
tuprints@ulb.tu-darmstadt.de
Bitte zitieren Sie dieses Dokument als:
URN: urn:nbn:de:tuda-tuprints-18931
URL: http://tuprints.ulb.tu-darmstadt.de/1893
Die Veröffentlichung steht unter folgender Creative Commons Lizenz:
Namensnennung – Keine kommerzielle Nutzung – Keine Bearbeitung 2.0 Deutschland
http://creativecommons.org/licenses/by-nc-nd/2.0/de/
iiABSTRACT
Personalization of Internet services is a significant feature and exploit-
ing 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-peersolution,eachpeerisresponsiblefortheinformationabout
the object it represents, therefore, updating and publishing information
isdonedirectlywithoutasinglepointoffailure. Itisavailabletoawide
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. Su-
perpeers 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 Peerfact-
Sim.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
overlaytothephysicalunderlaywhichreducedtotaltransmissiondelay
and unnecessary underlay traffic. Although uneven load distribution
vseems 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 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
underextremechurnandcriticalfailuresistobecreditedtothevarious
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.
viZUSAMMENFASSUNG
DurchPersonalisierungbringenInternetdiensteeinengroßenMehrwert,
insbesonderewenndabeiderAufenthaltsortdesNutzerseinbezogen
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 Informa-
tionen über das gesuchte Objekt (beispielweise eine Speisekarte, die
Ausstattung oder Preise) sind selten verfügbar, da solch große Daten-
mengen 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 Engi-
neering 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 Evalua-
tionen identifizieren wir den Einfluss von deren Designentscheidungen
auf Qualitätsaspekte wie Effizienz, Skalierbarkeit, Robustheit und Sta-
bilität. Die Grundlage für das Design unserer Lösung basiert auf dieser
Studie.
Das resultierende Overlay-Netzwerk, Globase.KOM, ist ein struk-
turiertes 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 Projek-
tionderWeltkarteistinrechteckige,überlappungsfreieZonenaufgeteilt.
JedeZoneisteinemSuperpeerzugeteilt,dersichselbstinnerhalbdieser
Zone befindet. Dieser ist für alle Peers in der Zone verantwortlich. Die
Superpeers formen einen Baum, welcher aus den Teilmengenbeziehun-
gen der Zonen besteht.
Ein weiterer Beitrag dieser Dissertation ist eine klare Evaluations-
methodikzurUntersuchungvonPeer-to-Peer-basiertenSuchoverlaynet-
zen, durch die Definition von Metriken und verschiedenen Lastmod-
ellen – die entscheidende Qualitätskriterien adressieren. Für realis-
tische Lastmodelle analysieren wir das Verhalten der Nutzern von
VoIP-Anwendungen wie Skype, das sich stark von dem Nutzungsver-
halten populärer Dateitauschbörsen unterscheidet. Als Evaluation-
swerkzeug nutzen wir das Simulationsrahmenwerk PeerfactSim.KOM
viiund 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 Beantwor-
tung 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
SuperpeershöhererBaumebenen. UnsereLösungskaliertlogarithmisch
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
desAdressbereichs,dessenVerwaltungunddieZwischenverbindungen.
DemIdentifikatoreinesPeerskannmandessenLageunddenzuständi-
gen Bereich entnehmen. Dies ermöglicht eine elegante Wahl von Zwis-
chenverbindungen und effizientes ’greedy Routing’. Die Zwischen-
v 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 benutztwerden. Die Simulationsergeb-
nisse wurden durch einen Prototypen bestätigt. Die Anwendbarkeit
unser Lösung zeigen wir beispielhaft für verteilte multimediale Kom-
munikation und zukünftige Peer-to-Peer-basierte, kollaborative Anwen-
dungen.
viii"Feeling gratitude and not expressing it
is like wrapping a present and not giving it."
— William A. Ward
ACKNOWLEDGMENTS
OneofthethingsIlookedforwardtomostwhilewritingthethesiswas
writing the acknowledgments to all of the people who contributed to it.
I am pleased to thank Prof. Ralf Steinmetz for believing in a girl
whose voice trembled, on the verge of tears during a disastrous in-
terview presentation. Thank you very much for all of your support,
guidance, and encouragement! Or (because you insist on speaking
more German for practice) – Vielen Dank für Unterstützung und Er-
muttigung! I would like to thank my co-supervisor Prof. Klaus Wehrle
for his kind help and valuable feedback.
My first year in KOM was made so much easier with the greatest
mentor one can have, who generously shares his experiences and ideas.
Oli, gigantic thank you for all that you have done! Moving to Germany,
adaptingandjustgettingbyinfirstweekswouldhavebeenmuchmore
complicatedanddifficultwithoutthehugesupportandhelpfromNico.
Thank you for all your advice, friendship, frankness and many funny
moments. Kalman, thanks for being a fantastic colleague and team
worker, full of energy and ideas, always ready to help and sacrifice
your time. Most of all thank you for being such a great friend!
MyP2PGroup@KOMwasthesourceofmostoftheideas,motivation,
and fun at work. Sebastian, my first and best student, a brilliant
colleague, who together with Konstantin provided powerful simulation
frameworkPeerfactSim.KOM-thankyouboth! Osama,thanksforyour
support, making us laugh, and providing us with various Lebanese
delicacies. Christian and Dominik - thank you for your understanding
and support in the last few weeks.
QuaP2P group brought forward many inspiring discussions during
three years of cooperation. A special thanks goes to Prof. Andy Schürr,
Prof. Max Mühlhäuser, Prof. Alejandro Buchmann, Thorsten Strufe,
Dirk Bradler, and Christof Leng for their valuable input.
I enjoy working and brainstorming with my students immensely. A
great many thanks go to all of them, especially Leo, Aleksandar, Andre,
Till, Pei, Julius, Andre, Hans, Leonid, Nico, Patrick, and Christian.
KOM is a great environment for productive work and personal
development. My colleagues Doreen, Sonja, Alex Perez, Stefan Schulte,
Julian, Lasse, Parag, Matthias Kropf, Tronje, Mathias Hollick, Michael
Niemann, Farid, Andre König, Rainer, Christoph, without really being
aware of it, encouraged me with the right words and feedback in the
rightmoments. IwouldliketothanktoNickforunselfishlysharinghis
experiences in writing PhD thesis and Andre Miede for this beautiful
template. Gisela, Karola, Sabine, Moni, Marion, and Liselotte - thank
you for bringing so much warmness and cheerfulness to the institute.
ixVasilios Darlagianis introduced me to the peer-to-peer research and
taughtmehowtoreadperfectlywrittenpaperswithcriticalperspective
- thank you for everything! I would also like to thank Kai Fischbach,
KrishnaandShrutiPanditforalloftheirvaluablehints,encouragement
and inspiration. Prof. Abdulmotaleb El Saddik provided valuable tips
about research and writing process and learned me the importance of
laugh and fun while hard and exhaustive work :)
I am especially grateful to my husband, excellent colleague, and best
friend, Patrick for being so supportive, caring and patient with me.
Thankyouforallofthefruitfulresearchdiscussionsandhelpinediting
the thesis, particularly now in the last weeks of writing. Puno te volim!
Most importantly, I would like to thank my dearest parents for being
my best friends as well as my greatest support and inspiration -
. Sale, my coolest and caring brother, thanks
for, among all other things, brainwashing me constantly with so many
different music styles. Avola is my second family - thanks for all your
help. Margret, Salomon, Sonali, Anita, and Christian thank you for
being on my side.
A special thank you goes to my dear and supportive friends Irena,
Milica, Ljubica, and Ana who proved that distance does not influence
real friendship. Bibiana, thank you so much for your support in the
first phases of writing this thesis and for being such a dear and caring
friend. This thesis would not have any ’a’ or ’the’ without Annabel
Baird, who proof read my thesis. Thank you for being such a cheerful
and positive friend and encouraging me with e-mails starting with
"Dear Dr. Sandra" :-) Aleksandra Popovic and Zoran Dimitrijevic had
a big influence on me five years ago, introducing me to the research
world which inspired my decision about my career path.
Beyond being a significant part of my research, Skype and P2P
technology allow me stay in contact with my family and friends in
BelgradewhileFacebookcuresoccasionalnostalgia. Acknowledgments
must go to the Matrix Soundtrack which was always there for me
during long nights in the office, keeping me running and giving me the
illusion of saving the world :-)
x

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin