Master Parisien de Recherche en Informatique - M2
2-17-1 : Fondements sur la modélisation des réseaux
Description du cours
Suivre ce lien
Intervenants
Sous-ensemble des personnes suivantes :
Francois Baccelli,
Bruno Gaujal,
Alain Jean-Marie,
Jean Mairesse,
Laurent Massoulié
Planning du cours 2010-2011
Les cours ont lieu les vendredis de 16.15 à 18.45, au 45 rue d'Ulm
(ENS), salle R (2ieme sous-sol, aile Rataud).
- 17 septembre : Max-plus et Network calculus I
- 24 septembre : Max-plus et Network calculus II
- 1 octobre : Max-plus et Network calculus III
- 8 octobre : Max-plus et Network calculus IV
- 15 octobre : Max-plus et Network calculus V
- 22 octobre : Réseaux markoviens I
- 29 octobre : Réseaux markoviens II
- 5 novembre : Réseaux markoviens III
- 12 novembre : Réseaux markoviens IV
- 19 novembre : Réseaux markoviens V
- 26 novembre : Pas de cours
- 3 décembre : Examen (2h)
Résumé des cours 2010-2011
- 1. Réseaux Max-Plus et Network Calculus (J. Mairesse)
Ce cours a pour but de montrer comment une approche algébrique
(essentiellement en utilisant l'algèbre (max,plus)) des systèmes à
événements discrets permet de calculer certaines performances des
réseaux de communications.
On étudiera plus particulièrement le semi-anneau des matrices carrées
à coefficients dans (R,max,plus), qui permet de calculer les dates de
tirs de transitions dans les graphes d'événements sous forme de
récurrence d'un système linéaire, ainsi que le comportement
asymptotique d'un tel système, donné par le spectre (max,plus) de la
matrice itérée.
On étudiera aussi le semi-anneau des fonctions croissantes munies du
minimum point à point et de l'inf-convolution, qui permet de calculer
des bornes sur les délais et les tailles de buffers dans des réseaux
informatiques. Cette technique appelée le "network calculus" repose
sur la définition de fonctions de contrainte sur les processus
d'arrivées et les processus de service dans chaque noeud du réseau.
Des questions algorithmiques dans ces deux domaines seront abordées et
des applications au controle de fenetre dans les réseaux et à la
garantie de qualité de service pour les flux vidéo seront finalement
discutées.
- 2. Réseaux markoviens à forme produit (A. Jean-Marie)
Méthodologie de l'évaluation de la qualité de service dans les
réseaux. Théorie des files d'attente, principes généraux et
métriques. Chaines de Markov en temps continu. Probabilités
transitoires et stationnaires. Réversibilité. Files d'attente
Markoviennes. Réseaux de files d'attente a forme produit: réseaux de
Jackson et Kelly.
Examen
Support de cours - Feuilles d'exercice
- Réseaux Markoviens
Le support de cours d'Alain Jean-Marie (LIRMM, Montpellier), version
2010-2011 : suivez
ce lien.
Un autre support de cours de Philippe Bougerol (Laboratoire de
Probabilités, Paris 6). Le matériel est
globalement le même que celui du cours, mais la présentation
est différente.
Suivez ce
lien.
D'autres références :
Livre disponible en ligne :
Reversibility
and Stochastic Networks. F.P. Kelly, Wiley, 1979. (En
particulier les chapitres 1, 2, 3 et 4.)
Livres non-disponibles en ligne :
Perron-Frobenius : "Non-negative matrices and Markiv chains",
E. Seneta, Springer, 1981.
Markov : "Markov chains. Gibbs fields, Monte Carlo simulation, and
queues", P. Brémaud, Springer, 1999.
Pour les personnes ne disposant pas des bases en Probabilités,
un cours introductif de Jean Bertoin (Laboratoire de
Probabilités, Paris 6) :
suivez ce
lien.
- Réseaux Max-Plus
Feuille d'exercices : fichier.pdf.
Un support de cours de Jean Mairesse, la présentation et le
matériel sont un peu orthogonaux au cours oral : fichier.pdf (58 pages).
D'autres références :
Livre disponible en ligne :
Synchronization and linearity (F. Baccelli,
G. Cohen, G.J. Olsder, J.-P. Quadrat), Wiley, 1992.
Cours en ligne "Théorie algébrique des systèmes à événement discrets" par Guy
Cohen : Suivez ce
lien.
Stages
Plusieurs stages sont proposés dans le cadre du cours 2.17.1. A
titre indicatif, voici certains des stages proposés
dans le passé.
Les personnes intéréssées par
un stage peuvent s'adresser aux enseignants sans
attendre.