Abstract
Providing up-to-date input to users' applications is an important data management problem for a distributed computing environment, where each data storage location and intermediate node may have specific data available, storage limitations, and communication links available. 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 will aid in decision making. This 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. The network is assumed to be oversubscribed and not all requests for data items can be satisfied. A mathematical model for the basic data staging problem is reviewed. Then, three multiple-source shortest-path algorithm based procedures for finding a near-optimal schedule of the communication steps for staging the data are described. Each procedure can be used with each of seven cost criteria developed. A subset of the 21 possible resulting heuristics that are expected to perform well (based on earlier experiments) are evaluated in simulation studies considering different priority weightings schemes, different average number of links used to satisfy each data request, and different network loadings. Finally, an approach considering data items with "more desirable" and "less desirable" available versions is evaluated using a variable time, variable accuracy algorithm, and simulation results are presented. The proposed heuristics are shown to perform well with respect to upper and lower bounds. Furthermore, the heuristics using a complex cost criterion allow more highest priority messages to be received than a simple-cost-based heuristic that schedules all highest priority messages first.
Date of this Version
May 1999