Rendu

Ce notebook est à rendre sur Teide pour mardi 3 janvier à midi (12h00). Merci de rendre le notebook (.ipynb) ainsi qu'une version pdf ou html du notebook (file -> download as -> pdf)

1. Un peu de théorie : la M/M/1/K

On considère la file d'attente M/M/1/K:

  • les paquets arrivent selon un processus de Poisson d'intensité $\lambda$ et sont servis dans l'ordre d'arrivée
  • la durée de service est exponentielle de paramètre $1$
  • le nombre de paquets en attente est limité à $K$ paquets. Les clients qui arrivent alors qu'il y a déjà $K$ clients sont rejetés.

Question 1

Proposer un modèle Markovien de ce système. Quel est son générateur infinitésimal?

Question 2 -- Stabilité

Pour quelles valeurs de $\lambda$ la chaine a-t-elle une unique mesure stationnaire?

Question 3 -- Temps d'attente et taux de rejet

Exprimer la probabilité qu'un client soit rejeté (en régime stationnaire) en fonction de $\lambda$ et de $K$. Exprimer aussi le temps d'attente moyen d'un client en fonction de K (On pourra se servir de la formule de Little https://en.wikipedia.org/wiki/Little's_law)

Pour $K=100$ et $K=1000$, tracer en fonction de $\lambda$ le temps d'attente et la probabilité de rejet. Pouvez vous en déduire pourquoi les routeurs ont des files d'attente (buffers) petites?

In [ ]:

2. Méthode de rejet

On se donne un tableau de nombres positifs $p=(p_0,\dots,p_{n-1})$ tels que $\sum_i p_i=1$. Écrire un algorithme permettant de générer une loi selon la distribution $p$ en utilisant la méthode de rejet. Quelle est la complexité moyenne de votre algorithme?

Remarque : on ne demande pas un programme python mais uniquement un algorithme en pseudo-code.

3. Algorithme de Cache

On dispose d'un cache pouvant stocker $m$ objets et d'une collection de $n$ objets. On suppose que les requètes de l'objet $i$ sont générées selon un procesus de Poisson d'intensité $\lambda_i$. On appelle $\lambda_i$ la popularité de l'objet $i$. Lorsqu'un objet n'est pas dans le cache, il faut en supprimer un. On veut comparer les deux politiques suivantes:

  • LRU - Les objets sont ordonnés dans le cache par ordre de requète. L'objet $i$ est le $i$ème dernier à avoir été requis. Lorsqu'un nouvel objet entre dans le cache, on le met en position $0$ et on décale tous les autres d'un cran (en enlevant l'ancien objet en position $n-1$ du cache).
  • CLIMB - Les objets sont ordonnés dans le cache. Lorsqu'un objet est requis:
    • Si cet objet n'était pas dans le cache, il remplace l'objet en position $n-1$
    • Si cet objet était dans le cache en position $i\ge1$, il échange sa place avec l'objet en position $i-1$.

3.1 Théorie

On suppose que $n=8$, $m=4$ et $\lambda=[3,1,1,1,1,1,1,1]$. On note $X_t\in[0,1,2,3,out]$ la position de l'objet de popularité $3$ dans le cache ("out" signifie "hors du cache")

Question 1

Pour chacune des deux politiques (LRU et CLIMB), $X_t$ est-il une chaîne de Markov? Si oui, décrire son générateur infinitésimal.

Question 2

Pour chaque politique: à quelles conditions $X_t$ a une unique mesure stationnaire? Calculer la probabilité que la page 0 (celle de popularité $3$) soit présente dans le cache en régime stationnaire. En déduire la probabilité qu'en régime stationnaire, une page demandée soit dans le cache.

3.2 Simulation

On suppose maintenant que $n=100$, $m=30$ et $\lambda_i=1/(i+1)$.

Par simulation, calculer la probabilité qu'un objet requis à l'instant $t$ soit dans le cache (pour $t\in\{1,5,10,100\}$) et pour chacune des deux politiques. On fera attention au calcul des intervalles de confiance.

Ces résultats confirment-t-ils vos résultats théoriques? En pratique, recommandez vous d'utiliser LRU ou CLIMB?

In [ ]:
In [ ]: