Résumé
Prefetching control is a vital operation for the On-demand interactive systems where the instantaneous response is the crucial factor for the system success. The controller in such type of interactive system operates in an uncertain environment and makes sequences of decisions with long and short term stochastic effects. The difficulty, then, is to determine at every system state which contents to prefetch into the cache. We address the prefetching control problem in which the controller seeks to reach a Zero-Cost system state as quickly as possible while minimizing costs along the way (i.e. taking the shortest path). We model this control problem as a Negative Stochastic Dynamic Programming problem in which we minimize the undiscounted total expected cost. Our first contribution is formulating the prefetching problem as a control problem using the Markov Decision Process formalism. Our control model, PREF-CT, integrates the main models necessary for an adequate prefetching control operation; the prediction model, the access model, the network resource model, and the performance model. Our second contribution is the detection of a special structure of the optimal prefetching policy. Exploiting this special structure permits to develop two strategically different algorithms, ONE-PASS and TREE-DEC, which improve the complexity of computing the optimal prefetching policy.