Approximating Optimal Broadcast of Files in a Hose-Model Network

This paper is the first to address broadcast in the hose model in its full generality, i.e., the asymmetric heterogeneous setting where the upload and download capacities of each peer can be different. Previous papers have only considered the symmetric setting when the upload and download capacity of each peer are identical [8]; see Section 1.2 for details. The problem of finding a constant approximation for the asymmetric setting has been open, and even the setting of uniform upload capacities had not been considered earlier.

Additionally, the paper introduces the novel migratory setting that allows a peer to download from multiple peers subject to its download capacity constraint. This is a natural relaxation and does not lead to loss of data identity, as we still process the chunk as a whole. The constraint that a peer starts uploading only after receiving the complete chunk is important and separates our model from the fluid limit model.

Our first result is a novel completion time integer program for the problem of minimising makespan in the migratory setting. Formulating this integer program requires proving that a certain non-trivial property is necessary and sufficient for characterising valid broadcast schedules. Relaxing the integrality constraints gives a linear program, and we exploit the structure of the optimum solution of this LP to obtain a solution with makespan at most $e^{1/e}\mathrm{𝙾𝙿𝚃}+P$ (Theorem 5). $P$ is the time required for the slowest peer to download the chunk and while it is definitely less than $\mathrm{𝙾𝙿𝚃}$, it could be significantly smaller.

For the non-migratory setting, we do not know how to formulate a suitable integer program, but we circumvent this difficulty by restricting attention to so-called slotted schedules. We formulate an LP by restricting attention to downloads that fit into “slots”; we establish that this restriction does not lead to a significant increase in makespan. Our algorithm for rounding the optimum solution to the linear program proceeds through three stages each of which requires careful reasoning about the structure of the solution. This yields a solution of makespan $3{\mathrm{𝙾𝙿𝚃}}^{\prime }+P$ where ${\mathrm{𝙾𝙿𝚃}}^{\prime }$ is the minimum makespan of any slotted schedule. Since ${\mathrm{𝙾𝙿𝚃}}^{\prime }\le 6\mathrm{𝙾𝙿𝚃}$ (Lemma 7) we obtain a solution of makespan at most $18\mathrm{𝙾𝙿𝚃}+P$ (Theorem 11).

In the Appendix, we also consider 2 special cases in the non-migratory setting. When all download capacities are identical we extend the results of [12] to obtain a 2-approximation algorithm. When all upload capacities are identical we modify the download capacities of some peers and add some dummy peers to obtain a modified instance with makespan at most $2\mathrm{𝙾𝙿𝚃}+P$. We then find an optimum schedule for this modified instance and convert it into a schedule for the original instance with makespan at most $2\mathrm{𝙾𝙿𝚃}+2P$.

In the results mentioned above, we assume that the root peer has an upload capacity at least as large as the largest download capacity. If such is not the case, we can, in $\max \{P,1/u(0)\}$ time units ($u(0)$ is the upload capacity of the root peer) transfer the chunk to the peer with the largest upload capacity and then run our algorithms. This increases the makespan by at most $\mathrm{𝙾𝙿𝚃}$ as $1/u(0)$ is also a lower bound on $\mathrm{𝙾𝙿𝚃}$. In the non-migratory model, no peer can receive the chunk at a rate larger than the largest upload capacity, and so we can cap all download capacities at this value. For the migratory model, we show (Theorem 5) that the schedule obtained by our algorithm has makespan $P^{1/PQ}\mathrm{𝙾𝙿𝚃}+P$ where $Q$ is the ratio of the largest upload capacity to the largest download capacity of the peers.

The problem of broadcasting, where the task is to disseminate a message from a source node to the remaining nodes of a network as quickly as possible, has been studied under various models (see [9] for a survey). A popular model is the telephone model where communication happens in rounds. In each round, a peer with the message can communicate it to exactly one other peer and the objective is to minimize the number of rounds. If every node can communicate with any other node, Bar-Noy et al. [5] gave a simple recursive doubling algorithm which is optimal when the number of nodes is even and an additive 1 approximation when the number of nodes is odd. When communication can happen only between adjacent nodes of a given graph, Ravi [14] defined the notion of poise and used it to give a $O(\frac{{\log }^{2}n}{\log \log n})$-approximation, later improved to a $O(\frac{\log n}{\log \log n})$-approximation by Elkin and Kortsarz [7].

In the simultaneous send/receive model a peer can send the message to one peer and receive a message from another peer in the same round. Bar-Noy et al. [5] gave an optimal algorithm for broadcasting multiple messages for this model. A natural generalisation of this model is the $k$-port model which allows each peer to send $k$ messages to $k$ peers and receive $k$ messages from $k$ peers in a single round. An additive 1 approximation for the minimum number of rounds needed to send multiple messages was obtained in [4].

Another natural generalisation to these models is allowing for network heterogeneity. Banikazemi et al. [3] considered a setting of heterogeneous processors (peers) capable of point-to-point communication with each other. The peers could have different sending speeds/rates and the model requires that any peer take part in at most a single message transmission at any given time. For this model they proposed a fastest node first algorithm (FNF); in each iteration, the peer with the least transmission time which has the message sends it to the peer with the least transmission time which does not have the message. Liu [12] gave a 2-approximation algorithm for minimizing makespan in this model and showed that the fastest node first algorithm is optimum if sending rates are integer multiples of each other. Khuller and Kim [11] proved that the Fastest node first algorithm is a 1.5-approximation.

Mundinger et al. [13] considered the file-sharing problem and introduced the uplink-sharing model. The file is broken into multiple chunks and a peer can receive a chunk only from 1 other peer. However, a peer could simultaneously send a chunk to multiple peers. The rate of transfer is constrained by the upload capacity of the sending peer and the authors assume that concurrent uploads from one peer would share the upload capacity equally (fair-sharing assumption). Under this assumption, they prove that for identical upload capacities, a simple greedy algorithm is optimal. The authors [13] also studied the fluid limit model where the chunks are infinitesimally small.

Goetzmann et al. [8] removed the fair sharing assumption from [13] and generalised the model by introducing download capacity constraints. They consider the setting of symmetric heterogeneous capacities – equal upload and download capacities per peer that may differ among peers. Continuing with the assumption that a peer can receive a chunk from only one other peer, they prove that the problem of minimizing makespan is strongly NP-hard and give a $(1+2\sqrt{2})$-approximation algorithm for a single chunk and a 5-approximation algorithm for multiple chunks.

We formulate an integer program with completion times to determine if a single chunk can be shared by all the peers within time $C$. We then relax the integrality constraint to obtain a linear program that we solve to obtain a fractional solution.

Let $x$ be an optimum solution to the linear program and let $U_f(t)=U(t),t\in [T]$. We can modify the algorithm from Section 3.1.2 to compute the schedule corresponding to the solution $x$. With each $x_{jt}>0$ we associate a pseudo-peer $⟨j,t⟩$ which has download capacity $x_{jt}\cdot d(j)$, upload capacity $x_{jt}\cdot u(j)$ and needs to download only a $x_{jt}$ fraction of the chunk by time slot $t$. The algorithm can be used to schedule the download of the chunk to these pseudo-peers in order of increasing $t$. The only modification needed is that $\beta$, the fraction of the chunk that remains to be downloaded to the pseudo-peer $⟨j,t⟩$, is initially set to $x_{jt}$, and $\gamma$, the largest fraction of chunk which can be downloaded in a time-slot, is now set to $x_{jt}\cdot d(j)$.

Thus, if the upload capacity in time slot $t$ is $U_f(t)$, we can build a schedule such that an $x_{jt}$ fraction of the chunk finishes downloading to pseudo-peer $⟨j,t⟩$ and hence to peer $j$ by time slot $t$. Let $c(j)$ be the earliest time slot such that ${\sum }_{t\in [c(j)]}{x}_{jt}=1$. Peer $j$ completes downloading the chunk at time slot $c(j)$ in this schedule we have built and hence it can start uploading the chunk only after time slot $c(j)$. Thus the true (or integral) upload capacity in time slot $t$ in this schedule is . Note that $U_f(t)$, the fractional upload capacity at time slot $t$, is the sum of the upload capacities of all peers weighted by the fraction of the chunk that they have received by time slot $t$. It follows therefore, that for all time slots $t$, $U_f(t)\ge U_i(t)$. A feasible schedule can, in any time slot $t$, only permit downloads of total capacity at most the true upload capacity $U_i(t)$ and hence the schedule obtained from solution $x$ is not feasible. In order to build a feasible schedule we need a better understanding of the difference between $U_f$ and $U_i$. Informally, the following lemma shows that for two peers in the same class, the download of the peer with higher upload capacity precedes the download of the peer with lower upload capacity.

A peer $j$ is in class $l$ if ; let $\varphi (j)$ denote the class of peer $j$. A peer downloads the chunk in slot $(k,p)$ if the chunk is downloaded in the interval $[p\cdot 2^k,(p+1)\cdot 2^k)$ at a uniform rate $1/2^k$. A peer $j$ can download the chunk in a slot of class $k$ only if $k\ge \varphi (j)$. We call a schedule slotted if every peer downloads the chunk in some slot and we formulate an LP to minimize the makespan of a slotted schedule. The following Lemma, whose proof we omit due to space constraints, argues that the makespan of a slotted schedule is not significantly more than the makespan of the optimum schedule.

Let $T$ be our estimate of the minimum makespan and let $x_{ijkp},i\in [0..n],j\in [n],k\in [0..K],p\in [0..\lfloor T/2^k\rfloor )$ be 1 if peer $j$ downloads the chunk from peer $i$ in slot $(k,p)$. Note that peer $i$ can upload the chunk in a slot $(k,p)$ only if $2^{-k}\le u(i)$. We combine this with our earlier observation that $k\ge \varphi (j)$ to define variables $x_{ijkp}$ only for $k\ge {\kappa }_{ij}$ where ${\kappa }_{ij}=\max (\varphi (j),{\log }_{2}u{(i)}^{-1})$

1. 1.

   The constraint ${\sum }_{k,p}{\sum }_{i\in [0..n]}{x}_{ijkp}\ge 1$ ensures that peer $j$ downloads the chunk in some slot.

2. 2.

   Let $y_{jt}$ denote the fraction of the chunk downloaded by peer $j$ before time $t$. Note that this is at most . Peer 0 (the root) has the chunk available to it at time 0 and hence $y_{0t}=1,\forall t\in [T]$.

3. 3.

   The total downloads from peer $i$ assigned to slots containing $t$ is ${\sum }_{k,p:t\in (k,p)}{\sum }_{j\in [n]}{x}_{ijkp}\cdot 2^{-k}$ and this cannot exceed $u(i)y_{it}$ which is the total upload capacity of peer $i$ at time $t$.

This then yields the following system of linear inequalities.

If the above linear system is infeasible, our estimate of $T$ is too low and we double $T$. By performing a binary search on $T$ we determine the smallest $T$, say $T^{\ast }$, such that the linear system is feasible and let $x$ be this feasible solution.

An important property of $x$, along the lines of Lemma 4, is that if $j_1,j_2$ are peers of the same class and $u(j_1)>u(j_2)$, then $j_2$ cannot be downloading the chunk in a slot that ends strictly before any slot in which $j_1$ downloads the chunk.

Thus for each class, the chunk is received by peers of this class in decreasing order of their upload capacity. For each class $l$ order the peers of this class by decreasing upload capacity, breaking ties arbitrarily and let $⟨l,i⟩$ be the $i^{\mathrm{th}}$ peer in this ordering; it would be convenient to define $⟨l,0⟩$ as 0 (the root peer). Let $y_{lkp}={\sum }_{i\in [n]}{\sum }_{j\in {\varphi }^{-1}(l)}{x}_{ijkp}$ be the total extent to which peers of class $l$ download the chunk in a slot $(k,p)$. To determine which slot each peer of class $l$ downloads the chunk in, we order slots $(k,p)$ by increasing end-time. Then peer $⟨l,1⟩$ downloads the chunk in the earliest slots of this ordering for which the sum of $y_{lkp}$ is 1. In general, if $c(l,i)$ denotes the time at which the chunk is fully downloaded by peer $⟨l,i⟩$ then $c(l,i)=t$ is the earliest time at which ${\sum }_{k,p:(k,p)\le t}{y}_{lkp}\ge i$. We define $c(l,0)$ as 0. Thus, $0=c(l,0)\le c(l,1)\le c(l,2)\le \mathrm{\cdots }\le c(l,i)\le \mathrm{\cdots }$. Note that a peer could be downloading the chunk from many different peers and hence, $x,y$ is a migratory schedule. We now modify $x,y$ in a sequence of steps to obtain a non-migratory schedule.