Peer-to-PeerScaling ProblemP2P SystemWhy p2p?OutlineP2p file-sharingWhat’s out there?SearchingSearching 2FrameworkNext Topic...Napster: HistoryNapster: OveriewNapster: PublishNapster: SearchNapster: DiscussionNext Topic...Gnutella: HistoryGnutella: OverviewGnutella: SearchGnutella: DiscussionKaZaA: HistoryKaZaA: OverviewKaZaA: Network DesignKaZaA: File InsertKaZaA: File SearchKaZaA: FetchingKaZaA: DiscussionStability and SuperpeersBitTorrent: HistoryBitTorrent: OverviewBitTorrent: Publish/JoinBitTorrent: FetchBitTorrent: Sharing StrategyBitTorrent: SummaryNext Topic...Distributed Hash TablesDHT: OverviewDHT: Overview (2)DHT: Example - ChordDHT: Consistent HashingDHT: Chord Basic LookupDHT: Chord “Finger Table”DHT: Chord JoinDHT: Chord JoinDHT: Chord JoinDHT: Chord JoinDHT: Chord RoutingDHT: Chord SummaryDHT: DiscussionWhen are p2p / DHTs useful?A Peer-to-peer Google?Writable, persistent p2pP2P: SummaryExtra SlidesKaZaA: Usage PatternsKaZaA: Usage Patterns (2)KaZaA: Usage Patterns (3)Freenet: HistoryFreenet: OverviewFreenet: Routing TablesFreenet: RoutingFreenet: Routing PropertiesFreenet: Anonymity & SecurityFreenet: DiscussionPeer-to-Peer15-4412Scaling Problem• Millions of clients ⇒ server and network meltdown3P2P System• Leverage the resources of client machines (peers)– Computation, storage, bandwidth4Why 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 with huge scale– Same techniques attractive for both companies / servers / p2p• E.g., Akamai’s 14,000 nodes• Google’s 100,000+ nodes5Outline• 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, …6P2p 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 the Internet7What’s out there?Central Flood Super-node floodRouteWholeFileNapster Gnutella FreenetChunkBasedBitTorrent KaZaA(bytes, not chunks)DHTseDonkey20008SearchingInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?9Searching 2• 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?)10Framework• 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?11Next Topic...• Centralized Database– Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Swarming– BitTorrent• Unstructured Overlay Routing– Freenet• Structured Overlay Routing– Distributed Hash Tables12Napster: History• 1999: Sean Fanning launches Napster• Peaked at 1.5 million simultaneous users• Jul 2001: Napster shuts down13Napster: Overiew• Centralized Database:– Join: on startup, client contacts central server– Publish: reports list of files to central server– Search: query the server => return someone that stores the requested file– Fetch: get the file directly from peer14Napster: PublishI have X, Y, and Z!Publishinsert(X,123.2.21.23)...123.2.21.2315Napster: SearchWhere is file A?Query Replysearch(A)-->123.2.0.18Fetch123.2.0.1816Napster: 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 failure17Next Topic...• Centralized Database– Napster• Query Flooding– Gnutella• Intelligent Query Flooding– KaZaA• Swarming– BitTorrent• Unstructured Overlay Routing– Freenet• Structured Overlay Routing– Distributed Hash Tables18Gnutella: History• In 2000, J. Frankel and T. Pepper from Nullsoft released Gnutella• Soon many other clients: Bearshare, Morpheus, LimeWire, etc.• In 2001, many protocol enhancements including “ultrapeers”19Gnutella: Overview• Query Flooding:– Join: on startup, client contacts a few other nodes; these become its “neighbors”– Publish: no need– Search: ask neighbors, who ask their neighbors, and so on... when/if found, reply to sender.• TTL limits propagation– Fetch: get the file directly from peer20I have file A.I have file A.Gnutella: SearchWhere is file A?QueryReply21Gnutella: 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 later22KaZaA: History• In 2001, KaZaA created by Dutch company Kazaa BV• Single network called FastTrack used by other clients as well: Morpheus, giFT, etc.• Eventually protocol changed so other clients could no longer talk to it• Most popular file sharing network today with >10 million users (number varies)23KaZaA: 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 fetch simultaneously from multiple peers24KaZaA: Network Design“Super Nodes”25KaZaA: File InsertI have X!Publishinsert(X,123.2.21.23)...123.2.21.2326KaZaA: File SearchWhere is file A?Querysearch(A)-->123.2.0.18search(A)-->123.2.22.50Replies123.2.0.18123.2.22.5027KaZaA: 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–
View Full Document
Unlocking...