1CSE 123bCSE 123bCommunications SoftwareCommunications SoftwareSpring 2002Spring 2002Lecture 14: PeerLecture 14: Peer--toto--Peer NetworksPeer NetworksStefan SavageStefan SavageSome slides courtesy Ion Stoica and Srini SeshanMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 2PeerPeer--toto--peer systemspeer systemsz Examples◆ Napster, Gnutella, Freenet, KaZaA, CFS, etc.z Definition?◆ No distinction between client and server◆ All nodes are potential users of a service AND potential providers of a serviceMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 3ClassificationsClassificationsz What resource is shared?◆ CPU: SETI@Home◆ Storage & BW: most of the restz How are resources located?◆ Centralized systems» Napster, Seti@Home◆ Distributed systems» Unstructured: e.g. Gnutella» Structured/routed: e.g. CFS/Chord, Freenetz Search vs LookupMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 4ChallengesChallengesz Dynamic availabilityz Scale z Heterogeneityz Securityz Fairnessz Performancez ManagementMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 5The Lookup ProblemThe Lookup ProblemInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 6Centralized Lookup (Napster)Centralized Lookup (Napster)Publisher@ClientLookup(“title”)N6N9N7DBN8N3N2N1SetLoc(“title”, N4)Simple, but O(N) state and a single point of failureKey=“title”Value=MP3 data…N42May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 7NapsterNapsterz Simple centralized scheme Æ motivated by ability to sell/controlz How to find a file:◆ On startup, client contacts central server and reports list of files◆ Query the index system Æ return a machine that stores the required file» Ideally this is the closest/least-loaded machine◆ Fetch the file directly from peerz Advantages: ◆ Simplicity, easy to implement sophisticated search engines on top of the index systemz Disadvantages:◆ Robustness, scalabilityMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 8Flooded Queries (Gnutella)Flooded Queries (Gnutella)N4Publisher@ClientN6N9N7N8N3N2N1Robust, but worst case O(N) messages per lookupKey=“title”Value=MP3 data…Lookup(“title”)May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 9GnutellaGnutellaz Distributed location informationz Idea: multicast the requestz How to find a file:◆ Send request to all neighbors◆ Neighbors recursively multicast the request◆ Eventually a machine that has the file receives the request, and it sends back the answerz Advantages:◆ Totally decentralized, highly robustz Disadvantages:◆ Not scalable; the entire network can be swamped with request (to alleviate this problem, each request has a TTL) May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 10Gnutella DetailsGnutella Detailsz Basic message header◆ Unique ID, TTL, Hopsz Message types◆ Ping – probes network for other nodes◆ Pong – response to ping, contains IP addr, # of files, # of Kbytes shared◆ Query – search criteria + speed requirement of node◆ QueryHit – successful response to Query, contains addr + port to transfer from, speed of node, number of hits, hit results, node ID◆ Push – request to node ID to initiate connection, used to traverse firewallsz Ping, Queries are floodedz QueryHit, Pong, Push reverse path of previous messageMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 11Routed Queries Routed Queries ((FreenetFreenet, Chord, etc), Chord, etc)N4PublisherClientN6N9N7N8N3N2N1Lookup(“title”)Key=“title”Value=MP3 data…May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 12Example: Example: FreenetFreenetz Architecture:◆ Each file is identified by a unique identifier◆ Each machine stores a set of files, and maintains a “routing table” to route the individual requestsz Additional goals to file location:◆ Provide publisher anonymity, security ◆ Resistant to attacks – a third party shouldn’t be able to deny the access to a particular file (data item, object), even if it compromises a large fraction of machines3May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 13FreenetFreenetQueryQueryz User requests key XYZ – not in local cachez Looks up nearest key in routing table and forwards to corresponding nodez If request reaches node with data, it forwards data back to upstream requestor◆ Requestor adds file to cache, adds entry in routing table◆ Any node forwarding reply may change the source of the reply → helps anonymityz If data not found, failure is reported backMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 14Data StructureData Structurez Each node maintains a common stack◆ id – file identifier◆ next_hop – another node that store the file id◆ file – file identified by id being stored on the local node z Forwarding: ◆ Each message contains the file id it is referring to◆ If file id stored locally, then stop» Forwards data back to upstream requestor» Requestor adds file to cache, adds entry in routing table◆ If not, search for the “closest” id in the stack, and forward the message to the corresponding next_hopid next_hop file……May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 15Query ExampleQuery ExampleNote: doesn’t show file caching on the reverse path 4 n1 f412 n2 f125 n39 n3 f93 n1 f314 n4 f145 n314 n5 f1413 n2 f133 n6n1n2n3n44 n1 f410 n5 f108 n6n5query(10)12344’5May 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 16FreenetFreenetSummarySummaryz Advantages◆ Totally decentralize architecture Æ robust and scalablez Disadvantages◆ Does not always guarantee that a file is found, even if the file is in the networkMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 17Example: ChordExample: Chordz Associate to each node and item a unique id in a uni-dimensional space z Goals◆ Scales to hundreds of thousands of nodes◆ Handles rapid arrival and failure of nodesz Properties ◆ Routing table size O(log(N)) , where N is the total number of nodes◆ Guarantees that a file is found in O(log(N)) stepsMay 31, 2002 CSE 123b – Lecture 14 – Peer-to-Peer Networks 18Data StructureData Structurez Assume identifier space is 0..2mz Each node maintains◆ Finger table» Entry i in the finger table of n is the first