程序代写代做代考 c/c++ scheme distributed system Java c# algorithm Week 6 - P2P Systems

Week 6 – P2P Systems

PEER-TO-PEER
SYSTEMS
Dr Bailin Deng

Motivation
• Any P2P services you used before?

Motivation
• Limitation of client-server architecture

• Lack of scalability (hardware & network capacity)

Motivation
• Limitation of client-server architecture

• Lack of scalability (hardware & network capacity)
• Lack of fault-tolerance

Motivation
• Peer-to-peer network

• Decentralized: each node (peer) can be both client and server

Motivation
• Peer-to-peer network

• Decentralized: each node (peer) can be both client and server
• Sharing resources (computing power, storage, data etc.)

Overview
• Examples of P2P networks
• Structured vs unstructured P2P
• Peer-to-peer middleware

Example: SETI@Home
• Search for Extraterrestrial Intelligence (SETI) using

internet-connected computers

https://setiathome.berkeley.edu/

Example: SETI@Home
• Radio SETI: listen for narrow-bandwidth signals using

radio telescopes

Radio telescope

Example: SETI@Home
• Early days: analyze signals using supercomputers

Radio telescope Supercomputer

Signals

Example: SETI@Home
• Distributed computing

Radio telescope

Server@Berkeley
Signals

Example: SETI@Home
• Distributed computing

Radio telescope

Server@Berkeley

Data

Example: SETI@Home
• Distributed computing

Radio telescope

Server@Berkeley

Results

Example: SETI@Home
• SETI@Home client:

• Either as a screensaver (runs when computer is idle)
• Or runs continuously

Example: SETI@Home

Real-time overview: https://setiathome.berkeley.edu/kiosk/

Example: Napster
• P2P file sharing system, launched

in 1999

• Popular for music exchange, with
millions of users at its peak

• Shut down in 2001 due to
copyright infringement

Example: Napster
• Clients provide files, and servers keep index of the files
• Newly joined nodes send its list of files and metadata to the

index server

Example: Napster
• Downloading in Napster

File location request

Example: Napster
• Downloading in Napster

List of peers
offering the file

Example: Napster
• Downloading in Napster

File request

Example: Napster
• Downloading in Napster

File delivered

Example: Napster
• Downloading in Napster

Index update

Example: Napster
• Advantages

• Simple implementation
• Fast and effective file lookup

Example: Napster
• Disadvantage: reliance on central servers

• Does not scale well
• Server shutdown breaks the whole network

Example: Gnutella (0.4)
• True P2P file sharing system, without central servers
• Each client connects to a list of neighbor peers

so on. A few checks are needed to prevent messages from circulating endlessly.
First, in case the message loops back or is received over more than one path, each
peer can keep a list of message identifiers that it has previously received. If it sees
the same message again, it simply drops the duplicate message. Second, so that
peers don’t have to remember messages for an arbitrary time, which would
require a continuously growing amount of storage, each message has a time-to-
live (TTL) value that limits its lifetime. The TTL value of a message is set by the
message originator and decremented by 1 at each peer that receives the message.
When the TTL value of a message reaches 0, it is no longer forwarded.

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

As mentioned earlier, each peer has a list of neighbors. It initializes its list of
neighbors when it joins the overlay, for example, by getting a copy of the neigh-
bor list of the first peer in the overlay that it connects to. Over time it can add and
remove peers from its neighbor list. To refresh and update its neighbor list, it can
send requests to current neighbors asking for their neighbors. It can also use

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Example: Gnutella (0.4)
• Newly joined nodes do not need to publish their files; they

just wait for file queries

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Example: Gnutella (0.4)
• Challenge: how to locate files?

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Example: Gnutella (0.4)
• Send query to neighbors, with TTL = 7

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Example: Gnutella (0.4)
• If a neighbor has the file, it returns the result
• If not, it forwards the query to their neighbors, with

decremented TTL

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Example: Gnutella (0.4)
• Continue until TTL reaches zero

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Example: Gnutella (0.4)
• Continue until TTL reaches zero
• Simple flooding: query requests flood across network

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Simple Flooding
• Easy to implement
• Large overhead: even if a file is found quickly, messages

continue to propagate along other paths.

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Example: Gnutella (0.4)
• Advantages:

• Distributed network structure that is scalable
• No reliance on central servers: network cannot be easily taken down

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Example: Gnutella (0.4)
• Disadvantage:

• Bounded depth of query path reduces success probability
• Simple flooding search is inefficient

This simple query algorithm is called flooding (Figure 3.1B) and is shown in
the following pseudo-code:

FloodForward(Query q, Source p)

// have we seen this query before?

if(q.id 2 oldIdsQ) return // yes, drop it
oldIdsQ ¼ oldIdsQ [ q.id // remember this query
// expiration time reached?

q.TTL ¼ q.TTL – 1
if q.TTL ” 0 then return // yes, drop it
// no, forward it to remaining neighbors

foreach(s 2 Neighbors) if(s 6¼ p) send(s,q)

A
Query
B

FIGURE 3.1 (A) Unstructured topology showing connections between peers and (B) query
flooding to four hops.

Basic Routing in Unstructured Overlays 47

Query

Improved Search Strategies
• Expanded ring search: The initiating node carries out a

series of searches with increasing TTL.

Improved Search Strategies
• Expanded ring search: The initiating node carries out a

series of searches with increasing TTL.

• Start query with a small TTL; if file is found, then stop
• Otherwise, resend the query with larger TTL
• Continue until TTL reaches upper limit

Improved Search Strategies
• Expanded ring search: The initiating node carries out a

series of searches with increasing TTL.

• Start query with a small TTL; if file is found, then stop
• Otherwise, resend the query with larger TTL
• Continue until TTL reaches upper limit

• Particularly effective for popular files that are frequently
replicated: high chance to find a match with a few hops

Improved Search Strategies
• Random walk: the initiating node sets off a number of

walkers that follow random pathways
• Send query to a randomly selected neighbor
• Message propagate across a random path
• If query fails, send to another neighbor

unstructured overlays is to control the replication and placement of objects and
the neighbor relationships to increase the likelihood of finding the objects. We
discuss several approaches later in this chapter and describe overall search
mechanisms in Chapter 7.

Random Walk

To avoid the message overhead of flooding, unstructured overlays can use some
type of random walk. In random walk (Figure 3.2A), a single query message is
sent to a randomly selected neighbor. The message has a TTL value that is decre-
mented at each hop. If the query locates a node with the desired object, the
search terminates and the object is returned. Otherwise the query fails, as deter-
mined by a timeout or an explicit failure message returned by the last peer on the
walk. The initiating peer has the choice to reissue a query along another ran-
domly chosen path. To improve the response time, several random walk queries
can be issued in parallel (Figure 3.2B).

The key step in random walk is the random selection of the next hop, which
avoids forwarding the query back to the node from which the query was
received. The pseudo-code for RandomWalk follows:

RandomWalk(source, query, TTL)

if (TTL > 0) {

TTL ¼ TTL – 1
// select next hop at random, don’t send back to source

while((next_hop ¼ neighbors[random()]) ¼¼ source)
send(source, query,TTL)

}

Query
A

Query
B

FIGURE 3.2 (A) Random walk and (B) k-way parallel random walk, k ¼ 3.

Basic Routing in Unstructured Overlays 49

Improved Search Strategies
• Random walk: the initiating node sets off a number of

walkers that follow random pathways
• Send query to a randomly selected neighbor
• Message propagate across a random path
• If query fails, send to another neighbor

Random Walk

The key step in random walk is the random selection of the next hop, which
avoids forwarding the query back to the node from which the query was
received. The pseudo-code for RandomWalk follows:

RandomWalk(source, query, TTL)

if (TTL > 0) {

TTL ¼ TTL – 1
// select next hop at random, don’t send back to source

while((next_hop ¼ neighbors[random()]) ¼¼ source)
send(source, query,TTL)

}

Query
A

Query
B

FIGURE 3.2 (A) Random walk and (B) k-way parallel random walk, k ¼ 3.

Basic Routing in Unstructured Overlays 49

Improved Search Strategies
• Random walk: the initiating node sets off a number of

walkers that follow random pathways
• Send query to a randomly selected neighbor
• Message propagate across a random path
• If query fails, send to another neighbor

Random Walk

The key step in random walk is the random selection of the next hop, which
avoids forwarding the query back to the node from which the query was
received. The pseudo-code for RandomWalk follows:

RandomWalk(source, query, TTL)

if (TTL > 0) {

TTL ¼ TTL – 1
// select next hop at random, don’t send back to source

while((next_hop ¼ neighbors[random()]) ¼¼ source)
send(source, query,TTL)

}

Query
A

Query
B

FIGURE 3.2 (A) Random walk and (B) k-way parallel random walk, k ¼ 3.

Basic Routing in Unstructured Overlays 49

Improved Search Strategies
• Random walk: the initiating node sets off a number of

walkers that follow random pathways
• Send query to a randomly selected neighbor
• Message propagate across a random path
• If query fails, send to another neighbor

Random Walk

The key step in random walk is the random selection of the next hop, which
avoids forwarding the query back to the node from which the query was
received. The pseudo-code for RandomWalk follows:

RandomWalk(source, query, TTL)

if (TTL > 0) {

TTL ¼ TTL – 1
// select next hop at random, don’t send back to source

while((next_hop ¼ neighbors[random()]) ¼¼ source)
send(source, query,TTL)

}

Query
A

Query
B

FIGURE 3.2 (A) Random walk and (B) k-way parallel random walk, k ¼ 3.

Basic Routing in Unstructured Overlays 49

Random Walk

The key step in random walk is the random selection of the next hop, which
avoids forwarding the query back to the node from which the query was
received. The pseudo-code for RandomWalk follows:

RandomWalk(source, query, TTL)

if (TTL > 0) {

TTL ¼ TTL – 1
// select next hop at random, don’t send back to source

while((next_hop ¼ neighbors[random()]) ¼¼ source)
send(source, query,TTL)

}

Query
A

Query
B

FIGURE 3.2 (A) Random walk and (B) k-way parallel random walk, k ¼ 3.

Basic Routing in Unstructured Overlays 49

Improved Search Strategies
• Random walk: the initiating node sets off a number of

walkers that follow random pathways
• Send query to a randomly selected neighbor
• Message propagate across a random path
• If query fails, send to another neighbor
• Can send multiple queries in parallel

Improved Search Strategies
• Gossiping: A node sends a request to a given neighbor with

certain probability, which can be based on previous
experience and/or current context.

Gnutella 2
• Hybrid architecture

• Ultrapeers: high-bandwith nodes connected with original
Gnutella protocol

• Leaf nodes, each connected to a few ultrapeers
Ultrapeers

Leaf nodes

Gnutella 2
• Queries propagate via ultrapeers

Ultrapeers

Leaf nodes

Gnutella 2
• Queries propagate via ultrapeers

Ultrapeers

Leaf nodes

Gnutella 2
• Queries propagate via ultrapeers

Ultrapeers

Leaf nodes

Gnutella 2
• Queries propagate via ultrapeers

• Reduce the number of hops required for exhaustive search

Ultrapeers

Leaf nodes

Skype (circa 2006)
• Similar hybrid architecture

Figure 12.5. This figure does not show other key elements needed to support
other features of Skype, such as Skype-to-PSTN calls and voicemail.

Calls involving one or more ordinary nodes are relayed through supernodes.
Then the network and computing resources used by supernodes can be consider-
ably higher than ordinary nodes. Some limited study has been made of Skype selec-
tion of supernodes. Experimental evidence seems to indicate that supernodes may
be used that are remote from the actual call path.538 For example, on a set of inter-
national calls, the RTT on the call path sometimes exceeded 300 msec, which
crosses the acceptable perceptual threshold of delay for voice calls (Figure 12.6A).

Further, the time to select a relay sometimes exceeded several hundred sec-
onds (Figure 12.6B). Xie and Yang545 show that Skype call quality would decrease
significantly if supernodes in edge networks (called AS stubs) adopted a policy of
blocking relay traffic. Zhou et al.539 show that if the relay population dropped

Skype login
server

ordinary host

super node

neighbour relationships in the
Skype network

Message exchange
with the login server
during login

FIGURE 12.5 Skype network entities.541 # 2006 S. Baset and H. Schulzrinne.

290 CHAPTER 12 Voice Over Peer-to-Peer

Figure 12.5. This figure does not show other key elements needed to support
other features of Skype, such as Skype-to-PSTN calls and voicemail.

Skype login
server

ordinary host

super node

neighbour relationships in the
Skype network

Message exchange
with the login server
during login

FIGURE 12.5 Skype network entities.541 # 2006 S. Baset and H. Schulzrinne.

290 CHAPTER 12 Voice Over Peer-to-Peer

Baset, S.A. and Schulzrinne, H.G. (2006). An analysis
of the Skype peer-to-peer Internet telephony protocol.
In Proceedings of INFOCOM’06, pp. 1–11.

BitTorrent
• Popular P2P file-sharing application, designed particularly

for downloading large files

BitTorrent
• Popular P2P file-sharing application, designed particularly

for downloading large files
• 15–27 million concurrent users at any time, as of 2013

BitTorrent
• Principal feature: splitting files into fixed-sized chunks

• Clients download many chunks in parallel from different peers

BitTorrent
• Principal feature: splitting files into fixed-sized chunks

• Clients download many chunks in parallel from different peers
• Fast download speed, especially for popular files

BitTorrent
• Each file is associated with a .torrent file that holds the

metadata
• Name and size of the file
• Location of a tracker (a centralized server managing the download)
• An SHA-1 checksum for each trunk, for verifying the content

BitTorrent
• To download a file:

• A client contacts the tracker to obtain a set of peers that can support
the download

• The client contact the peers to download the chunks
• After a chunk is downloaded, it is made available for other peers to

download

BitTorrent
• To download a file:

• A client contacts the tracker to obtain a set of peers that can support
the download

• The client contact the peers to download the chunks
• After a chunk is downloaded, it is made available for other peers to

download

BitTorrent
• Seeder: a peer that has the complete file.

• Initially there is only one seeder
• Later other peers finish the download and become seeders

• For popular file, there are many seeders within the
network, offering high download speed

Visualization

http://mg8.org/processing/bt.html

Categories of P2P Systems
• Three main categories:

• Centralized systems: peer connects to server which coordinates
and manages communication. e.g. SETI@home

Categories of P2P Systems
• Three main categories:

• Centralized systems: peer connects to server which coordinates
and manages communication. e.g. SETI@home

• Brokered systems: peers connect to a server to discover other
peers, but then manage the communication themselves (e.g.
Napster). Also called Brokered P2P.

Categories of P2P Systems
• Three main categories:

• Centralized systems: peer connects to server which coordinates
and manages communication. e.g. SETI@home

• Brokered systems: peers connect to a server to discover other
peers, but then manage the communication themselves (e.g.
Napster). Also called Brokered P2P.

• Decentralized systems: peers run independently with no central
services. Discovery is decentralized and communication takes place
between the peers. e.g. Gnutella.

Categories of P2P Systems
• Three main categories:

• Centralized systems: peer connects to server which coordinates
and manages communication. e.g. SETI@home

• Brokered systems: peers connect to a server to discover other
peers, but then manage the communication themselves (e.g.
Napster). Also called Brokered P2P.

• Decentralized systems: peers run independently with no central
services. Discovery is decentralized and communication takes place
between the peers. e.g. Gnutella. True P2P

Overview
• Examples of P2P networks
• Structured vs unstructured P2P
• Peer-to-peer middleware

Unstructured P2P
• Napster, Gnutella, Bittorrent, etc.

• No overall control of network. Only simple rules for a node to
join the network

• Decentralized/self-organizing, resilient to node failure
• No guarantee of performance
• Risk of generating excessive message traffic to locate objects.

Structured P2P
• Global policy for

• Topology of the network
• Placement of data objects
• Routing/search algorithm for data object allocation

Structured P2P
• Global policy for

• Topology of the network
• Placement of data objects
• Routing/search algorithm for data object allocation

• Efficient: bounded time for location of objects
• At cost of maintaining the underlying structures

Example of Structured P2P: Pastry
• Overlay and routing network that offers efficient location

of nodes and objects
• Overlay: an application-level network on top of another network

Example of Structured P2P: Pastry
• Overlay and routing network that offers efficient location

of nodes and objects
• Overlay: an application-level network on top of another network

• All nodes and objects are assigned 128-bit globally
unique identifiers (GUIDs)

Example of Structured P2P: Pastry
• The GUID space is considered as circular

• 1 is adjacent to 2 and 3
• 0 is adjacent to 1 and 2128-1

SECTION 10.5 OVERLAY CASE STUDIES: PASTRY, TAPESTRY 439

Figure 10.6 illustrates this for a Pastry system with l = 4. (In typical real
installations of Pastry, l = 8.) Based on the definition of leaf sets we can conclude that
at each step M is forwarded to a node that is closer to D than the current node and that
this process will eventually deliver M to the active node closest to D. But such a
routing scheme is clearly very inefficient, requiring ~ N/2l hops to deliver a message
in a network with N nodes.

Stage II: The second part of our explanation describes the full Pastry algorithm and
shows how efficient routing is achieved with the aid of routing tables.

Each Pastry node maintains a tree-structured routing table giving GUIDs and
IP addresses for a set of nodes spread throughout the entire range of 2128 possible
GUID values, with increased density of coverage for GUIDs numerically close to its
own.

Figure 10.7 shows the structure of the routing table for a specific node, and
Figure 10.8 illustrates the actions of the routing algorithm. The routing table is
structured as follows: GUIDs are viewed as hexadecimal values and the table
classifies GUIDs based on their hexadecimal prefixes. The table has as many rows as
there are hexadecimal digits in a GUID, so for the prototype Pastry system that we
are describing, there are 128/4 = 32 rows. Any row n contains 15 entries – one for
each possible value of the nth hexadecimal digit, excluding the value in the local

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 message can be delivered in ~ log16(N ) hops.

0 FFFFF….F (2128-1)

65A1FC

D13DA3

D4213F

D462BA

D471F1

D467C4
D46A1C

Example of Structured P2P: Pastry
• Each node maintains

• A leaf set of nodes whose
GUIDs are numerically
closest to its own

• A routing table consisting of
nodes whose GUIDs share
common prefix with its own

SECTION 10.5 OVERLAY CASE STUDIES: PASTRY, TAPESTRY 439

Stage II: The second part of our explanation describes the full Pastry algorithm and
shows how efficient routing is achieved with the aid of routing tables.

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 message can be delivered in ~ log16(N ) hops.

0 FFFFF….F (2128-1)

65A1FC

D13DA3

D4213F

D462BA

D471F1

D467C4
D46A1C

Example of Structured P2P: Pastry
• In each routing step, the current

node delivers the message to
an active node in the leaf set or
the routing table, with a GUID
numerically closest to its
destination.

SECTION 10.5 OVERLAY CASE STUDIES: PASTRY, TAPESTRY 439

Stage II: The second part of our explanation describes the full Pastry algorithm and
shows how efficient routing is achieved with the aid of routing tables.

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 message can be delivered in ~ log16(N ) hops.

0 FFFFF….F (2128-1)

65A1FC

D13DA3

D4213F

D462BA

D471F1

D467C4
D46A1C

Example of Structured P2P: Pastry
• Guaranteed delivery of message

• Takes O(log N) steps for a network
with N nodes

SECTION 10.5 OVERLAY CASE STUDIES: PASTRY, TAPESTRY 439

Stage II: The second part of our explanation describes the full Pastry algorithm and
shows how efficient routing is achieved with the aid of routing tables.

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 message can be delivered in ~ log16(N ) hops.

0 FFFFF….F (2128-1)

65A1FC

D13DA3

D4213F

D462BA

D471F1

D467C4
D46A1C

Example of Structured P2P: Pastry
• For more technical details:

• Coulouris, G., Dollimore, J., Kindberg, T.
and Blair G., 2005. Distributed Systems:
Concepts and Design. 5th Edition.
Pearson Education. Section 10.5

SECTION 10.5 OVERLAY CASE STUDIES: PASTRY, TAPESTRY 439

Stage II: The second part of our explanation describes the full Pastry algorithm and
shows how efficient routing is achieved with the aid of routing tables.

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 message can be delivered in ~ log16(N ) hops.

0 FFFFF….F (2128-1)

65A1FC

D13DA3

D4213F

D462BA

D471F1

D467C4
D46A1C

Structured Vs Unstructured P2P

Advantage Disadvantage
Structured Guaranteed to locate

objects, with time and
complexity bounds;
relatively low message
overhead

Need to build and maintain
complex overlay structures

Unstructured Self-organizing and
resilient to node failure

No guarantee on locating
objects; prone to excessive
message overhead which can
affect scalability

Overview
• Examples of P2P networks
• Structured vs unstructured P2P
• Peer-to-peer middleware

P2P Middleware
• P2P systems must enable clients to access data

resources quickly and dependably
• A lot of effort required to design such P2P services

P2P Middleware
• P2P systems must enable clients to access data

resources quickly and dependably
• A lot of effort required to design such P2P services

• P2P middleware systems are designed to meet the
need for the automatic placement and subsequent
location of the distributed objects
• Simplifies the construction of P2P services

P2P Middleware
• Functional requirements

• Any node must be able to locate and communicate with any
individual resource which is made available.

• The system must be able to cope with the arbitrary addition or
removal of resources and hosts

• A simple/appropriate programming interface

P2P Middleware
• Non-functional requirements

• Global scalability: must support applications that access millions of
objects on hundreds of thousands of hosts.

• Load balancing: must balance workload across the computers.
• Optimization for local interactions between neighbouring peers:

Should place resources close to the nodes that use them the most.
• Accommodating to highly dynamic host availability: hosts are

free to join or leave at any time.
• Security of data in an environment of heterogeneous trust:

authentication and encryption mechanisms to ensure the integrity
and privacy of information.

• Anonymity and deniability and resistance to censorship: holder
and recipient can maintain anonymity; host can deny responsibility
for holding and supplying data

Example: JXTA
• Open-source P2P protocol specification started by Sun

Microsystems in 2001

• A set of XML messages that allow any device
connected to a network to exchange messages and
collaborate

• Independent of programming languages: Java, C/C++,
C# implementations available

References
• Coulouris, G., Dollimore, J., Kindberg, T. and Blair G.,

2005. Distributed Systems: Concepts and Design. 5th Edition.
Pearson Education. (Chapter 10)

• Buford, J., Yu, H. and Lua, E.K., 2009. P2P Networking and
Applications. Morgan Kaufmann.

• Taylor, I.J. and Harrison, A., 2008. From P2P and Grids to Services
on the Web: Evolving Distributed Communities. Springer Science &
Business Media.

Related Posts