Topic: optimal decision for prefetching under uncertainty
Supervisors: Alain Jean-Marie, Sara Alouf, Inria NEO project-team, Sophia Antipolis
Place: Sophia-Antipolis.
Résumé:
Prefetching is a basic technique used to reduce the latency of diverse computer services. Its principle is to bring proactively information at the “closest” of where it might be used, with the risk that it might never been used at all. Deciding what to prefetch amounts to make a compromise between latency and the waste of resources (network bandwidth, storage, energy) if contents is mistakenly prefetched.
Modeling the problem in case of web/video/gaming navigation, is done by identifying a graph of “documents” connected by links representing the possible chaining. A surfer, either random or strategic, browses this graph. The prefetching controller must make it sure that the documents browsed are always available locally.
For the decision problem about feasibility, that is, deciding whether the controller can always satisfy the surfer with the network resources available, one uses a model of “games on graphs”: the opponent of the surfer is the prefetcher who marks the documents/nodes in the graph. The surfer tries to avoid these marked documents. Complexity results are obtained in [1] and subsequent references. In the case where the surfer is random and/or the graph is not completely known in advance, the question is largely unexplored. In the case where the graph is a tree, it is shown in [2] that neither the greedy strategy, nor the one optimal for the whole tree, are optimal when the tree is discovered progressively.
The general goal of the internship will then be to determine the optimal prefetching strategy in the presence of randomness, at least for certain classes of graphs. The theoretical framework will be the Markov Decision Processes: MDP, in the line of the model described in [3]. This theory allows to characterize the optimal strategy, but not necessarily to compute it in practice.
Among the different points which can be studied during the internship:
– identify simple situations where the computation of the optimal strategy is indeed possible
– deduce heuristics (sub-optimal strategies), applicable in the general case, which have a reasonable computational complexity
– evaluate their efficiency through pseudo-random simulation (“Monte-Carlo”).
Prrequisites expected: good understanding of discrete probabilities. The knowledge of MDP theory is a a plus, but it will be possible to aquire it at the beginning of the intership.
Bibliography:
-
[1] To satisfy impatient Web surfers is hard
Fedor V. Fomin, Frédéric Giroire, Alain Jean-Marie, Dorian Mazauric, Nicolas Nisse
Theoretical Computer Science 526 (2014) 1 17
http://dx.doi.org/10.1016/j.tcs.2014.01.009 -
[2] Stratégies de préchargement
Quentin Petitjean
Rapport de stage de L3 de l’Ens Cachan, août 2019 -
[3] Pefetching Control for On-Demand Contents Distribution: A Markov Decision Process Model
Olivia Morad and Alain Jean-Marie
IEEE 22nd International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2014), septembre 2014
http://dx.doi.org/10.1109/MASCOTS.2014.58
