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)

Responsable : 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.

Organisation du cours, évaluation, intervenants 2017-2018

Horaire: Le cours sera structuré en 10 séances de 2h30 chacune. Il aura lieu le vendredi de 16:15 a 18:45 en période 2 (première séance: 8 décembre).

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

Évaluation: la note du cours sera basée sur trois devoirs

  1. Deux devoirs à la maison (20% chacun)
  2. Un devoir surveillé de 3h (60%)

Le programme et les intervenants:

  1. Réseaux markoviens à forme produit et applications (12,5h, B. Gaujal);
  2. Contrôle optimal stochastique pour les réseaux (12,5h, A. Busic).

Résumé des cours 2016-2017

Le cours se présente en deux parties. Ces deux parties sont relativement indépendantes mais font référence l'une a l'autre.

Partie 1: Réseaux Aléatoires

1. Modélisation et simulation de systèmes à événements discrets : schéma de Matthès, application

2. Chaînes de Markov à temps continu, résultats principaux, lien avec les chaînes de Markov à temps discret

3. Théorie des files d'attente : M/M/1, M/G/1, loi de Little, insensibilité

4. Réseaux à forme produit : réseaux de Jackson et de Kelly (réseaux à commutation de paquets et à commutation de circuits)

5. Étude de quelques protocoles d'ordonnancement.

Partie 2: Contrôle Optimal des Réseaux

1. Questions de contrôle optimal pour les réseaux

2. Théorie du contrôle optimal stochastique. Équation de Bellman et programmation dynamique.

3. Les politiques à seuil. Les politiques à indice.

4. Exemples et illustrations.

Planning du cours

* 08/12/17 Bruno Gaujal 1

* 15/12/17 Bruno Gaujal 2

* 22/12/17 Ana Busic 1

* 12/01/18 Ana Busic 2

* 19/01/18 Bruno Gaujal 3

* 26/01/18 Bruno Gaujal 4

* 02/02/18 Bruno Gaujal 5

* 09/02/18 Ana Busic 3

* 16/02/18 Ana Busic 4

* 23/02/18 Ana Busic 5

* 09/03/18 Exam (à confirmer)

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.di.ens.fr/~busic/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

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA