Steiner, Moritz (2008) Structures and Algorithms for Peer-to-Peer Cooperation. PhD thesis Informatique, Eurecom p.218.

Full text available as: - SteinerDiss.pdf ( 3175 Kb )

Licence: Copyright

Alternative Locations: http://www.eurecom.fr/~btroup/BPublished/SteinerDiss.pdf, http://www.informatik.uni-mannheim.de/pi4/publications/Steiner2008d.pdf

Abstract

Peer-to-peer overlay networks are distributed systems, without any hierarchical organization or centralized control. Peers form self-organizing overlay networks that are on top of the Internet.



Both parts of this thesis deal with peer-to-peer overlay networks, the first part with unstructured ones used to build a large scale Networked Virtual Environment. The second part gives insights on how the users of a real life structured peer-to-peer network behave, and how well the proposed algorithms for publishing and retrieving data works. Moreover we analyze the security (holes) in such a system.



Networked virtual environments (NVEs), also known as distributed virtual environments, are computer-generated, synthetic worlds that allow simultaneous interactions of multiple participants. Many efforts have been made to allow people to interact in realistic virtual environments, resulting in the recent boom of Massively Multiplayer Online Games (MMOG).



In the first part of the thesis, we present a complete study of an augmented Delaunay-based overlay for peer-to-peer massively shared virtual worlds. We design an overlay network matching the Delaunay triangulation of the participating peers in a generalized d-dimensional space. Especially, we describe the selforganizing algorithms for peer insertion and deletion.



To reduce the delay penalty of overlay routing, we propose to augment each node of the Delaunay-based overlay with a limited number of carefully selected shortcut links creating a small-world. We show that a small number of shortcuts is sufficient to significantly decrease the delay of routing in the space.



We present a distributed algorithm for the clustering of peers. The algorithm is dynamic in the sense that whenever a peer joins or leaves the NVE, the clustering will be adapted if necessary by either splitting a cluster or merging clusters. The main idea of the algorithm is to classify links between adjacent peers into short intracluster and long inter-cluster links.



In a structured system, the neighbor relationship between peers and data locations is strictly defined. Searching in such systems is therefore determined by the particular network architecture. Among the strictly structured systems, some implement a distributed hash table (DHT) using different data structures. DHTs have been actively studied in literature and many different proposals have been made on how to organize peers in a DHT. However, very few DHTs have been implemented in real systems and deployed on a large scale. One exception is KAD, a DHT based on Kademlia, which is part of eDonkey, a peer-to-peer file sharing system with several million simultaneous users.



In the second part of this thesis we give a detailed background on KAD, the organization of the peers, the search and the publish operations, and we describe our measurement methodology. We have been crawling KAD continuously for more than a year. We obtained information about geographical distribution of peers, session times, peer availability, and peer lifetime. We found that session times are Weibull distributed and show how this information can be exploited to make the publishing Mechanism much more efficient.



As we have been studying KAD over the course of the last two years we have been both, fascinated and frightened by the possibilities KAD offers. We show that mounting a Sybil attack is very easy in KAD and allows to compromise the privacy of KAD users, to compromise the correct operation of the key lookup and to mount DDOS with very little resources.

References

Steiner, Moritz (2008) Structures et Algorithmes pour la coopération pair-à-pair. Doctorat Informatique, Eurecom

Table of content

List of Figures xiii

List of Tables xvii

1 Introduction 1

1.1 Peer-to-peer networks - 1

1.2 Networked virtual environments - 4

1.3 Organisation of the Thesis - 7

I An Augmented Delaunay Overlay for Decentralized Virtual

Worlds 11

2 Introduction 13

2.1 Networked Virtual Environments - 14

2.2 Contributions - 15

3 Maintaining a Delaunay-based Overlay 17

3.1 Model and Definitions - 17

3.2 Peer Insertion - 18

3.3 Peer Deletion - 23

4 Underlay Shortcuts 29

4.1 Principles - 30

4.2 Related Work - 31

4.3 Algorithm - 32

4.4 Simulation Results and Evaluation - 32

4.5 Conclusion - 40

5 Dynamic and Distributed Clustering 41

5.1 Principles - 42

5.2 Related Work - 43

5.3 Algorithm - 44

5.4 Simulation Results and Evaluation - 49

5.5 Conclusion - 55

6 Conclusion of Part I 57

II Measurements of real world peer-to-peer networks 59

7 Introduction 61

7.1 Contributions - 62

8 Background and Methodology 65

8.1 Routing in Kademlia - 65

8.2 Two-Level Publishing in Kademlia - 66

8.3 Crawling Peers with Blizzard - 68

8.4 Spying for Content with Mistral - 73

8.5 Azureus - 75

8.6 Vivaldi Network Coordinates - 75

9 Peer behavior in KAD 77

9.1 Global View of KAD - 78

9.2 Peer View - 86

9.3 Related Work - 95

9.4 Design Implications - 97

9.5 Conclusion - 98

10 Content in KAD 101

10.1 The Sybil Attack - 102

10.2 The Content Pollution Attack - 104

10.3 Spy Results - 106

10.4 Reducing the Publish Actions - 109

10.5 Related Work - 113

10.6 Conclusion - 115

11 Content Access in aMule 117

11.1 Architecture - 118

11.2 Analysis of the Content Search Process - 123

11.3 Evaluation - 125

11.4 Improving the Content Lookup - 133

11.5 Related Work - 134

11.6 Discussion and Conclusions - 135

12 Applying the Developed Measurement Techniques to Azureus 137

12.1 Measurement Methodology - 138

12.2 Dataset - 139

12.3 Crawl Results - 140

12.4 Evaluation of the Vivaldi Internet Coordinates Used in Azureus - 146

12.5 Conclusion - 153

13 Conclusion of Part II 155

14 Summary 159

Statistiques de consultation

Repository Staff Only: edit this item