problem definition: sharing of large (100s of MB) files content often illegal to redistribute (e.g., movies, commercial software, ...) want fast downloads for many concurrent users drawbacks of centralized server: vulnerable to government order to shut down concentration of storage at one node concentration of upload bandwidth at one node peer-to-peer approach (e.g., Gnutella): store one or more copies of file at many clients allow a clients to download from any other client that has the file advantages: no central server to be shut down by government storage aggregated across many nodes upload bandwidth aggregated across many nodes (if many have the data in question!) challenges: finding which peers have data (e.g., Gnutella floods; DHT routes in ID space; ...) churn: nodes arrive and depart often limitation: free-riding a selfish user may download but refuse to upload because sum of download bandwidth and sum of upload bandwidth across whole system must be equal, free-riders can severely limit total download capacity BitTorrent system description: publisher: creates .torrent file describing data being published: length name content hashes (more below) URL for *tracker* (described later) makes .torrent file available for download on standard web server tracker: a standard web server that coordinates group of peers (*swarm*) that are downloading the same file each peer sends HTTP requests to tracker describing: file sought port for inbound connections tracker responds with: random list of IP addresses of peers in the swarm for that file some recent BitTorrent clients have no central tracker, instead use a DHT among peers seed: a peer that already has whole file origin of file's data for others in swarm must send entire file at least once before can depart peers learn other peers from tracker; connect to one another directly to request content note that only transfer metadata--never "contraband" data--are exchanged with centralized server, and only during transient lifetime of a swarm low b/w requirements at tracker and web server offering .torrent file arguably no record of illegal activity at fixed central server tracker learns stats on upload and download rates of peers, but only for operator monitoring; not used by system itself. because files are large, to maximize parallelism between peers' transfers, BT divides file into *pieces* typically 256KB in size; each is identified by its SHA-1 hash; the catalog of pieces (their SHA-1 hashes) is in the .torrent file each peer initially retrieves from a central web server (note that it can be replicated at many web servers) peers can verify they have the right data by verifying SHA-1 hashes of the pieces they receive each peer reports to other peers the pieces it has; downloading peer thus asks its peers for pieces it is missing that they have if downloader finishes receiving a piece, then requests next one, there'd be one RTT of idle time. to avoid that, and keep pipe full, BT breaks pieces into *subpieces* of 16 KB each, pipelines several parallel requests (typically 5), launches new one each time a subpiece has completely arrived. Q: how does BT decide which piece to request next? intuition: impacts performance significantly. want to make sure all pieces remain available within swarm, and makes it more likely a node acquires pieces it can upload to others (important in BT for reasons we'll soon discuss). first: once a peer has a subpiece from a piece, the other subpieces for that piece are top priority. Speeds acquiring that whole piece. next: rarest first. among pieces held by peers, pick the one held by the fewest of them. increases chance you hold a piece others want (important for TFT). observation: if seed has low upload b/w, rarest first nicely ensures peers tend only to ask seed for pieces it hasn't yet sent to any other peers. gets the seed to send each unique piece of the file to someone else in the swarm quickly. next: random first piece a newly joined client doesn't have any pieces to send to others. if it requested rarest first, that piece would be slow to arrive (since it's only available from few, possibly one, peer). so newly joined client requests a random piece first, to acquire its first piece quickly, so that it can start uploading to others. finally: endgame mode once requests are outstanding for all subpieces not held, the client requests all missing subpieces from all peers, in case any of them are being delayed by peers who are uploading slowly. cancel pending requests for subpieces that finish arriving. speeds the end of a download. Q: how do peers decide whom to download from and whom to upload to? peer's selfish goal: maximize own download speed system designer's goals: maximize aggregate download speed across all peers; prevent "free-riding" tit-for-tat (TFT): only send (upload) to those who *reciprocate* by sending to you. in BT parlance, *choke* those who don't reciprocate; don't send to them. original BT (in Cohen's 2003 paper) unchokes (uploads to) only 4 peers at a time; the modern BT reference implementation unchokes sqrt(upload rate) peers at a time; many modern clients still unchoke only 4 peers at a time Q: which peers to unchoke? basically, the ones from whom a peer can download fastest. original BT client measures download tput over a sliding 20-second interval. every 10 seconds, BT chooses which peers to unchoke and chokes the others at bootstrap, no one has sent yet; under TFT, no one would ever start sending if they insisted the peer sent to them first. original BT bootstrap technique for TFT: at random, "optimistically" unchoke one peer for 30 seconds. send to them in hope they may reciprocate, and may offer download tput greater than that of other currently unchoked peers. (later BT bootstrap technique for TFT: at random, "optimistically" unchoke peers (2 per 10-second interval)--send to them in the hope they may reciprocate.) anti-snubbing: if choked by peer for more than a minute, blacklist him, and don't unchoke him except optimistically (i.e., randomly). i.e., focus attention on other peers, as that peer was not reciprocating. pareto efficiency definition: given an allocation of resources (e.g., download rate) to users, there exists no other allocation in which one user gets more of the resource and no other users get less of the resource. --- Bram Cohen's original BT paper: Cohen, Bram, "Incentives Build Robustness in BitTorrent", 2003. (Unpublished draft; available online.) --- Questions about evaluation of BitTyrant: 1) The evaluation in Figure 10 (one BitTyrant client in a swarm of BitTorrent peers) is for a client with a 128 KB/s upload capacity. But BitTyrant offers the most benefit when upload capacity is greatest. Would be more balanced to show alongside these results ones for a BitTyrant client with, e.g., 128 Kbits/s upload capacity. 2) The evaluation in Figure 11 (all BitTyrant clients on PlanetLab) is for downloading a *short* 5 MB file. BitTyrant doesn't do optimistic unchoking--and that mechanism is very good at "exploring" the set of possible peers to find ones that offer faster downloads than the current set of peers. That leaves open the question of how BitTyrant performs in *longer* transfers (e.g., 1 GB, not 5 MB), when network congestion levels may change for some peers over time--without optimistic unchoking, how effectively can BitTyrant notice when a peer that was slow before offers faster downloads now?