§2.5Peer-to-Peer File Distribution

The problem

Distribute a large file from a single server to N hosts, called peers. The file might be a new release of an operating system, a software patch, or a video.

In client-server distribution, the server must send a copy to each peer. That places an enormous burden on the server and consumes a great deal of its upload capacity.

In P2P distribution, each peer can redistribute any portion of the file it has already received to any other peer, so it helps the server do its job.

Client-server: the time grows without limit

Two observations bound the distribution time distribution time Simple How long it takes until every peer has a complete copy of the file. Precise The time it takes to get a copy of a file to all N peers. For the client-server architecture it is D_cs = max{NF/u_s, F/d_min}, which grows without bound as N grows. For P2P it is D_P2P = max{F/u_s, F/d_min, NF/(u_s + Σu_i)}, which stays bounded because each peer adds upload capacity. introduced in ch. 2 — open in glossary D_cs.

• The server must transmit one copy of the file to each of the N peers, so it must transmit NF bits. At upload rate u_s, that takes at least NF/u_s.
• Let d_min be the download rate of the slowest peer. That peer cannot obtain all F bits in less than F/d_min seconds.

Putting them together gives the lower bound, and the homework shows the server can schedule its transmissions so the bound is actually achieved. So take it as the distribution time:

D_{cs} = \max\left\{ \frac{NF}{u_s},\ \frac{F}{d_{min}} \right\} \tag{2.1}

Peer-to-peer: the time stops growing

Now let each peer help. Three observations bound D_P2P.

1. At the start only the server has the file. To get it into the community it must send each bit at least once into its access link, so the time is at least F/u_s. Note the difference from the client-server case: a bit the server sends once may never need to be sent by the server again, because the peers redistribute it among themselves.
2. As before, the slowest peer needs at least F/d_min.
3. The total upload capacity of the system is u_total = u_s + u_1 + … + u_N. The system must deliver F bits to each of N peers, so NF bits in total, and it cannot do that faster than u_total. So the time is at least NF/(u_s + Σu_i).

D_{P2P} = \max\left\{ \frac{F}{u_s},\ \frac{F}{d_{min}},\ \frac{NF}{u_s + \sum_{i=1}^{N} u_i} \right\} \tag{2.3}

If each peer could redistribute a bit the instant it received it, there is a scheme that actually achieves this bound. In reality whole chunks are redistributed rather than individual bits, so equation 2.3 is a good approximation of the true minimum.

the server must send one copy to each peer: N x F = 32,000,000,000,000 bits
so it needs at least NF/u_s = 32000 s
the slowest peer cannot receive F bits faster than F/d_min = 640 s
D_cs = max{ 32000 s , 640 s } = 32000 s
the server's upload is the binding constraint — and it grows with every peer added

the server must push each bit into the network at least once: F/u_s = 32.0 s
the slowest peer still needs F/d_min = 640 s
the system as a whole uploads at u_s + Σu_i = 6.00 Gbps
and must deliver NF = 32,000,000,000,000 bits, so at least 5333 s
D_P2P = max{ 32.0 s , 640 s , 5333 s } = 5333 s
binding constraint: aggregate upload

BitTorrent

BitTorrent is the most popular P2P file distribution protocol. It was originally developed by Bram Cohen, and there are now many independent clients conforming to it — just as there are many browsers conforming to HTTP (HyperText Transfer Protocol) HyperText Transfer Protocol The application-layer protocol that requests and transfers Web documents. introduced in ch. 1 .

A torrent torrent Simple The whole group of machines sharing one particular file. Precise In BitTorrent, the collection of all peers participating in the distribution of a particular file. A torrent may have fewer than ten or more than a thousand peers at any instant of time. introduced in ch. 2 — open in glossary is the collection of all peers participating in the distribution of one particular file. Peers download equal-size chunks chunk Simple One equal-sized piece of a file that peers trade with each other. Precise An equal-size piece of a file that peers in a torrent download from one another, with a typical chunk size of 256 kilobytes. A peer joining a torrent has no chunks and accumulates them over time, uploading chunks while it downloads. introduced in ch. 2 — open in glossary of the file from one another, typically 256 kB each. A peer joining a torrent has no chunks, and accumulates them over time while uploading chunks to others.

Once a peer has the whole file it may selfishly leave, or altruistically stay and keep uploading. Any peer may leave at any time with only a subset of chunks, and rejoin later.

The tracker, and finding neighbours

Each torrent has one infrastructure node, the tracker tracker Simple The one server in a torrent that keeps the list of who is taking part. Precise The infrastructure node of a torrent. A peer registers with the tracker on joining and periodically confirms it is still there. When a new peer joins, the tracker randomly selects a subset of participating peers — for concreteness, 50 — and sends their IP addresses to the newcomer. The newcomer then tries to open TCP connections to all of them. introduced in ch. 2 — open in glossary . A peer registers with it on joining and periodically confirms it is still there, so the tracker knows who is participating. A torrent may have fewer than ten peers or more than a thousand at any instant.

When Alice joins, the tracker randomly selects a subset of peers — say 50 — and sends her their IP (Internet Protocol) Internet Protocol The network-layer protocol that defines the datagram format and addressing every Internet device must use. introduced in ch. 1 addresses. Alice tries to open TCP (Transmission Control Protocol) Transmission Control Protocol The Internet transport protocol that delivers data reliably and in order, with flow control and congestion control. introduced in ch. 1 connections to all of them. Those she succeeds with are her neighbouring peers. Some will leave and others will arrive, so the set fluctuates.

Which chunk to ask for

Periodically Alice asks each neighbour for the list of chunks it has. With L neighbours she gets L lists, and can then request chunks she does not have.

Her policy is rarest first rarest first Simple Ask first for the piece that the fewest of your neighbours have. Precise The BitTorrent technique for deciding which chunks to request. From among the chunks it does not have, a peer determines those that are rarest among its neighbours — that have the fewest repeated copies — and requests those first. The rarest chunks are then redistributed more quickly, roughly equalising the number of copies of each chunk in the torrent. introduced in ch. 2 — open in glossary .

Who to send to

Alice must also decide which requests to answer, and here BitTorrent uses a clever trading algorithm.

The four highest-rate neighbours are unchoked unchoked Simple Being one of the four neighbours a peer is currently sending chunks to. Precise In BitTorrent, the state of the four neighbours that are feeding a peer bits at the highest rate, to which that peer reciprocates by sending chunks. The rates are recalculated every 10 seconds, and the set may change. All neighbours other than these four and the optimistically unchoked one are choked, and receive nothing. introduced in ch. 2 — open in glossary , recalculated every 10 seconds. One more, chosen at random every 30 seconds, is optimistically unchoked optimistically unchoked Simple The one extra neighbour picked at random every 30 seconds, to give newcomers a chance. Precise In BitTorrent, the additional neighbour a peer picks at random every 30 seconds and sends chunks to, regardless of measured rate. This lets peers discover better trading partners, and lets new peers that have nothing to trade obtain their first chunks. introduced in ch. 2 — open in glossary . Every other neighbour is choked and receives nothing.

BitTorrent has other mechanisms this section does not cover: pieces (mini-chunks), pipelining, random first selection, endgame mode and anti-snubbing.

Distributed hash tables

One more P2P application deserves a mention. A distributed hash table distributed hash table Simple A simple database whose records are spread over the peers of a P2P system. Precise A DHT: a simple database with the database records distributed over the peers in a P2P system. DHTs have been widely implemented, for example in BitTorrent, and have been the subject of extensive research. introduced in ch. 2 — open in glossary ( DHT (Distributed Hash Table) Distributed Hash Table A simple database whose records are spread over the peers of a P2P system. introduced in ch. 2 ) is a simple database whose records are distributed over the peers of a P2P system. DHTs have been widely implemented — in BitTorrent among others — and have been the subject of extensive research.

Check yourself