Rendu

Ce notebook est à rendre sur Teide pour lundi 7 novembre au soir (22h). Merci de rendre le notebook (.ipynb) ainsi qu'une version pdf du notebook (file -> download as -> pdf)

In [141]:
# On se donne deux commandes pour importer numpy&matplotlib et avoir les graphiques "inline"
from pylab import *     
%matplotlib inline

Exercice 1. Simulation et stabilité

Dans cette exercice, on s'intéresse à simuler le comportement d'un serveur de calcul. On utilise pour cela un modèle simplifié en temps discret.

Le serveur reçoit des tâches de calcul à effectuer. On suppose que la durée d'exécution d'une tâche est constante, égale à une unité de temps. Si plusieurs tâches arrivent en même temps, le serveur les stocke dans une file d'attente.

On note $A_t$ le nombre de tâches arrivant à l'instant $t$ et $X_t$ le nombre de tâches en attente à l'instant $t$.

Question 1 -- écrire une formule de récurrence liant $X_{t+1}$ et $A_t$.

Question 2 -- On veut observer comment évolue le nombre de tâches en attente au cours du temps. Pour cela, on suppose que le nombre d'arrivées $A_t$ est distribué selon une loi de Poisson de paramètre $\rho$. Compléter le code à trou suivant et tracer comment évolue le nombre de tâches en attente au cours du temps pour $\rho=0.5$ et $\rho=2$. Qu'observez vous?

In [143]:
def simu_serveur(rho,T):
    X = [0]*T;
    for t in range(T-1):
        arrival = poisson(rho);
        X[t+1] = "A COMPLETER ICI"  
    return(X)
#plot(simu_serveur( rho=0.5, T=1000))
#figure();
#plot(simu_serveur(rho=2,T=1000))

On dit qu'un système est stable si le nombre de tâche de tend pas vers l'infini. En terme mathématiques, si $\liminf_{t\to\infty} X_t < \infty$.

Question 3 (Stabilité). Pour quelles valeurs de $\rho$ votre serveur est-il stable?

Exercice 2 - le protocole Aloha

Le protocole Aloha est le premier protocole à accès multiple. Il a été mis en place pour un réseau de communication radio sur les îles Hawai. L'objectif est de partager une fréquence unique pour toutes les communications.

Dans ce protocole, toutes les stations sont autorisées à émettre un paquet à tout moment. Si, deux stations émettent en même temps, il y a une collision et le paquet doit être retransmis. Afin d'éviter une nouvelle collision, une station qui vient de subir une collision attend un temps aléatoire avant de retransmettre son paquet.

On modèle ce système par un système en temps discret. On note $X_t$ le nombre de stations ayant un paquet à transmettre.

  • A l'instant $t$, $A_t$ nouvelles stations arrivent avec chacune $1$ paquet à transmettre. Toutes ces stations essaient d'émettre leur paquet.
  • Si deux stations (ou plus) essaient d'émettre en même temps, les deux paquets sont perdus et les stations devront ré-essayer dans le futur. Ces stations réessaient à chaque pas de temps avec probabilité $p>0$ jusqu'à réussir.

Question 4 Exprimer en fonction de $X_t$ et de $A_t$ la probabilité qu'il y ait une transmission réussie (justifier).

Question 5 Compléter le code à trou suivant.

In [146]:
def aloha(rho,T,p):
    X = [0]*T;
    n = 0;
    for t in range(T-1):
        n = X[t]
        arrival = poisson(rho);
        departure = "A COMPLETER ICI"
        X[t+1] = "A COMPLETER ICI"
    return(X)
#figure(); plot(aloha(.3,30000,.1))
#figure(); plot(aloha(.2,10000,.5))

Question 6 (Stabilité) Tracer le nombre de paquets en attente pour différentes valeurs de $\rho$ et de $p$. Qu'observez vous? Pour quelles valeurs de $\rho$ et $p$ pensez vous que le système est stable? Donner un argument heuristique qui explique vos observations.

In [ ]:

Exercice 3 : Aloha avec abandons

Dans l'exercice précédent, on a supposé que les serveurs réessaient de transmettre leur paquet jusqu'à réussir. On considère le même protocole mais on suppose maintenant que les serveurs abandonnent au bout de $K$ essais.

Abandons aléatoires

On suppose que le nombre d'essais que chaque station s'autorise est un nombre aléatoire $K$ qui est distribué selon une loi géométrique de paramètre $p$. Autrement dit, à chaque fois qu'une station fait une tentative infructueuse, elle s'autorise à continuer avec probabilité $q$ et quitte le système avec probabilité $1-q$.

Question 7 Exprimer la loi du nombre d'abandons à l'instant $t$, en fonction de $X_t$ et $q$.

Question 8 On fixe $q=1/2$ et $p=0.1$. Compléter le code ci dessous.

  • Que pensez vous de la stabilité du système?
  • Tracer en fonction de $\rho$ le nombre moyen de paquets transmis avec succès (par unité de temps). Qu'observez vous?
In [150]:
def aloha_abandon(rho,T,p,q):
    X = [0]*T;
    success = 0; 
    for t in range(T-1):
        arrival = poisson(rho);
        departure = " A COMPLETER ICI" 
        abandon = " A COMPLETER ICI" 
        X[t+1] = "A COMPLETER ICI"
        success += departure;
    return(success/T)

# EXEMPLE DE CODE POUR TRACER LA MOYENNE: 
#myRho = linspace(0,5,11);
#throughput = zeros((len(myAbandon),len(myRho)));
#for j,rho in enumerate(myRho):
#    throughput[j]=aloha_abandon(rho,10000,.1, 0.5)
#plot(myRho,throughput)

Abandons déterministes

On suppose maintenant que chaque serveur essaie de retransmettre au plus $\lfloor 1/q \rfloor$.

Question 9 Peut-on facilement adapter le code du simulateur ci dessus?

Question 10 Écrire un simulateur a événements discrets et reprendre la question 8. Qu'observez vous?

In [ ]:
In [ ]: