Peer-to-Peer Protocols and SystemsP2P - OutlineProblem: ScalabilitySlide 4Solution:Three Classes of P2P Systems1) P2P File-sharing SystemsSlide 8File searchingSlide 10File-sharing: FrameworkP2P File-sharing Systems(old) Napster: History(old) Napster: OverviewNapster: PublishNapster: SearchNapster: DiscussionSlide 18Gnutella: HistoryGnutella: OverviewGnutella: SearchGnutella: DiscussionSlide 23KaZaA: HistoryKaZaA: OverviewKaZaA: Network DesignKaZaA: File InsertKaZaA: File SearchKaZaA: FetchingKaZaA: DiscussionStability and SuperpeersSlide 32Distributed Hash TablesDHT: OverviewDHT: Overview (continued)DHT: Example – ChordDHT: Consistent HashingDHT: Chord Basic LookupDHT: Chord “Finger Table”DHT: Chord JoinSlide 41Slide 42Slide 43DHT: Chord RoutingDHT: Chord SummaryDHT: Discussion1) P2P File-sharing: Summary2) P2P File Distribution Systems (i.e. BitTorrent)BitTorrent: HistoryBitTorrent: OverviewBitTorrent: Publish/JoinBitTorrent: FetchBitTorrent: Summary3) P2P Streaming Systems (i.e. Overlay Multicast a.k.a. End System Multicast)Live Broadcast: Pre-InternetLive Internet Broadcast: Pre-P2PSolution...?Solution: IP Multicast?Solution (again!):Internet broadcasting StructureEnd System Multicast (ESM) (a.k.a Overlay Multicast)Example ESM Tree http://esm.cs.cmu.eduSingle Overlay Distribution TreeSingle Overlay Distribution TreeMultiple Overlay Distribution TreesSlide 66Slide 67Multiple Overlay Distribution TreesMy Research with ESMESM + LAN MulticastP2P Systems: SummaryExtra Slides (From previous P2P lectures)KaZaA: Usage PatternsKaZaA: Usage Patterns (2)KaZaA: Usage Patterns (3)Freenet: HistoryFreenet: OverviewFreenet: Routing TablesFreenet: RoutingFreenet: Routing PropertiesFreenet: Anonymity & SecurityFreenet: DiscussionPeer-to-PeerProtocols and SystemsTA: David Murray15-441 Spring 20064/19/20062P2P - Outline•What is P2P?•P2P System Types–1) File-sharing–2) File distribution–3) Streaming•Uses & Challenges3Problem: Scalability•Hundreds of clients => 1 server–OK•Thousands of clients => 1 server–Maybe OK•Millions/billions of clients => 1 server–What happens?...45Solution:Distribute the cost among the end users6Three Classes of P2P Systems•1) File-sharing–(old) Napster (centralized)–Gnutella (flooding)–KaZaA (intelligent flooding)–DHTs/Chord (structured overlay routing)•2) File distribution–BitTorrent•3) Streaming–End System Multicast (a.k.a. Overlay Multicast)1) P2P File-sharing Systems81) P2P File-sharing Systems•Centralized Database–(old) Napster•Query Flooding–Gnutella•Intelligent Query Flooding–KaZaA•Structured Overlay Routing–Distributed Hash Tables9File searchingInternetN1N2N3N6N5N4PublisherKey=“title”Value=MP3 data…ClientLookup(“title”)?10File searching•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?)11File-sharing: Framework•Common Primitives:–Join: how do I begin participating?–Publish: how do I advertise my file?–Search: how do I find a file?–Fetch: how do I retrieve a file?12P2P File-sharing Systems•Centralized Database–(old) Napster•Query Flooding–Gnutella•Intelligent Query Flooding–KaZaA•Structured Overlay Routing–Distributed Hash Tables13(old) Napster: History•1999: Sean Fanning launches Napster•Peaked at 1.5 million simultaneous users•Jul 2001: Napster shuts down•[2003: Napster’s name reused for an online music service (no relation)]14(old) Napster: Overview•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 peer15Napster: PublishI have lots of TV show theme song files!Publishinsert(XenaThemeSong.mp3, 123.2.21.23)Insert(HerculesThemeSong.mp3, 123.2.21.23)...123.2.21.2316Napster: Search“Where is the XenaTheme song?”Replysearch(Xena)FetchQuery17Napster: 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 failure18P2P File-sharing Systems•Centralized Database–(old) Napster•Query Flooding–Gnutella•Intelligent Query Flooding–KaZaA•Structured Overlay Routing–Distributed Hash Tables19Gnutella: 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”20Gnutella: 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 peer21“I have XenaEpisode1.mpg”“I haveXenaEpisode1.mpg”Gnutella: Search“Where isXenaEpisode1.mpg?”QueryReply22Gnutella: 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 later23P2P File-sharing Systems•Centralized Database–(old) Napster•Query Flooding–Gnutella•Intelligent Query Flooding–KaZaA•Structured Overlay Routing–Distributed Hash Tables24KaZaA: 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 it25KaZaA: 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, supernodes flood query amongst themselves.–Fetch: get the file directly from peer(s); can fetch simultaneously from multiple peers26KaZaA: Network Design“Super Nodes”27KaZaA: File InsertI have lots of files!Publishinsert(Xena.mp3, 123.2.21.23)Insert(Hercules.mp3,123.2.21.23)123.2.21.2328KaZaA: File SearchWhere is
View Full Document