Improving ISP Locality in BitTorrent Traffic via Biased Neighbor Selection.ppt
Improving ISP Locality in BitTorrent Traffic via Biased Neighbor Selection,P2P and ISPs:Not Friends,P2P applications are notoriously difficult to“traffic engineer”ISPs:different links have different monetary costsP2P applications:Peers are all equalChoices made based on measured performanceNo regards for underlying ISP topology or preferences,P2P and ISPs:Cant Be Foes,ISPs:need P2P for customersP2P:need ISPs for bandwidthCurrent state of affairs:a clumsy co-existenceISPs“throttle”P2P traffic along high-cost linksUsers suffer,Can They Be Partners?,ISPs inform P2P applications of its preferencesP2P applications schedule traffic in ways that benefit both Users and ISPs This paper gives an example for BitTorrent,Outline,Review of BitTorrent Biased Neighbor Selection:Design and ImplementationsEvaluationsComparison with Alternatives,BitTorrent File Sharing Network,Goal:replicate K chunks of data among N nodesForm neighbor connection graphNeighbors exchange data,BitTorrent:Neighbor Selection,Trackerfile.torrent,1,Seed,Whole file,A,5,2,3,4,BitTorrent:Piece Replication,Trackerfile.torrent,1,Seed,Whole file,A,3,2,BitTorrent:Piece Replication Algorithms,“Tit-for-tat”(choking/unchoking):Each peer only uploads to 7 other peers at a time6 of these are chosen based on amount of data received from the neighbor in the last 20 secondsThe last one is chosen randomly,with a 75%bias toward new comers(Local)Rarest-first replication:When peer 3 unchokes peer A,A selects which piece to download,Performance of BitTorrent,Conclusion from modeling studies:BitTorrent is nearly optimal in idealized,homogeneous networksDemonstrated by simulation studiesConfirmed by theoretical modeling studiesIntuition:in a random graph,Prob(Peer As content is a subset of Peer Bs)50%,Random Neighbor Selection,Existing studies all assume random neighbor selectionBitTorrent no longer optimal if nodes in the same ISP only connect to each otherRandom neighbor selection high cross-ISP trafficQ:Can we modify the neighbor selection scheme without affecting performance?,Biased Neighbor Selection,Idea:of N neighbors,choose N-k from peers in the same ISP,and choose k randomly from peers outside the ISP,ISP,Implementing Biased Neighbor Selection,By TrackerNeed ISP affiliations of peersPeer to AS mapsPublic IP address ranges from ISPsSpecial“X-”HTTP headerBy traffic shaping devicesIntercept“peer tracker”messages and manipulate responsesNo need to change tracker or client,Evaluation Methodology,Event-driven simulatorUse actual client and tracker codes as much as possibleCalculate bandwidth contention,assume perfect fair-share from TCPNetwork settings14 ISPs,each with 50 peers,100Kb/s upload,1Mb/s downloadSeed node,400Kb/s uploadOptional“university”nodes(1Mb/s upload)Optional ISP bottleneck to other ISPs,Limitation of Throttling,Throttling:Cross-ISP Traffic,Redundancy:Average#of times a data chunk enters the ISP,Biased Neighbor Selection:Download Times,Biased Neighbor Selection:Cross-ISP Traffic,Importance of Rarest-First Replication,Random piece replication performs badlyIncreases download time by 84%-150%Increase traffic redundancy from 3 to 14Biased neighbors+Rarest-First More uniform progress of peers,Biased Neighbor Selection:Single-ISP Deployment,Presence of External High-Bandwidth Peers,Biased neighbor selection alone:Average download time same as regular BitTorrentCross-ISP traffic increases as#of“university”peers increaseResult of tit-for-tatBiased neighbor selection+Throttling:Download time only increases by 12%Most neighbors do not cross the bottleneckTraffic redundancy(i.e.cross-ISP traffic)same as the scenario without“university”peers,Comparison with Alternatives,Gateway peer:only one peer connects to the peers outside the ISPGateway peer must have high bandwidthIt is the“seed”for this ISPEnds up benefiting peers in other ISPsCaching:Can be combined with biased neighbor selectionBiased neighbor selection reduces the bandwidth needed from the cache by an order of magnitude,Summary,By choosing neighbors well,BitTorrent can achieve high peer performance without increasing ISP costBiased neighbor selection:choose initial set of neighbors wellCan be combined with throttling and caching P2P and ISPs can collaborate!,Related Work,Many modeling studies of BitTorrentSimulation studiesMeasurements of real torrents,Future Work,Implementation of tracker-side changes and experimentsTheoretical modeling of biased neighbor selectionDynamic biased neighbor selection for“global congestion avoidance”,
