Scheduling transmissions in a network

Abstract

Consider k stations wishing to transmit messages over a network of channels to a common receiver. The capacity of a channel is the maximum amount of data which can be transmitted in a time unit. In addition to the transmission stations, the network contains switching nodes. Given that the jth station has σj messages (j = 1,..., k) to transmit, it is desired to find a schedule with minimum completion time T. The amount of data sent over a channel may vary in time. A schedule is stationary if the amount of data sent in a time unit is constant throughout the schedule. It is first shown that for every schedule there exists a stationary schedule with the same completion time. Thus, the search for an optimum schedule is confined to stationary schedules. The problem of finding an optimum stationary schedule is formulated as a multisource single-sink network flow problem, in which the net amount of outgoing flow from each source (transmission station) within one time unit is σj T. An O(k|E||V|2) time algorithm to find the minimum T similar to Dinic's flow algorithm is suggested. Using Sleator and Tarjan's techniques an O(k2|E||V|log|V|) algorithm is derived. The running time of both algorithms is independent of the σj's and the capacities. © 1985.