Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Fondements sur la modélisation des réseaux (24h, 3 ECTS)

Responsables : François Baccelli et Jean Mairesse

Objectifs

Le but de ce cours est double :

  • proposer des modèles mathématiques pertinents pour les réseaux de communications;
  • donner les bases théoriques permettant de mener à bien l'analyse de la dynamique de ces modèles.

Le cours est structuré en thèmes, pouvant être plus ou moins développés suivant les années :

  • Réseaux de files d'attente et modélisation markovienne (réseaux à commutation de paquets, réseaux à commutation de circuits);
  • Optimisation et théorie des jeux pour les réseaux (contrôle optimal stochastique, programmation dynamique, jeux de routage, etc.);
  • Dynamique des systèmes à événements discrets temporisés (semi-anneau max plus, inf convolutions, fonctions topicales, réseaux de Petri temporisés, modèles d'empilements de pièces, etc.);
  • Contrôle de flux dans les réseaux de communication (TCP, contrôle de flux et de congestion, régulation, network calculus, ordonnancement etc.);
  • Graphes aléatoires (à la Erdos-Renyi), modèles de géométrie aléatoire (modèles de couverture, percolation) en relation avec la modélisation des réseaux de communication radio.

Plan du cours et intervenants prévus pour 2014-2015

Le cours sera structuré en 10 séances de 2.30 chacune. Le cours a lieu le lundi de 8.45 a 11.15 en période 2 (première séance: à déterminer).

Lieu: Batiment Sophie Germain, salle 1008. Le cours aura lieu en anglais si un ou plusieurs étudiants le demandent et en français sinon.

Le programme est le suivant (en construction):

  1. Réseaux markoviens à forme produit et applications (10h, A. Bušić);
  2. Contrôle optimal stochastique pour les réseaux (10h, A. Jean-Marie);

Résumé des cours 2014-2015

1. Chaînes de Markov en temps continu : probabilités transitoires et stationnaires; réversibilité. Simulation des systèmes à événements discrets et les chaînes de Markov : Génération des variables aléatoires (méthode d'inverse et méthode de rejet). Du temps discret vers le temps continu; réversibilité.

2. Partage de ressources et des files d'attente. Théorie des files d'attente et files d'attente Markoviennes. Réseaux Markoviens à forme produit: réseaux de Jackson et de Kelly (réseaux à commutation de paquets et à commutation de circuits). Schémas de Matthes ; exemples (file d'attente ; réseaux de Jackson ; trafic http).

3. Ordonnancement et MaxWeight

4. Controle optimal pour les réseaux. Equation de Bellman et programmation dynamique. Application au problème du routage (“c.mu rule”, suites billard, politiques d'indice).

5. Optimisation et chaines de Markov. Echantillonage de Gibbs. Chaines de Markov perturbées. Application au routage.

Planning du cours

1. 9/12 –> A. Bušić: chaines de Markov, temps discret, temps continu

2. 16/12 –> pas de cours

3. 6/01 –> A. Bušić: réseaux Markoviens, les bases

4. 13/01 –> A. Bušić: réseaux Markoviens, suite

5. 20/01 –> A. Jean-Marie: contrôle stochastique, les bases

6. 27/01 –> A. Jean-Marie: contrôle stochastique, suite

7. 03/02 –> A. Jean-Marie: applications

8. 10/02 –> A. Bušić: applications

9. 17/02 –> A. Jean-Marie: applications

10. 24/02 –> A. Bušić: séance d'exercices (en fonction de la demande)

Examen : 10/03/2015 9h salle 1008. Documents autorisés: 2 feuilles A4 R/V avec des notes.

Page Web courante du cours

Sur cette page, vous trouverez des informations sur les examens, des documents pédagogiques, des feuilles d'exercices: http://www.liafa.univ-paris-diderot.fr/~mairesse/MPRI/

Pré-requis

Une familiarité avec les probabilités discrètes et les chaînes de Markov, est préférable sans être obligatoire. (En particulier, le cours commencera par des éléments sur les processus de Markov à temps continu. Ce qui permettra au passage de voir ou de revoir les notions de base sur les chaines de Markov à temps discret.)

Bibliographie

  • Reversibility and Stochastic Networks, F. Kelly, Wiley, 1979.
  • Markov Decision Processes: Discrete Stochastic Dynamic Programming (2nd edition), M. Puterman, Wiley, 2005.
  • Population Games and Evolutionary Dynamics, W. Sandholm, MIT Press, 2010.

Les années précédentes

Équipe pédagogique

Ana BusicCRINRIAhttp://www.di.ens.fr/~busic/
Alain Jean-MarieDRINRIAhttp://www.lirmm.fr/~ajm/index.html