4
$\begingroup$

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here.

PROBLEM FORMULATION: Given a file of size K (bits) residing at a node 1, we would like to disseminate it in minimum time to a set of N other nodes (stations/computers). All the N+1 nodes are connected to each other, hence they are vertices in a full graph. Any node $i$ is connected to a node $j$ with two links of equal capacity (bandwidth) $W$: link $(i,j)$ (which can only be used by $i$ to send a piece of the file to node $j$) and link $(j,i)$ (which can only be used by $j$ to send a piece of the file to node $i$).

Any node has the possibility to split the file it receives in smaller segments and send different segments to different neighbors. Also, any node can merge two segments that used to be adjacent in the original file and send them as a singe segment to one of the neighboring nodes.

One node can (AT THE SAME TIME!) receive data from at most one node and send data to at most one node (not necessarily a different node!).

The problem is that when sending a segment of any size, the sender has to spend a fixed amount of time $H$ encoding the segment to be sent to the neighbor. $H$ is NOT dependent on the size of the segment and this time interval has to precede immediately the time allocated to transmission.

Similarly, at the receiver, immediately after receiving a segment, a node has to spend a FIXED amount of time $H$ immediately after the reception is finished for decoding that segment. No part of any segment that is under reception can be sent until the segment has been completely received and the corresponding FIXED decoding time has elapsed.

QUESTION: How to split the original file in segments at various nodes and how to schedule the transmission of these segments in order to obtain an optimal (or, approximately optimal) schedule.

Attempts: a greedy algorithm that schedules a transmission as soon as two nodes that have something new to communicate to each other become available. The file is split in equal-sized segments, each of which takes more than $H$ time to transmit. It is not clear how far from optimum is this algorithm.

OTHER NOTES: I examined various problems that looked similar from M. Pinedo -- Scheduling: Theory, Agorithms and Systems. Also looked into Dynamic Programming and Optimal Control and Bertsekas -- Network Optimization: Continuous and discrete Models. Nothing seems to come close, unfortunately. Dynamic Programming, for instance is more concerned with shortest-path problems, which does not seem to be the case here. This also does not seem to be a circulation problem, because new quantities of flow are created at other nodes. Also, two different segments of same size cannot be treated as equivalent, barring the use of fluid approaches.

The closest references that I could find are listed below (they are very interesting, but not exactly useful here either):

[1] A. Srinivasan, C.-P. Teo -- A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria, 2001, SIAM J. Comput.

[2] D. Bertsimas, D. Gamarnik -- Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing

FINAL REMARKS: It is clear that the dissemination of a segment should overlap with the dissemination of other segments with index number closer to it (pipelining), but how to optimally schedule these transmissions is not clear at all. I also started to suspect that an optimal solution may be ery expensive to find and that a polynomial approximation may suffice. However, the PTAS-es that I know of are really for much simpler scheduling problems and apparently cannot be adapted.

EDIT 1: I had forgotten to add that each link has the same delay: $U$ seconds pass between the moment a node $i$ puts a first bit on the link and the moment the recipient $j$ receives that bit. $U$ is independent of the size of the segment sent. This delay is the same for all links. The delay is incurred for each intermediate link, of course. The encoding delay is the same for all links and all segment sizes.

EDIT 2: I was thinking of making a backtracking algorithm for small instances, but even that does not seem to be very obvious. I would also appreciate if someone could point out to similar problems and/or techniques that might be of use here. Thank you! Also, is there anything obvious in this problem that escapes my attention or is the problem indeed difficult?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 1. Can you define what you mean by optimal? What is the metric / objective function you will use to evaluate a candidate schedule? Is it time until the last recipient has finished receiving the file? 2. Does delay come only from the encoding delay at each node, or is there also a delay to send a file over each edge (e.g., based on size of segment divided by bandwidth)? Is the delay at each node the same? Is there a delay at each intermediate node along the path from sender to receiver, or only at the original sender and ultimate recipient? (cont.) $\endgroup$ Commented Oct 2, 2015 at 18:36
  • 1
    $\begingroup$ 3. Can a node batch up multiple segments and then encode them all at once, and if so, is the encoding delay the same as for encoding a single segment? 4. I'm still thinking about some kind of network flow (or min-cost flow) based approach, where each node $v$ gets replaced with two nodes $v_\text{in},v_\text{out}$ plus an edge $v_\text{in} \to v_\text{out}$ whose weight corresponds to the decoding/encoding delay at $v$ -- though I don't quite see how to make things work. $\endgroup$ Commented Oct 2, 2015 at 18:40
  • $\begingroup$ Indeed, by optimal I mean minimum makespan (i.e. the time the last recipient has received all the segments needed to assemble the full file). The delay is of course caused by the limited bandwidth. It takes s/W time to send a segment of s bits. $\endgroup$ Commented Oct 2, 2015 at 22:42
  • $\begingroup$ HOWEVER, I had forgotten to add that each link has the same delay: $U$ seconds pass between the moment a node $i$ puts a first bit on the link and the moment the recipient $j$ receives that bit. $U$ is independent of the size of the segment sent. This delay is the same for all links. The delay is incurred for each intermediate link, of course. The encoding delay is the same for all links and all segment sizes. $\endgroup$ Commented Oct 2, 2015 at 22:42
  • $\begingroup$ So encoding delay is incurred at each intermediate node? e.g., if I send a segment along the path $A \to B \to C$, there's encoding delay at A, decoding+encoding delays at B, and decoding delay at C, even though all B is doing is passing on the segment unchanged? And, there is no way to batch up segments to reduce encoding delay? So, if I send one segment along the path $A \to \C \to D$ and another segment along $B \to C \to D$, $C$ can't wait until it has received both segments, concatenate them, and then encode the result and send it to $D$, incurring only a single encoding delay? $\endgroup$ Commented Oct 2, 2015 at 23:54

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.