Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Peer-to-Peer15-4412Scaling Problem•Millions of clients ⇒ server and network meltdown3P2P System•Leverage the resources of client machines (peers)–Computation, storage, bandwidth4Why p2p?•Scaling: Create system whose capacity grows with # of clients - automatically!•Self-managing–This aspect attractive for corporate/datacenter needs–e.g., Amazon’s 100,000-ish machines, google’s 300k+•Harness lots of “spare” capacity at end-hosts•Eliminate centralization–Robust to failures, etc.–Robust to censorship, politics & legislation??5Today’s Goal•p2p is hot.•There are tons and tons of instances•But that’s not the point•Identify fundamental techniques useful in p2p settings•Understand the challenges•Look at the (current!) boundaries of where 2p is particularly useful56Outline•p2p file sharing techniques–Downloading: Whole-file vs. chunks–Searching•Centralized index (Napster, etc.)•Flooding (Gnutella, etc.)•Smarter flooding (KaZaA, …)•Routing (Freenet, etc.)•Uses of p2p - what works well, what doesn’t?–servers vs. arbitrary nodes–Hard state (backups!) vs soft-state (caches)•Challenges–Fairness, freeloading, security, …7Searching & FetchingHuman: “I want to watch that great 80s cult classic ‘Better Off Dead’”1.Search: “better off dead” -> better_off_dead.movor -> 0x539fba83ajdeadbeef2.Locate sources of better_off_dead.mov3.Download the file from them78SearchingInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?9Search Approaches•Centralized•Flooding•A hybrid: Flooding between “Supernodes”•Structured910Different types of searches•Needles vs. Haystacks–Searching for top 40, or an obscure punk track from 1981 that nobody’s heard of?•Search expressiveness–Whole word? Regular expressions? File names? Attributes? Whole-text search?•(e.g., p2p gnutella or p2p google?)11Framework•Common Primitives:–Join: how to I begin participating?–Publish: how do I advertise my file?–Search: how to I find a file?–Fetch: how to I retrieve a file?12Centralized•Centralized Database:–Join: on startup, client contacts central server–Publish: reports list of files to central server–Search: query the server => return node(s) that store the requested file13Napster Example: PublishI have X, Y, and Z!Publishinsert(X, 123.2.21.23)...123.2.21.2314Napster: SearchWhere is file A?Query Replysearch(A)-->123.2.0.18Fetch123.2.0.1815Napster: Discussion•Pros:–Simple–Search scope is O(1) for even complex searches (one index, etc.)–Controllable (pro or con?)•Cons:–Server maintains O(N) State–Server does all processing–Single point of failure•Technical failures + legal (napster shut down 2001)16Query Flooding•Join: Must join a flooding network–Usually, establish peering with a few existing nodes•Publish: no need, just reply•Search: ask neighbors, who ask their neighbors, and so on... when/if found, reply to sender.–TTL limits propagation17I have file A.I have file A.Example: GnutellaWhere is file A?QueryReply18Flooding: Discussion•Pros:–Fully de-centralized–Search cost distributed–Processing @ each node permits powerful search semantics•Cons:–Search scope is O(N)–Search time is O(???)–Nodes leave often, network unstable•TTL-limited search works well for haystacks.–For scalability, does NOT search every node. May have to re-issue query later19Supernode Flooding•Join: on startup, client contacts a “supernode” ... may at some point become one itself•Publish: send list of files to supernode•Search: send query to supernode, supernodes flood query amongst themselves.–Supernode network just like prior flooding net20Supernode Network Design“Super Nodes”21Supernode: File InsertI have X!Publishinsert(X, 123.2.21.23)...123.2.21.2322Supernode: File SearchWhere is file A?Querysearch(A)-->123.2.0.18search(A)-->123.2.22.50Replies123.2.0.18123.2.22.5023Supernode: Which nodes?•Often, bias towards nodes with good:–Bandwidth–Computational Resources–Availability!24Stability and Superpeers•Why superpeers?–Query consolidation•Many connected nodes may have only a few files•Propagating a query to a sub-node would take more b/w than answering it yourself–Caching effect•Requires network stability•Superpeer selection is time-based–How long you’ve been on is a good predictor of how long you’ll be around.25Superpeer results•Basically, “just better” than flood to all•Gets an order of magnitude or two better scaling•But still fundamentally: o(search) * o(per-node storage) = O(N)–central: O(1) search, O(N) storage–flood: O(N) search, O(1) storage–Superpeer: can trade between2526Structured Search:Distributed Hash Tables•Academic answer to p2p•Goals–Guatanteed lookup success–Provable bounds on search time–Provable scalability•Makes some things harder–Fuzzy queries / full-text search / etc.•Read-write, not read-only•Hot Topic in networking since introduction in ~2000/200127Searching Wrap-UpType O(search) storage Fuzzy?Central O(1) O(N) YesFlood ~O(N) O(1) YesSuper < O(N) > O(1) YesStructured O(log N) O(log N) not really28DHT: Overview•Abstraction: a distributed “hash-table” (DHT) data structure:–put(id, item);–item = get(id);•Implementation: nodes in system form a distributed data structure–Can be Ring, Tree, Hypercube, Skip List, Butterfly Network, ...29DHT: Overview (2)•Structured Overlay Routing:–Join: On startup, contact a “bootstrap” node and integrate yourself into the distributed data structure; get a node id–Publish: Route publication for file id toward a close node id along the data structure–Search: Route a query for file id toward a close node id. Data structure guarantees that query will meet the publication.–Important difference: get(key) is for an exact match on key!•search(“spars”) will not find file(“briney
View Full Document
Unlocking...