On multi-channel data broadcast scheduling

We consider the following communi. cation problem. A single server is given access to a set of data items, channels over which items may be broadcast, and requests that arrive tit various, times for the items. At each system tick, the server must select an item to broadcast for each available channel, thus satisfying all requests for,that item, with the goal of minimizing the total wait time of all requests. Though several on-line scheduling algorithms have been developed for this problem, these algorithms have been stupid primarily through simulation experiments with little-emphasis, on theoretical analysis. In this paper we prove a general lower bound to the competitive ratios of all on-line algorithms for the problem in the, context of unit-sized items and multiple channels. We also I provide competitive analysis of two well-known on-line algorithms First, Come First Served and Most. Requested First. The competitive ratios obtained for the two algorithms consistent with I previous simulation experiments.' The fact that the competitive ratios match our general lower bound indicates the optimality of the algorithms.