Models for dynamic file migration in distributed computer systems
Olivia R. Liu Sheng · 1986
This thesis studies the impact of film migration operations on system performance and develops automatic mechanisms for incorporating file migrations as part of the system operations. The mechanisms are developed following two common approaches: one pursues the optimal solution, and the other generates solutions that are not guaranteed to be optimal but requires less computational complexity. An optimal file migration policy is derived from the comparisons of future system performance among all viable options at various system states. Using proper state representation and the probabilistic assumption of state transitions, a recursive relationship can be found between system performance at consecutive decision points. The optimization models, thus, are formulated as Markov decision models based on the underlying recursive relationships for a variety of file migration policies. The primary distinctions among various classes of migration policies stem from the incorporation of dynamic file deletions and from the variability of film access intensities over time. In view of the exponential computational complexity of the optimization models, an adaptive decision heuristic for file migration is developed to ascertain the applicability of the file migration control mechanism in large systems. The heuristic acts on the most recent estimate of file access intensity and employs simple rules of thumb to derive individual file migration decisions. The trade-off between the optimization models and the heuristic is clearly that of the performance levels versus computational complexity. The optimization analysis not only generates the best possible solutions, but provides insight into the problem structure, and is used later for developing heuristics. The main advantages of those heuristics are their implementation simplicity and the improvements in system performance levels offered by them, compared to static policies. The performance of dynamic and static policies are analytically and numerically compared. These comparisons show that improvements of various degrees can be achieved by the optimal file migration policies as well as by the heuristic file migration decisions. In addition, file migration implementations are found to be less sensitive to imperfect estimation of the system environments than are static file allocation policies. (Abstract shortened with permission of author.)