Heuristics for scheduling data requests using collective communications in a distributed communication network
The collective communication process studied here involves the ability of users to request information from diverse sources (both in terms of locality and data type) and receive this information before the users' deadlines expire. A model has been developed and examined for the case when the network is oversubscribed and not all requests in the system can be satisfied. This model is based upon systems that are in use or are planned for development. The heuristics presented for scheduling data traffic do not have explicit control of the network; the heuristics work with a network manager to configure and set up single-source, multiple-destination information channels that allow users to receive information. The goal is to create a near-optimal set of collective communication information channels that will satisfy the users' requests, Four components are employed to create value functions that are used to order the importance of the information channels for presentation to the network manager. In addition, two different weightings for the relative importance of different priority levels are considered. Simulation studies have been performed that evaluate the performance of the heuristics developed. It is shown that the heuristics perform well compared to the upper and lower bounds developed. These results call be used to develop techniques that can be deployed in actual military systems. Furthermore. the model and heuristics studied here can be applied to other domains. Such as business applications that utilize the internet to obtain critical information. (C) 2001 Academic Press.
scheduling distributed systems network protocols routing