Upload
gilles-samba
View
5.882
Download
4
Embed Size (px)
Citation preview
Simulations de Réseaux !!!!!!!!!
jeudi 14 mai 2009
• Modélisation des systèmes
• Simulation à événements discrets
• Intervalles de confiances
• Les simulateurs
• Exemple de simulation
• Conseils
jeudi 14 mai 2009
Modélisation des systèmes
jeudi 14 mai 2009
• Quand on ne peut pas facilement observer les états du système,
• Quand on désire analyser l’enchaînement des événements dans le système, ainsi que les relations de causes à effets,
• Quand on désire valider une solution analytique,
• Quand la complexité des interactions dans le système est telle quelle ne peut être étudiée qu'au travers de simulations,
• Quand on désire visualiser les états d'un système,
• Quand on veut tester différentes optimisations pour améliorer un système déjà existant.
Intérêt de la simulation ?
jeudi 14 mai 2009
• Quand il y a une solution analytique ?
• Quand il est plus facile de faire directement des mesures sur le système réel ?
• Quand il manque trop des données sur les systèmes à étudier ?
• Quand on ne peut pas valider les résultats de simulations ?
• Quand le système a étudier est trop complexe ?
Les simulations sont elles toujours utiles ?
jeudi 14 mai 2009
Avantages /Inconvénients• Avantages
• Observations des états du systèmes,
• Etudes des points de fonctionnement d'un système,
• Etudes de systèmes à échelle de temps variable,
• Etudes de l'impact des variables sur les performances du système,
• Etude d'un système sans les contraintes matérielles.
• Inconvénients
• La conception de modèles peut nécessiter des compétences spéciales,
• Une autre forme d'analyse plus proche de la réalité est peut être nécessaire
• Résultats difficilement interprétables :
• Résultats pas forcément généralisable,
• Résultats sont fonction des entrées du système
jeudi 14 mai 2009
Types de modèles(1/2)Classification des modèles
jeudi 14 mai 2009
Types de modèles(2/2)• Simulations statiques
• Monte Carlo: méthode applicable seulement si le temps n'a pas d'influence (Von Neumann & Ulam, projet Manathan), utilise des tirages aléatoires et souvent uniformes
• Simulations dynamiques
• Système qui change dans le temps
• Simulations Déterministes
• Qui ne contient pas de variable aléatoire, une variable d'entrée donnée, produit toujours le même résultat
• Simulations Stochastiques
• Entrées et sorties sont aléatoires
jeudi 14 mai 2009
Exemples• Files d'attente
• Variable d'état : temps d'attente
• Réponse : Discret, Stochastique, Dynamique
• Machines de production
• Variable d'état: occupé, en attente, en panne
• Réponse : Discret, Stochastique, Dynamique
• Bruits d'un systèmes électronique
• Variable d'état: niveau de bruit
• Réponse : Continue, Stochastique, Statiquejeudi 14 mai 2009
Simulation à événements discrets
jeudi 14 mai 2009
• Utilisation d'un ordonnanceur comme élément de base du simulateur,
• Chaque événement représente un changement d'état, couplé avec une variable qui indique le temps auquel l'événement aura lieu,
• Ordonnanceur, gère une liste d'événements triés selon leurs date de déclenchement,
• Lorsque que l'ordonnanceur exécute un événement, il modifie la variable représentant le temps courant.
Simulations à événements discrets (1/3)
jeudi 14 mai 2009
Simulations à événements discrets (2/3)
jeudi 14 mai 2009
Simulations à événements discrets (3/3)
L'unité de traitement ne modifie jamais le firetime
jeudi 14 mai 2009
Exemple
jeudi 14 mai 2009
• Les simulateurs les plus couramment utilisés dans le domaine des réseaux, mais d'autres types de simulateurs existent :
• Simulateur à pas fixes,
• Simulateur de modèle fluide.
• Les simulateurs à pas fixes sont peu utilisés car gourmands en ressources,
• Simulateur de modèle fluide, nécessite la connaissance d'équations différentielles permettant de calculer les évolutions du système
Simulations à événements discrets (1/3)
jeudi 14 mai 2009
• Les simulateurs à pas fixe, scrutent l'évolution du systèmes entre deux incréments de temps,
• Nécessitent de balayer tous les intervalles de temps
• Beaucoup plus coûteux que de sauter d'événements en événements
• Simulent le système même quand il ne se passe rien
• Très peu utilisés de nos jours
• Simplicité d'utilisation
Simulations à événements discrets (2/3)
jeudi 14 mai 2009
• Les simulations avec des modèles fluides, ne sont pas encore beaucoup développées
• N2NSoft (Baccelli)
• Alcatel : réseaux d'accès ADSL
• TCP peut être modélisé par un systèmes d'équations différentielles (TCP Vegas)
• Plus besoin de modélisation au niveau paquets pour avoir des résultats précis
Simulations à événements discrets (3/3)
F. BACCELLI, D. HONGInteraction of TCP flows as Billiards,IEEE/ACM Transactions on Networking (2005) 13, 4
jeudi 14 mai 2009
Simulateur de réseaux sans fil
jeudi 14 mai 2009
Intervalles de confiances
jeudi 14 mai 2009
Intervalles de confiances
f = mx
jeudi 14 mai 2009
Intervalles de confiances (iid)X = X1, X2, ....Xn
µ̂n =1n
n!
i=1
Xi
!̂2n =
1n! 1
n!
i=1
(Xi ! µ̂n)2
µ̂n ± !"̂2
n!n
Les intervalles de confiances sont de :
! est le (1! "/2) quantile de la distribution de Student tn!1
jeudi 14 mai 2009
Intervalles de confiances (iid)
Zi =1m
m!
j=1
Z2(i!1)+j
Z̄b =1b
b!
j=1
Zj
!̂2b =
1b! 1
b!
j=1
(Zi ! Z̄b)2
Z̄b ± !
!"̂2
b
b
Les intervalles de confiances sont de :
Méthode Batch Mean divise les échantillons en b bloc de taille m
! est le (1! "/2) quantile de la distribution de Student tb!1
jeudi 14 mai 2009
Intervalles de confiances (non iid)
Z̄b ± !T
!T = 4.5!
"̂2b
"b
n
Méthode Batch Mean, Legal avec intervalles de confiances à 95%
Ne prend pas comme hypothèse que la moyenne des blocs est i.i.d, distribution à queue lourde, processus
avec mémoire...etc
jeudi 14 mai 2009
Exemple
jeudi 14 mai 2009
Quantile – Quantile Plot ou test de conformité empirique (2/2)
• Il est parfois nécessaire de déterminer ou de caractériser la distribution des résultats obtenus :
• Est ce que les données sont i.i.d selon une loi normale ?
• Vérification rapide Quantile Plot
• Le alpha quantile d'une distribution de probabilité est la valeur telle que la probabilité qu'une variable aléatoire suivant cette distribution lui soit inférieure ou égale vaut alpha. Bien entendu, alpha doit être compris entre 0 et 1, puisqu'il représente une probabilité
jeudi 14 mai 2009
Quantile – Quantile Plot ou test de conformité empirique (2/2)
jeudi 14 mai 2009
Conclusion
• Calculer l'intervalle de confiance permet de connaître la valeur de l'imprécision de mesure,
• Il permet de stopper des simulations quand la précision voulue est atteinte (je veux la moyenne avec une précision de +/0.01)
• Valider qualitativement la valeur du résultat qu’on a obtenu,
• Sur une échelle de 0 à 10 j'obtiens une moyenne de 5 avec un intervalle de confiance de +/3 !!!!!
jeudi 14 mai 2009
Simulateurs
jeudi 14 mai 2009
Simulateurs
• NS-2, SNS (NS distribué)
• Jist + Swans (nouveau)
• Jsim (nouveau)
• Qualnet, Glomosim (performant)
• Opnet (nombreux modèles)
jeudi 14 mai 2009
Pourquoi NS-2• NS est le système
de référence
• Un outil libre
• Ajout de composants à la demande
• Développement orienté objets
• Un logiciel de simulation multicouche
• Interface OTcl
• Un noyau en C++ (scheduler...)
• Couches réseaux codées en C++
jeudi 14 mai 2009
Simulations• Support: Lan,
Mobile, satellite, ATM
• IntServ/DiffServ
• Multicast
• Ad hoc
• Transport
• TCP
• Contrôle de congestion
• Application
• Web cache
• Multimédia
jeudi 14 mai 2009
Simulations• Implémentation en C++
• Scénario en Otcl
• Test de simulation avec Nam
• Résultat, post processing :
• perl
• awk
• gnuplot
• xgraph
jeudi 14 mai 2009
Simulations• NS exécute la simulation, NAM visualisation de la
simulation
• Gnuplot, Xgraph, Tracegraph, interprétation des résultats
jeudi 14 mai 2009
Structure de NS-2
jeudi 14 mai 2009
Les composants de NS-2• Ns, Le simulateur
• Nam, the network animator
• Visualise les fichiers de trace de NS
• Nam editor: GUI pour générer des scripts NS
• Pre-processing:
• Générateur de trafic et topologie (setdest)
• Post-processing:
• Analyse des fichiers de trace, Awk, Perl, ou Tcl
jeudi 14 mai 2009
• Modèle de trafic:
• Web, FTP, telnet, constant-bit rate, real audio
• Protocole de la couche transport :
• Unicast: TCP (Reno, Vegas, etc.), UDP
• Multicast: SRM
• Routage et file d’attente:
• Routage (distance vector , link state), ad hoc (dsr, aodv)
• Discipline de file d’attente: RED, drop-tail, etc
• Liens physiques:
• Filaire (point-to-point, LANs), wireless (propagation multiple), satellite
jeudi 14 mai 2009
Classes du Simulateur• Application
• Générateur de trafic
• Agent
• Protocoles
• Nœud
• Nœuds du réseau
• Link
• Liens entre les noeuds
• Monitor
• Elaboration de statistique sur un lien particulier
jeudi 14 mai 2009
Anatomie d’une simulation
jeudi 14 mai 2009
Interface OTcl• Contrôle la simulation
• Un composant du simulateur
• Interaction avec le simulateur
• Les principales classes sont dans l’interpréteur
• Manipulation (création, connections …) des classes du simulateur
jeudi 14 mai 2009
Otcl (1/3)• Instantiation
• set Obj [new Class]
• Méthode
• $Obj Methode arg1 arg2
• Commande
• [<commande>]
jeudi 14 mai 2009
Otcl (2/3)• Fonction
proc printArg {nom} { puts “hello $nom“}
jeudi 14 mai 2009
• constructeur
Class Person# constructeur:Person instproc init {age} { $self instvar age_ set age_ $age}# méthode:Person instproc greet {} { $self instvar age_ puts “$age_ years old: How are you doing?”}
# subclass:Class Kid - superclass PersonKid instproc greet {} { $self instvar age_ puts “$age_ years old kid: What’s up, dude?”
}
set a [new Person 45]set b [new Kid 15]$a greet$b greet
jeudi 14 mai 2009
Evenements• Crée l’ordonnanceur
• set ns [new Simulator]
• Ordonnance les événements
• $ns at <time> <event>
• <event>: une commande tcl
• $ns at 5.0 “finish”
• Lance le l’ordonnanceur
• $ns runjeudi 14 mai 2009
Topologie• Nœuds
• set n0 [$ns node]
• set n1 [$ns node]
• Liens et discipline de file d'attente
• $ns <liens> $n0 $n1 <bande passante> <délai> <queue>
• <type de lien>: duplex-link, simplex-link
• <type de queue>: DropTail, RED, CBQ, FQ, SFQ, DRR, diffserv RED queues
jeudi 14 mai 2009
Trafic (1/3)• Exponentielle, on-off
• set src [new Application/Traffic/Exponential]
• set src [new Application/Traffic/Pareto]
• UDP
• set udp [new Agent/UDP]
• set null [new Agent/Null]
• $ns attach-agent $n0 $udp
• $ns attach-agent $n1 $null
• $ns connect $udp $null
jeudi 14 mai 2009
Trafic (2/3)
• CBR
• set src [new Application/Traffic/CBR]
• $src set packetSize_ 1500
• $src set rate_ 100Kb
jeudi 14 mai 2009
Trafic (2/3)• TCP
• set tcp [new Agent/TCP]
• set tcpsink [new Agent/TCPSink]
• $ns attach-agent $n0 $tcp
• $ns attach-agent $n1 $tcpsink
• $ns connect $tcp $tcpsink
• FTP
• set ftp [new Application/FTP]
• $ftp attach-agent $tcp
• Telnet
• set telnet [newApplication/Telnet]
• $telnet attach-agent $tcp
jeudi 14 mai 2009
Monitor (1/2)• Monitor flow
• $tcp fid_ 1;
• set flowmon [$ns makeflowmon Fid]
• set lien [$ns link $n0 $n1]
• $ns attach-fmon $lien $flowmon
• set fcl [$flowmon classifier]
• %%% dans FINISH %%%
• set stats_tcp [$fcl lookup auto 0 0 1]
• set bw [$stats_tcp set bdepartures_]
jeudi 14 mai 2009
Monitor (2/2)• Monitor queue
• set monitor [ $ns queue-monitor $n0 $n1 stdout]
• puts stdout “[ $monitor set pdepartures_ ]”
• puts stdout “[ $monitor set barrivals_ ]”
• puts stdout “[ $monitor set pdrops]”jeudi 14 mai 2009
Exemple de simulation
jeudi 14 mai 2009
Simulation (1/3)
• Trafic CBR
• Protocole UDP
• Lien 1Mb, discipline de file d ’attente FIFO
• Délai 10ms
jeudi 14 mai 2009
Simulation (2/3)#creation de l ’instance de simulationset ns [new Simulator]#creation des fichier de trace set nf [open out.nam w]$ns namtrace-all $nf proc finish {} { global ns nf $ns flush-trace close $nf exec nam out.nam & exit 0} #scheduler$ns at 5.0 "finish"#lancement de la simulation $ns run
jeudi 14 mai 2009
Simulation (3/3)set n0 [$ns node]set n1 [$ns node] $ns duplex-link $n0 $n1 1Mb 10ms DropTail set udp0 [new Agent/UDP]$ns attach-agent $n0 $udp0set cbr0 [new Application/Traffic/CBR]$cbr0 attach-agent $udp0 set null0 [new Agent/Null] $ns attach-agent $n1 $null0 $ns connect $udp0 $null0 $ns at 0.5 "$cbr0 start"$ns at 4.5 "$cbr0 stop"
jeudi 14 mai 2009
Conseils
jeudi 14 mai 2009
TopologieDumbbell
évaluation de paramètres de bout en bout
Parking Lot
évaluation de paramètres changeant, RTT, équité ...etc
jeudi 14 mai 2009
Conseils• Paramètres importants
• taille de la fenêtre TCP, MAX RTT ne doit pas être limitatif
• TCP “flavor”
• Taille des files d'attente (delais*BP)
• Active queue Management
• Problèmes
• Durée des simulations
• Topologie
• RTT
jeudi 14 mai 2009
Références• [1] Mark Allman, Aron Falk, “On the Effective Evaluation of TCP,”
ACM Computer Communication review, vol. 25, no. 5, pp. 59 - 70, 1999.
• [2] Sally Floyd and Vern Paxson, “Difficulties of simulating the Internet,” IEEE/ACM transaction on networking, vol. 9, no. 4, pp 392-403, 2001.
• [3] Sally floyd and Eddie Kohler, “Internet Research Needs Better Models,” ACM Hotnets-1, October, 2002.
• [4] http://www.icir.org/models/bettermodels.html
• [5] V. Gauthier, S. Gam, "Les simulateurs", Chapter of the book "Simulations des Réseaux (Traité IC2, série Réseaux et télécoms)", Editor: Monique Becker, Andre Luc Beylot, chapter 7, Hermes, 2006, ISBN 2-7462-1166-1.
jeudi 14 mai 2009
Références• [6] S. Kurkowski, T. Camp and M. Colagrosso, "MANET simulation
studies: the incredibles," in SIGMOBILE Mobile Computer Communication Revenue, vol. 9, no. 4, pp. 50 - 61, 2005.
• [7] D. Cavin, Y. Sasson and A. Schiper, "On the accuracy of MANET simulators," In Proc of the Workshop on Principles of Mobile Computing (POMC’02), Toulouse, France, October , 2002, pp. 38-43.
• [8] Jean-Yves Le Boudec, "Performance Evaluation Lecture Notes (Methods, Practice and Theory for the Performance Evaluation of Computer and Communication Systems)", http://icawww.epfl.ch/perfval/lectureNotes.html
• [9] Averill M. Law and W. David Kelton, "Simulation Modeling and Analysis, 3/e”, Mac Graw Hill, 2000.
• [10] F. Baccelli, D. Hong, "Interaction of TCP flows as Billiards," IEEE/ACM Transactions on Networking, vol. 13, no. 4, 2005.
jeudi 14 mai 2009