Mathematics of Torrenting

Question

It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds on what the speedup can be.

Does anyone know of any references where things like speedup compared to direct downloads are modeled?

I am thinking of a model similar to this.

Suppose there is a file of size $Bk$, split into $k$ blocks $b_1,\ldots,b_k$ of size $B$, which is initially held by $s$ seeds. There are initially $p$ peers who want to download the file, and so there are $N:=p+s$ people total (assume for simplicity that no new peers enter or leave when a peer finishes downloading, he always seeds for the rest of time [a harder model would allow seeds to have a random (exponential) lifetime]). Label the users $U_1,U_2,\ldots,U_N$. Also suppose user $i$ has an upload speed limit $u_i$ and a download speed limit $d_i$.

Assume blocks must be downloaded completely (the idea is that a they are 1mb or so, and we will treat this as a sort of atomic unit for download time purposes).

Then there is an availability distribution on the blocks, we assume all $N$ users know the distribution at all times.

I am looking for references which attempt to answer questions like:

What is the best way (or a good way) to arrange connections among users, and how much faster is this method than saying there is a central server which serves downloaders as fast as it can?

Answer 1

I'm going to assume that users $U_1,\ldots,U_p$ are peers and users $U_{p+1},\ldots,U_N$ are seeders. I'm also only going to look at the steady state, where each for each pair of users $u_i,u_j$, there's at least one block that $i$ has and $j$ doesn't, and also a block that $j$ has and $i$ doesn't.

Inidivudally, peer $i$ can at most download with bandwith $$ b_i \leq \min \left\{d_i, \sum_{j\in\{1,\ldots,N\} \setminus \{i\}} u_i\right\} \text{.} $$ i.e. his download speed is limited by the combined upload speeds of all other users, or his own downstream bandwith, whatever is smaller. Additionally, the sum of download bandwiths over all peers cannot exceed the sum of upload bandwidths over all users, i.e. $$ \sum_{i=1}^p b_i \leq \sum_{i=1}^N u_i \text{.} $$ The total time it takes for all $p$ peers to finish their download is then $$ T = B\cdot\max_{i=1}^p \frac{1}{b_i} = \frac{B}{\min_{i=1}^p b_i}\text{,} $$ assuming that at any time, the data distribution allows all peers to use the whole bandwidth $b_i$ available to them.

Now assume the download bandwiths $b_i$ are alloted as follows:

1. Each peers gets a fair share of the upload bandwith of all other users, meaning one $p$-th of the upload bandwith of all seeders, and one $(p-1)$-th of the upload bandwith of all peers (a peer can't upload to itself!), i.e. $$ \hat b_i = \sum_{j=\{1,\ldots,p\}\setminus\{i\}} \frac{u_i}{p-1} + \sum_{j=p+1}^N \frac{u_i}{p} $$

2. Whenever $\hat b_i$ exceeds $d_i$, i.e. the user's downstream bandwith, the bandwidth is (naturally!) clamped to $d_i$, and the excessive bandwidth is distributed evenly over all users with higher downstream bandwiths.

Now look at the user with the smallest $b_i$. There are two cases - either $b_i = \hat b_i$, or $b_i = d_i$. Thus $$\begin{eqnarray} T = \max \left\{ \frac{B}{\min_{i=1}^p d_i}, \frac{B}{\min_{i=1}^p \hat b_i} \right\} \end{eqnarray}$$