Matemáticas de Torrenting

Question

Es más o menos común conocimiento que una red bittorrent tiene el potencial de ser mucho más rápido que las descargas directas, pero yo nunca he visto ninguna de matemática real que describe por qué, o cualquier teórico de los límites sobre lo que el speedup puede ser.

¿Alguien sabe de alguna referencia donde cosas como la aceleración en comparación con las descargas directas son modelados?

Estoy pensando en un modelo similar a este.

Supongamos que hay un archivo de tamaño de $Bk$, dividido en $k$ bloques de $b_1,\ldots,b_k$ del tamaño de la $B$, que es inicialmente detenido por $s$ semillas. Hay inicialmente $p$ compañeros que desea descargar el archivo, y así no se $N:=p+s$ total de personas (supongamos para simplificar que no hay nuevos compañeros entrar o salir cuando un compañero termine de descargar, siempre semillas por el resto del tiempo [más difícil de modelo permitiría semillas para tener una al azar (exponencial) de por vida]). La etiqueta de los usuarios $U_1,U_2,\ldots,U_N$. También suponga que el usuario $i$ tiene un límite de velocidad de subida $u_i$ y una velocidad de descarga límite de $d_i$.

Asumir los bloques deben ser descargados completamente (la idea es que ellos son de 1 mb o así, y vamos a tratar esto como una especie de unidad atómica para el tiempo de descarga).

A continuación, hay una disponibilidad de la distribución de los bloques, asumimos todos los $N$ de los usuarios de conocer la distribución en todo momento.

Estoy buscando referencias de los cuales se intenta responder a preguntas como:

¿Cuál es la mejor manera (o de una buena manera) para organizar las conexiones entre los usuarios, y cuánto más rápido de este método es que diciendo que no hay un servidor central que sirve downloaders tan rápido como pueda?

Answer 1

Voy a suponer que los usuarios de $U_1,\ldots,U_p$ son compañeros y usuarios $U_{p+1},\ldots,U_N$ son sembradoras. Yo también soy sólo va a ver en el estado estacionario, donde cada uno para cada par de usuarios $u_i,u_j$, hay al menos un bloque que $i$ $j$ no, y también un bloque que $j$ $i$ no.

Inidivudally, peer $i$ pueden descargar con un ancho de banda $$ b_i \leq \min \left\{d_i, \sum_{j\in\{1,\ldots,N\} \setminus \{i\}} u_i\right\} \text{.} $$ es decir, su velocidad de descarga está limitada por la combinación de velocidades de carga de todos los demás usuarios, o sus propias aguas abajo de ancho de banda, lo que sea menor. Además, la suma de los anchos de banda de descarga de más de todos los compañeros que no puede exceder de la suma de los anchos de banda de subida encima de todos los usuarios, es decir, $$ \sum_{i=1}^p b_i \leq \sum_{i=1}^N u_i \text{.} $$ El tiempo total que se tarda para todos los $p$ a los compañeros a terminar su descarga es entonces $$ T = B\cdot\max_{i=1}^p \frac{1}{b_i} = \frac{B}{\min_{i=1}^p b_i}\text{,} $$ suponiendo que en cualquier momento, la distribución de los datos permite a todos los compañeros a utilizar todo el ancho de banda de $b_i$ disponible para ellos.

Supongamos ahora que la descarga anchos de banda $b_i$ está asignado de la siguiente manera:

1. Cada uno de los compañeros que recibe una parte justa de la carga de ancho de banda de todos los otros usuarios, es decir, un $p$-ésimo de la carga de ancho de banda de todas las sembradoras, y un $(p-1)$-ésimo de la carga de ancho de banda de todos los pares (peer no se puede cargar a sí mismo!), es decir, $$ \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. Siempre que $\hat b_i$ supera $d_i$, es decir, el usuario de abajo ancho de banda, el ancho de banda (por supuesto!) sujeta a $d_i$, y el exceso de ancho de banda se distribuye uniformemente en todos los usuarios con más aguas abajo anchos de banda.

Ahora mira el usuario con el menor $b_i$. Hay dos casos - o bien $b_i = \hat b_i$ o $b_i = d_i$. Por lo tanto $$\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}$$