Bit Torrent and multicast routing

Bit Torrent is a protocol for downloading (typically large) files from the Web. For a given file that is being downloaded by several users, its principle is that of avoiding useless capacity occupation for each download by storing the file at intermediate nodes.

This principle clearly works with a particular type of traffic request: the same large file being requested by several nodes of the network G=(V,E). Under such assumption, the traffic model is different from the usual set of point-to-point demands we have seen in class for wired networks. This is more of a multicast demand, defined by a source s, and a set of destination nodes, T\subseteq V\setminus\{s\}.

For a detailed description, check the Wikipedia entry. Each of the destination nodes requests the same file at different times, and receives chunks of that file in seemingly random order. A polite destination node keeps that chunk and sends it to other destination upon request. We’ll have to simplify that a bit in order to make it fit in the Optimization/simulation context.

The problem, in our simplified version, is that of finding, for several source nodes and their corresponding sets of destination nodes, the subgraph structure that allows to send the full file to the source to each destination node while minimizing the total capacity occupation.

The input is:

  • A graph G=(V,E);
  • A set of pairs (s_k,T_k) for k=1,2\ldots, K, where s_k\in V and T_k\subseteq V\setminus\{s_k\};
  • A given file size M_k and request time d_k for each demand k=1,2\ldots, K;
  • A constant download speed of r for each file and a capacity of c_{ij} for each arc (i,j)\in A;

The problem is that of finding the optimal multicast flow from each source, which have to begin at the given start time, to all its destination in order to minimize the maximum edge capacity occupation (i.e. congestion).

Data: consider the instance modeling the Atlanta backbone network. Capacities are the first number in the LINKS section, and should be ignored. For simplicity, only consider one demand for each node i: the first demand whose source is i in the DEMANDS section. All file sizes, i.e., demands, M_k are expressed in Mb (and not Mb/s) and are again in the DEMANDS section. For each demand, the source is the node i, while the set T_k is the set of three nodes (i + 4) \textrm{ mod } 15, (i+8) \textrm{ mod } 15, and (i+12) \textrm{ mod } 15.

All time frames d_k are expressed in minutes and, as there is one demand k for every source node i, let d_i = i\cdot10 minutes. Finally, let r = 1 Mb/s.