1Peer-to-Peer15-4412Outline• 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, …23Wither p2p?• Harness lots of spare capacity– 1 Big Fast Server: 1Gbit/s, $10k/month++– 2,000 cable modems: 1Gbit/s, $ ??– 1M end-hosts: Uh, wow.• Build self-managing systems / Deal withhuge scale– Same techniques attractive for both companies /servers / p2p• E.g., Akamai’s 14,000 nodes• Google’s 100,000+ nodes4P2p file-sharing• Quickly grown in popularity– Dozens or hundreds of file sharing applications– 35 million American adults use P2P networks --29% of all Internet users in US!– Audio/Video transfer now dominates traffic on theInternet35What’s out there?DHTseDonkey2000KaZaA(bytes,notchunks)BitTorrentChunkBasedFreenetGnutellaNapsterWholeFileRouteSuper-nodefloodFloodCentral6SearchingInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?47Searching 2• Needles vs. Haystacks– Searching for top 40, or an obscure punktrack from 1981 that nobody’s heard of?• Search expressiveness– Whole word? Regular expressions? Filenames? Attributes? Whole-text search?• (e.g., p2p gnutella or p2p google?)8Framework• 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?59Next Topic...• Centralized Database– Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Swarming– BitTorrent• Unstructured Overlay Routing– Freenet• Structured Overlay Routing– Distributed Hash Tables10Napster: History• 1999: Sean Fanning launches Napster• Peaked at 1.5 million simultaneoususers• Jul 2001: Napster shuts down611Napster: Overiew• Centralized Database:– Join: on startup, client contacts centralserver– Publish: reports list of files to centralserver– Search: query the server => returnsomeone that stores the requested file– Fetch: get the file directly from peer12Napster: PublishI have X, Y, and Z!Publishinsert(X, 123.2.21.23)...123.2.21.23713Napster: SearchWhere is file A?Query Replysearch(A)-->123.2.0.18Fetch123.2.0.1814Napster: Discussion• Pros:– Simple– Search scope is O(1)– Controllable (pro or con?)• Cons:– Server maintains O(N) State– Server does all processing– Single point of failure815Next Topic...• Centralized Database– Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Swarming– BitTorrent• Unstructured Overlay Routing– Freenet• Structured Overlay Routing– Distributed Hash Tables16Gnutella: History• In 2000, J. Frankel and T. Pepper fromNullsoft released Gnutella• Soon many other clients: Bearshare,Morpheus, LimeWire, etc.• In 2001, many protocol enhancementsincluding “ultrapeers”917Gnutella: Overview• Query Flooding:– Join: on startup, client contacts a fewother nodes; these become its “neighbors”– Publish: no need– Search: ask neighbors, who ask theirneighbors, and so on... when/if found,reply to sender.• TTL limits propagation– Fetch: get the file directly from peer18I have file A.I have file A.Gnutella: SearchWhere is file A?QueryReply1019Gnutella: Discussion• Pros:– Fully de-centralized– Search cost distributed– Processing @ each node permits powerful searchsemantics• 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 later20KaZaA: History• In 2001, KaZaA created by Dutch companyKazaa BV• Single network called FastTrack used byother clients as well: Morpheus, giFT, etc.• Eventually protocol changed so other clientscould no longer talk to it• Most popular file sharing network today with>10 million users (number varies)1121KaZaA: Overview• “Smart” Query 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, supernodesflood query amongst themselves.– Fetch: get the file directly from peer(s); can fetchsimultaneously from multiple peers22KaZaA: Network Design“Super Nodes”1223KaZaA: File InsertI have X!Publishinsert(X, 123.2.21.23)...123.2.21.2324KaZaA: File SearchWhere is file A?Querysearch(A)-->123.2.0.18search(A)-->123.2.22.50Replies123.2.0.18123.2.22.501325KaZaA: Fetching• More than one node may have requested file...• How to tell?– Must be able to distinguish identical files– Not necessarily same filename– Same filename not necessarily same file...• Use Hash of file– KaZaA uses UUHash: fast, but not secure– Alternatives: MD5, SHA-1• How to fetch?– Get bytes [0..1000] from A, [1001...2000] from B– Alternative: Erasure Codes26KaZaA: Discussion• Pros:– Tries to take into account node heterogeneity:• Bandwidth• Host Computational Resources• Host Availability (?)– Rumored to take into account network locality• Cons:– Mechanisms easy to circumvent– Still no real guarantees on search scope or search time• Similar behavior to gnutella, but better.1427Stability 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/wthan answering it yourself– Caching effect• Requires network stability• Superpeer selection is time-based– How long you’ve been on is a good predictor ofhow long you’ll be around.28BitTorrent: History• In 2002, B. Cohen debuted BitTorrent• Key Motivation:– Popularity exhibits temporal locality (Flash Crowds)– E.g., Slashdot effect, CNN on 9/11, new movie/gamerelease• Focused on Efficient Fetching, not Searching:– Distribute the same file to all peers– Single publisher, multiple downloaders• Has some “real” publishers:– Blizzard Entertainment using it to distribute the beta of theirnew game1529BitTorrent: Overview• Swarming:– Join: contact centralized “tracker” server, get alist of peers.– Publish: Run a tracker server.– Search:
View Full Document
Unlocking...