UNIT 3
Peer-to-Peer Systems
• Peer to peer systems aim to support useful
distributed services and applications using data
and computing resources available in the
personal computers and workstations that are
present in the internet and other networks
Characteristics :
[Link] resources to the system
[Link] same functional capabilities and
responsibilities
[Link] operation does not depend on the
existence of centrally administered systems
Distinctions between IP and overlay routing for
peer-to-peer applications
IP Application-level routing overlay
Scale IPv4 is limited to 232 addressable nodes. The Peer-to-peer systems can address more objects.
IPv6 name space is much more generous The GUID name space is very large and flat
(2128), but addresses in both versions are (>2128), allowing it to be much more fully
hierarch ically structured and much of the space occupied.
is pre-allocated accordi ng to administrative
requirements.
Load balancing Loads on routers are determined by network Object locations can be randomized and hence
topology and associated traffic patterns. traffic patterns are divorced from the network
topology.
Network dynamics IP routing tables are updated asynchronously on Routing tables can be updated synchronously or
(addition/deletion of a best-efforts basis with time constants on the asynchronously with fractions of a second
objects/nodes) order of 1 hour. delays.
Fault tolerance Redundancy is designed into the IP network by Routes and object references can be replicated
its managers, ensuring tolerance of a single n-fold, ensuring tolerance of n failures of nodes
router or network connectivity failure. n-fold or connections.
replication is costly.
Target identificatio n Each IP address maps to exactly one target Messages can be routed to the nearest replica of
node. a target object.
Security and anonymity Addressing is only secure when all nodes are Security can be achieved even in environments
trusted. Anonymity for the owners of addresses with limited trust. A limited degree of
is not achievable. anonymity can be provided.
Napster: peer-to-peer file sharing with a centralized,
replicated index
peers
Napster server Napster server
Index 1. File location Index
request
3. File request
2. List of peers
offering the file
5. Index update
4. File delivered
Distribution of information in a routing overlay
AХs routing knowledge DХs routing knowledge
A
D
Object:
BХs routing knowledge CХs routing knowledge
Node:
Basic programming interface for a distributed hash table
(DHT) as implemented by the PAST API over Pastry
put(GUID, data)
The data is stored in replicas at all nodes responsible for the object
identified by GUID.
remove(GUID)
Deletes all references to GUID and the associated data.
value = get(GUID)
The data associated with GUID is retrieved from one of the nodes
responsible it.
Figure 10.5: Basic programming interface for distributed object location
and routing (DOLR) as implemented by Tapestry
publish(GUID )
GUID can be computed from the object (or some part of it, e.g. its
name). This function makes the node performing a publish
operation the host for the object corresponding to GUID.
unpublish(GUID)
Makes the object corresponding to GUID inaccessible.
sendToObj(msg, GUID, [n])
Following the object-oriented paradigm, an invocation message is
sent to an object in order to access it. This might be a request to
open a TCP connection for data transfer or to return a message
containing all or part of the object’s state. The final optional
parameter [n], if present, requests the delivery of the same
message to n replicas of the object.
Figure 10.6: Circular routing alone is correct but inefficient
Based on Rowstron and Druschel [2001]
0 FFFFF....F (2128-1) The dots depict live nodes. The
space is considered as circular:
node 0 is adjacent to node (2128-
1). The diagram illustrates the
D471F1 routing of a message from node
65A1FC to D46A1C using leaf set
D467C4 information alone, assuming leaf
D46A1C sets of size 8 (l = 4). This is a
degenerate type of routing that
would scale very poorly; it is not
used in practice.
D13DA3
65A1FC
Figure 10.7: First four rows of a Pastry routing table
The routing table is located at a node whose GUID begins 65A1. Digits are in hexadecimal. The n’s represent [GUID, IP address] pairs specifying the next
hop to be taken by messages addressed to GUIDs that match each given prefix. Grey- shaded entries indicate that the prefix matches the current GUID up
to the given value of p: the next row down or the leaf set should be examined to find a route. Although there are a maximum of 128 rows in the table, only
log16 N rows will be populated on average in a network with N active nodes.
Figure 10.8: Pastry routing example Based on Rowstron and Druschel [2001]
Routing a message from node 65A1FC to D46A1C.
With the aid of a well-populated routing table the
0 FFFFF....F (2128-1) message can be delivered in ~ log 16 (N ) hops.
D471F1
D467C4
D46A1C D462BA
D4213F
D13DA3
65A1FC
Figure 10.9: Pastry’s routing algorithm
To handle a message M addressed to a node D (where R[p,i] is the element at column i,
row p of the routing table):
1. If (L -l < D < Ll) { // the destination is within the leaf set or is the current node.
2. Forward M to the elementL i of the leaf set with GUID closest toD or the current
node A.
3. } else { // use the routing table to despatchM to a node with a closer GUID
4. find p, the length of the longest common prefix of D and A. and i, the (p+1)th
hexadecimal digit of D.
5. If (R[p,i] ° null) forward M to R[p,i] // route M to a node with a longer common
prefix.
6. else { // there is no entry in the routing table
7. Forward M to any node in L or R with a common prefix of length i, but a
GUID that is numerically closer.
}
}
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012
Figure 10.10: Tapestry routing From [Zhao et al. 2004]
4377 (Root for 4378)
Tapestry routings
for 4377
43FE 437A
publish path
4228
4361
Location mapping 4378
PhilХs 4664
for 4378
Books
4B4F 4A6D
Routes actually
taken bysend(4378) E791 4378
57EC AA93 PhilХs
Books
Replicas of the file PhilХs Books (G=4378) are hosted at nodes 4228 and AA93. Node 4377 is the root node
for object 4378. The Tapestry routings shown are some of the entries in routing tables. The publish paths show
routes followed by the publish messages laying down cached location mappings for object 4378. The location
mappings are subsequently used to route messages sent to 4378.
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012
Figure 10.11: Structured versus unstructured peer-to-peer systems
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012
Figure 10.12: Key elements in the Gnutella protocol
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012 13
Figure 10.13: Storage organization of OceanStore objects
AGUID
VGUID of current
certificate
version
version i+1
VGUID of
BGUID (copy on write)
version i
d1 d2 d3
root block
version i indirection blocks
data blocks d1 d2 d3 d4 d5
Version i+1 has been updated in blocks d1,
d2 and d3. The certificate and the root
VGUID of version i-1
blocks include some metadata not shown.
All unlabelled arrows are BGUIDs.
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012
Figure 10.14: Types of identifier used in OceanStore
Name Meaning Description
BGUID block GUID Secure hash of a data block
VGUID version GUID BGUID of the root block of a version
AGUID active GUID Uniquely identifies all the versions of an object
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012
Figure 10.15: Performance evaluation of the Pond prototype emulating NFS
LAN WAN Predominant
operations in
Phase Linux NFS Pond Linux NFS Pond benchmark
1 0.0 1.9 0.9 2.8 Read and write
2 0.3 11.0 9.4 16.8 Read and write
3 1.1 1.8 8.3 1.8 Read
4 0.5 1.5 6.9 1.5 Read
5 2.6 21.0 21.5 32.0 Read and write
Total 4.5 37.2 47.0 54.9
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012
Figure 10.16: Ivy system architecture
Ivy node
DHash server
Application Application
DHash server
Ivy server DHash server
DHash server
Modifled
NFS Client
module DHash server
Kernel
Instructor’s Guide for Coulouris, Dollimore, Kindberg and Blair, Distributed Systems: Concepts and Design Edn. 5
© Pearson Education 2012
