15-744: Computer NetworkingNext LectureOverviewPeer-to-Peer Networks: BitTorrentBitTorrent: Simultaneous DownloadingBitTorrent: TrackerBitTorrent: ChunksBitTorrent: Overall ArchitectureSlide 9Slide 10Slide 11Slide 12Slide 13Slide 14BitTorrent: Chunk Request OrderBitTorrent: Rarest Chunk FirstFree-Riding Problem in P2P NetworksBit-Torrent: Preventing Free-RidingBitTyrant: Gaming BitTorrentSlide 20Slide 21Obvious Solutions (1)Obvious Solutions (2)Domain Name System GoalsDNS RecordsDNS Design: Hierarchy DefinitionsDNS Design: Zone DefinitionsDNS Design: Cont.Servers/ResolversDNS: Root Name ServersTypical ResolutionLookup MethodsWorkload and CachingSlide 37Subsequent Lookup ExampleReliabilityReverse Name LookupPrefetchingRoot ZoneNew gTLDsNew RegistrarsDo you trust the TLD operators?Protecting the Root NameserversDNS Hacks: Blackhole ListsDNS ExperienceSlide 51Some Interesting AlternativesSlide 5315-744: Computer NetworkingL-17 P2P and DNSNext Lecture23Overview•P2P•DNSPeer-to-Peer Networks: BitTorrent•BitTorrent history and motivation•2002: B. Cohen debuted BitTorrent•Key motivation: popular content•Popularity exhibits temporal locality (Flash Crowds)•E.g., Slashdot/Digg effect, CNN Web site on 9/11, release of a new movie or game•Focused on efficient fetching, not searching•Distribute same file to many peers•Single publisher, many downloaders•Preventing free-loading4BitTorrent: Simultaneous Downloading•Divide large file into many pieces•Replicate different pieces on different peers•A peer with a complete piece can trade with other peers•Peer can (hopefully) assemble the entire file•Allows simultaneous downloading•Retrieving different parts of the file from different peers at the same time•And uploading parts of the file to peers•Important for very large files5BitTorrent: Tracker•Infrastructure node•Keeps track of peers participating in the torrent•Peers register with the tracker•Peer registers when it arrives•Peer periodically informs tracker it is still there•Tracker selects peers for downloading•Returns a random set of peers•Including their IP addresses•So the new peer knows who to contact for data•Can have “trackerless” system using DHT6BitTorrent: Chunks•Large file divided into smaller pieces•Fixed-sized chunks•Typical chunk size of 256 Kbytes•Allows simultaneous transfers•Downloading chunks from different neighbors•Uploading chunks to other neighbors•Learning what chunks your neighbors have•Periodically asking them for a list•File done when all chunks are downloaded78BitTorrent: Overall ArchitectureWeb page with link to .torrentABCPeer[Leech]Downloader“US”Peer[Seed]Peer[Leech]TrackerWeb Server.torrent9BitTorrent: Overall ArchitectureWeb page with link to .torrentABCPeer[Leech]Downloader“US”Peer[Seed]Peer[Leech]TrackerGet-announceWeb Server10BitTorrent: Overall ArchitectureWeb page with link to .torrentABCPeer[Leech]Downloader“US”Peer[Seed]Peer[Leech]TrackerResponse-peer listWeb Server11BitTorrent: Overall ArchitectureWeb page with link to .torrentABCPeer[Leech]Downloader“US”Peer[Seed]Peer[Leech]TrackerShake-handWeb ServerShake-hand12BitTorrent: Overall ArchitectureWeb page with link to .torrentABCPeer[Leech]Downloader“US”Peer[Seed]Peer[Leech]TrackerpiecespiecesWeb Server13BitTorrent: Overall ArchitectureWeb page with link to .torrentABCPeer[Leech]Downloader“US”Peer[Seed]Peer[Leech]TrackerpiecespiecespiecesWeb Server14BitTorrent: Overall ArchitectureWeb page with link to .torrentABCPeer[Leech]Downloader“US”Peer[Seed]Peer[Leech]TrackerGet-announceResponse-peer listpiecespiecespiecesWeb ServerBitTorrent: Chunk Request Order•Which chunks to request?•Could download in order•Like an HTTP client does•Problem: many peers have the early chunks•Peers have little to share with each other•Limiting the scalability of the system•Problem: eventually nobody has rare chunks•E.g., the chunks need the end of the file•Limiting the ability to complete a download•Solutions: random selection and rarest first15BitTorrent: Rarest Chunk First•Which chunks to request first?•The chunk with the fewest available copies•I.e., the rarest chunk first•Benefits to the peer•Avoid starvation when some peers depart•Benefits to the system•Avoid starvation across all peers wanting a file•Balance load by equalizing # of copies of chunks16Free-Riding Problem in P2P Networks•Vast majority of users are free-riders•Most share no files and answer no queries•Others limit # of connections or upload speed•A few “peers” essentially act as servers•A few individuals contributing to the public good•Making them hubs that basically act as a server•BitTorrent prevent free riding•Allow the fastest peers to download from you•Occasionally let some free loaders download17Bit-Torrent: Preventing Free-Riding•Peer has limited upload bandwidth•And must share it among multiple peers•Prioritizing the upload bandwidth: tit for tat•Favor neighbors that are uploading at highest rate•Rewarding the top few (e.g. four) peers•Measure download bit rates from each neighbor•Reciprocates by sending to the top few peers•Recompute and reallocate every 10 seconds•Optimistic unchoking•Randomly try a new neighbor every 30 seconds•To find a better partner and help new nodes startup18BitTyrant: Gaming BitTorrent•Lots of altruistic contributors•High contributors take a long time to find good partners•Active sets are statically sized•Peer uploads to top N peers at rate 1/N•E.g., if N=4 and peers upload at 15, 12, 10, 9, 8, 3•… then peer uploading at rate 9 gets treated quite well1920BitTyrant: Gaming BitTorrent•Best to be the Nth peer in the list, rather than 1st•Distribution of BW suggests 14KB/s is enough•Dynamically probe for this value•Use saved bandwidth to expand peer set•Choose clients that maximize download/upload ratio•Discussion•Is “progressive tax” so bad?•What if everyone does this?21Overview•P2P•DNS22Obvious Solutions (1)Why not centralize DNS?•Single point of failure•Traffic volume•Distant centralized database•Single point of update•Doesn’t sc ale!23Obvious Solutions (2)Why not use /etc/hosts?•Original Name to Address Mapping•Flat namespace•/etc/hosts •SRI kept main copy•Downloaded regularly•Count of hosts was increasing: machine per domain machine per user•Many more downloads•Many more
View Full Document