11 · P2P distribution + BitTorrent ★
Slides 2-71 → 2-79 · HW2 P5, P6, P7 · Sample midterm P6, 1e
The question
How long does it take to get a file of size \(F\) from one server to \(N\) peers? Upload and download capacity are the limited resources (the network core has plenty of bandwidth).
| Symbol | Meaning |
|---|---|
| \(F\) | file size (bits) |
| \(N\) | number of peers (clients) |
| \(u_s\) | server upload rate |
| \(u_i\) | peer \(i\)'s upload rate |
| \(d_i\), \(d_{min}\) | peer \(i\)'s download rate, and the slowest peer's download rate |
Client-server
Two things must happen, and the slower one sets the time:
- Server must upload \(N\) full copies, one per client: \(NF\) bits at rate \(u_s\) → \(NF/u_s\).
- Every client must download the whole file. The slowest one takes \(F/d_{min}\).
For large \(N\), \(NF/u_s\) wins, so the time grows linearly in \(N\).
P2P
Three things must happen:
- The server must upload at least one copy: \(F/u_s\).
- Every client must download the whole file: \(F/d_{min}\).
- All clients together must download \(NF\) bits. The total upload capacity in the system is the server plus every peer: \(u_s + \sum u_i\).
If all peers upload at the same rate \(u\), then \(\sum u_i = Nu\):
$$\frac{NF}{u_s + Nu}$$As \(N\) grows, demand (\(NF\)) grows, but so does capacity (\(Nu\)). The third term levels off near \(F/u\). That's self-scalability.
• Units. Put F and every rate in the same unit first. 20 Gbits = 20,000 Mbits (use 1000, as the HW solution does). 300 Kbps = 0.3 Mbps. Then the answer comes out in seconds.
• Upload vs download. The server and the swarm-capacity terms use upload rates (\(u\)). Only \(F/d_{min}\) uses a download rate.
• In the P2P sum, include \(u_s\). The server still uploads.
• Compute every term and take the max, not the sum.
Worked example: HW2 P5
Q: \(F = 20\) Gbits = 20,000 Mbits. \(u_s = 30\) Mbps. Every peer \(d_i = 2\) Mbps. Find the minimum distribution time for \(N = 10, 100, 1000\) and \(u = 300\) Kbps, 700 Kbps, 2 Mbps.
Terms that don't depend on N or u
$$\frac{F}{d_{min}} = \frac{20{,}000}{2} = 10{,}000 \text{ s} \qquad \frac{F}{u_s} = \frac{20{,}000}{30} \approx 667 \text{ s}$$Client-server
$$\frac{NF}{u_s} = \frac{N \times 20{,}000}{30}$$N = 10: \(6{,}667\), but \(F/d_{min} = 10{,}000\) is bigger → 10,000 s.
N = 100: 66,667 s. N = 1000: 666,667 s. (u doesn't matter: client-server ignores peer uploads.)
P2P, one cell in full: N = 100, u = 0.3 Mbps
$$\frac{NF}{u_s + Nu} = \frac{100 \times 20{,}000}{30 + 100(0.3)} = \frac{2{,}000{,}000}{60} = 33{,}333 \text{ s}$$ $$D_{P2P} = \max\{667,\ 10{,}000,\ 33{,}333\} = \mathbf{33{,}333 \text{ s}}$$Full answer (seconds)
| Client-server | N = 10 | N = 100 | N = 1000 |
|---|---|---|---|
| any u | 10,000 | 66,667 | 666,667 |
| P2P | N = 10 | N = 100 | N = 1000 |
|---|---|---|---|
| u = 300 Kbps | 10,000 | 33,333 | 60,606 |
| u = 700 Kbps | 10,000 | 20,000 | 27,397 |
| u = 2 Mbps | 10,000 | 10,000 | 10,000 |
Where the other P2P cells come from:
- N = 10: the swarm term is \(200{,}000/33 \approx 6{,}061\) (u = 0.3), \(200{,}000/37 \approx 5{,}405\) (0.7), \(200{,}000/50 = 4{,}000\) (2). All below 10,000, so \(F/d_{min}\) wins → 10,000.
- N = 100, u = 0.7: \(2{,}000{,}000/100 = 20{,}000\). u = 2: \(2{,}000{,}000/230 \approx 8{,}696\) → 10,000 wins.
- N = 1000: \(2 \times 10^7/330 \approx 60{,}606\), \(2 \times 10^7/730 \approx 27{,}397\), \(2 \times 10^7/2030 \approx 9{,}852\) → 10,000 wins.
Slide graph (2-75)
\(F/u = 1\) hour, \(u_s = 10u\), \(d_{min} \ge u_s\). Client-server = \(NF/u_s = N/10\) hours, a straight line (N = 30 → 3 hours). P2P ≈ \(N/(10 + N)\) hours, which flattens out below 1 hour (N = 30 → 0.75 hours).
Worked example: HW2 P6 / Sample midterm P6
Q: Client-server, fluid model: the server can send to many peers at once at different rates, as long as the total ≤ \(u_s\).
(a) If \(u_s/N \le d_{min}\), give a scheme with distribution time \(NF/u_s\). (This is sample P6.)
The server sends the file to all N clients in parallel, at rate \(u_s/N\) each (total = \(u_s\), so it's allowed).
Since \(u_s/N \le d_{min}\), every client can download at that rate. Each client gets the file in
$$\frac{F}{u_s/N} = \frac{NF}{u_s}$$All of them finish at the same time, so the distribution time is \(NF/u_s\).
(b) If \(u_s/N \ge d_{min}\), give a scheme with distribution time \(F/d_{min}\).
The server sends to all N clients in parallel at rate \(d_{min}\) each.
The total is \(N d_{min} \le u_s\) (from the assumption), so the server can do it. Each client gets the file in \(F/d_{min}\), all at the same time, so the distribution time is \(F/d_{min}\).
BitTorrent
- The file is split into 256 Kb chunks.
- Torrent = the group of peers exchanging chunks of one file.
- Tracker = keeps track of which peers are in the torrent.
- A new peer (Alice) registers with the tracker, gets a list of peers, and connects to a subset of them, her "neighbors". She starts with no chunks and collects them over time.
- While downloading, a peer also uploads chunks to others.
- Churn: peers come and go. Once a peer has the whole file, it may selfishly leave or altruistically stay.
Requesting chunks: rarest first
Peers have different subsets of chunks. Alice periodically asks each neighbor for its chunk list, then requests her missing chunks, rarest first (the chunks the fewest neighbors have). That spreads rare chunks before they disappear from the swarm.
Sending chunks: tit-for-tat
- Alice sends chunks to the 4 peers currently sending to her at the highest rate. Everyone else is choked (gets nothing from her).
- She re-evaluates the top 4 every 10 s.
- Every 30 s, she picks one more peer at random and starts sending to it: optimistic unchoking. That peer may then join her top 4.
How it plays out: (1) Alice optimistically unchokes Bob. (2) Alice becomes one of Bob's top-4 providers, so Bob sends back. (3) Bob becomes one of Alice's top-4 providers. Higher upload rate → better trading partners → faster download.
Sample midterm 1e: how does a new peer get her first chunk?
Worked example: HW2 P7 (free-riding)
Q: Bob joins a torrent but never uploads anything.
(a) Can he still get the whole file?
Yes, as long as enough peers stay in the swarm long enough. He'll keep receiving chunks through other peers' optimistic unchoking. (It's slow, since he'll never make anyone's top 4.)
(b) He uses many lab computers (different IPs) to free-ride faster. How?
Run a BitTorrent client on each host. Each one free-rides and gets optimistically unchoked by different peers. Combine the chunks from all hosts into one file. A small scheduler can make each host ask for different chunks to avoid duplicates. (This is a kind of Sybil attack: one user pretending to be many peers.)
Quick check
1. F = 1 Gbit, N = 50, \(u_s\) = 20 Mbps, \(d_{min}\) = 5 Mbps. Client-server distribution time?
F = 1000 Mbits. $$D_{cs} = \max\left\{\frac{50 \times 1000}{20},\ \frac{1000}{5}\right\} = \max\{2500,\ 200\} = \mathbf{2500 \text{ s}}$$2. Same as #1, P2P with every peer uploading at u = 1 Mbps?
$$\frac{F}{u_s} = 50 \qquad \frac{F}{d_{min}} = 200 \qquad \frac{50{,}000}{20 + 50(1)} = \frac{50{,}000}{70} \approx 714$$ \(D_{P2P} \approx \mathbf{714 \text{ s}}\).3. Same as #2, but u = 4 Mbps?
$$\frac{50{,}000}{20 + 200} = \frac{50{,}000}{220} \approx 227$$ \(\max\{50,\ 200,\ 227\} \approx \mathbf{227 \text{ s}}\).4. Why does P2P have \(F/u_s\) instead of \(NF/u_s\)?
In P2P the server only has to upload one copy. The peers redistribute it to each other.5. What does the third P2P term, \(NF/(u_s + \sum u_i)\), represent?
All N peers need F bits each, so \(NF\) bits total must be delivered. The most the system can upload per second is the server's rate plus every peer's rate.6. If \(u_s/N \ge d_{min}\), what client-server scheme gives time \(F/d_{min}\)?
Send to all N clients in parallel at rate \(d_{min}\) each. The total \(N d_{min} \le u_s\), so the server can do it, and every client finishes in \(F/d_{min}\).7. A new BitTorrent peer has no chunks. How does she get her first one? (sample 1e)
Optimistic unchoking: every 30 s, each peer randomly picks one extra peer to send to. She gets chunks that way and can then trade.8. What is tit-for-tat? How often is the top 4 re-evaluated?
A peer sends chunks to the 4 peers that are sending it chunks at the highest rate, and chokes the rest. The top 4 is re-evaluated every 10 s. (Optimistic unchoke: every 30 s.)9. Why request rarest chunks first?
So rare chunks get copied and spread before the few peers holding them leave the swarm.10. Can a free-rider get the whole file? (HW2 P7a)
Yes, through other peers' optimistic unchoking, as long as enough peers stay in the swarm long enough.← 10 · Email + DNS · all topics · 12 · Video, CDNs, sockets →