Vu / Lupu / Ooi Peer-to-Peer Computing

Principles and Applications
1. Auflage 2009
ISBN: 978-3-642-03514-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 317 Seiten

Peer-to-peer (P2P) technology, or peer computing, is a paradigm that is viewed as a potential technology for redesigning distributed architectures and, consequently, distributed processing. Yet the scale and dynamism that characterize P2P systems demand that we reexamine traditional distributed technologies. A paradigm shift that includes self-reorganization, adaptation and resilience is called for. On the other hand, the increased computational power of such networks opens up completely new applications, such as in digital content sharing, scientific computation, gaming, or collaborative work environments. In this book, Vu, Lupu and Ooi present the technical challenges offered by P2P systems, and the means that have been proposed to address them. They provide a thorough and comprehensive review of recent advances on routing and discovery methods; load balancing and replication techniques; security, accountability and anonymity, as well as trust and reputation schemes; programming models and P2P systems and projects. Besides surveying existing methods and systems, they also compare and evaluate some of the more promising schemes. The need for such a book is evident. It provides a single source for practitioners, researchers and students on the state of the art. For practitioners, this book explains best practice, guiding selection of appropriate techniques for each application. For researchers, this book provides a foundation for the development of new and more effective methods. For students, it is an overview of the wide range of advanced techniques for realizing effective P2P systems, and it can easily be used as a text for an advanced course on Peer-to-Peer Computing and Technologies, or as a companion text for courses on various subjects, such as distributed systems, and grid and cluster computing.

Quang Hieu Vu is currently a Research Fellow at Institute for Infocomm Research (I2R), Singapore. He obtained his PhD degree from the Singapore-MIT Alliance in 2008. Before joining I2R, he was respectively a Research Fellow at National University of Singapore and Imperial College London. His research interests include peer-to-peer, information retrieval, and network security. Mihai Lupu has been a post-doctoral research fellow with the Information Retrieval Facility in Vienna, Austria, since October 2008. He has recently received his PhD degree from the Singapore-MIT Alliance at the National University of Singapore, where he has worked mostly on Information Retrieval on Peer-to-Peer Networks. His research interests include information retrieval and management, peer-to-peer and ad-hoc networks. Beng Chin Ooi is Professor of Computer Science at the National University of Singapore (NUS). He obtained his PhD from Monash University, Australia, in 1989. He has served as a PC member for international conferences including ACM SIGMOD, VLDB, IEEE ICDE, WWW, SIGKDD and is the recipient of ACM SIGMOD 2009 Contributions award and an IEEE fellow. His research interests include database performance issues, indexing techniques, multimedia and spatio-temporal databases, P2P systems and advanced applications, and data intensive scalable computing.  

Autoren/Hrsg.

Vu, Quang Hieu

Lupu, Mihai

Ooi, Beng Chin

Inhaltsverzeichnis

1;Preface;5
1.1;Organization of the Book;6
2;Acknowledgements;8
3;Contents;9
4;Introduction;15
4.1;Peer-to-Peer Computing;15
4.2;Potential, Benefits, and Applications;17
4.3;Challenges and Design Issues;21
4.4;P2P vs. Grid Computing;22
4.5;Summary;24
5;Architecture of Peer-to-Peer Systems;25
5.1;A Taxonomy;26
5.1.1;Centralized P2P Systems;27
5.1.2;Decentralized P2P Systems;27
5.1.3;Hybrid P2P Systems;29
5.2;Centralized P2P Systems;29
5.2.1;Napster: Sharing of Digital Content;31
5.2.2;About SETI@home;32
5.3;Fully Decentralized P2P Systems;34
5.3.1;Properties;35
5.3.2;Gnutella: The First "Pure" P2P System;36
5.3.2.1;Properties;36
5.3.3;PAST: A Structured P2P File Sharing System;38
5.3.3.1;Properties;38
5.3.4;Canon: Turning Flat DHT into Hierarchical DHT;40
5.3.4.1;Properties;42
5.3.5;Skip Graph: A Probabilistic-Based Structured Overlay;42
5.3.5.1;Properties;44
5.4;Hybrid P2P Systems;45
5.4.1;BestPeer: A Self-Configurable P2P System;46
5.5;Summary;50
6;Routing in Peer-to-Peer Networks;52
6.1;Evaluation Metrics;53
6.2;Routing in Unstructured P2P Networks;53
6.2.1;Basic Routing Strategies;54
6.2.1.1;Breadth-First Search;54
6.2.1.2;Depth-First Search;54
6.2.2;Heuristic-Based Routing Strategies;56
6.2.2.1;Iterative Deepening;56
6.2.2.2;Directed BFS and Intelligent Search;57
6.2.2.3;Local Indices Search;58
6.2.2.4;Routing Indices-Based Search;59
6.2.2.5;Random Walk;60
6.2.2.6;Adaptive Probabilistic Search;61
6.2.2.7;Bloom Filter Based Search;61
6.2.2.8;Interest-Based Shortcuts;62
6.3;Routing in Structured P2P Networks;63
6.3.1;Chord;65
6.3.2;CAN;69
6.3.3;PRR Trees, Pastry and Tapestry;71
6.3.4;Viceroy;76
6.3.5;Crescendo;77
6.3.6;Skip Graph;78
6.3.7;SkipNet;80
6.3.8;P-Grid;80
6.3.9;P-Tree;82
6.3.10;BATON;84
6.4;Routing in Hybrid P2P Networks;86
6.4.1;Hybrid Routing;86
6.4.1.1;Edutella;87
6.4.1.2;Ultrapeers;89
6.4.1.3;Structured Superpeers;90
6.5;Summary;91
7;Data-Centric Applications;94
7.1;Multi-Dimensional Data Sharing;95
7.1.1;VBI-Tree;97
7.1.2;Mercury;99
7.1.3;SSP;101
7.2;High-Dimensional Indexing;103
7.2.1;CISS;104
7.2.2;ZNet;105
7.2.3;M-Chord;107
7.2.4;SIMPEER;109
7.2.5;LSH Forest;110
7.3;Textual Information Retrieval;111
7.3.1;Basic Techniques;113
7.3.1.1;Query and Document Representation;113
7.3.1.2;Directory Management;114
7.3.1.3;Ranking of Results;116
7.3.1.4;Improving the Performance of Information Retrieval;116
7.3.2;PlanetP;117
7.3.3;Summary Index;119
7.3.4;pSearch;120
7.3.5;PRISM;122
7.4;Structured Data Management;124
7.4.1;Query Processing in Heterogeneous Data Sources;125
7.4.1.1;Semantics;125
7.4.1.2;Mapping Heterogeneous Data Sources;126
7.4.1.3;Query Processing over Relational Databases;128
7.4.1.4;Query Processing over XML Documents;129
7.4.1.5;Unstructured Keyword Query Processing over Relational Databases;130
7.4.1.6;Indexing Schemes;131
7.4.2;Piazza;131
7.4.2.1;Peer-Programming Language;132
7.4.2.2;Query Reformulation Algorithm;133
7.4.3;Hyperion;134
7.4.3.1;Mapping Table Construction;134
7.4.3.2;Query Processing;136
7.4.4;PeerDB;136
7.4.4.1;Table-to-Query Similarity Measurement;137
7.4.4.2;Query Processing;137
7.5;Summary;138
8;Load Balancing and Replication;140
8.1;Load Balancing;141
8.1.1;When Load Balancing is Triggered;141
8.1.1.1;Dynamic Load Balancing;141
8.1.1.2;Static Load Balancing;142
8.1.1.3;The Power of Two Choices;143
8.1.2;How Load Balancing is Performed;144
8.2;Load Balancing in Concrete Systems;145
8.2.1;Basic Load Balancing Schemes with Virtual Nodes;145
8.2.1.1;One-to-One Scheme;145
8.2.1.2;One-to-Many Scheme;146
8.2.1.3;Many-to-Many Scheme;146
8.2.2;Y0 Protocol;147
8.2.3;The S&M Protocol;148
8.2.3.1;The Design of the S&M Protocol;149
8.2.4;A Combination of Both Local and Random Probes;150
8.2.4.1;Load Imbalance Boundary;150
8.2.5;Mercury;150
8.2.5.1;Load Balancing with Histograms;151
8.2.6;Online Balancing of Range-partitioned Data;152
8.3;Replication;153
8.3.1;Replica Granularity;153
8.3.1.1;Full Replication;154
8.3.1.2;Block Replication;154
8.3.2;Replica Quantity;155
8.3.2.1;Uniform Replication;155
8.3.2.2;Proportional Replication;155
8.3.2.3;Square-root Replication;155
8.3.3;Replica Distribution;156
8.3.4;Replica Consistency;157
8.3.4.1;Replication with Expiration;157
8.3.4.2;Immediate Updates;157
8.3.5;Replica Replacement;157
8.3.5.1;Minimum Relative Size;158
8.4;Replication in Concrete Systems;158
8.4.1;Replication in Read-only Unstructured P2P Systems;158
8.4.2;Replication in Read-only Structured P2P Systems;158
8.4.2.1;Past;158
8.4.2.2;Cooperative File System;159
8.4.3;Beehive;160
8.4.3.1;Analytical Model;160
8.4.3.2;Replication;161
8.4.4;Symmetric Replication for Structured Peer-to-Peer Systems;162
8.4.4.1;Node Grouping;162
8.4.4.2;Data Replication;162
8.4.5;CUP: Controlled Update Propagation in Peer-to-Peer Networks;163
8.4.5.1;System Architecture;163
8.4.5.2;Data Replication;163
8.4.6;Dynamic Replica Placement for Scalable Content Delivery;164
8.4.6.1;Disseminating Tree Construction;164
8.4.6.2;Disseminating Tree Maintenance;165
8.4.7;Updates in Highly Unreliable, Replicated P2P Systems;165
8.4.8;Proactive Replication;167
8.4.8.1;Replication Protocol Design;167
8.5;Summary;168
9;Security in Peer-to-Peer Networks;170
9.1;Routing Attacks;170
9.1.1;Incorrect Lookup Routing;171
9.1.2;Incorrect Routing Updates;171
9.1.3;Incorrect Routing Network Partition;171
9.1.4;Secure Routing Scheme;172
9.2;Storage and Retrieval Attacks;173
9.3;Denial-of-Service Attacks;175
9.3.1;Managing Attacks;176
9.3.2;Detecting and Recovering from Attacks;177
9.3.3;Other Attacks;179
9.4;Data Integrity and Verification;179
9.4.1;Verifying Queries in Relational Databases;180
9.4.2;Self-verifying Data with Erasure Code;183
9.5;Verifying Integrity of Computation;184
9.6;Free Riding and Fairness;185
9.6.1;Quota-Based System;186
9.6.2;Trading-Based Schemes;187
9.6.3;Distributed Auditing;188
9.6.4;Incentive-Based Schemes;189
9.6.5;Adaptive Topologies;191
9.7;Privacy and Anonymity;192
9.8;PKI-Based Security;194
9.9;Summary;195
10;Trust and Reputation;196
10.1;Concepts;197
10.1.1;Trust Definitions;197
10.1.1.1;What is Trust;197
10.1.1.2;Trust in the View of Psychology;197
10.1.1.3;Trust in the View of Sociology;197
10.1.1.4;Trust in a Broader View;198
10.1.2;Trust Types;198
10.1.2.1;Trust in Action;198
10.1.2.2;Trust in Recommendation;198
10.1.3;Trust Values;199
10.1.3.1;Single Value;199
10.1.3.2;Binary Values;199
10.1.3.3;Multiple Values;199
10.1.3.4;Continuous Values;200
10.1.4;Trust Properties;200
10.1.4.1;Autonomy;200
10.1.4.2;Asymmetry;200
10.1.4.3;Transitivity;201
10.1.4.4;Composability;201
10.2;Trust Models;201
10.2.1;Trust Model Based on Credentials;202
10.2.2;Trust Model Based on Reputation;202
10.3;Trust Systems Based on Credentials;203
10.3.1;PolicyMaker;203
10.3.1.1;System Architecture;204
10.3.1.2;The PolicyMaker Language;204
10.3.1.3;Query Processing;205
10.3.2;Trust-X;205
10.3.2.1;System Architecture;205
10.4;Trust Systems Based on Individual Reputation;207
10.4.1;P2PRep;207
10.4.1.1;Basic Polling Protocol;207
10.4.1.2;Enhanced Polling Protocol;208
10.4.2;XRep;209
10.4.3;Cooperative Peer Groups in NICE;210
10.4.3.1;Trust Evaluation;210
10.4.3.2;Finding Paths Between Two Nodes in the Trust Graph;211
10.4.4;PeerTrust;211
10.4.4.1;General Trust Metric;212
10.5;Trust Systems Based on Both Individual Reputation and Social Relationship;213
10.5.1;Regret;213
10.5.1.1;Individual Dimension;213
10.5.1.2;Social Dimension;213
10.5.1.3;Ontology Dimension;213
10.5.2;NodeRanking;215
10.5.2.1;Social Network Construction;215
10.5.2.2;Reputation Evaluation;215
10.5.2.3;NodeRanking Algorithm;215
10.6;Trust Management;216
10.6.1;Server Based Trust Management;216
10.6.2;Gossiping Based Trust Management;217
10.6.3;Structured P2P Based Trust Management;217
10.6.4;XenoTrust;218
10.6.4.1;Architecture;220
10.6.5;EigenRep;220
10.6.5.1;Local Reputation;221
10.6.5.2;Global Reputation;221
10.6.6;Trust Management with P-Grid;223
10.6.6.1;Trust Evaluation;223
10.6.6.2;P-Grid Based Trust Management;223
10.7;Summary;225
11;P2P Programming Tools;228
11.1;Low Level P2P Programming;228
11.1.1;Sockets;229
11.1.2;Remote Procedure Call;229
11.1.3;Web Services;230
11.2;High Level P2P Programming;230
11.2.1;JXTA;231
11.2.1.1;Implementations;232
11.2.1.2;Protocols;232
11.2.1.3;Adding Value to the Network;233
11.2.1.4;Other Considerations;233
11.2.2;BOINC;234
11.2.3;P2;235
11.2.3.1;The Specification Language: NDlog;235
11.2.3.2;The Execution Framework;236
11.2.4;Mace;236
11.2.5;OverlayWeaver;236
11.2.6;Microsoft's Peer-to-Peer Framework;237
11.3;Deployment and Testing Environments;238
11.3.1;PlanetLab;238
11.3.1.1;Participating in PlanetLab;238
11.3.1.2;Application Deployment on PlanetLab;239
11.3.2;Emulab;239
11.3.2.1;Interfacing Emulab and PlanetLab;240
11.3.3;Amazon.com;240
11.4;Summary;240
12;Systems and Applications;242
12.1;Classic File Sharing Systems;242
12.1.1;Napster;242
12.1.1.1;Overview;242
12.1.1.2;How Napster Works;243
12.1.1.3;Protocol;244
12.1.1.4;Litigation: an Issue Beyond Technology;246
12.1.2;Gnutella;246
12.1.2.1;Overview of Gnutella;246
12.1.2.2;Protocol;248
12.1.2.3;Challenges;249
12.1.3;Freenet;250
12.1.3.1;Freenet Working Mechanisms;251
12.1.3.2;Freenet Protocol;254
12.1.3.3;Merits and Limitations;256
12.2;Peer-to-Peer Backup;256
12.2.1;pStore;257
12.2.2;A Cooperative Internet Backup Scheme;260
12.2.3;Pastiche;261
12.2.4;Samsara-Fairness for Pastiche;263
12.2.5;Other Systems;264
12.2.6;Analysis of Existing Systems;265
12.3;Data Management;267
12.3.1;Architectures for P2P Data Management Systems;267
12.3.1.1;PIER;267
12.3.1.2;BestPeer;269
12.3.2;XML Content Routing Network;271
12.3.2.1;Mesh-based Content Routing;271
12.3.2.2;View Selection;272
12.3.2.3;XML Data Filtering;273
12.3.3;Continuous Query Processing;273
12.3.3.1;PeerCQ;274
12.3.3.2;CQ-Buddy;274
12.3.3.3;Medusa;275
12.4;Peer-to-Peer-Based Web Caching;275
12.4.1;Background of Web Caching;275
12.4.2;Squirrel;276
12.4.2.1;Pastry: The Supporting P2P Infrastructure;277
12.4.2.2;How Squirrel Works;277
12.4.3;BuddyWeb: A P2P-based Collaborative Web Caching System;279
12.4.3.1;Architecture of BuddyWeb;280
12.4.3.2;Similarity-Based Reconfiguration;281
12.4.3.3;Similarity-based Routing and Self-adaptive Hopping;282
12.5;Communication and Collaboration;283
12.5.1;Instant Messaging;283
12.5.2;Jabber;283
12.5.2.1;Jingle;284
12.5.2.2;Serverless Communication;284
12.5.3;Skype;284
12.5.4;Distributed Collaboration;285
12.5.4.1;JBuilder;285
12.5.4.2;MS Groove;285
12.5.4.3;Collanos Workspace;286
12.6;Mobile Applications;286
12.6.1;Communication Applications;286
12.6.2;File Sharing Applications;287
12.6.2.1;Peer-to-Peer in Spirit;288
12.6.2.2;Peer-to-Peer in Implementation;288
12.7;Summary;289
13;Conclusions;291
13.1;Summary;291
13.1.1;Architecture;291
13.1.2;Routing and Resource Discovery;292
13.1.3;Data-Centric Applications;293
13.1.4;Load Balancing and Replication;294
13.1.5;Programming Models;294
13.1.6;Security Problems;295
13.1.7;Trust Management;296
13.2;Potential Research Directions;297
13.2.1;Sharing Structured Databases;297
13.2.2;Security;298
13.2.3;Data Stream Processing;299
13.2.4;Testbed and Benchmarks;299
13.3;Applications in Industry;300
13.3.1;Supply Chain Management Case Study;301
13.3.1.1;Potential Issues;303
13.3.1.2;Queries;304
14;References;305
15;Index;321