Performance analysis of structured overlay networks [Elektronische Ressource] / vorgelegt von Andreas Binzenhöfer

Sujets

• Informatik

Informations

• Publié par: julius-maximilians-universitat_wurzburg
• Publié le: 01 janvier 2008
• Nombre de lectures: 6
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Julius-Maximilians-Universität Würzburg
Institut für Informatik
Lehrstuhl für Verteilte Systeme
Prof. Dr. P. Tran-Gia
Performance Analysis of Structured
Overlay Networks
Andreas Binzenhöfer
Würzburger Beiträge zur
Leistungsbewertung Verteilter Systeme
Bericht 01/08Würzburger Beiträge zur
Leistungsbewertung Verteilter Systeme
Herausgeber
Prof. Dr. P. Tran-Gia
Universität Würzburg
Institut für Informatik
Lehrstuhl für Verteilte Systeme
Am Hubland
D-97074 Würzburg
Tel.: [phone]
Fax.: [phone]
email: [e-mail]
Satz
Reproduktionsfähige Vorlage vom Autor.
AGesetzt in LT X Computer Modern 9pt.E
ISSN 1432-8801Performance Analysis of Structured
Overlay Networks
Dissertation zur Erlangung des
naturwissenschaftlichen Doktorgrades
der Julius–Maximilians–Universität Würzburg
vorgelegt von
Andreas Binzenhöfer
aus
Würzburg
Würzburg 2008Eingereicht am: 04.12.2007
bei der Fakultät für Mathematik und Informatik
1. Gutachter: Prof. Dr.-Ing. P. Tran-Gia
2. Gutachter: Prof. Dr.-Ing. J. Eberspächer
3. Gutachter: Prof. N. Wakamiya
Tag der mündlichen Prüfung: 06.02.2008Acknowledgements
This monograph summarizes five years of research studies, an everlasting strug-
gle for publications, numerous perceived nervous breakdowns, and above all a
very pleasant time with my colleagues who by now have all become dear friends
of mine. This work would not have been possible if it had not been for them and
a number of other people who all helped and supported me in different ways.
First of all I would like to thank my advisor Prof. Phuoc Tran-Gia who not
only provided me with an excellent opportunity to work in a scientific environ-
ment but did so with great technical as well as interpersonal commitment. Due
to his untiring efforts I was able to participate in both industrial as well as Eu-
ropean research projects. Beyond that I was also given the opportunity to visit
international conferences and colleagues, which was an invaluable experience I
would not like to have missed. I would also like to express my gratitude to Prof.
Jörg Eberspächer and Prof. Naoki Wakamiya who both acted as reviewers of this
thesis and provided me with valuable comments in discussions at multiple occa-
sions including joint projects, conferences, workshops, and short term visits. I am
also very much obliged to Prof. Dr. Klaus Schilling and Prof. Dr. Dietmar Seipel
for being available as examiners for my disputation. Furthermore, I would like
to thank Markus Fiedler, Ilkka Norros, Masayuki Murata, and Krzysztof Paw-
likowski for providing me the opportunity to visit their research laboratories.
My deepest appreciation goes to our secretary Mrs. Förster who with surpass-
ing patience and dedication makes life a lot easier for us at the department. I
would also like to thank the people at Bosch, Siemens, AOK, and DATEV who
worked together with me over the last five years. From both communication and
iAcknowledgements
collaboration with them I gained a great deal of experience and never lost track of
the practical aspects of my work. In addition to this I would like to thank Barbara
Emmert, Stefan Mühleck, Björn auf dem Graben, Johannes Dölfel, Markus Weiß
and especially Holger Schnabel, who all completed their diploma thesis under
my supervision and thereby eased my workload.
I also had the privilege of working with amazing colleagues, who were always
generous with their time and expertise. In particular, I’m very much indebted to
Dirk Staehle who has been generous and unstinting with his advise and sugges-
tions. He never got tired of discussing a problem over coffee and fascinatingly
always came up with a proper solution. In addition to him I also would like to
thank Tobias Hoßfeld, Simon Oechsner, Robert Henjes, and Oliver Rose who all
helped me to solve an important coupon collectors problem. Rastin Pries who
constantly challenged and occasionally outmatched me in a ferocious battle for
the most delicious breakfast. Barbara Staehle who has an unmatched talent to
transform scientific research results into a true piece of art. Michael Menth who
is the living proof that it still pays off to be fair-minded. Rüdiger Martin and
Andreas Mäder who both accompanied me for more than ten years on my jour-
ney through University. I also greatly benefited from conversations with Daniel
Schlosser, Michael Duelli, Thomas Zinner, Jens Milbrandt, Stefan Köhler, and
Kurt Tutschku. Furthermore, it is a pleasure to acknowledge my former colleague
Kenji Leibnitz who despite a distance of roughly 9000 km became an even closer
friend during the last years. Among the many researchers I met outside our de-
partment, Gerald Kunzmann became my closest colleague and a dear friend.
Special thanks go to my parents Alfred and Margot Binzenhöfer, as well as to
my brother Stefan Binzenhöfer. My family provided me with the necessary means
to adhere to my ideas and plans without ever questioning any of my decisions.
Finally, I would like to offer heartfelt thanks to my wife Stefanie Binzenhöfer.
Throughout the many years we spent together she has always been my help and
strength. Whenever I needed a friend, she was there for me. Whenever I had
doubts, she believed in me. I dedicate this to her.
iiContents
1 Introduction 1
1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Peer-to-Peer Key Technologies 5
2.1 Unstructured Overlay Networks . . . . . . . . . . . . . . . . . . 6
2.1.1 Gnutella: Distributed Search and Flooding . . . . . . . . 7
2.1.2 Freenet: Anonymity Protection . . . . . . . . . . . . . . 9
2.2 Structured P2P Networks . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Chord . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Kademlia . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Pastry . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.4 Content Addressable Networks (CAN) . . . . . . . . . . 26
2.3 Hybrid Architectures . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1 Client-Server-based Overlay Architectures . . . . . . . . 31
2.3.2 Content Distribution Networks (CDN) . . . . . . . . . . 33
2.3.3 SuperPeer-based Architectures . . . . . . . . . . . . . . 35
3 Performance Analysis of Structured P2P Networks 39
3.1 Functional and Stochastic Scalability . . . . . . . . . . . . . . . 40
3.2 General Approaches and Related Work . . . . . . . . . . . . . . 42
3.3 Delay Analysis of Chord-based Overlay Networks . . . . . . . . 46
3.3.1 Computation of the Peer Distance Distribution . . . . . . 47
iiiContents
3.3.2 Analytical Model of the Search Delay . . . . . . . . . . 54
3.3.3 Influence of Stochastic Network Conditions . . . . . . . 56
3.4 Evaluation of the Stability of Ring-based Architectures . . . . . . 61
3.4.1 Abstract Mathematical Model . . . . . . . . . . . . . . . 62
3.4.2 Derivation of Realistic Failure Probabilities . . . . . . . . 66
3.4.3 Validation of the Stability of the Overlay Structure . . . . 67
3.5 Simulative Evaluation of a Carrier-Grade Kademlia Network . . . 73
3.5.1 Description of the Simulation Environment . . . . . . . . 74
3.5.2 Improving the Search Efficiency . . . . . . . . . . . . . 76
3.5.3 Increasing the Robustness of the Overlay . . . . . . . . . 79
3.5.4 Reducing the Redundancy Overhead . . . . . . . . . . . 84
4 Modeling the Dynamics of P2P Overlays 91
4.1 Problem Formulation and Related Work . . . . . . . . . . . . . . 92
4.2 Estimating the Current Peer Population . . . . . . . . . . . . . . 96
4.2.1 Analytical Model . . . . . . . . . . . . . . . . . . . . . 96
4.2.2 Maximum Likelihood Estimation . . . . . . . . . . . . . 102
4.2.3 Accuracy of the Estimate . . . . . . . . . . . . . . . . . 104
4.3 Assessing the User-Behavior . . . . . . . . . . . . . . . . . . . 112
4.3.1 Algorithm to Capture the Fluctuations in the Overlay . . . 112
4.3.2 Analytical Derivation of the Churn Rate . . . . . . . . . 116
4.3.3 Accuracy, Responsiveness, and Practicability . . . . . . . 124
4.4 Monitoring a Distributed P2P System at Runtime . . . . . . . . . 132
4.4.1 A Divide and Conquer Approach . . . . . . . . . . . . . 133
4.4.2 Analytical Evaluation of the Algorithm . . . . . . . . . . 139
4.4.3 Interpretation of the Collected Statistics . . . . . . . . . 144
5 Conclusion 149
Bibliography and References 153
iv1 Introduction
In the last decades computer networks became one of the major building blocks
of our society. Large parts of our private and business life already depend on this
infrastructure for communication, information, and exchange of data. However,
until today the Internet is still driven by algorithms and technologies which have
been developed in the seventies and eighties. The traditional service architecture
in the Internet, e.g., is based on the simple client-server principle. That is, a sin-
gle central unit provides several clients with a service. Due to the continuously
increasing number of both users and services in today’s networks, it became time