2.5 Peer-to-Peer File Distribution¶

This note explains P2P file distribution and how it works, as well as the scalability of P2P architectures.

Recall that P2P architecture, there is minimal (or no) reliance on always-on infrastructure servers. Instead, pairs of intermittently connected hosts, called peers, communicate directly with each other. The peers are not owned by a service provider, but are instead PCs, laptops, and smartphones controlled by users.

Let's consider a very natural P2P application, distributing a large file from a single server to a large number of peers. It might be a Linux OS. In client-server file distribution, server must send a copy of the file to each of the peers. The most popular P2P file distribution protocol is BitTorrent.

Scalability of P2P Architectures¶

Consider a simple quantitative model for distributing a file to a fixed set of peers for both architecture types. The server and the peers are connected to the Internet with access links. Let's denote the upload rate of the server's access link by \(u_s\), the upload rate of the \(i\)th peer's access link by \(u_i\), and the download rate of the \(i\)th peer's access link by \(d_i\). Denote the file size to be distributed by \(F\) and the number of peers that want to obtain a copy of the file by \(N\).

Distribution time is the time it takes to get a copy of the file to all \(N\) peers. Let's assume the Internet core has abundant bandwidth, implying that all the bottlenecks will be in access networks. Also assume the server and clients are not doing any other network applications, so all is devoted to distributing the file.

The distribution time for client-server architecture, denoted by \(D_{cs}\). Client-server architecture, none of the peers aids in distributing the file. We observe: 1. Server must transmit one copy of the file to each of the \(N\) peers. Thus, the server must transmit \(NF\) bits. Since the server's upload rate is \(u_s\), the time to distribute the file must be at least \(NF/u_s\). 2. Let \(d_{min}\) denote the download rate of the peer with the lowest download rate. The peer with the lowest download rate cannot obtain all \(F\) bits of the file in less than \(F/d_{min}\) seconds. Thus the minimum distribution time is at least \(F/d_{min}\).

So, we obtain

\[ D_{cs} \geq max\left\{\frac{NF}{u_s}, \frac{F}{d_{min}}\right\} \]

This is the lower bound. Let's just take this lower bound provided above as the actual distribution time, so we have equality in the equation above.

For \(N\) large enough, the client-server distribution time is given by \(NF/u_s\). So the distribution time increases linearly with the number of peers \(N\).

Let's do a similar analysis for P2P architecture, where each peer assists the server in distributing the file. We observe: 1. Only the server has the file at the beginning of the distribution. To get this file into the community of peers, the server must send each bit of the file at least once into its access link. Thus the minimum distribution time is at least \(F/u_s\). 2. The peer with the lowest download rate cannot obtain all \(F\) bits of the file in less than \(F/d_{min}\) seconds. The minimum distribution time is at least \(F/d_{min}\). 3. The total upload capacity of the system as a whole is equal to the upload rate of the server plus the upload rates of each individual peer, that is, \(u_{total} = u_s + u_1 +\cdots + u_N\). The system must deliver \(F\) bits to each \(N\) peers, thus delivering \(NF\) bits. The minimum distribution time is also at least \(NF/(\text{sum of u's})\).

We obtain the minimum distribution time for P2P, denoted by \(D_{P2P}\).

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

This is a lower bound, but lets say that the actual minimum distribution time is with the equality.

Let's compare the distribution time for client-server architectures and P2P architecture:

2.5.1 mindistribution.png

BitTorrent¶

BitTorrent is a popular P2P protocol for file distribution. The collection of all peers participating in the distribution of a particular file is called a torrent. Peers in a torrent download equal-size chunks of the file from one another, with typeical chunk size of 256 KiB. When a peer first joins a torrent, it has no chunks, and over time, it accumulates more and more chunks. While it downloads chunks it also uploads chunks to other peers. When a peer acquires the entire file, it may selfishly leave the torrent, or altruistically remain in the torrent and continue to upload chunks to other peers.