CS 6390 Advanced Computer NetworksPeer-to-Peer Networks: Unstructured and StructuredPeer-to-Peer Networks: How did it start?ModelMain ChallengeOther ChallengesNapster Technology: Directory ServiceNapsterNapster: ExampleNapster: Limitations of Central DirectoryPeer-to-Peer Networks: GnutellaGnutellaSlide 15Slide 16Gnutella: ProtocolGnutella: Peer JoiningGnutella: Pros and ConsKaZaA: Exploiting HeterogeneitySlide 21KaZaA: Motivation for Super-NodesPeer-to-Peer Networks: BitTorrentBitTorrent: Simultaneous DownloadingBitTorrent ComponentsFree-Riding Problem in P2P NetworksStructured P2P SystemsDistributed Hash Tables (DHTs)DHT Design GoalsChord: A Scalable Peer-to-peer Lookup Service for Internet ApplicationsMotivationCentralized SolutionDistributed Solution (1)Distributed Solution (2)PowerPoint PresentationChord IDsConsistent Hashing [Karger 97]Slide 38An Alternative Idea for LookupsSlide 40Chord-based LookupsSlide 42Joining the ringSlide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Handling FailuresSlide 52CS 6390Advanced Computer NetworksPeer-to-Peer Networking2Peer-to-Peer Networks:Unstructured and Structured What is a peer-to-peer network?Unstructured Peer-to-Peer NetworksNapsterGnutellaKaZaABitTorrentDistributed Hash Tables (DHT) and Structured NetworksChord Many others that we will not discuss… Some slides borrowed from Dr. Zhi Li Zhang3Peer-to-Peer Networks:How did it start?A killer application: NaptserFree music over the InternetKey idea: share the content, storage and bandwidth of individual (home) usersInternet4ModelEach user stores a subset of filesEach user has access (can download) files from all users in the system5Main ChallengeFind where a particular file is storedABCDEFE?6Other ChallengesScale: up to hundred of thousands or millions of machines Dynamicity: machines can come and go any time8Napster Technology: Directory ServiceUser installing the softwareDownload the client programRegister name, password, local directory, etc.Client contacts Napster (via TCP)Provides a list of music files it will share… and Napster’s central server updates the directoryClient searches on a title or performerNapster identifies online clients with the file… and provides IP addressesClient requests the file from the chosen supplierSupplier transmits the file to the clientBoth client and supplier report status to Napster9NapsterAssume a centralized index system that maps files (songs) to machines that are aliveHow to find a file (song)Query the index system return a machine that stores the required fileIdeally this is the closest/least-loaded machineftp the fileAdvantages: Simplicity, easy to implement sophisticated search engines on top of the index systemDisadvantages:Robustness, scalability (?)10Napster: ExampleABCDEFm1m2m3m4m5m6m1 Am2 Bm3 Cm4 Dm5 Em6 FE?m5E?E12Napster: Limitations of Central DirectorySingle point of failurePerformance bottleneckCopyright infringementSo, later P2P systems were more distributed File transfer is decentralized, but locating content is highly centralized13Peer-to-Peer Networks: GnutellaQuery floodingJoin: contact a few nodes to become neighborsPublish: no need!Search: ask neighbors, who ask their neighborsFetch: get file directly from another node14GnutellaDistribute file locationIdea: flood the requestHow to find a file:Send request to all neighborsNeighbors recursively forward the requestEventually a machine that has the file receives the request, and it sends back the answerAdvantages:Totally decentralized, highly robustDisadvantages:Not scalable; the entire network can be swamped with request (to alleviate this problem, each request has a TTL)15GnutellaAd-hoc topologyQueries are flooded for bounded number of hopsNo guarantees on recallQuery: “xyz”xyzxyz16GnutellaFully distributedNo central serverPublic domain protocolMany Gnutella clients implementing protocolOverlay network: graphEdge between peer X and Y if there’s a TCP connectionAll active peers and edges form an overlay networkGiven peer will typically be connected with < 10 overlay neighbors17Gnutella: ProtocolQuery message sent over existing TCPconnectionsPeers forwardQuery messageQueryHit sent over reversepathQueryQueryHitQueryQueryQueryHitQueryQueryQueryHitFile transfer:HTTPScalability:limited scopeflooding18Gnutella: Peer JoiningJoining peer X must find some other peer in Gnutella network: use list of candidate peersX sequentially attempts to make TCP with peers on list until connection setup with YX sends Ping message to Y; Y forwards Ping message. All peers receiving Ping message respond with Pong messageX receives many Pong messages. It can then setup additional TCP connections to some of these responding peers19Gnutella: Pros and ConsAdvantagesFully decentralizedSearch cost distributedProcessing per node permits powerful search semanticsDisadvantagesSearch scope may be quite largeSearch time may be quite longHigh overhead and nodes come and go often20KaZaA: Exploiting HeterogeneityEach peer is either a group leader or assigned to a group leaderTCP connection between peer and its group leaderTCP connections between some pairs of group leadersGroup leader tracks the content in all its childreno r d i n a r y p e e rg r o u p - l e a d e r p e e rn e i g h o r i n g r e l a t i o n s h i p si n o v e r l a y n e t w o r k21KaZaA: Exploiting HeterogeneitySmart query floodingJoin: on start, the client contacts a super-node (and may later become one)Publish: client sends list of files to its super-nodeSearch: send query to super-node, and the super-nodes flood queries among themselvesFetch: get file directly from peer(s); can fetch from multiple peers at once22KaZaA: Motivation for Super-NodesQuery consolidationMany connected nodes may have only a few filesPropagating query to a sub-node may take more time than for the super-node to answer itselfStabilitySuper-node selection favors nodes with high up-timeHow long you’ve been on is a good predictor of how long you’ll be around in the future23Peer-to-Peer Networks: BitTorrentKey motivation: popular contentPopularity exhibits temporal locality (Flash Crowds)E.g., Slashdot effect, CNN Web site on 9/11,
View Full Document
Unlocking...