Application Layer Peer-to-Peer Networks Overview
This content explores peer-to-peer (P2P) architecture, emphasizing its decentralized nature where peers directly communicate without an always-on server. It outlines various applications like BitTorrent for file distribution, Skype for VoIP, and gaming scenarios involving matchmaking. It compares the efficiency of P2P networks versus traditional client-server models in terms of file delivery time, considering upload capacities and network dynamics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Application Layer Peer-to-peer UIUC CS438: Communication Networks Summer 2014 Fred Douglas Slides: Fred, Kurose&Ross (sometimes edited)
A Step Back Today, everything is megacorps: Google etc. You
A Step Back What, fundamentally, does the internet do? mobile network global ISP home network regional ISP Internet End host End host institutional network
Pure P2P architecture no always-on server arbitrary end systems directly communicate peers are intermittently connected and change IP addresses examples: File distribution (BitTorrent) Can be pure File distribution (Freenet) VoIP (Skype) Registration + authentication Many games Lobby, matchmaking
Motivation: File distribution Question: how much time to distribute file (size F) from one server to N peers? the traditional way (e.g. from an HTTP server) if peers also upload to each other us: server upload capacity di: peer i download capacity u1 d1 file, size F u2 us d2 server di uN network (with abundant bandwidth) ui dN ui: peer i upload capacity
Client-server vs. P2P: example 3.5 P2P Client-Server Minimum Distribution Time 3 2.5 2 1.5 1 0.5 0 0 5 10 15 20 25 30 35 N
P2P file distribution: BitTorrent file divided into fixed size chunks torrent: group of peers exchanging chunks of a file tracker: tracks peers participating in torrent [list of peers]
P2P file distribution: BitTorrent peer joining torrent: Starts with no chunks; can only download Can pass on any chunk it gets Eventually completes the file, and Becomes a seeder , or Leaves During download 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
BitTorrent: requesting, sending file chunks requesting chunks: at any given time, different peers have different subsets of file chunks periodically, Alice asks each peer for list of chunks that they have Alice requests missing chunks from peers, rarest first sending chunks: tit-for-tat Alice sends chunks to those four peers currently sending her chunks at highest rate other peers are choked by Alice (do not receive chunks from her) re-evaluate top 4 every10 secs every 30 secs: randomly select another peer, starts sending 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 !
Distributed Hash Table (DHT) Distribute (key, value) pairs over millions of peers pairs are evenly distributed over peers Any peer can query database with a key database returns value for the key To resolve query, small number of messages exchanged among peers Each peer only knows about a small number of other peers Robust to peers coming and going (churn)
Assign key-value pairs to peers rule: assign key-value pair to the peer that has the closest ID. convention: closest is the immediate successor of the key. e.g., ID space {0,1,2,3, ,63} suppose 8 peers: 1,12,13,25,32,40,48,60 If key = 51, then assigned to peer 60 If key = 60, then assigned to peer 60 If key = 61, then assigned to peer 1
Silly Strawman Circular DHT each peer only aware of immediate successor and predecessor. (Note: circular DHTs aren t the only way; e.g. 1 Kademlia) 12 60 13 48 25 40 overlay network 32
Resolving a query What is the value associated with key 53 ? 1 value 12 60 13 48 25 O(N) messages on avgerage to resolve query, when there are N peers 40 32
Circular DHT with shortcuts (Chord) 1 value What is the value for key 53 12 60 13 48 25 40 32 each peer keeps track of IP addresses of predecessor, successor, short cuts. reduced from 6 to 3 messages. possible to design shortcuts with O(log N) neighbors, O(log N) messages in query
Chord Me Finger Finger Finger Finger Finger
Peer churn handling peer churn: peers may come and go (churn) each peer knows address of its two successors each peer periodically pings its two successors to check aliveness if immediate successor leaves, choose next successor as new immediate successor 1 3 15 4 12 5 10 8 example: peer 5 abruptly leaves
Peer churn handling peer churn: peers may come and go (churn) each peer knows address of its two successors each peer periodically pings its two successors to check aliveness if immediate successor leaves, choose next successor as new immediate successor 1 3 15 4 12 10 8 example: peer 5 abruptly leaves peer 4 detects peer 5 s departure; makes 8 its immediate successor 4 asks 8 who its immediate successor is; makes 8 s immediate successor its second successor.
BitTorrent as true P2P Traditional BitTorrent Get peers from tracker Fully P2P BitTorrent Get peers from DHT, and direct exchange Magnet link provides file hash Look the hash up in DHT Trackers identified in .torrent file .torrent file hosted on a centralized torrent search engine site Magnet links: just text Search engines, forums, anonymous message boards,
P2P Motivation Revisited Client-server dominates the mainstream. Why? Performance Economies of scale Round trip times (Mass file distribution is a rare exception) So, why peer-to-peer? Avoid single points of failure Technological and social Power to the people Robustness, Survivability OR
Freenet Pure P2P document store Also forums implemented on top Goals Robustness Node failures Censorship Anonymity
Freenet Design Two components: storage, lookup Storage All nodes provide ~10+ GB storage to the network All content is encrypted: not visible to storer Storer never has any idea what it s storing Lookup Key-based routing, like a DHT Lookup path construction: always take the hop closest to the target value Data retrieval and insertion are both lookups Data retrieval
Freenet Lookup First, probe for a path Receive (or send) data once path is built Nodes relaying the data can cache it Data lookup caching means popular items are replicated, unpopular items forgotten
Freenet Topology Original design Start with connections to some bootstrap nodes Randomly add nodes in lookup paths to neighbors Darknet Only connect to nodes whose identity the user knows and trusts Relies on social network dynamics to give the necessary fast mixing / small world property
