The field of structured P2P systems has seen fast growth upon the introduction of Distributed Hash Tables (DHTs) in the early 2000s. The first proposals, including Chord, Pastry, Tapestry, were gradually improved to cope with scalability, locality and security issues. By utilizing the processing and bandwidth resources of end users, the P2P approach enables high performance of data distribution which is hard to achieve with traditional client-server architectures. The P2P computing community is also being actively utilized for software updates to the Internet, P2PSIP VoIP, video-on-demand, and distributed backups. The recent introduction of the identifier-locator split proposal for future Internet architectures poses another important application for DHTs, namely mapping between host permanent identity and changing IP address. The growing complexity and scale of modern P2P systems requires the introduction of hierarchy and intelligence in routing of requests. Structured Peer-to-Peer Systems covers fundamental issues in organization, optimization, and tradeoffs of present large-scale structured P2P systems, as well as, provides principles, analytical models, and simulation methods applicable in designing future systems. Part I presents the state-of-the-art of structured P2P systems, popular DHT topologies and protocols, and the design challenges for efficient P2P network topology organization, routing, scalability, and security. Part II shows that local strategies with limited knowledge per peer provide the highest scalability level subject to reasonable performance and security constraints. Although the strategies are local, their efficiency is due to elements of hierarchical organization, which appear in many DHT designs that traditionally are considered as flat ones. Part III describes methods to gradually enhance the local view limit when a peer is capable to operate with larger knowledge, still partial, about the entire system. These methods were formed in the evolution of hierarchical organization from flat DHT networks to hierarchical DHT architectures, look-ahead routing, and topology-aware ranking. Part IV highlights some known P2P-based experimental systems and commercial applications in the modern Internet. The discussion clarifies the importance of P2P technology for building present and future Internet systems.
Author(s): Dmitry Korzun, Andrei Gurtov
Publisher: Springer
Year: 2012
Language: English
Pages: 389
Cover......Page 1
Fundamentals of Hierarchical Organization,
Routing, Scaling, and Security......Page 4
ISBN 9781461454823......Page 5
Foreword......Page 8
Preface......Page 10
Contents......Page 16
Abbreviations......Page 22
Part I:
Introduction......Page 24
Overview of Part I......Page 26
1.1 Introduction......Page 28
1.2 Mathematical Preliminaries......Page 29
1.3 Distributed Hash Tables......Page 30
1.4.1 Consistent Hashing and Uniform Partitioning......Page 35
1.4.2 Inaccuracy of the Homogeneity Assumption......Page 36
1.4.3 Arrangement Models......Page 38
1.5.1 Local Knowledge Size vs. Routing Performance......Page 39
1.5.2 System Operation Quality......Page 40
References......Page 41
2.1.1 Content Addressable Network......Page 48
2.2.1 Chord......Page 50
2.2.2 Kademlia......Page 52
2.2.3 Accordion......Page 53
2.3 PRR Trees......Page 54
2.3.1 Pastry......Page 55
2.3.3 Bamboo......Page 56
2.4.1 Trie......Page 58
2.5.1 De Bruijn Graphs......Page 59
2.6 Butterfly......Page 61
2.7 O(1)-Hop......Page 62
References......Page 63
Part II:
Local Strategies......Page 66
Overview of Part II......Page 68
3.1 Introduction......Page 70
3.2.1 Long-Range Neighbors......Page 71
3.2.2 Case Study: Symphony......Page 72
3.2.3 Path-Based Hierarchies......Page 75
3.3 Routing in Greedy DHTs and de Bruijn Graphs......Page 77
3.3.1 Conventional Greedy DHTs......Page 78
3.3.2 Chord-Like DHTs......Page 80
3.3.3 De Bruijn Graphs......Page 81
3.4.1 Kleinberg Tree-Based Model......Page 83
3.4.2 Proximity-Based Selection......Page 84
3.4.3 Other Criteria for Local Adaptation......Page 87
3.5 Global Routing and Lookup Structure......Page 88
3.5.2 Distributed Trie......Page 89
3.5.3 Cyclic Routing......Page 90
3.6.1 Designs with Large Routing Tables......Page 91
3.6.2 Maintenance Traffic Overhead......Page 92
3.6.3 Routing Table Consistency......Page 93
3.7 Local Routing and Replication......Page 95
3.7.1 Source-Aware Replication......Page 96
3.7.2 Even Replication......Page 98
3.7.3 Destination-Aware Replication......Page 100
3.7.4 Maintenance Overhead......Page 104
3.8 Summary......Page 105
References......Page 106
4.1 Introduction......Page 110
4.2 Node ID Specialization......Page 111
4.2.1 Viceroy......Page 112
4.2.2 Ulysses......Page 113
4.2.3 Cycloid......Page 114
4.2.4 Pappilon......Page 115
4.2.5 Censorship Resistant Network......Page 116
4.3 Specialized Node ID Management......Page 117
4.3.1 ID Assignment......Page 118
4.3.3 ID Reassignment......Page 119
4.4 Distributing Resources Among Nodes......Page 121
4.5 Resource Semantics......Page 122
4.6 Non-uniform Resource Distribution......Page 125
4.7 Topology Evolution......Page 127
References......Page 129
5.1 Introduction......Page 134
5.2 Clustering Principle......Page 136
5.3.1 Virtual Nodes......Page 138
5.3.2 Proximity-Based Clusters......Page 140
5.3.3 False Clustering......Page 143
5.4.1.1 Continuous Semantic Similarity Metric......Page 145
5.4.1.2 Discrete Semantic Classification......Page 146
5.4.2.1 Resource Popularity......Page 147
5.4.2.2 Social Rationality......Page 149
References......Page 151
6.1 Introduction......Page 156
6.2.1 Rank-Based Operational Decision-Making......Page 158
6.2.2 Node Ranks in BT-Exchange......Page 160
6.2.3 Local Ranks: Nodes and Resources......Page 163
6.3 Linear Ranking Model......Page 166
6.3.1 Linear Resource Ranks......Page 167
6.3.2 Reduction to Linear Programming......Page 172
6.3.3 Rank Existence......Page 176
6.4.1 Allocation of Common Resource......Page 178
6.4.2 BT Systems......Page 180
6.4.3 Plant-Like Systems......Page 182
6.4.4 Network Games and Market Pricing......Page 183
6.5 Summary......Page 185
References......Page 186
Summary of Part II......Page 188
Part III:
Beyond the Local Knowledge......Page 190
Overview of Part III......Page 192
7.1 Introduction......Page 194
7.2.1.1 Cluster-Based Model......Page 196
7.2.1.2 Tree-Based Model......Page 199
7.2.1.3 Group-Based Model......Page 200
7.2.2 Layering Principle......Page 202
7.2.3.1 Vertical Approach......Page 204
7.2.3.2 Horizontal Approach......Page 208
7.2.3.3 Disjoining and Nesting Principles......Page 209
7.3.1.1 Hierarchical Systems by Garc´es-Erice et al. [10]......Page 213
7.3.1.3 Structured Superpeers by Mizrak et al. [46]......Page 215
7.3.1.4 OneHop by Gupta et al. [6, 15]......Page 216
7.3.1.5 Rings of Unstructured Clouds by Singh and Liu [57]......Page 217
7.3.1.6 Chordella by Zoels et al. [77, 79]......Page 219
7.3.1.7 HONet by Tian et al. [62]......Page 220
7.3.1.8 Content-Based Hierarchy by Zoels et al. [76]......Page 221
7.3.1.9 Hierarchy-Adaptive Topology by Zhang et al. [71]......Page 223
7.3.1.10 Chord by Joung and Wang [19]......Page 224
7.3.1.11 Hierarchical DHT-Based Overlay Networks by Martinez-Yelmo
et al. [39–41]......Page 225
7.3.1.12 HSN by Guisheng et al. [13]......Page 227
7.3.2 Nested Hierarchical Architectures......Page 228
7.3.2.1 Brocade by Zhao et al. [74]......Page 229
7.3.2.2 eCAN by Xu et al. [66, 73]......Page 230
7.3.2.3 Super-Peer Based Lookup by Zhu et al. [75]......Page 231
7.3.2.4 Coral by Freedman et al. [7]......Page 232
7.3.2.5 HIERAS by Xu et al. [67]......Page 233
7.3.2.6 TOPLUS by Garces-Erice et al. [11]......Page 234
7.3.2.7 Canon by Ganesan et al. [9]......Page 235
7.3.2.8 Multi-Ring Hierarchy by Mislove and Druschel [45]......Page 236
7.3.2.9 Diminished Chord by Karger and Ruhl [20]......Page 237
7.3.2.10 Cyclone by Artigas et al. [1, 2]......Page 238
7.3.2.11 GTap by Zhang et al. [72]......Page 239
7.4.1 Local State Cost......Page 241
7.4.2 Routing Cost......Page 242
7.4.3 Network Traffic Cost......Page 243
References......Page 244
8.1 Introduction......Page 250
8.2 Problem Domain......Page 252
8.3.1 Cycle Transitions......Page 253
8.3.2 Dependable Routing and Path Length Upper Bounds......Page 254
8.3.3 Constructing Cycles......Page 255
8.3.5 Maintaining Cycles......Page 257
8.4 Simulation Results......Page 258
8.4.3 CR-Chord vs. Chord......Page 259
8.5 Discussion on Advanced Capabilities......Page 262
8.5.2 Cyclic vs. Acyclic Paths......Page 263
8.5.3 Multi-Path Routing......Page 264
8.6 Summary......Page 265
References......Page 266
9.1 Introduction......Page 268
9.2 Mathematical Background......Page 269
9.2.2 Nonnegative Linear Diophantine Equations......Page 270
9.3.1 Routing and Forwarding......Page 273
9.3.2 Forwarding Options as Grammar Rules......Page 274
9.4.1 Routes and Grammar Derivations......Page 276
9.4.2 Routes and ANLDE System Solutions......Page 277
9.4.3 Path Structure......Page 279
9.5.1 Workload and Utilization......Page 281
9.5.2 Connectivity......Page 283
9.5.3 Performance......Page 284
9.5.4 Comparisons......Page 285
9.5.5 Computational Complexity......Page 286
9.6 Summary......Page 287
References......Page 288
10.1 Introduction......Page 290
10.2.1 P2P Selection Problems......Page 292
10.2.2 PageRank Algorithm......Page 294
10.2.3 EigenTrust Algorithm......Page 295
10.3.1 Local Cyclic Structure......Page 297
10.3.2 Relation of Routing and Ranking......Page 299
10.3.3 Neighbor Selection and Malicious Nodes......Page 301
10.3.4 Resource Exchange......Page 302
10.4 Summary......Page 305
References......Page 306
Summary of Part III......Page 310
Part IV:
Applications......Page 312
Overview of Part IV......Page 314
11.1 Introduction......Page 316
11.2.1 DHT Routing......Page 318
11.2.2 Chord......Page 319
11.2.3 Attacks by Dropping Lookups......Page 320
11.3 Integration of Cyclic Routing with Chord......Page 321
11.4.2 Simulation Scheme......Page 324
11.4.3 Churn Model......Page 325
11.4.4 Success and Failure Types......Page 327
11.5.1 Basic Facts......Page 329
11.5.2 Variations......Page 333
11.5.3 Analysis of Cycles......Page 336
11.6 Related Work, Comparison, and Discussion......Page 340
11.7 Summary......Page 344
References......Page 345
12.1 Introduction......Page 348
12.2.1 Host Identity Protocol (HIP)......Page 349
12.2.3 Host Identity Indirection Infrastructure (Hi3)......Page 350
12.3 Control Plane......Page 351
12.3.1 Request Types......Page 352
12.3.1.2 Mobility Update......Page 353
12.3.2.1 Upper Bounds for Costs......Page 354
12.3.2.2 Costs Inside and Outside of i3......Page 355
12.3.3 Latency Estimates......Page 356
12.4.1 General Workload Pattern......Page 359
12.4.2.1 Mobile Peers......Page 360
12.5 Scalability Analysis......Page 361
12.5.1 The Utilization/Latency Trade-Off......Page 362
12.5.2.1 Estimating the Needed i3 Size......Page 363
12.5.2.2 Resistance to DDoS Attacks......Page 364
References......Page 365
13.1 OpenDHT......Page 368
13.2 Google's BigTable......Page 370
13.3 Amazon's Dynamo......Page 371
13.4 Facebook's Cassandra......Page 373
13.5 LinkedIn Voldemort......Page 375
13.7 BitTorrent......Page 376
Reference......Page 378
Summary of Part IV......Page 380
Index......Page 382
