Sujet de stage M2

Sujet: décision optimale pour le préchargement dans l’incertain
Encadrants: Alain Jean-Marie, Sara Alouf, équipe-projet Inria NEO, Sophia Antipolis
Lieu du stage: Sophia-Antipolis.

Résumé:

Le préchargement est une technique de base pour réduire la latence de divers services informatiques. Son principe est d’amener préventivement les données « au plus près » de l’endroit où elles pourraient être utilisées, au risque qu’elles ne le soient jamais. Décider quoi précharger revient à faire un compromis entre le bénéfice attendu sur la latence et le gaspillage de ressources (réseau, stockage, énergie) si on s’est trompé.

La modélisation du problème dans le cas de navigation web/vidéo/gaming, revient à identifier un graphe de « documents » unis par des liens représentant les enchainements possibles. Un « surfeur » aléatoire ou, au contraire, stratégique, parcourt ce graphe. Le contrôleur du préchargement doit faire en sorte que les documents parcourus sont toujours disponibles.

Pour le problème de décision de faisabilité, c’est-à-dire savoir si le contrôleur peut toujours satisfaire le surfeur avec les ressources dont il dispose, on utilise un modèle de « jeux sur graphes »: l’adversaire du surfeur est le préchargeur qui marque les documents dans le graphe, et le surfeur essaie d’éviter ces documents. Des résultats de complexité ont été obtenus dans [1] et d’autres références ultérieures. Dans le cas où le surfeur est aléatoire et/ou le graphe n’est pas connu complètement à l’avance, la question reste largement inexplorée. Dans le cas où le graphe est un arbre, il est montré dans [2] que ni la stratégie gloutonne, ni celle optimale pour l’arbre tout entier, ne sont optimales quand l’arbre est découvert progressivement.

Le stage aura donc pour objectif général de déterminer la stratégie de préchargement optimale en présence d’aléatoire, au moins pour certaines classes de graphes. Le cadre théorique sera celui des Processus de Décision Markoviens (Markov Decision Processes: MDP), dans la lignée du modèle décrit dans [3]. Cette théorie permet de caractériser la stratégie optimale, mais pas forcément de la calculer en pratique.

Parmi les différents points qui pourront être étudiés pendant le stage:
– identifier des situations simples dans lesquelles le calcul effectif de la stratégie optimale est possible
– en déduire des heuristiques (stratégies sous-optimales), applicables dans le cas général, et dont le calcul serait de complexité raisonnable
– évaluer leur efficacité par simulation pseudo-aléatoire (dite « Monte-Carlo »).

Prérequis souhaités: familiarité avec les probabilités discrètes. La connaissance de la théorie des MDP est un plus, mais elle pourra être acquise au début du stage.

Bibliographie:

  • [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, August 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), September 2014
    http://dx.doi.org/10.1109/MASCOTS.2014.58

Les commentaires sont clos.