11/10/2023
Peer to Peer Networks
P2P Application Examples
• File Sharing Applications (esp.Mp3 music)
– Napster, Gnutella, KaZaA, eDonkey, eMule, KAD, …
• Video downloads, video-on-demand (VoD), large-scale file
distribution (e.g., software updates)
– BitTorrent & variants, …
• Skype (P2P VoIP & video conferencing)
• (real-time/near-real time) video broadcasting, video streaming, …
– pplive, qqlive, …..
• Technology Applications
– Dynamo: Amazon storage substrate
– Akamai Netsession: P2P streaming client
– WebRTC for browser-browser video streaming
1
11/10/2023
Peer to Peer Networks
• Reducing load of servers
• Faster distribution of content
• Scalable content distribution
• Low barrier to deployment
• Organic growth (self-scalable)
• Resilience to attacks and failures
• Resources grow with size of network
• Churn of peers makes network unstable
Locating the Relevant Peers
• Three main approaches
– Central directory (Napster)
– Query flooding (Gnutella)
– Hierarchical overlay (Kazaa, modern Gnutella)
• Design goals
– Scalability
– Simplicity
– Robustness
– Plausible deniability
2
11/10/2023
P2P (Application) Model
• Each user stores a subset of files (content)
• Each user has access (can download) files from all users in
the system
Key Challenges in “pure” peer-to-peer model
• How to locate your peer & find what you want?
• Need some kind of “directory” or “look-up” service
E – centralized
F – distributed, using a hierarchal
D structure
– distributed, using a flat
structure
E?
– distributed, with no structure
(“flooding” based)
– distributed, using a “hybrid”
A
C structured/unstructured
B approach
Other Challenges
Technical:
• Scale: up to hundred of thousands or millions of machines
• Churn: machines can come and go any time
Social, economic & legal:
• Incentive Issues: free-rider problem
– Vast majority of users are free-riders
• most share no files and answer no queries
– A few individuals contributing to the “public good”
• Copyrighted content and piracy
• Trust & security issues
3
11/10/2023
Unstructured P2P Applications
• Napster
– a centralized directory service
– peers directly download from other peers
• Gnutella
– fully distributed directory service
– discover & maintain neighbors, ad hoc topology
– flood & forward queries to neighbors (with bounded hops)
• Skype
– exploit heterogeneity, certain peers as “super nodes”
– two-tier hierarchy: when join, contact a super-node
– smart query flooding
– peer may fetch data from multiple peers at once
• Pros and Cons of each approach?
Napster Architecture:
An Illustration
m5
m6 E (centralized) directory service
F D
E? m1 A
E m2 B m4
m3 C
m4 D
E? m5 E
m5 m6 F
C
A
B m3
m1
m2
4
11/10/2023
Gnutella
• Ad-hoc topology
• Queries are flooded for bounded number of hops
• No guarantees on recall
xyz
xyz
Query: “xyz”
KaZaA: Exploiting Heterogeneity
peer
• Each peer is either a group
leader or assigned to a group
leader (supernode)
supernode
– TCP connection between
peer and its group leader
– TCP connections
between some pairs of
group leaders
• Group leader tracks the content
in all its children ordinary peer
• Q: how to select supernodes? group-leader peer
neighoring relationships
in overlay network
10
5
11/10/2023
Voice-over-IP: Skype
Skype clients (SC)
• proprietary application-
layer protocol (inferred via
reverse engineering)
– encrypted msgs Skype
• P2P components: login server supernode (SN)
clients: Skype peers
connect directly to supernode
overlay
each other for VoIP call network
super nodes (SN):
Skype peers with
special functions
overlay network: among
SNs to locate SCs
login server
P2P voice-over-IP: Skype
Skype client operation:
1. joins Skype network by
contacting SN (IP address
cached) using TCP Skype
2. logs-in (username, login server
password) to centralized
Skype login server
3. obtains IP address for
callee from SN, SN
overlay
or client buddy list
4. initiate call directly to
callee
6
11/10/2023
Skype: peers as relays
• problem: both Alice, Bob
are behind “NATs”
– NAT prevents outside peer
from initiating connection to
insider peer
– inside peer can initiate
connection to outside
relay solution:Alice, Bob
maintain open connection
to their SNs
• Alice signals her SN to connect
to Bob
• Alice’s SN connects to Bob’s
SN
• Bob’s SN connects to Bob over
open connection Bob initially
initiated to his SN
P2P file distribution: BitTorrent
file divided into 256Kb chunks
peers in torrent send/receive file chunks
tracker: tracks peers torrent: group of peers
participating in torrent exchanging chunks of a file
Alice arrives …
… obtains list
of peers from tracker
… and begins exchanging
file chunks with peers in torrent
7
11/10/2023
BitTorrent: Overall Architecture
Web Server Tracker
C
A
Peer
Peer [Seed]
B
[Leech]
Peer
Downloader
[Leech]
P2P file distribution: BitTorrent
peer joining torrent:
• has no chunks, but will accumulate them
over time from other peers
• registers with tracker to get list of peers,
connects to subset of peers
(“neighbors”)
while downloading, peer uploads chunks to other peers
peer may change peers with whom it exchanges chunks
churn: peers may come and go
once peer has entire file, it may (selfishly) leave or (altruistically)
remain in torrent
8
11/10/2023
BitTorrent: requesting, sending file chunks
Requesting chunks: Sending chunks: tit-for-tat
at any given time, different Alice sends chunks to those four
peers have different peers currently sending her chunks
subsets of file chunks at highest rate
periodically, Alice asks • other peers are choked by Alice (do
each peer for list of chunks not receive chunks from her)
that they have • re-evaluate top 4 every10 secs
Alice requests missing every 30 secs: randomly select
chunks from peers, rarest another peer, starts sending
first chunks
• “optimistically unchoke” this peer
• newly chosen peer may join top 4
BitTorrent: tit-for-tat
(1) Alice “optimistically unchokes” Bob
(2) Alice becomes one of Bob’s top-four providers; Bob reciprocates
(3) Bob becomes one of Alice’s top-four providers
higher upload rate: find better
trading partners, get file faster !
9
11/10/2023
Spotify
• Uses BT as basic protocol
– Uses server for first 15s
– Tries to find peers and
download from them
– Only 8.8% of bytes come
from servers
• When 30s left
– Starts searching for next track
– Uses sever with 10s to go if
no peers found
19
BitTorrent & Video Distribution
• Designed for large file (e.g., video) downloads
– esp. for popular content, e.g. flash crowds
• Focused on efficient fetching, not search
– Distribute same file to many peers
– Single publisher, many downloaders
• Divide large file into many pieces
– Replicate different pieces on different peers
– A peer with a complete piece can trade with other peers
• Allows simultaneous downloading
– Retrieving different parts of the file from different peers at
the same time
– Fetch rarest piece first
• Also includes mechanisms for preventing “free riding”
20
10
11/10/2023
Structured P2P Networks
• Introduce a structured logical topology
• Abstraction: a distributed hash table data structure
– put(key, object); get (key)
– key: identifier of an object
– object can be anything: a data item, a node (host), a document/file,
pointer to a file, …
• Design Goals: guarantee on recall
– i.e., ensure that an item (file) identified is always found
– Also scale to hundreds of thousands of (or more) nodes
– handle rapid join/leave and failure of nodes
• Proposals
– Chord, CAN, Kademlia, Pastry, Tapestry, etc
21
Distributed hash table
Distributed application
put(key, data) get (key) data
Distributed hash table
node node …. node
DHT provides the information look up service for P2P applications.
• Nodes uniformly distributed across key space
• Nodes form an overlay network
• Nodes maintain list of neighbors in routing table
• Decoupled from physical network topology
22
11
11/10/2023
Key Ideas (Concepts & Features)
• Keys and node ids map to the same “flat” id space
– node ids are thus also (special) keys!
• Management (organization, storage, lookup, etc) of keys using consistent
hashing
– distributed, maintained by all nodes in the network
• (Logical) distance defined on the id space: structured!
– different DHTs use different distances/structures
• Look-up/Routing Tables (“finger table” in Chord)
– each node typically maintains O(log n) routing entries
– organizing using structured id space: more information about nodes closer-
by; less about nodes farther away
• Bootstrap, handling node joins/leaves or failures
– when node joins: needs to know at least one node in the system
• Robustness/resiliency through redundancy
23
DHT identifiers
• assign integer identifier to each peer in range
[0,2n-1] for some n.
– each identifier represented by n bits.
• require each key to be an integer in same range
• to get integer key, hash original key
– e.g., key = hash(“Led Zeppelin IV”)
– this is why its is referred to as a distributed “hash”
table
12
11/10/2023
Consistent Hashing
• Every key is hashed to generate a number in a circular range
• Every node/replica assigned an ID in the same space
• A key is stored at the first N nodes which succeed the hash of
the key in the circular ring
– Called “preference list” of the key
• First node on the list is the coordinator for the key
– Get/put operations at all nodes managed by coordinator
• For better load balancing, every node is treated as multiple
virtual nodes, assigned many positions on list
– Preference list will contain N distinct physical nodes
Consistent Hashing Properties
• Load balance: all nodes receive roughly the same
number of keys
• For N nodes and K keys, with high probability
– each node holds at most (1+)K/N keys
– (provided that K is large enough compared to N)
13
11/10/2023
Circular DHT (1)
1
3
15
4
12
5
10
8
• each peer only aware of immediate successor
and predecessor.
• “overlay network”
Circular DHT (1)
O(N) messages
on average to resolve 0001 Who’s responsible
query, when there for key 1110 ?
are N peers I am
0011
1111
1110
1110 0100
1110
1100
1110
1110 0101
Define closest 1110
as closest 1010
successor 1000
14
11/10/2023
Circular DHT with finger table
1 Who’s responsible
for key 1110?
3
15
4
12
5
10
8
• each peer keeps track of IP addresses of predecessor,
successor, short cuts.
• reduced from 6 to 2 messages.
• possible to design shortcuts so O(log N) neighbors, O(log N)
messages in query
15
