Providing up-to-date input to users' applications is an important data managemerit problem for a distributed computing environment, where each data storage location and intermediate node may have specific clata 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 clata staging problem in which all parameter values for the communication system and the data request information represent the best known iriforlilation 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 lilathelilatical model for the basic clata staging problem is introduced. Then, three multiple-source shortest-path algorithm based heurist ~csfo r finding a near-optimal schedule of the colillilunication steps for staging the dai a are presented. Each heuristic can be used i q ith each of four cost criteria de1,eloped. Thus. twelve implementations are examined. In addition. two different weighting:; for the relative importance of different priority levels are considered. The performance of the proposed heuristics are evaluated and co~~iparebdy simulations. The proposed heuristics are shown to perform well with respect to upper and lower bounds. Furthermore, the heuristics and a colnplex 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

January 1999