# PRF - Amphi 4

[Slides](https://moodle.insa-lyon.fr/pluginfile.php/47789/mod_resource/content/7/4tc-prf-03_simulation.pdf)

###### tags : `PRF` `Amphi`

## Simulation basics

Trois types de simulation :
- Montecarlo
- Evénement discret
- Emulation

### Emulation

Pas une vraie abstraction du système mais une copie exacte qui tourne dans un environnement différent (device, hardware, OS, ...).
Emulation $\neq$ Simulation

### Montecarlo (Simulation)

Répéter une expérience aléatoire plusieurs fois en observant le résultat à chaque fois.
*Hypothèse* Le comportment du système ne bouge pas au cours du temps

### Simulation à événement discret
3 notions de base:
- *Entité* : tous les objets qui font partie du système
- *Etat du système* : l'ensemble des variables qui permettent de déterminer l'état actuel du système
- *Evénement* : n'importe quelle action qui permet de changer l'état du système

On modélise le système comme une suite d'événements chronologiques. Les changements d'état sont discrets dans le temps.

2 types de simulateurs à événement discret :
- **Time-driven** : le temps évolue à intervalle réguliers. Les événements sont synchros avec ces intervalles de temps. On utilise des time-slots. Problème, cette méthode n'est pas très flexible. Si le time-slot est trop petit on va perdre beaucoup de temps en idle, s'il est trop grand on peut perdre une transmission.


- **Event-driven** : Les changements d'état se font au moment où l'événement se produit. S'adapte mieux aux systèmes mais plus compliqué à coder.


2 façons d'injecter des événements dans notre système :
- **Trace-based** *(une trace)*: une suite d'événements ordonnés dans le temps (obtenu via une observation réelle ou générée par un autre simulateur)
- :heavy_plus_sign: Haut réalisme
- :heavy_minus_sign: Plus coûteux
- :heavy_minus_sign: Moins réaliste
- **Processus stochastique** : Utilisation d'une loi de probabilité en entrée (ex: loi de Poisson)
- :heavy_plus_sign: génération rapide d'une grande quantité d'événements
- :heavy_minus_sign: Besoin de valider les hypothèses liées au processus stochastique

## Event-Driven Simulation

### Elements clés

#### Temps système
Temps simulé (*ex : je simule 4h de fonctionnement du système*) $\neq$ Temps d'exécution (Durée de la simulation)

#### Evénement
La structure d'un événement est constitué d'un:
- Type : Représente l'action qui va être effectuée
- Temps : Moment d'apparition de l'événement
- Pointeur : Utilisé pour construire la FES

#### FES (*Future Event Set / File des événements futurs*)
FES : File des événements futurs, File des éléments ordonnés dans le temps simulé
FES a 2 primitives :
- *get* : je vais chercher le prochain événement
- *schedule* : je planifie le prochain événement

3 façons d'implémenter la FES :
- **Liste chaînée** : Coût max en complexité : $O(N)$ pour l'insertion et $O(1)$ pour l'extraction


- **Multiples listes chaînées** : Coût max en complexité : $O(N_i)$ pour l'insertion (où $N_i$ est le nombres d'événements de type i présents dans la FES) et $O(1)$ pour l'extraction


- **Tas** (*Arbre ayant pour clé une valeur toujours inférieure à la clé de ses enfants, avec max 2 enfants*) : coût d'insertion $O(log_2N)$, coût d'extraction $O(log_2N)$ car si on retire la racine, il faut réorganiser l'arbre en entier sinon il ne ressemble plus à rien


:arrow_right: **Conclusion** : si petit système, il vaut mieux prendre la liste chaînée, sinon il faut prendre la structure en tas car moins complexe à calculer pour le processeur

#### Event loop
Cycle qui performe à chaque opération :
- Extraction du prochain événement
- Mise à jour du temps système
- Exécution d'une action associée à l'événement

*NB : Pendant le traitement d'un événement, on peut insérer un autre événement.*

Conditions de fin :
- La FES est vide
- Le temps simulé est assez grand
- Le nombre d'événements simulé est assez grand
- Un certain événément a été simulé
- Une anomalie s'est produite

*Voir exemple d'exécution dans les slides*

#### Eléments additionnels

##### Data collection routines

*Objectif* : Quelles données mesurer et comment ?

Exemples de données mesurées en telecom :
- Appels bloqués
- Utilisateurs actifs
- Nombre moyen de paquets dans le système

:warning: *Lorsque l'on fait la moyenne du nombre d'événements sur un intervalle de temps, il faut la pondérer et considérer aussi le temps où y a rien qui se passe dedans.*

Différents types de mesure en fontion du niveau de détail :
- Une seule valeur
- Une moyenne
- Une distribution

##### Intervalle de confiance

Définition : La moyenne a 95% de chances de se trouver dans cette intervalle

*Démonstration dans les slides*