Slide 1Major issue in real P2P systemsChurn was just one issue!Consequences?Today look at two solutionsConnection to Game TheoryBitTorrentCommon ScenarioIP Multicast?Slide 10Client-ServerClient-ServerIP multicastEnd-host based multicastEnd-host based multicastEnd-host based multicastEnd-host multicast using single treeEnd-host multicast using single treeEnd-host multicast using single treeEnd-host multicast using single treeBitTorrentBitTorrent SwarmHow a node enters a swarm for file “popeye.mp4”How a node enters a swarm for file “popeye.mp4”How a node enters a swarm for file “popeye.mp4”How a node enters a swarm for file “popeye.mp4”Contents of .torrent fileTerminologyPeer-peer transactions: Choosing pieces to requestChoosing pieces to requestChoosing pieces to requestTit-for-tat as incentive to uploadAnti-snubbingWhy BitTorrent took offWhy BitTorrent took offPros and cons of BitTorrentPros and cons of BitTorrentPros and cons of BitTorrent“Trackerless” BitTorrentWhy is (studying) BitTorrent important?Why is (studying) BitTorrent important?Other file-sharing systemsFile-sharing systems…ReferencesGame-Based ApproachesKen BirmanCornell University. CS5410 Fall 2008.Major issue in real P2P systemsSuppose that John Smith signs up to use FileSnarfer and checks all the boxes off: he’s happy to upload files, has ample space, his machine is always turned on.… but over time his disk starts to fill up… and he enables power management, so his machine starts to turn itself off automatically sometimes… and his bandwidth changes when he moves to his room in the coop he’ll live in next yearFrom the perspective of FileSnarfer, John made a lot of promises and isn’t keeping them!Churn was just one issue!With churn, nodes come and go unexpectedly, but at least you can “detect” the failure in most casesWith John’s scenario, nodes exhibitHeterogenous capabilities: some are up for long periods, have lots of resources, and are well connectedOthers may be down a lot, low on stuff, behind firewalls, have slow linksAnd these attributes “churn” too: a single machine may behave very differently over the course of a day, or over its lifetime in the FileSnarfer overlayConsequences?When people try to download from John they may get very poor performanceAnd overlay routes via John could failIn fact this suggests a way to attack the FileSnarfer platform: just sign up lots of people just like John!Like a Sybil attack but even betterThese guys are just eager users and lousy “peers”!Topic this raises: how to do P2P stuff in a world of heterogeneous peers that churn in many dimensionsToday look at two solutionsBitTorrentA famous platform and in fact a very successful commercial product nowCore idea is to create “swarms” in which nodes that currently have more resource tend to bubble to the top and play more active roles and nodes with less resource bubble to the edges and are served last (and least)BAR GossipExtends the BitTorrent concept and also generalizes it. A model of Byzantine, Altruistic and Rational behaviorConnection to Game TheoryThe mathematical theory of games dates back centuries, but the recent version was pioneered by Nash at Princeton in 1940’s (“A beautiful mind”)He imagined games with two or more players, in which each makes moves and tries to win some payoffEach is selfish. Question Nash posed: what strategy works best if you are a game player?His deep idea: If we formalize notions of payoff some games settle into a Nash EquilibriumBitTorrent and BAR Gossip create scenarios in which doing what’s best for you is also best for the system!BitTorrentCS514Vivek Vishnumurthy, TACommon ScenarioMillions want to download the same popular huge files (for free)ISO’sMedia (the real example!)Client-server model failsSingle server failsCan’t afford to deploy enough serversIP Multicast?Recall: IP Multicast not a real option in general settingsNot scalableOnly used in private settingsAlternativesEnd-host based MulticastBitTorrentOther P2P file-sharing schemes (later in lecture)Router“Interested” End-hostSourceRouter“Interested” End-hostSourceClient-ServerRouter“Interested” End-hostSourceClient-ServerOverloaded!Router“Interested” End-hostSourceIP multicastRouter“Interested” End-hostSourceEnd-host based multicastEnd-host based multicast“Single-uploader” “Multiple-uploaders”Lots of nodes want to downloadMake use of their uploading abilities as wellNode that has downloaded (part of) file will then upload it to other nodes.Uploading costs amortized across all nodesEnd-host based multicastAlso called “Application-level Multicast”Many protocols proposed early this decadeYoid (2000), Narada (2000), Overcast (2000), ALMI (2001)All use single treesProblem with single trees?End-host multicast using single treeSourceEnd-host multicast using single treeSourceEnd-host multicast using single treeSourceSlow data transferEnd-host multicast using single treeTree is “push-based” – node receives data, pushes data to childrenFailure of “interior”-node affects downloads in entire subtree rooted at nodeSlow interior node similarly affects entire subtreeAlso, leaf-nodes don’t do any sending!Though later multi-tree / multi-path protocols (Chunkyspread (2006), Chainsaw (2005), Bullet (2003)) mitigate some of these issuesBitTorrentWritten by Bram Cohen (in Python) in 2001“Pull-based” “swarming” approachEach file split into smaller piecesNodes request desired pieces from neighborsAs opposed to parents pushing data that they receivePieces not downloaded in sequential orderPrevious multicast schemes aimed to support “streaming”; BitTorrent does notEncourages contribution by all nodesBitTorrent SwarmSwarmSet of peers all downloading the same fileOrganized as a random meshEach node knows list of pieces downloaded by neighborsNode requests pieces it does not own from neighborsExact method explained laterHow a node enters a swarm for file “popeye.mp4”File popeye.mp4.torrent hosted at a (well-known) webserverThe .torrent has address of tracker for fileThe tracker, which runs on a webserver as well, keeps track of all peers downloading fileHow a node enters a swarm for file “popeye.mp4”File
View Full Document