15-744: Computer NetworkingOverviewPeer-to-Peer NetworksThe Lookup ProblemCentralized Lookup (Napster)Flooded Queries (Gnutella)Routed Queries (Chord, etc.)Slide 8Centralized: NapsterSlide 10Flooding: Old GnutellaSlide 12Flooding: Old Gnutella DetailsFlooding: Old Gnutella ExampleFlooding: Gnutella, KazaaSlide 16Routing: Structured ApproachesRouting: ChordAside: HashingRobust hashingConsistent HashConsistent Hash – ExampleRouting: Chord Basic LookupRouting: Finger table - Faster LookupsRouting: Chord SummaryRouting: Chord ExampleSlide 27Slide 28Routing: Chord ExamplesRouting: QueryWhat can DHTs do for us?Slide 32ComparisonDeconstructing DHTsDHT Routing GeometriesTree (Plaxton, Tapestry)Hypercube (CAN)Ring (Chord)Hybrid (Pastry)XOR (Kademlia)Geometry’s Impact on RoutingFRS for Ring GeometryFNS for Ring GeometryFlexibility: at a GlanceGeometry Flexibility Performance?Analysis of Static ResilienceDoes flexibility affect static resilience?Which is more effective, FNS or FRS?Does Geometry affect performance of FNS or FRS?Understanding DHT Routing: ConclusionNext Lecture15-744: Computer NetworkingL-16 P2P2Overview•P2P Lookup Overview•Centralized/Flooded Lookups•Routed Lookups – Chord•Comparison of DHTs3Peer-to-Peer Networks•Typically each member stores/provides access to content•Basically a replication system for files•Always a tradeoff between possible location of files and searching difficulty•Peer-to-peer allow files to be anywhere searching is the challenge•Dynamic member list makes it more difficult•What other systems have similar goals?•Routing, DNS4The Lookup ProblemInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?5Centralized Lookup (Napster)Publisher@ClientLookup(“title”)N6N9N7DBN8N3N2N1SetLoc(“title”, N4)Simple, but O(N) state and a single point of failureKey=“title”Value=MP3 data…N46Flooded Queries (Gnutella)N4Publisher@ClientN6N9N7N8N3N2N1Robust, but worst case O(N) messages per lookupKey=“title”Value=MP3 data…Lookup(“title”)7Routed Queries (Chord, etc.)N4PublisherClientN6N9N7N8N3N2N1Lookup(“title”)Key=“title”Value=MP3 data…8Overview•P2P Lookup Overview•Centralized/Flooded Lookups•Routed Lookups – Chord•Comparison of DHTs9Centralized: Napster•Simple centralized scheme motivated by ability to sell/control•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 peer10Centralized: Napster•Advantages: •Simple•Easy to implement sophisticated search engines on top of the index system•Disadvantages:•Robustness, scalability•Easy to sue!11Flooding: Old Gnutella•On startup, client contacts any servent (server + client) in network•Servent interconnection used to forward control (queries, hits, etc)•Idea: broadcast the request•How to find a file:•Send request to all neighbors•Neighbors recursively forward the request•Eventually a machine that has the file receives the request, and it sends back the answer•Transfers are done with HTTP between peers12Flooding: Old Gnutella•Advantages:•Totally decentralized, highly robust•Disadvantages:•Not scalable; the entire network can be swamped with request (to alleviate this problem, each request has a TTL)•Especially hard on slow clients•At some point broadcast traffic on Gnutella exceeded 56kbps – what happened?•Modem users were effectively cut off!13Flooding: Old Gnutella Details•Basic message header•Unique ID, TTL, Hops•Message types•Ping – probes network for other servents•Pong – response to ping, contains IP addr, # of files, # of Kbytes shared•Query – search criteria + speed requirement of servent•QueryHit – successful response to Query, contains addr + port to transfer from, speed of servent, number of hits, hit results, servent ID•Push – request to servent ID to initiate connection, used to traverse firewalls•Ping, Queries are flooded•QueryHit, Pong, Push reverse path of previous message14Flooding: Old Gnutella ExampleAssume: m1’s neighbors are m2 and m3; m3’s neighbors are m4 and m5;…ABCDEFm1m2m3m4m5m6E?E?E?E?EEE15Flooding: Gnutella, Kazaa•Modifies the Gnutella protocol into two-level hierarchy•Hybrid of Gnutella and Napster•Supernodes•Nodes that have better connection to Internet•Act as temporary indexing servers for other nodes•Help improve the stability of the network•Standard nodes•Connect to supernodes and report list of files•Allows slower nodes to participate•Search•Broadcast (Gnutella-style) search across supernodes•Disadvantages•Kept a centralized registration allowed for law suits 16Overview•P2P Lookup Overview•Centralized/Flooded Lookups•Routed Lookups – Chord•Comparison of DHTs17Routing: Structured Approaches•Goal: make sure that an item (file) identified is always found in a reasonable # of steps•Abstraction: a distributed hash-table (DHT) data structure •insert(id, item);•item = query(id);•Note: item can be anything: a data object, document, file, pointer to a file…•Proposals•CAN (ICIR/Berkeley)•Chord (MIT/Berkeley)•Pastry (Rice)•Tapestry (Berkeley)•…18Routing: Chord•Associate to each node and item a unique id in an uni-dimensional space•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)) steps19Aside: Hashing•Advantages•Let nodes be numbered 1..m•Client uses a good hash function to map a URL to 1..m •Say hash (url) = x, so, client fetches content from node x•No duplication – not being fault tolerant.•One hop access•Any problems?•What happens if a node goes down?•What happens if a node comes back up? •What if different nodes have different views?20Robust hashing•Let 90 documents, node 1..9, node 10 which was dead is alive again•% of documents in the wrong node?•10, 19-20, 28-30, 37-40, 46-50, 55-60, 64-70, 73-80, 82-90•Disruption coefficient = ½•Unacceptable, use consistent hashing – idea behind Akamai!21Consistent Hash•“view” = subset of all hash buckets that are visible•Desired features•Balanced – in any one view, load is equal across buckets•Smoothness – little impact on hash bucket contents when buckets are
View Full Document
Unlocking...