The idea: every downloader also uploads
One server that sends a file to N clients must push N copies through its own uplink. The more clients, the longer it takes. In peer-to-peer (P2P) file sharing, a peer that has part of the file sends it on to others. Each new peer brings its own upload capacity, so the group, the swarm, gets faster as it grows. BitTorrent is the best known protocol of this kind.
The page has a seed S (it has the whole file) and four leechers P1-P4 with nothing yet. P5 waits outside until it joins. Pieces move in rounds of 10 seconds. In each round an uploader sends one piece to each peer it has unchoked. The boxes that fly between peers are pieces, coloured by piece number.
Pieces and the info_hash
A torrent cuts the file into pieces of equal size, usually 256 KiB to 4 MiB. The page uses 8 pieces, numbered 0 to 7. The .torrent file lists the SHA-1 hash of every piece, so a peer can check each piece on its own and throw away a bad one. The SHA-1 hash of the torrent's info section is the info_hash. It names the torrent everywhere: in the tracker request, in the handshake between peers and in the DHT. A magnet link holds little more than the info_hash.
Peers talk over TCP. After a handshake (protocol name, info_hash, peer_id) each side sends a
bitfield, one bit per piece it has, and then a have message for each new piece.
The other messages are interested, choke/unchoke, request
and piece. The page sums them up per round.
Finding peers: the tracker
A tracker is a server that keeps the list of peers for each info_hash. It never touches
the file. A peer sends it an HTTP announce with the info_hash, its peer_id and port, and how much
it still needs (left). The tracker answers with a list of peers and an
interval: when to announce again, often about 30 minutes. In Demo 1, P5 announces with
left=8, gets back S, P1, P2, P3 and P4, and then shakes hands with all five.
No tracker: the Kademlia DHT
A tracker is a single point of failure. The Mainline DHT (BEP 5) replaces it with a distributed hash table built on Kademlia. Every DHT node has a random 160-bit ID; the page uses 6 bits. The peer list for a torrent is kept by the nodes whose IDs are closest to its info_hash. Kademlia measures closeness with XOR: the distance from a to b is a XOR b, read as a number. Two IDs that share a long run of leading bits are close.
Each node keeps a routing table of k-buckets. Bucket i holds up to k contacts (k = 8 in
BitTorrent, 2 here) whose distance has its highest bit at position i. So a node knows many nodes near itself
and only a few far away, but at least one in every range. To look up a key, a node asks the closest contact it
knows with get_peers. A node that holds peers for the key answers with them
(values). Any other node answers with the k contacts it knows closest to the key
(nodes). Each answer shares at least one more leading bit with the key than the node that sent it,
so a lookup in a DHT of n nodes takes about log2 n steps.
In Demo 2, P5 (ID 6) looks up 45 = 101101. It asks 32 (distance 13), which points to 41 and 43.
It asks 41 (distance 4), which points to 44 and 46. Node 44 (distance 1) holds the peer list, so 3 queries are
enough. P5 then sends announce_peer, with a token it got from the answer, to the closest nodes,
so the next newcomer finds it too. In Demo 3 node 44 is down: its query times out, and P5 asks 46,
the next closest, which also holds the list. A dead node costs one timeout, not the lookup. Real lookups send
α = 3 queries at once, so a slow node hardly matters.
Kademlia is one way to map a key to the nodes that are responsible for it. A Dynamo-style hash ring is another: see Consistent Hashing. A ring needs every node to know the full membership; Kademlia needs only a few contacts per distance range.
Which piece next: rarest first
A downloader can choose any piece the uploader has and it lacks. BitTorrent asks for the rarest one: the piece with the fewest copies among the peers it knows (the "copies of each piece" row on the canvas). Common pieces can be had from anybody later. Rare ones may vanish. The page breaks ties by the lowest piece number; real clients pick at random among the rarest, and pick the very first piece at random so they have something to trade quickly.
The difference shows when the seed leaves. In Demo 6 peers pick at random and S leaves after round 4. In those 4 rounds S sent 8 pieces, but some went to peers that already had a copy, so piece 3 never left the seed. After S leaves, nobody has it, and nobody can ever finish. In Demo 7 the same seed with rarest first sends each of the 8 pieces once, the swarm keeps a full copy, and every peer finishes.
Who gets my upload: choking and tit-for-tat
A peer cannot upload well to everyone at once, so it chokes most peers and unchokes a few. Every 10 seconds it unchokes the peers that uploaded to it fastest over the last 20 seconds (4 regular slots in real clients, 1 on the page). That rule is tit-for-tat: you get the most from the peers you give the most to. On top of that, one optimistic unchoke slot goes to a peer chosen in turn, and it changes every 30 seconds. It lets a new peer with nothing to offer get its first pieces, and it lets a peer find partners that are faster than its current ones. A finished peer (a seed) has nothing to gain, so it serves peers in turn (round robin).
A free rider downloads but never uploads. In Demo 8 P4 is one. After 4 rounds P1, P2 and P3 have 5, 5 and 6 pieces, but P4 has only 3: it never earns a tit-for-tat slot and gets pieces only from the seed and from optimistic unchokes. Run Finish from there and P4 still gets the whole file, because in a swarm this small the peers soon have spare upload. Researchers showed the same in large swarms (the BitThief client); tit-for-tat slows free riders down rather than shutting them out.
How long it takes: client-server vs P2P
Let F be the file size, us the server's (seed's) upload rate, ui the upload rate of peer i and dmin the slowest download rate. With N peers, Kurose and Ross give these lower bounds on the time until everyone has the file:
| lower bound on the time | why | |
|---|---|---|
| client-server | max(N·F/us, F/dmin) | the server sends N copies alone |
| P2P | max(F/us, F/dmin, N·F/(us + Σui)) | the seed sends at least one copy; together they send N copies |
On the page F = 8 pieces, us = 2 pieces per round, ui = 2 and download is unlimited. With N = 4 the client-server bound is 4·8/2 = 16 rounds, and Demo 5 takes exactly 16. The P2P bound is max(8/2, 32/10) = 4 rounds. Demo 4 takes 6 rounds: a piece must arrive before it can be sent on, and early on the peers have little to trade. Add P5 (N = 5) and client-server needs 20 rounds, while the P2P bound stays at 4.
Real swarms are limited by the network too: see Network Delay and Throughput for why the slowest link sets the rate. Many peers sit behind home routers that block incoming connections, which is why BitTorrent also uses hole punching and the uTP protocol over UDP; see NAT. For another way a large group spreads information without a central server, see Gossip and SWIM.
What the page leaves out
- Blocks: a peer requests 16 KiB blocks of a piece, keeps several requests in flight, and checks the piece hash at the end. Endgame mode, which asks every peer for the last blocks, is not shown.
- Real rates and times: the page moves whole pieces in fixed 10-second rounds and lets downloads be unlimited.
- The full Kademlia lookup: α = 3 parallel queries, continuing until the k closest nodes have answered, tokens that expire, bucket refresh and node churn. UDP messages are bencoded, and IDs are 160 bits.
- Peer exchange (PEX), local peer discovery, web seeds, super-seeding, encryption and uTP congestion control.