Md. Theys et al., A mathematical model and scheduling heuristics for satisfying prioritized data requests in an oversubscribed communication network, IEEE PARALL, 11(9), 2000, pp. 969-988
Citations number
25
Categorie Soggetti
Computer Science & Engineering
Journal title
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Providing up-to-date input to users' applications is an important data mana
gement problem for a distributed computing environment, where each data sto
rage location and intermediate node may have specific data available, stora
ge limitations, and communication links available. Sites in the network req
uest data items and each request has an associated deadline and priority. I
n a military situation, the data staging problem involves positioning data
for facilitating a faster access time when it is needed by programs that wi
ll aid in decision making. This work concentrates on solving a basic versio
n of the data staging problem in which all parameter values for the communi
cation system and the data request information represent the best known inf
ormation 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 pro
blem is introduced. Then, three multiple-source shortest-path algorithm-bas
ed heuristics for finding a near-optimal schedule of the communication step
s for staging the data are presented. Each heuristic can be used with each
of four cost criteria developed. Thus, 12 implementations are examined. In
addition, two different weightings for the relative importance of different
priority levels are considered. The performance of the proposed heuristics
are evaluated and compared by simulations. The proposed heuristics are sho
wn to perform well with respect to upper and lower bounds. Furthermore, the
heuristics and a complex cost criterion allow more highest priority messag
es to be received than a simple-cost-based heuristic that schedules all hig
hest priority messages first.