Computer Networking › Section B · The application layer › Topic B.5

Peer-to-peer file distribution

Sending one large file to thousands of people can swamp any single server. Peer-to-peer distribution turns every downloader into an uploader as well, and a short calculation shows why that lets the system keep up however many people join.

The distribution problem

Suppose a game update, a Linux installation image or a large data set must reach N computers. In the client-server approach, one server sends a full copy to every client, so its upload link must carry N copies. In the peer-to-peer (P2P) approach, the server sends the file into the system once or a few times, and the peers then trade pieces with each other, each uploading to others as it downloads. The question is how the time to give everyone the whole file, the distribution time, grows as N grows. To compare fairly, assume the core of the internet has plenty of capacity, so only access links limit the transfer.

Distribution time with a single server

Let the file have F bits, the server's upload rate be \(u_s\), and the slowest peer's download rate be \(d_{min}\). The server must upload N copies, which takes at least \(NF/u_s\). The slowest client cannot download faster than \(d_{min}\), which takes at least \(F/d_{min}\). The distribution time is at least the larger of the two:

D_{cs} \ge \max\left(\frac{NF}{u_s}, \frac{F}{d_{min}}\right)

For large N the first term wins, so the time grows in proportion to the number of clients: ten times the audience means ten times the wait.

Distribution time with peers

With P2P, peer i also uploads at rate \(u_i\). Three limits apply. The server must send every bit at least once, taking \(F/u_s\). The slowest peer must still download the whole file, taking \(F/d_{min}\). And all NF bits must be uploaded by someone, at a total rate of at most \(u_s + \sum u_i\). So

D_{P2P} \ge \max\left(\frac{F}{u_s}, \frac{F}{d_{min}}, \frac{NF}{u_s + \sum u_i}\right)

As N grows, the total upload capacity grows with it. That is the self-scaling property: each new peer adds demand, but also supply.

Worked example: server against swarm

A 1 GB file, 8,000 Mbit with 1 GB taken as \(10^9\) bytes, goes to N peers. The server uploads at 100 Mbit/s, each peer uploads at 10 Mbit/s, and the slowest downloads at 50 Mbit/s. 1. For N = 10: client-server needs \(\max(800, 160) = 800\) s; P2P needs \(\max(80, 160, 80{,}000/200) = 400\) s. 2. For N = 100: client-server 8,000 s; P2P \(800{,}000/1{,}100 \approx 727\) s. 3. For N = 1,000: client-server 80,000 s, over 22 hours; P2P about 792 s. Check: with u = 10 Mbit/s, each peer's upload rate, the P2P time can never pass \(F/u = 800\) s however large N becomes, while the client-server time keeps growing.

BitTorrent: torrents, chunks and trackers

BitTorrent is the best-known P2P distribution protocol. The set of peers sharing one file is a torrent, or swarm. The file is cut into equal pieces whose size is a power of two, such as 256 KiB (\(2^{18}\) bytes), with larger pieces for big files, and peers trade pieces rather than whole files, so a peer can upload pieces it has while still downloading others. A small .torrent file or a magnet link identifies the content and a cryptographic hash of each piece, so a peer can reject corrupted or fake data. To find others, a joining peer asks a tracker, a server that lists the peers in the swarm, or uses a distributed hash table (DHT), in which the peers themselves store that list.

Which piece to fetch: rarest first

A peer regularly learns which pieces each neighbour holds. When choosing what to request next, it picks the piece held by the fewest neighbours: the rarest first. This spreads scarce pieces quickly, so that copies of every piece exist in many places. Without it, everyone might fetch the same easy pieces, and the swarm could stall when the few peers holding a rare piece leave. A new peer with nothing to trade may instead grab a random piece first, simply to get something it can upload.

Who to upload to: tit-for-tat

Upload capacity is the scarce resource, so BitTorrent rewards peers that give back. A peer measures how fast each neighbour is sending to it and uploads to the few that supply it fastest, in the classic design the top 4, re-evaluated every 10 seconds. These peers are unchoked; the rest are choked. Every 30 seconds it also unchokes one random extra peer, an optimistic unchoke. That gives newcomers a start and lets a peer discover better partners. This reciprocity, tit-for-tat, discourages free-riding, downloading without uploading, because peers that give nothing get served slowly.

Worked example: one peer's decisions

Peer P has five neighbours, A to E, sending to it at 6, 2, 9, 4 and 7 Mbit/s. P still needs pieces 12, 30 and 55, held by 4, 1 and 3 neighbours respectively. 1. Rarest first: piece 30 is held by only one neighbour, so P requests it first, then 55, then 12. 2. Tit-for-tat: ranking by rate gives C (9), E (7), A (6) and D (4), so P unchokes those four. 3. B, at 2 Mbit/s, is choked, but it could still be chosen for the next optimistic unchoke. Check: if B later sends at 8 Mbit/s after being unchoked, it would join the top four and push D out at the next 10-second review.

Where P2P is used, and its limits

P2P distribution suits large files wanted by many people at once: open-source operating system images, game patches and scientific data sets. Some software updaters and video systems combine CDN servers with peer sharing to cut their bandwidth bills. P2P has drawbacks. Home upload links are usually much slower than download links, which limits total capacity. Peers come and go, a behaviour called churn, so availability is never guaranteed. Sharing reveals a peer's IP address to the swarm, and a file's hash proves only that pieces match the published file, not that the file is lawful or safe.

Common mistakes to avoid

First, assuming P2P has no floor; the slowest peer's download limit \(F/d_{min}\) applies to both designs, so for small swarms the gain can be modest. Second, forgetting that the server must upload at least one full copy, \(F/u_s\). Third, mixing bits and bytes: a 1 GB file is 8,000 Mbit. Fourth, describing rarest-first as choosing the piece the peer itself is missing most; it means the piece fewest neighbours hold. Fifth, thinking tit-for-tat ignores newcomers; optimistic unchoking gives them a chance. Sixth, confusing BitTorrent the protocol with any particular use of it.

Key takeaways

Client-server distribution time is at least the larger of \(NF/u_s\) and \(F/d_{min}\), so it grows in proportion to N. P2P time is at least the largest of \(F/u_s\), \(F/d_{min}\) and \(NF/(u_s + \sum u_i)\); because upload capacity grows with N, it levels off. BitTorrent splits files into hashed pieces traded within a swarm, found through trackers or a DHT. Peers request rarest pieces first and upload tit-for-tat to their best suppliers, with optimistic unchoking for newcomers. Slow uploads, churn and exposed addresses limit P2P.

Flashcards

Flashcard

Distribution time

Time until every peer has the whole file

Compare client-server and P2P.

Test your understanding

Question 1 of 5

A 500 MB file (4,000 Mbit) goes to 200 peers. The server uploads at 50 Mbit/s, each peer at 5 Mbit/s, and the slowest peer downloads at 20 Mbit/s. What is the minimum P2P distribution time, to the nearest second?

Question 2 of 5

For the same file and server, why does client-server distribution take 16,000 s?

Question 3 of 5

A peer can request piece 8, held by 5 neighbours, or piece 21, held by 1 neighbour. What does rarest-first choose, and why?

Question 4 of 5

What is the purpose of BitTorrent's optimistic unchoke?

Question 5 of 5

Why does P2P distribution time level off as the number of peers grows?

← Previous topicNext topic →