Intitulé du module :
Modélisation et Evaluation
de Performances des Systèmes (MEPS)
Filières de la Maîtrise d’Informatique faisant
appel au module :
La modélisation et l’évaluation de performance est indispensable à toute mise en œuvre d’un système réel et peut donc être considérée comme une annexe utile aux différents modules :
Architecture des processeurs
Noyaux des Systèmes
Architecture des réseaux
Systèmes répartis et Middleware
1. Objectif
L'objectif de ce module est de sensibiliser les étudiants aux problèmes de modélisation et d'évaluation des performances des systèmes réels tels les systèmes informatiques, les réseaux de communication et les systèmes de production. Il se propose de répondre aux questions suivantes : Pourquoi évaluer les performances d'un système ? Dans quels cas cela est-il nécessaire ? Comment modéliser un système ? Quel type de modèle utiliser ? Comment analyser le modèle ? Dans quels cas utiliser des méthodes analytiques ou des techniques de simulation ?
Dans ce module, on s'intéressera à la fois aux aspects méthodologiques, aux outils mathématiques, aux techniques de simulation et à des applications spécifiques de l'évaluation de performances. Le domaine d’application privilégié est celui des réseaux de communication.
2. Programme
2.1.
Présentation générale
- Problématique de l'évaluation de performances
- Modèles simples à base de Chaînes de Markov
- Modèles plus complexes de type Files d'attente
- Vie quotidienne
- Réseaux
- Systèmes informatiques
- Systèmes de production
- Analyse :
- Chaînes de Markov
- Files d'attente simples
- Réseaux de files d'attente à forme produit
- Généralités sur la simulation
- Simulateur NS (Network Simulator)
2.2.
Cursus détaillé
11 cours :
Rappel de probabilités / Variables aléatoires / Processus stochastiques
cours 2 et 3 : Modélisation par Chaînes de Markov
- Temps discret / continu
- Outil simple de modélisation et d’analyse des systèmes
- Préliminaire nécessaire à l’analyse des files d’attente
- Nombreux exemples :
• Mécanismes de contrôle de flux et d’admission dans les réseaux, leaky bucket
• Central téléphonique et commutateurs
• Problèmes de partage de ressources système
• Problèmes de fiabilité dans les systèmes de production
• Systèmes de production à flux tendu
cours 4 : Le formalisme « Files d’attente »
- Présentation détaillée du formalisme
• Files simples
• Réseaux de files d’attente
- Exemple de modèles simples
• Réseaux de communication
• Systèmes informatiques
• Systèmes de production
cours 5 : Evaluation de performance :
- « Analyse stochastique » versus « Analyse opérationelle »
- Notion de « Stabilité » et d’ « Ergodicité »
- Etude analytique et simulation
cours 6 et 7 : Les files simples
- Les files markoviennes : M/M/1, M/M/1/K, M/M/C, etc.
• Ressource système : M/M/1
• Atelier de production : M/M/1/K
• Central téléphonique : M/M/C
- Les files à lois générales : M/G/1 et G/M/1
- Les extensions : représentation par des lois de type phase
cours 8 et 9 : Les réseaux de file d’attente à forme produit
- Les réseaux ouverts (Jackson)
- Les réseaux fermés (Gordon et Newell)
• Algorithmes de convolution
• Algorithmes MVA
- Modélisation de systèmes plus complexes (ouverts et fermés) :
• Réseaux de communication constitué de plusieurs lignes et commutateurs
• Tâches d’un système informatique dont l’activité correspond à l’accès à une succession de ressources
• Ateliers de production
Présentation de l’outil de simulation NS (Network Simulator)
- Architecture logicielle
- Utilisation
11 TD :
TD 1 : Probabilités / Variables aléatoires / Processus stochastiques
TD 2 : Modélisation par chaînes de Markov à temps discret
TD 3 : Modélisation par chaînes de Markov à temps continu
TD 4 : Modélisation par files markoviennes
TD 5 : Les files M/G/1 et G/M/1
TD 6 : Les extensions des files M/G/1 et G/M/1
TD 7 : Les réseaux de files d’attente ouverts
TD 8 : Les réseaux de files d’attente fermés
TD 9 (sur machine) : Prise en main de l’outil de Simulation NS
TD 10 (sur machine) : Ecriture de composants de simulation en C++ :
Leaky bucket, contrôle de flux par fenêtre, partage de ressources
TD 11 (sur machine) : Réalisation d’un modèle Réseau
3. Organisation
3.1.
Responsable pédagogique
B. BAYNAT, Maître de Conférences Paris 6
3.2.
Equipe pédagogique
P. ANELLI, Maître
de Conférences Paris 6
B. BAYNAT, Maître
de Conférences Paris 6
C. DUTHEILLET, Maître de Conférences Paris 6
3.3.
Effectif étudiant
3.3.1. Effectif attendu
2 groupes de TD, soit une cinquantaine d’étudiants.
3.3.2. Effectif maximum encadrable
4 groupes de TD, soit plus d’une centaine d’étudiants.
3.4.
Stages
Aucun stage prévu.
3.5.
Moyens en salles pour les cours, TD et TP
- Un amphi pour le cours, muni d’un rétro-projecteur
- Une salle de TD pour chacun des groupes
- Une ou deux salles de TP pour chacun des groupes (2 étudiants max par machine)
3.6.
Moyens informatiques
3.6.1. Matériels
Des machines Unix suffisamment puissantes pour faire tourner le logiciel de simulation NS, très gourmand en ressources CPU.
3.6.2. Logiciels
Le logiciel de simulation NS (Network Simulator) orienté Réseaux, du domaine public.
3.7.
Contrôle des connaissances
- 60 % : examen final
- 40 % : contrôle continu
- 20 % : note de TD, interrogations en amphi, devoir à rendre
- 20 % : mini-projet de simulation
3.8.
" Points capitalisables "
7 points capitalisables ?
4. Profil de compétences à l’entrée
(pré-compétences)
4.1.
Savoirs scientifiques et techniques de l’Informatique
- Notions avancées de Réseaux (M)
- Notions de base de programmation en C (N)
- Notions de base de Shell Unix (N)
4.2.
Autres savoirs
- Mathématiques :
- Probabilités / Variables aléatoires / Processus stochastiques (M)
- Algébrique : Intégration / Dérivation / Décomposition en éléments simples (M)
- Statistiques de base : Moyenne, Ecart-type, etc. (N)
4.3.
Savoir-faire techniques
- Utilisation d’un environnement logiciel sous Unix (M)
- Capacité d’apprentissage d’un langage de simulation (Network Simulator) (N)
4.4.
Savoir-faire généraux
- Savoir réfléchir !
5. Profil de compétences à la sortie
(post-compétences)
5.1.
Savoirs scientifiques et techniques de l’Informatique
- Comprendre la nécessité d’évaluer les performances d’un système
- dans une phase de conception
- dans une phase d’exploitation (dans des conditions anormales de fonctionnement)
- Ebauche de méthodologie de modélisation des systèmes informatiques et des réseaux
- Comprendre les points forts / faibles des techniques analytiques et de la simulation
- Etude analytique des performances d’un modèle de type file d’attente
- Etude par simulation des performances d’un réseau de communication
5.2.
Autres savoirs
- Quelques notions économiques (liées aux sous / sur-dimensionnement de systèmes)
5.3.
Savoir-faire techniques
- Utilisation d’un logiciel de simulation
5.4.
Savoir-faire généraux
- Comprendre qu’il est préférable de bien réfléchir à un problème avant de s’y atteler !
6. Commentaires
Bibliographie conseillée
[BAY 00] Baynat B., Théorie des files d’attente, des chaînes de Markov aux réseaux à forme
produit, Hermes science publications, Paris , 2000.
[GRO 85] Gross D. et Harris C.M., Fundamentals
of Queueing Theory, John Wiley, Chichester, New York, 1985.
[KLE 75] Kleinrock L., Queueing Systems, Volume 1: Theory, John Wiley, New York, London,
Sydney, Toronto, 1975.
[ROS 93] Ross S.M., Introduction to Probability Models, 5th edition,
Academic Press, New York, 1993.
[NS-2] Network Simulator, http://www.isi.edu/nsnam/