THE MULTICHANNEL QUICKEST-PATH PROBLEM

Let N = (V, A, c, l) be an input network with node set V,arc set A, non-negative are weight functions c and l. Let sigma be the amount of data to be transmitted. The multichannel quickest-path problem is to find a transmission strategy by which the data are partitioned into a set of parts, each of which is sent by a selected routing path in N such that the time required to ship sigma units of data from the source to the sink is minimal. In this paper a mathematical description of the multichannel quickest-path problem is first given. Then a necessary and sufficient condition for the optimal strategy of the problem is obtained, and a set of formulae of the optimal strategy is derived. Then the multichannel quickest-path problem with capacity constraint is discussed, and a shortest-path first method for the capacity assignment is proposed. Finally, a general algorithm suitable for dynamic network environment with time complexity O(e(2) + ne log n) is designed.