Abstract |
Tactical coalition applications are usually time- critical. Hence, it is important to consider the latency of com- munication pipelines in addition to throughput. In this paper, we study the problem of sending a given amount of data from one node to another node in the fastest possible time on a directed network, where edges have given bandwidths and transmission latencies. The two extremes of this problem are shortest-path routing and max-flow routing. Namely, when the amount of data is small, the bottleneck is latency rather than bandwidth so the problem is solved by shortest-path routing; and when the amount of data is large, the bottleneck is bandwidth so the problem is solved by max-flow routing. In general, the optimal routing strategy changes over time, starting with a max-flow strategy when a large amount of data remains to be transferred and then progressively turning into shortest-path when there is less data remaining to be transferred. We propose an efficient algorithm for solving this dynamic data transmission and routing problem. The methods developed in this paper is fundamental to incorporating the effect of latency in other more complex coalition problems. |