Handbook of Peer-to-Peer Networking (eBook)

Preface 6
Acknowledgements 9
Contents 10
List of Contributors 35
Part I Introduction to Peer-to-Peer Networking 44
Peer-to-Peer Networking and Applications: Synopsis and Research Directions 45
John F. Buford and Heather Yu 45
1 Introduction 45
1.1 Significance and Emergence 45
1.2 Key Applications 47
1.3 Definition and Properties of P2P Systems 48
1.4 Business Models 49
1.5 Technology Drivers 50
1.6 Structure of the Chapter 52
2 Overlay Basics 52
2.1 Classification and Taxonomy 52
2.2 Unstructured Overlays 53
2.3 Structured Overlays 55
2.4 Hierarchical and Federated Overlays 58
2.5 Service Overlays 59
2.6 Semantic Overlays 60
2.7 Sensor Overlays 61
2.8 Research Directions 61
3 Overlay Dynamics, Heterogeneity and Mobility 61
3.1 Churn and Overlay Maintenance 61
3.2 Mobility in P2P Overlays 62
3.3 Overlays for MANETs and Ad Hoc Networks 63
3.4 Heterogeneity and Variable Hop Overlays 63
3.5 Research Directions 65
4 P2P Content Access and Delivery 65
4.1 Content Search 66
4.2 P2P Streaming and Multicasting 69
4.3 Caching and Replication 71
4.4 Summary of Design Issues 73
4.5 Research Issues 73
5 Security 74
5.1 The P2P Security Concern 74
5.2 Basic Classifications of P2P Network Security Threats 75
5.3 Counter Measures 76
5.4 Fairness, Trust and Privacy Issues 78
5.5 More on P2P Security 78
6 Summary 79
References 79
The Social Impact of P2P Systems 88
Andrea Glorioso, Ugo Pagallo, and Giancarlo Ruffo 88
1 Introduction 88
2 Legal Issues 89
3 Sociological Aspects 93
4 Economic Trends 95
5 Political Aspects 99
6 Turning Forthcoming P2P Systems into Reality 102
6.1 Overlay Level 103
6.2 Accounting Level 104
6.3 Market Level 105
7 Conclusions 107
References 108
From Client-Server to P2P Networking 112
Lu Liu and Nick Antonopoulos 112
1 Introduction 112
2 Network Architecture Evolution 113
2.1 Client-Server Architecture 113
2.2 Grid Architecture 113
2.3 Peer-to-Peer Architecture 114
3 Evolution of Peer-to-Peer Networks 115
3.1 Centralised Peer-to-Peer Networks 116
3.2 Decentralised Peer-to-Peer Networks 117
3.3 Hybrid Peer-to-Peer Networks 118
4 Peer-to-Peer Search Systems 120
4.1 Structured P2P Systems 120
4.2 Unstructured P2P Systems 123
4.2.1 Blind Search 123
4.2.2 Informed Search 124
5 Future Trends 127
5.1 Self-organising Systems 127
5.2 Hybrid Systems 128
6 Conclusions 128
References 128
Examining the Use of Peer-to-Peer Networks from an Activity Perspective 131
Jorn De Boever and Dirk De Grooff 131
1 Introduction 131
2 Theoretical Framework: Activity Theory 132
2.1 Activity Theory and Human-Computer Interaction 132
2.2 Importance of Context 133
2.3 Activity System 134
3 Methods 136
4 Understanding the Use of P2P Networks 138
4.1 Process of Using Bittorrent Clients 138
4.1.1 Different Levels of Motivations 138
4.1.2 Bittorrent Peers' Behavior 141
4.2 Process of Using Gnutella Clients 145
4.2.1 Different Levels of Motivations 145
4.2.2 Gnutella Peers' Behavior 147
5 Discussion and Conclusion 151
References 153
Part II Unstructured P2P Overlay Architectures 155
Unstructured Peer-to-Peer Network Architectures 156
Xing Jin and S.-H. Gary Chan 156
1 Introduction 156
2 Design Considerations 158
3 Unstructured P2P Networks for File Sharing 158
3.1 A Centralized Approach: Napster 158
3.2 A Distributed Approach: Gnutella 159
3.3 A Hybrid Approach: FastTrack/Kazaa 161
3.4 Other Approach: BitTorrent 162
3.5 Comparison and Discussion 163
4 Advanced Issues in File Sharing 164
4.1 Content Replication 164
4.2 Security and Reputation System 166
4.2.1 Reputation Computing 167
4.3 Reputation Storage and Retrieval 168
5 Other Applications of Unstructured P2P Networks 171
5.1 Media Streaming: CoolStreaming 171
5.2 VoIP: Skype 174
6 Mobile Unstructured P2P Networks 176
6.1 Characteristics of Mobile Wireless Networks 176
6.2 Approaches for Mobile Unstructured P2P Networks 177
7 Conclusion 179
References 179
Exchanging Peers to Establish P2P Networks 182
Mursalin Akon, Mohammad Towhidul Islam, Xuemin (Sherman) Shen, and Ajit Singh 182
1 Introduction 182
2 The PROOFS Network 183
2.1 Evolution 183
2.2 Components 184
2.3 Protocols 184
2.3.1 ConstructOverlay 184
2.3.2 LocateObject 185
2.4 Properties of the PROOFS Networks 186
2.5 Results 186
2.5.1 Connectivity 187
2.5.2 Noncooperative Peers 187
3 The CYCLON Network 187
3.1 An Enhanced Exchange Operation 187
3.2 Results 188
3.2.1 Average Path Length 188
3.2.2 Average Clustering Coefficient 189
3.2.3 Degree Distribution 189
4 The IPPS Network 190
4.1 The Problem and the Goal 191
4.2 System Model 192
4.3 Topology Maintenance 193
4.3.1 The Exchange Operation 193
4.3.2 The Merge Operation 195
4.3.3 Number of P2P Neighbors 195
4.4 Results 197
4.4.1 Computational and Memory Complexity 197
4.4.2 Number of Link Level Hops per P2P hop 197
4.4.3 Dual Cognizance 198
4.4.4 Minimum Connectivity 199
5 The Gradient Topology Network 200
5.1 The Preliminaries 200
5.2 Exchange Operation 201
5.3 Search 202
5.4 Results 202
6 Concluding Remarks 202
References 203
Peer-to-Peer Topology Formation Using Random Walk 205
Kin-Wah Kwong and Danny H.K. Tsang 205
1 Introduction 205
2 Literature Review 207
3 Our Proposed Protocol 208
3.1 P2P Network Model 208
3.2 Joining Process 209
3.3 Rebuilding Process 211
4 Protocol Analysis 211
4.1 Stabilizing Network Model 212
4.2 Analysis of Mean Degree of P2P Network 213
4.3 Analysis of Node Degree Evolution 215
4.4 Simple Analysis of Peer's Workload 217
4.5 Analysis of P2P Network Diameter 218
5 Simulation 219
5.1 Node Capacity Distributions 220
5.2 P2P Network Diameter 220
5.3 Node Degree Equilibrium 221
6 Conclusion 222
References 224
Semantic Social Overlay Networks 226
Alexander Löser, Steffen Staab, and Christoph Tempich 226
1 Semantics and Communities in Peer-to-Peer Networks 227
1.1 Query Routing Strategies in Social Networks 227
1.2 Knowledge Sharing Strategies in Virtual Organizations 228
2 System Architecture 229
2.1 Building Blocks 229
2.2 Query and Result Messages 230
2.3 Similarity Function 231
3 Overlay Construction, Index Creation and Maintenance 232
3.1 Content Provider and Recommender Shortcuts 232
3.2 Bootstrapping Shortcuts 234
3.3 Default Network Shortcuts 235
4 Routing in Semantic Social Overlay Networks 235
4.1 Overview 236
4.2 Selecting Best Matching Shortcuts 236
5 Experimental Setup 237
5.1 Content Distribution 239
5.2 Query Distribution 241
5.3 Peer-to-Peer Network Setup 241
5.4 Simulator Setup and Simulation Statistics 243
5.5 Evaluation Measures 243
6 Evaluation and Optimization 244
6.1 Performance Against State-of-the-Art Approaches 245
6.2 Layer and Semantic Similarity Function Contribution 246
6.3 Tradeoff Between Clustering and Recall 247
6.4 Setting Optimal Index Size 249
6.5 Setting Optimal Index Weight 250
6.6 Performance for Conjunctive Queries 251
7 Related Work 252
8 Summary 254
References 255
Part III Structured P2P Overlay Architectures 257
Overview of Structured Peer-to-Peer Overlay Algorithms 258
Krishna Dhara, Yang Guo, Mario Kolberg, and Xiaotao Wu 258
1 Overview 258
2 Basic Features of Structured P2P Overlays/Networks 259
2.1 Geometries 260
2.2 Routing Algorithm 261
2.3 Join/Leave Mechanisms 262
2.4 Routing Table Maintenance 264
2.5 Bootstrapping 265
3 Logarithmic Degree Overlays 265
3.1 Chord 265
3.2 Pastry 267
3.3 Kademlia 269
3.4 Tapestry 270
3.5 P-Grid 271
4 Constant Degree Overlays 273
4.1 CAN 273
4.2 Ulysses 275
4.3 Cycloid 276
5 O(1)-Hop Overlays 278
5.1 Kelips 278
5.2 OneHop 279
5.3 EpiChord 281
5.4 D1HT 283
6 Comparison and Analysis 284
7 Conclusions 288
7.1 Open Research Issues 288
7.2 Summary 289
References 289
Distributed Hash Tables: Design and Applications 292
C.-F. Michael Chan and S.-H. Gary Chan 292
1 Introduction 292
2 Performance Characteristics and Design Considerations 293
2.1 Common Performance Characteristics 294
2.2 Design Considerations 294
3 DHT Schemes 295
3.1 Chord 295
3.2 Pastry 297
3.3 Kademlia 299
3.4 Other DHTs 300
4 Design Fundamentals 301
4.1 Static Resilience 301
4.2 Path Latency 301
4.3 Local Convergence 302
4.4 Network Diameter and Node State Tradeoffs 302
5 Applications 303
5.1 Cooperative File Storage (CFS) 303
5.2 Scribe 305
5.3 VMesh 306
5.4 Internet Indirection Infrastructure (i3) 307
6 DHTs in Wireless Networks 309
6.1 Characteristics of Wireless Networks 309
6.2 Challenges of Using DHTs in Wireless Networks 310
6.3 Search Approaches for Wireless Networks 312
7 Conclusions 313
References 314
The Gamut of Bootstrapping Mechanisms for Structured Overlay Networks 316
Anwitaman Datta 316
1 Introduction 316
2 A Taxonomy of Structured Overlay Topologies 318
2.1 Ring 318
2.1.1 Ring Self-Stabilization Highlights 320
2.2 Tree 321
2.2.1 The P-Grid Overlay 321
3 Quasi-Sequential Construction of Overlays 323
3.1 Load-Balancing Considerations 324
4 Parallelized Construction of Overlays 325
4.1 Sorting Peer-IDs as a Mechanism to Build a Ring 327
4.1.1 Pairing and Merging Virtual Trees 327
4.1.2 Gossip Based Mechanism 328
4.2 Recursive Proportional Partitioning 330
5 The Need and Challenges of Merging Two Similar StructuredOverlays 333
5.1 Merger of Two Ring Based Networks 336
5.1.1 Ring Loses Bearing During the Merge Process 337
5.1.2 Managing Keys on the Merged Ring 338
5.2 Merger of Two Structurally Replicated P-Grid Networks 339
5.2.1 Managing Keys in the Merged Network 341
6 Summary and Conclusion 341
References 342
Network-Aware DHT-Based P2P Systems 344
Marguerite Fayçal and Ahmed Serhrouchni 344
1 Motivations 344
2 DHT-Based Architectures 345
3 Requirements 347
4 State of the Art 348
5 Semantics for Resource Sharing 352
5.1 A Context-Aware P2P System 352
5.2 A Network Provider Oriented P2P System 354
6 Prospects 357
7 Conclusion 358
References 359
On Adding Structure to Unstructured Overlay Networks 362
João Leitão, Nuno A. Carvalho, José Pereira, Rui Oliveira,and Luís Rodrigues 362
1 Introduction 363
2 Adding Structure to Unstructured Overlay Networks 364
2.1 Existing Protocols 365
2.1.1 Narada 365
2.1.2 Localiser 366
2.1.3 Araneola 367
2.1.4 GoCast 368
2.1.5 T-Man 369
2.1.6 Plumtree 370
2.2 Key Properties to Preserve 371
2.3 Performance Metrics 372
2.4 Methodologies 373
3 Overlay Optimization 374
3.1 Overview 374
3.2 Architecture 375
3.2.1 Oracles 375
3.2.2 Rationale 376
3.2.3 Unbiased Neighbors 376
3.3 Algorithm 377
3.4 Performance 379
3.4.1 Experimental Setting 379
3.4.2 Stable Environment 380
3.4.3 Massive Failures 382
4 Gossip Optimization 383
4.1 Overview 383
4.1.1 Background 384
4.1.2 Approach 384
4.2 Architecture 385
4.2.1 Gossip Protocol Layer 387
4.2.2 Payload Scheduler Layer 388
4.3 Strategies and Oracles 390
4.3.1 Strategies 390
4.3.2 Oracles 392
4.4 Performance 392
4.4.1 Network Emulation 392
4.4.2 Implementation and Configuration 393
4.4.3 Traffic and Measurements 393
4.4.4 Statistics 394
4.4.5 Experimental Results 394
5 Discussion and Future Directions 396
References 398
Mathematical Modeling of Routing in DHTs 401
Peter Kersch and Robert Szabo 401
1 Introduction 401
1.1 DHTs Revisited 402
2 Modeling DHT Routing 405
2.1 Renewal Processes Revisited 407
2.2 Assumptions and Notations 408
2.2.1 Degree of Randomness 410
2.2.2 Bidirectional Overlay Model 411
2.2.3 Node ID Distribution 412
3 Transformed View of Long-Range Connections 412
3.1 Long-Range Connection Density 413
3.2 Regular Power-Law Routing Overlays 415
3.3 Probabilistic Power-Law Routing Overlays 417
3.4 Distortions in the Transformed View 419
4 Stochastic Analysis of Routing 419
4.1 Analysis of Routing in the Transformed view 421
4.1.1 Regular Power-Law Routing Overlays 423
4.1.2 Probabilistic Power-Law Routing Overlays 423
4.1.3 Deterministic Power-Law Routing Overlays 426
4.1.4 Comparison of Per-Hop Routing Progress in the Transformed View 426
4.2 Upper Bound on the Expected Number of Routing Hops 429
5 Summary 433
References 434
Part IV Search and Query Processing 436
Keyword Search in Unstructured Peer-to-Peer Networks 437
Dingyi Han and Yong Yu 437
1 Introduction 438
1.1 Background 438
1.2 Keyword Search Problem 439
1.3 Evaluation Metrics 440
2 Blind Routing 441
2.1 Pure Flooding and Its Variations 441
2.1.1 Pure Flooding 441
2.1.2 Expanding Ring 443
2.1.3 Light Flood 444
2.2 Random Walk and Its Variations 445
2.2.1 Uniformly Random Walk 445
2.2.2 Max-Degree Biased Walk 446
2.3 Comparison and Summary 447
3 Routing Indices 447
3.1 Content Oriented Routing 448
3.1.1 Naive Routing Indices for Non-cyclic Topologies 448
3.1.2 Naive Routing Indices for Cyclic Topologies 450
3.1.3 Hop-Based Routing Indices 451
3.1.4 Scalable Query Routing 452
3.2 Query Oriented Routing 452
3.2.1 Max-Feedback Biased Walk 452
3.2.2 Adaptive Probabilistic Search 453
3.2.3 Learning Based Query Routing 454
3.3 Comparison and Summary 455
4 Multi-Keyword Search 456
5 Conclusion 457
References 457
Distributed Search and Pattern Matching 459
Reaz Ahmed and Raouf Boutaba 459
1 Introduction 459
2 Large Scale Distributed Systems 460
2.1 Content Sharing 461
2.2 Service Discovery 463
2.3 Distributed XML Databases 465
3 Distributed Search Requirements 467
4 Components of a Distributed Search System 469
4.1 Query Semantics 469
4.1.1 Schema 470
4.1.2 Expressiveness 471
4.2 Translation 471
4.3 Routing 472
5 Search Techniques in Content Sharing P2P Systems 473
5.1 Structured Techniques 473
5.2 Un-structured and Semi-structured Techniques 476
5.3 Summary 477
6 Search Techniques in P2P Service Discovery 477
6.1 Summary 478
7 Search Techniques in Distributed XML Databases 480
7.1 Summary 481
8 The DPM Abstraction 482
8.1 Distributed Pattern Matching (DPM) 482
8.2 Mapping to DPM Framework 483
8.2.1 P2P Content Sharing 484
8.2.2 Service Discovery 484
8.2.3 Distributed XML Databases 485
8.3 Known Solutions to the DPM Problem 485
8.3.1 DPMS: Distributed Pattern Matching System 486
8.3.2 Plexus 488
8.3.3 Summary 489
9 Conclusion 489
References 490
Distributed Semantic Overlay Networks 494
Christos Doulkeridis, Akrivi Vlachou, Kjetil Nørvåg,and Michalis Vazirgiannis 494
1 Introduction 495
2 Semantic Overlay Networks 496
2.1 Aims of SON Generation 497
2.1.1 Intra-SON Similarity 497
2.1.2 Inter-SON Similarity 497
2.2 Requirements for SON Generation 498
2.2.1 Unsupervised Algorithms 498
2.2.2 Scalability 498
2.2.3 Self-organization 499
2.2.4 Autonomy 499
2.2.5 Decentralization 500
3 Distributed Creation of Semantic Overlay Networks 500
3.1 The DESENT Approach to Decentralized and Distributed SON Creation 500
4 Searching in Semantic Overlay Networks 505
4.1 Traditional SON-Based Search 505
4.2 Super-Peer Organization 506
5 Applications of Semantic Overlay Networks 507
5.1 P2P Web Search -- Document Retrieval 507
5.1.1 SON Creation 508
5.1.2 Keyword-Based Search 509
5.2 P2P Image Retrieval 510
5.2.1 Architecture 511
5.2.2 Peer Organization 512
5.2.3 Similarity Search 512
6 Related Work 514
6.1 Unstructured P2P 515
6.1.1 Clustering 515
6.1.2 Classification 516
6.1.3 Gossip-Based 517
6.2 Structured P2P 518
6.2.1 Clustering 518
6.2.2 Classification 519
6.2.3 Gossip-Based 520
6.3 Evaluation 520
7 Summary and Future Trends 521
References 522
Self-adaptation and Self-organization for Search in Social-Like Peer-to-Peer Networks 526
Lu Liu, Jie Xu, Duncan Russell, and Zongyang Luo 526
1 Introduction 526
2 Background 528
3 AESLP: Adaptive and Efficient Social-Like Peer-to-Peer 529
3.1 Knowledge Index Creation and Update 529
3.2 Routing Algorithm for Simple Queries 532
3.2.1 Query Processing 532
3.2.2 Adaptive Forwarding 533
3.2.3 Node Selection 534
3.2.4 Query Routing Example 538
3.3 Routing Algorithm for Multi-Topic Queries 539
3.3.1 Routing Algorithm for Conjunctive Queries 539
3.3.2 Routing Algorithm for Query Packs 544
3.4 Adaptive Query 544
4 Simulations Methodology 546
4.1 Content Generation and Distribution 547
4.2 Topology Initialisation and Evolution 547
4.3 Network Churns 548
4.4 Search Network 548
5 Simulation Results 549
5.1 Initial Simulations 549
5.2 Performance Comparison to Relevant Methods 551
5.3 Performance Comparison to Derived Methods 552
5.4 Topology Evolution 553
5.5 Effects of Parameters 553
5.5.1 Size of Lists 554
5.5.2 Request Structure 555
5.5.3 Number of Receivers 556
5.6 Query Packs 558
6 Conclusions and Future Work 559
References 560
Data Sharing in P2P Systems 562
Rabab Hayek, Guillaume Raschia, Patrick Valduriez,and Noureddine Mouaddib 562
1 Introduction 563
2 P2P Networks 565
2.1 Unstructured 565
2.1.1 Hybrid Decentralized 566
2.1.2 Pure Decentralized 566
2.1.3 Partially Decentralized 567
2.2 Structured 567
2.3 Unstructured vs. Structured: Competition orComplementarity? 568
3 Data Indexing in P2P Systems 569
3.1 Index Types 570
3.1.1 Local Index 570
3.1.2 Centralized Index 573
3.1.3 Distributed Index 573
3.2 Semantic-Free Index: DHT 574
3.2.1 Tree 574
3.2.2 Ring 575
3.2.3 Hypercube 576
3.3 Semantic Index 577
3.3.1 Keyword Lookup 577
3.3.2 Peer Information Retrieval 579
3.3.3 Peer Data Management 581
4 Schema Management in P2P Systems 582
4.1 Pairwise Schema Mappings 583
4.2 Mapping Based on Machine Learning Techniques 584
4.3 Common Agreement Mapping 585
4.4 Schema Mapping Using IR Techniques 586
5 Querying in P2P Systems 586
5.1 Partial Lookup 587
5.1.1 Range Queries 587
5.1.2 Join Queries 588
5.1.3 Multi-Attributes Queries 589
5.1.4 Fuzzy Queries 589
5.2 Partial Answering 592
5.2.1 Top-k Queries 592
5.2.2 Skyline Queries 593
5.3 What About Approximate Answering? 594
References 597
Managing Linguistic Data Summaries in Advanced P2P Applications 602
Rabab Hayek, Guillaume Raschia, Patrick Valduriez,and Noureddine Mouaddib 602
1 Introduction 603
2 Summarization Process 604
2.1 Data Summarization 604
2.2 Input Data 606
2.2.1 Data Model 606
2.2.2 Background Knowledge 606
2.3 Process Architecture 607
2.3.1 Mapping Service 607
2.3.2 Summarization Service 608
2.3.3 Scalability Issues 609
2.4 Distributed Summary Representation 610
3 Summary Model for Hierarchical P2P Networks 611
3.1 Problem Statement 611
3.2 Model Architecture 613
3.3 Summary Management 613
3.3.1 Summary Construction 614
3.3.2 Summary Maintenance 614
3.3.3 Peer Dynamicity 617
4 Query Processing 617
4.1 Query Reformulation 618
4.2 Query Evaluation 619
4.2.1 Approximate Answering 620
4.2.2 Peer Localization 620
5 Performance Evaluation 621
5.1 Cost Model 622
5.1.1 Summary Update Cost 622
5.1.2 Query Cost 624
5.2 Simulation 625
5.2.1 Simulation Setup 625
5.2.2 Update Cost 626
5.2.3 Query Cost 628
6 Related Work 629
7 Conclusion 629
References 630
Case Study: Scoop for Partial Read from P2P Database 632
Farnoush Banaei-Kashani and Cyrus Shahabi 632
1 Introduction 633
1.1 Motivation and Problem Definition 633
1.2 Related Work 635
1.3 Scoop 636
1.3.1 Overview 636
1.3.2 Correctness and Efficiency 636
1.3.3 Originality 637
1.3.4 Experimental Results 638
1.3.5 Summary of Contributions 638
1.4 Roadmap 639
2 Partial Read Operation 639
2.1 Definitions 640
2.1.1 Communication Graph 640
2.1.2 Efficiency Measures for Sampling 641
3 Scoop: Partial Read by Epidemic Dissemination 642
3.1 SIR Epidemic Dissemination 642
3.2 Percolation Model 643
3.3 Tuning Scoop 646
3.3.1 Definitions 646
3.3.2 Analysis 646
4 A Real-World Example of Scoop 648
4.1 Network Topology 648
4.2 Analysis 649
4.3 Algorithm 649
5 Variants of Scoop 650
6 Experiments 651
6.1 Methodology 651
6.2 Results 652
7 Conclusion and Future Work 655
References 657
Part V Incentive Mechanisms 659
Incentive Mechanisms for Cooperation in Peer-to-Peer Networks 660
Daniel A. G. Manzato and Nelson L. S. da Fonseca 660
1 Introduction 661
2 Characteristics and a Classification of Uncooperative Behaviors 662
3 Comprehensive Study of Incentive Patterns 665
3.1 Trust Based Incentive Patterns 666
3.1.1 The Collective Pattern 666
3.1.2 The Community Pattern 667
3.2 Trade Based Incentive Patterns 670
3.2.1 The Barter Trade Pattern 670
3.2.2 The Bearer Notes Pattern and the Bearer Bills Pattern 672
3.2.3 The Banking Pattern 674
3.2.4 The Banknotes Pattern 676
4 Selection of Incentive Schemes 678
4.1 Incentive Mechanism for the CoopNet Network 678
4.2 Altruism in Peer-to-Peer Media Streaming 681
4.3 Multicast with Incentive in Peer-to-Peer Media Streaming 682
4.4 Client Selection with Differentiated Service 683
4.5 Incentives in BitTorrent 685
4.6 Trading in Trust, Tokens and Stamps 685
4.7 Mobility in Ad hoc Wireless Networks with Incentives 686
5 Final Remarks 687
References 688
Bandwidth Trading as Incentive 690
Kolja Eger and Ulrich Killat 690
1 Introduction 690
2 Trading Schemes for P2P Content Distribution 692
2.1 P2P Network Model 692
2.2 Resource Pricing 694
2.3 Reciprocal Rate Control 696
2.4 BitTorrent 697
3 Nash Equilibrium 697
4 Performance Evaluation 698
4.1 Static networks 699
4.2 Dynamic Networks 701
5 Bandwidth Trading and Piece Selection 703
5.1 Piece-Dependent Resource Pricing 710
6 TCPeer: A TCP Variant for P2P CDNs 711
7 Conclusion 712
References 713
Part VI Trust, Anonymity, and Privacy 715
Reputation-Based Trust Management in Peer-to-Peer Systems: Taxonomy and Anatomy 716
Loubna Mekouar, Youssef Iraqi, and Raouf Boutaba 716
1 Introduction and Motivation 716
2 Traditional Systems Versus Reputation-Based Systems 718
3 Trust and Reputation 719
3.1 Trust Definition 719
3.2 Reputation Definition 720
3.3 Trust Properties 720
3.4 System Model 721
3.4.1 Modeling the Network 721
3.4.2 Modeling the Nodes 722
3.4.3 Modeling the Reputation Management Infrastructure 724
4 The Anatomy of Reputation Systems 726
4.1 The Local Trust 727
4.1.1 What Kind of Trust Information is Gathered? 728
4.1.2 Where to Store Trust Information? 729
4.1.3 Is the Local Trust Information Sufficient? 730
4.2 The Reputation Query 731
4.2.1 To Whom the Requester Peer Should Send a Reputation Query? 731
4.2.2 How Many Peers Should the Requester Peer Contact? 732
4.2.3 What Kind of Information is Sent to the Requester Peer? 733
4.3 Reputation Computation 734
4.3.1 How to Deal with Liar Recommender Peers? 736
4.3.2 How to Deal with Fraudulent Recommender Peers? 737
4.3.3 How to Compute the Reputation? 737
4.4 The Use of Reputation 739
4.4.1 How to Choose a Peer Based on the Reputation Value? 739
4.4.2 How to Evaluate a Transaction After Downloading a Requested File? 740
4.5 Credibility Assessment 741
4.6 Incentives, Rewards and Punishment 741
5 Design Requirements 743
6 Centralized Reputation Systems 743
6.1 e-Commerce Applications 743
6.2 P2P Systems 746
6.2.1 Reputation Management Using DCRC and CORC 746
6.2.2 A Fine-Grained Reputation System for Reliable Service Selection: FineGrainedTrust 747
7 Decentralized Reputation Systems 748
7.1 The Distributed Trust Model: DistributedTrust 748
7.2 The Binary Distributed Trust Model: BinaryTrust 749
7.3 Reputation Management by Choosing Reputable Servents: P2PBasic and P2PEnhanced 750
7.4 Reputation Management by the XRep Protocol: XRep 750
7.5 Reputation Management Using EigenTrust 751
7.6 Limited Reputation Sharing in P2P Systems: LimitedReputation 752
7.7 Reputation Management Using Trust and Credibility Records: CredibilityRecords 753
7.8 Reputation Management Using CCCI Methodology: MDNT 753
7.9 Cooperative Peer Groups in Nice 753
8 Partially Decentralized Reputation Systems 754
8.1 BitTorrent 755
8.2 The Inauthentic Detector Algorithm (IDA) and the Malicious Detector Algorithm (MDA) 755
9 Conclusion 756
References 757
P2P Reputation Management Through Social Networking 760
Zoran Despotovic 760
1 Introduction 760
2 P2P Reputation Systems 762
2.1 P2P Systems Perspective 765
2.2 Classification of Existing Solutions 766
3 Probabilistic Signaling Reputation Mechanisms 768
3.1 Discussion 771
3.1.1 Performance Analysis 771
3.1.2 Implementation Overhead 771
4 Ad hoc Signaling Reputation Mechanisms 772
4.1 A Synchronous Algorithm 773
4.2 Discussion 775
4.2.1 Performance Analysis 776
4.2.2 Implementation Overhead 777
4.3 Bio-inspired P2P Reputation Systems 777
5 Sanctioning Reputation Mechanisms 778
5.1 Modeling Reputation 779
5.1.1 Perfect vs. Imperfect Monitoring 781
5.1.2 Truthful Feedback Submission 781
5.1.3 Evolutionary Settings 782
5.1.4 Critiques of Game-Theoretic Modeling 783
6 Identities: An Important Practical Problem 783
7 Discussion and Conclusions 784
References 785
State of the Art in Trust and Reputation Models in P2P networks 788
Félix Gómez Mármol and Gregorio Martínez Pérez 788
1 Introduction 788
2 Trust and Reputation Models 789
3 Discussion 802
3.1 Trust and Reputation Management -- What for? 802
3.2 Trust and Reputation Models Steps 803
3.3 Common Challenges and Solutions in Trust and Reputation Management Over P2P Networks 804
3.3.1 Modeling Trust and Reputation 805
3.3.2 Contextualized Trust and Reputation 805
3.3.3 P2P Networks Dynamism 806
3.3.4 Collusion 806
3.3.5 Identity Management -- Sybil Attack 807
3.4 Strengths and Weaknesses of the Described Models 808
3.5 Real Scenarios 809
4 Conclusions and Future Work 810
References 810
Anonymity in P2P Systems 812
Pilar Manzanares-Lopez, Juan Pedro Muñoz-Gea,Josemaria Malgosa-Sanahuja, and Juan Carlos Sanchez-Aarnoutse 812
1 Introduction 813
2 Source-Rewriting Systems 814
2.1 Mixes 814
2.1.1 Mixmaster 815
2.1.2 GNUnet 815
2.2 Onion Routing 816
2.2.1 Tor 817
2.2.2 Tarzan 818
2.2.3 I2P 819
2.3 Crowds 819
2.3.1 AP3 820
2.4 Freenet 821
3 Broadcast Systems 822
3.1 P5 822
3.2 Hordes 825
4 DC-Net Systems 826
4.1 Herbivore 826
5 Analysis of Anonymity 827
5.1 Mix 828
5.2 Onion Routing 829
5.3 Crowds 830
5.4 Crowds with Limited Path Lengths 831
6 Experimental Analysis of Anonymity 834
7 Summary 836
8 Future Research Directions 837
References 838
Private Peer-to-Peer Networks 840
Michael Rogers and Saleem Bhatti 840
1 Introduction 840
2 Background 841
2.1 Definitions 841
2.2 Technical Challenges 842
3 Survey of Deployed Systems 843
3.1 Group-Based Networks 843
3.2 Friend-to-Friend Networks 844
3.3 Other Networks 845
4 Architecture 846
5 Related Research 849
6 Conclusions 850
References 851
Part VII Broadcast and Multicast Services 856
Gossip-Based Broadcast 857
João Leitão, José Pereira, and Luís Rodrigues 857
1 Introduction 857
2 Gossip-Based Broadcast 859
2.1 Parameters 859
2.2 Strategies 860
2.3 Peer Sampling Service 861
2.4 Partial View 862
2.5 Strategies to Maintain Partial Views 863
2.6 Partial View Properties 863
2.7 Performance Metrics 865
2.8 An Overview of Existing Protocols 866
2.8.1 Gossip-Based Membership Protocols 866
2.8.2 Gossip-Based Broadcast Protocols 868
2.8.3 Structured Application-Level Multicast 869
3 The HyParView Protocol 871
4 Achieving Resilient Broadcast 873
5 Building Low Cost Spanning Trees 874
6 Experimental Evaluation 876
6.1 Experimental Setting 877
6.2 HyParView and Eager Push Strategy 878
6.3 Plumtree 881
7 Discussion and Future Directions 884
References 885
Employing Multicast in P2P Overlay Networks 887
Mario Kolberg 887
1 Introduction 887
1.1 IP Layer Multicast 887
1.2 Application Layer Multicast (ALM) 888
2 Using IP Multicasting for Parallel P2P Overlay operations 888
2.1 Host Group Multicasting 890
2.2 Multi-Destination Multicasting 890
2.3 Chuang-Sirbu Scaling Law 892
2.4 Strengths and Weaknesses 893
3 Application Layer Multicast 894
3.1 Mesh First Approaches (NARADA) 895
3.2 Tree First Approaches 895
3.3 Implicit Approaches 896
3.4 Strengths and Weaknesses 897
4 Conclusions 898
References 899
Multicast Services over Structured P2P Networks 901
Pilar Manzanares-Lopez, Josemaria Malgosa-Sanahuja,Juan Pedro Muñoz-Gea, and Juan Carlos Sanchez-Aarnoutse 901
1 From IP Multicast to ALM 902
2 Flooding-Based Structured ALM 903
2.1 CAN-Multicast 903
2.2 DKS/Chord Multicast 904
3 Tree-Based Structured ALM 907
3.1 Scribe 907
3.2 Bayeux 909
4 OverSim: A Useful P2P Simulation Tool 910
4.1 OMNeT++ 912
4.2 OverSim 912
4.3 Chord-Multicast Implementation 913
4.3.1 Simulator Structure 913
4.3.2 Functionality 914
4.4 Scribe Implementation 915
4.4.1 Simulator Structure 915
4.4.2 Functionality 915
5 Performance Evaluation 916
6 Summary 920
7 Future Research Directions 920
References 921
Multicast Routing in Structured Overlays and Hybrid Networks 923
Matthias Wählisch and Thomas C. Schmidt 923
1 Introduction 924
2 Overview of Structured Approaches to Group Communication 924
2.1 Flooding of (Sub-)Overlays 925
2.1.1 Multicast on CAN 925
2.1.2 Prefix Flooding 926
2.1.3 Distributed Tree Construction 927
2.2 Source-Specific Distribution Trees 927
2.3 Shared Distribution Trees 928
2.4 Bi-directional Shared Distribution Trees 929
3 Properties of Distribution Trees 930
3.1 CAN Flooding: k-ary Trees with Node Chains 930
3.2 Prefix-directed Forwarding: k-ary Trees with Node Redundancy 934
3.3 Reverse Path Forwarding: Topology-Induced Trees 936
4 Hybrid Multicast 938
4.1 Inter-Domain Multicast Tunneling and Overlays 939
4.2 Hybrid Shared Tree Architecture 940
4.2.1 The Inter-Domain Multicast Gateway 940
4.2.2 Connecting Small Size Domains 942
4.2.3 Connecting Large Size Domains 943
5 A Common API for Group Communication 945
5.1 General Design Principles for Structured Overlay Networks -- The Dabek Model 945
5.1.1 The Common Key-Based Routing API 946
5.1.2 Limitations of the KBR API 947
5.2 Towards a Structured P2P Group Communication API 948
5.2.1 Current State of the Art 949
5.2.2 Current Challenges 950
5.3 Architectural Components 951
5.3.1 Architectural Overview 952
5.3.2 An API Proposal 953
6 Discussions and Conclusions 954
6.1 Future Research Directions 956
References 956
Multicast and Bulk Lookup in Structured Overlay Networks 959
Ali Ghodsi 959
1 Introduction 959
1.1 Motivation 960
2 Preliminaries 960
2.1 Desirable Properties 963
3 Broadcast 964
3.1 Simple Broadcast 965
3.2 Simple Broadcast with Feedback 967
4 Bulk Operations 968
4.1 Bulk Operations 970
4.2 Bulk Operations with Feedbacks 972
4.3 Bulk Owner Operations 972
5 Fault-Tolerance 974
5.1 Pseudo Reliable Broadcast 976
6 Application: Efficient Overlay Multicast 978
6.1 Basic Design 978
6.2 Group Management 978
6.3 IP Multicast Integration 980
7 Related Work 981
References 982
Part VIII Multimedia Content Delivery 985
Peer-to-Peer Content Distribution and Over-The-Top TV: An Analysis of Value Networks 986
Jorn De Boever and Dirk De Grooff 986
1 Over-The-Top TV and P2P Systems 987
1.1 Evolutions of TV 987
1.2 Over-The-Top TV 988
2 Theoretical Framework 990
2.1 P2P Systems and Business Modeling 990
2.2 Business Modeling Theory 991
2.3 Value Networks 992
3 Case Studies 994
3.1 Case 1: Kontiki 994
3.2 Case 2: Zattoo 996
3.3 Case 3: Bittorrent Clients 999
4 The Role of ISPs 1001
5 Discussion and Conclusion 1003
References 1006
Live Video and IP-TV 1009
Maria Luisa Merani and Daniela Saladino 1009
1 Live Streaming and IP-TV 1009
2 A Taxonomy of P2P Video Broadcasting Systems 1011
3 Popular P2P Streaming Systems 1014
4 The Diffusion Process and a Reference System 1015
4.1 Mesh-Based Systems 1015
4.2 Scheduling 1017
4.3 Software Architecture and Overlay Membership 1017
4.4 New CoolStreaming 1019
5 Measurements and Quality Monitoring 1021
5.1 Network Edge Measurements 1022
5.2 System Measurements 1026
6 Modeling Insights 1033
6.1 First Modeling Efforts 1033
6.2 More Recent Contributions 1035
6.3 A Numerical Comparison Between Mesh and Multiple-Trees 1039
7 Open Issues and Promising Solutions 1042
7.1 QoS and QoE 1042
7.2 Network Awareness 1043
7.3 Network Coding for P2P Streaming 1044
8 Summary 1047
References 1047
Providing VoD Streaming Using P2P Networks 1049
Juan Pedro Muñoz-Gea, Josemaria Malgosa-Sanahuja,Pilar Manzanares-Lopez, and Juan Carlos Sanchez-Aarnoutse 1049
1 Introduction 1050
2 P2P VoD Services Overview 1052
3 Overlay Network Structure for P2P VoD 1052
3.1 Tree-Based Network Structure 1053
3.2 Mesh-Based Network Structure 1054
3.3 Hybrid Network Structure 1054
4 Forwarding Approaches 1055
4.1 Buffer-Forwarding 1055
4.2 Storage-Forwarding 1056
4.3 Hybrid-Forwarding 1056
4.4 Pre-Fetching 1057
5 Suppliers Search 1058
5.1 Searching in Buffer-Forwarding 1058
5.2 Searching in Storage-Forwarding 1060
6 Data Scheduling 1061
6.1 Scheduling in Buffer-Forwarding 1062
6.2 Scheduling in Storage-Forwarding 1062
7 Technical Challenges 1064
8 Summary 1064
9 Future Research Directions 1065
References 1065
Part IX Mobile P2P 1067
Peer-to-Peer Overlay in Mobile Ad-hoc Networks 1068
Marcel C. Castro, Andreas J. Kassler, Carla-Fabiana Chiasserini,Claudio Casetti, and Ibrahim Korpeoglu 1068
1 Introduction 1069
2 Overview on Peer-to-Peer and Ad-Hoc Networks 1071
2.1 Peer-to-Peer Overlay Networks 1071
2.2 Characteristics of Wireless Multi-hop and Mobility 1072
2.3 Traffic Routing in Multi-hop Networks 1074
2.3.1 Topology-Based Schemes 1074
2.3.2 Geographic-Based Routing 1075
2.3.3 Probabilistic Routing 1076
3 Challenges of Deploying P2P Services in Mobile Ad-hoc Networks 1076
4 Overview of P2P Solutions for Mobile Ad-hoc Networks 1081
4.1 Integration Principles Between P2P and MANETRouting Layer 1081
4.2 Unstructured P2P Networks for MANETs 1082
4.3 Structured P2P Networks for MANETs 1085
4.3.1 Transparent Layered DHT on Top of Broadcast Based Ad-hoc Routing Protocol 1085
4.3.2 Integrating DHT over the Network Layer 1087
4.4 Summary and Comparison of the Solutions 1092
5 P2P Application Scenarios for Mobile Ad-hoc Networks 1096
5.1 Decentralized Name Service 1096
5.2 Overlay-Based Multicast 1097
5.3 Multimedia Services 1098
6 Summary 1099
References 1100
Opportunistic Information Retrieval in Sparsely Connected Ad Hoc Networks 1104
Mooi-Choo Chuah and Jian-bin Han 1104
1 Introduction 1104
2 Related Work 1106
3 System Model 1107
4 Data/Index/Query Dissemination Schemes 1108
4.1 Data Caching 1108
4.2 Index Advertising 1109
4.3 Query Dissemination 1110
4.4 DTN Message Routing Scheme 1110
4.5 Three Information Retrieval Schemes 1111
5 Performance Evaluation 1112
5.1 Simulation Setup 1112
5.1.1 Node Movement Model 1112
5.1.2 Data Item Generation Model 1113
5.1.3 Query Model 1113
5.2 Simulation Results 1114
5.2.1 Impact of Node Density 1114
5.2.2 Impact of Mobility Model 1118
5.2.3 Impact of the Index/Data Replication Factors 1119
5.2.4 Non-uniform Access Pattern 1122
6 Discussion 1125
7 Concluding Remarks 1126
References 1127
The MOBI-DIK Approach to Searching in Mobile Ad Hoc Network Databases 1128
Yan Luo, Ouri Wolfson, and Bo Xu 1128
1 Introduction: MANET Databases 1128
2 Historical Background 1129
3 Scientific Fundamentals 1130
4 The MOBI-DIK Approach 1133
5 Key Applications 1136
6 Future Research Directions 1137
References 1138
Part X Fault Tolerance in P2P Networks 1147
Managing Network Partitions in Structured P2P Networks 1148
Tallat M. Shafaat, Ali Ghodsi, and Seif Haridi 1148
1 Introduction 1149
2 Preliminaries 1150
3 Detecting Network Partitions and Mergers 1152
4 Merging the Overlays 1153
4.1 Simple Ring Unification 1153
4.2 Gossip-Based Ring Unification 1154
5 Performance Evaluation 1156
6 Related Work 1159
6.1 Merging P-Grid Overlays 1159
6.1.1 P-Grid 1160
6.1.2 Merger 1160
6.2 Merging Pastry Overlays 1163
6.3 Overlay Construction from Random Graph 1163
6.4 Data Consistency 1164
7 Summary 1165
7.1 Open Questions 1166
References 1166
Load Balancing in Structured P2P Networks 1169
Yingwu Zhu 1169
1 Introduction 1169
1.1 Motivation 1169
1.2 Load Definition 1170
1.3 Goals 1171
2 Load Information Aggregation and Dissemination 1171
2.1 Tree Structure-Based Approach 1171
2.2 Gossip-Based Approach 1172
2.3 Summary 1173
3 Load Balancing 1173
3.1 Virtual Server-Based Approach 1173
3.2 Power of Two Choices 1174
3.3 Address-Space and Item Balancing 1174
3.4 Discussion 1175
4 Case Study: Efficient, Proximity-Aware Load Balancing 1175
4.1 Overview 1175
4.2 LBI Aggregation and Dissemination 1176
4.3 Proximity-Aware VSA 1178
4.4 VST 1180
4.5 Discussion 1181
5 Future Research 1182
6 Summary 1183
References 1183
Acyclic Preference-Based Systems 1185
Fabien Mathieu 1185
1 Introduction 1185
1.1 Stable Marriage: A Brief Overview 1187
1.2 Going P2P 1187
1.3 Outline 1188
2 Acyclic Preference-Based Systems 1188
2.1 Notation and Definition 1188
2.1.1 Preference-Based Systems 1188
2.1.2 Configurations 1189
2.1.3 Initiatives 1190
2.1.4 Nodes and Edges' Stability 1191
2.2 Acyclicity: Main Convergence Theorem 1191
2.3 Acyclic Classes 1194
2.3.1 P2P-Relevant Cases 1194
2.3.2 Considered Preferences 1195
3 Self-Stabilization Speed 1196
3.1 Upper Bounds 1196
3.1.1 Convergence (Rounds) 1196
3.1.2 Convergence (Initiatives) 1196
3.1.3 b-Matching Generalization 1197
3.2 Expected Convergence Time 1198
3.2.1 Generic Upper Bound 1198
3.2.2 Node-Based Preferences 1199
3.2.3 Random Acyclic Preferences 1200
3.2.4 Other Acyclic Preferences 1200
3.3 Simulations 1200
3.3.1 Best-Mate Initiative 1201
3.3.2 Random and Hybrid Initiatives 1203
4 Stable Configuration Description 1205
4.1 Specific Notation 1206
4.2 Acyclic Formulas 1206
4.2.1 Generic Formula 1206
4.2.2 Mean-Field Approximation 1207
4.3 Node-Based Preferences 1207
4.3.1 Fluid Limit 1208
4.3.2 Constant Degree Scaling 1208
4.3.3 Convergence Theorem 1208
4.3.4 Validation 1209
4.4 Acyclic and Distance-Based Preferences 1211
4.4.1 Complete Rank Distribution 1211
4.4.2 Distance Distribution 1213
4.4.3 Acceptable Rank Distribution 1214
4.5 b-Matching Generalization 1216
4.5.1 Mean Field Formulas 1216
4.5.2 Fluid Limits 1217
4.6 Some Basic Applications 1218
4.6.1 Stratification Trade-off 1219
4.6.2 Small-World Effect and Preference Dimension 1219
5 Conclusion 1221
References 1221
Part XI Measurement and P2P Traffic Characteristics 1224
The Behavior of Free Riders in BitTorrent Networks 1225
Manaf Zghaibeh, Kostas G. Anagnostakis, and Fotios C. Harmantzis 1225
1 Introduction 1226
2 BitTorrent Background 1227
3 Previous Work 1228
4 Methodology 1230
4.1 First Measurement Study 1230
4.2 Second Measurement Study 1231
5 Results and Discussion 1233
5.1 First Measurement Study 1233
5.2 Second Measurement Study 1236
5.2.1 Free Riders: Who Are They? 1236
5.2.2 Who Exploits BitTorrent? 1239
5.2.3 Is the Tit-for-Tat Robust? 1240
5.2.4 The Population of Peers and the Optimistic Unchoke 1243
5.2.5 Modified Approach to BitTorrent 1244
6 Conclusions 1245
7 Future Work 1247
References 1247
The Nature of Peer-to-Peer Traffic 1249
João V. P. Gomes, Pedro R. M. Inácio, Mário M. Freire, Manuela Pereira, and Paulo P. Monteiro 1249
1 Introduction 1250
2 The Importance of Traffic Characterisation 1252
2.1 The Effect of Peer-to-Peer Traffic in Computer Networks 1252
2.1.1 Consumption of Resources 1253
2.1.2 Traffic Asymmetry 1254
2.1.3 Peer-to-Peer Inside Organisations 1254
2.1.4 Network Security 1255
2.2 Making Peer-to-Peer a Practicable Solution: Traffic Classification 1256
2.2.1 Deep Packet Inspection Methods 1256
2.2.2 Classification in the Dark 1258
3 Peer-to-Peer Traffic Characterisation 1258
3.1 Generic Properties of Traffic from Peer-to-Peer Protocols 1259
3.2 Analysing Peer-to-Peer Traffic Behaviour 1260
3.3 Entropy as a Measure of Heterogeneity 1262
3.4 Capturing the Nature of Peer-to-Peer Traffic 1262
4 Inside a Network: Using Behavioural Characteristics to Identify Peer-to-Peer Traffic 1265
5 Summary 1267
References 1268
Characterization of P2P Systems 1271
Daniel Stutzbach and Reza Rejaie 1271
1 Introduction 1271
2 Measurement Techniques 1272
2.1 Passive Monitoring 1273
2.2 Participate 1274
2.3 Crawl 1274
2.4 Sample 1274
2.5 Centralize 1275
2.6 Summary 1275
3 What to Measure 1276
3.1 Static Peer Properties 1276
3.2 Dynamic Peer Properties 1277
3.2.1 Files Transfers 1278
3.3 Static Connectivity Properties 1279
3.4 Dynamic Connectivity Properties 1280
3.5 Summary 1280
4 Cruiser: A Fast P2P Crawler 1281
4.1 The Design of Cruiser 1282
4.1.1 Two-Tier Networks 1282
4.1.2 Distributed Architecture 1282
4.1.3 Asynchronous Communications 1282
4.1.4 Appropriate Timeouts 1283
4.2 Quantifying Snapshot Accuracy 1283
5 Sampling 1285
5.1 Sampling with Dynamics 1285
5.2 Sampling from Static Graphs 1286
5.2.1 Random Walks 1287
5.2.2 Adjusting for Degree Bias 1288
5.2.3 Evaluation 1288
5.3 Empirical Results 1290
5.3.1 Ion-Sampler 1290
5.3.2 Empirical Validation 1290
5.3.3 Efficiency 1291
6 Summary and Future Work 1292
References 1292
Improving Peer-to-Peer Transport Paths for Content Distribution 1295
Gerhard Hasslinger 1295
1 Introduction 1295
2 P2P Networking on Broadband Internet Platforms 1297
2.1 Users 1297
2.2 P2P Service and Protocol Designers 1298
2.3 Content and Service Providers 1298
2.4 Network and Broadband Access Providers 1299
2.5 Current Shifts in Internet Usage and Traffic Profiles 1299
3 Distribution and Access to Content on the Internet 1300
3.1 CDN Versus P2P Content Distribution 1301
3.2 Zipf Laws and 80:20 Rules 1302
4 Optimized Data Exchange in P2P Networks 1302
4.1 Current IETF Discussion on Application Layer TrafficEngineering 1303
4.2 Experience from the P4P Project Including Traffic Engineering 1304
4.3 Influence of Biased Source Selection on the Overlay Topology 1305
4.4 Caches 1306
4.5 Traffic Control for Bottlenecks 1307
5 Conclusions 1308
References 1308
Part XII Advanced P2P Computing and Networking 1310
A Formal Architectural Model for Peer-to-Peer Systems 1311
Lu Yan 1311
1 Introduction 1311
2 Action Systems 1312
2.1 Actions 1312
2.2 Classes and Objects 1313
2.3 OO-action System 1314
3 Initial Specification of the Gnutella System 1315
4 Action System Specification of the Gnutella System 1316
5 Refining Gnutella Servent 1318
5.1 Refining ConnectService 1319
5.2 Refining LookupService 1321
5.3 Refining DownloadService 1326
6 Concluding Remarks 1328
7 Future Directions 1328
References 1329
P2P Approach for Web Services Publishing and Discovery 1331
Mohmammad Towhidul Islam, Mursalin Akon, and Xuemin (Sherman) Shen 1331
1 Introduction 1331
2 Web Services 1333
2.1 Architecture of the Web Services 1333
2.2 UDDI Structure 1334
3 Peer-to-Peer Computing 1335
4 Web Services and P2P 1335
5 A Framework for Web Services Using P2P 1337
5.1 Registering a Peer 1337
5.2 Publishing Information 1338
5.3 Finding the Service 1338
6 Keyword Based Service Discovery 1339
6.1 System Architecture 1339
6.2 Query Engine 1340
6.3 Load Balancing 1341
7 Semantic Web Service 1341
7.1 Domain Ontology 1342
7.2 Semantic Web Service Discovery 1342
7.3 METEOR-S WSDI: A Semantic Web Services Tool 1343
7.3.1 Architecture of MWSDI 1343
8 Spider: A Unified Web Service Discovery Tool 1345
8.1 Keyword Based Search 1345
8.2 Ontology Based Search 1346
8.3 Behavior Based Search 1346
9 Discussion on Open Issues 1347
10 Conclusion 1347
References 1347
Content-Based Publish/Subscribe Systems 1349
Haiying Shen 1349
1 Introduction 1349
2 Subscription Models 1352
2.1 Topic-Based Systems 1352
2.2 Content-Based Systems 1353
2.3 Type-Based Systems 1353
3 Filter-Based and Multicast-Based Pub/Sub Systems 1354
4 Centralized and Distributed Pub/Sub Systems 1356
4.1 Centralized Pub/Sub Systems 1357
4.2 Distributed Broker-Based Pub/Sub Systems 1359
4.3 Distributed DHT-Based Pub/Sub Systems 1364
4.3.1 Introduction of DHT Overlay Networks 1365
4.3.2 Early DHT-Based Pub/Sub Systems 1367
4.3.3 DHT and Content Based Pub/Sub Systems 1370
5 Summary and Challenges 1376
References 1377
Supporting Collaboration and Creativity Through Mobile P2P Computing 1383
Adam Wierzbicki, Anwitaman Datta, ukasz Zaczek, and Krzysztof Rzadca 1383
1 Introduction 1383
2 Applications for Collaboration and Creativity Support 1385
3 Collaboration Middleware Functionality 1387
3.1 General-Purpose Mobile P2P Middleware 1387
3.2 Overview of Middleware Functions 1388
3.2.1 Session Management 1389
3.2.2 Conference Management 1389
3.2.3 Data Synchronization 1389
3.2.4 Data Sharing 1389
3.2.5 Presence 1390
3.2.6 Workspace Awareness 1390
3.2.7 Group Management 1390
3.2.8 Access Control 1390
3.2.9 Trust Management 1391
3.2.10 Event Management 1391
3.2.11 End-to-End Security Functions 1391
3.3 Required P2P Overlay Functions 1391
3.3.1 Routing 1391
3.3.2 Publish-Subscribe 1391
3.3.3 Multicast 1392
3.3.4 Overlay Adaptation Functions 1392
3.4 Research Issues Related to Middleware Function Design 1392
4 SIP and P2PSIP 1393
4.1 The Session Initiation Protocol 1393
4.2 P2PSIP 1397
4.2.1 P2PP 1399
4.3 A Case Study: SharedMind 1401
4.4 Research Issues Related to SIP and P2PSIP 1403
5 Vertically Integrated Overlay 1403
5.1 In the Realm of Ringless Routing 1404
5.2 Virtual Ring Routing 1405
5.2.1 Fuzzynet 1406
5.2.2 Lookup (Read) Operations on Fuzzynet 1407
5.2.3 Publish (Write) Operations on Fuzzynet 1408
5.3 Identity Crisis in a Large-Scale Decentralized World 1408
5.4 DHT Based on a SocialCircle 1409
5.4.1 VRR Adaptation for SocialCircle 1410
5.4.2 Average Stretch of SocialCircle 1411
5.4.3 Average Stretch Distribution 1412
5.4.4 Distribution of Minimum Distances 1412
5.5 The Outlook for Future Works 1413
5.5.1 Fuzzynet Adaptation of SocialCircle 1413
5.6 Good and Better Peers 1413
6 Conclusions 1414
References 1415
Index 1417