Heuristics for scheduling prioritized data requests with deadlines in an overloaded distributed computing network

Gives an overview of research that the authors have conducted in the area of offline scheduling heuristics for communication requests in an overloaded network, where not all requests can be satisfied. Sites in the network request data items and each request has an associated deadline and priority. In a military situation, the data-staging problem involves positioning data for facilitating a faster access time when it is needed by programs that are to aid in decision-making. The work concentrates on solving a basic version of the data-staging problem in which all parameter values for the communication system and the data request information represent the best known information collected so far and stay fixed throughout the scheduling process. Three multiple-source shortest-path algorithm-based heuristics for finding a near-optimal schedule of the communication steps for staging the data are presented. Each heuristic is used with each of four cost criteria which have been developed. The performance of the proposed heuristics was evaluated and compared by simulations. The best heuristic was then combined with three variations of the best cost criterion; these variations consider the length of the path and the size of the data time requested. Further simulation studies were then performed. Also examined was the situation where two different versions of data items were available, with different sizes and different worths to the user. It is shown that the proposed heuristics perform very well with respect to an upper-bound measure