Responsables : François Baccelli et Jean Mairesse

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.

Le cours sera structuré en 10 séances de 2.30 chacun. Le cours a lieu le lundi de 13.15 a 15.45 en période 2 (première séance le 10 décembre).

Le cours aura lieu a Chevaleret, salle 1E01 jusqu'à fin 2012, et Batiment Sophie Germain, salle 108, à partir de début 2013. Le cours aura lieu en anglais si un ou plusieurs étudiants le demandent et en français sinon.

Le programme est le suivant :

1. Réseaux markoviens à forme produit (7h30, J. Mairesse);
2. Controle optimal pour les réseaux (7h30, B. Gaujal);
3. Théorie des jeux pour les réseaux (5h, B. Gaujal);
4. Optimisation et chaines de Markov, (5h, J. Mairesse).

1. Réseaux markoviens de files d'attente à forme produit. Chaînes de Markov en temps continu : probabilités transitoires et stationnaires; réversibilité. Principes généraux de la 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).

2. 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).

3. Théorie des jeux dans les réseaux. Jeux atomiques et non-atomiques (équilibre de Nash/Wardrop). Prix de l'anarchie dans les jeux de routage, paradoxe de Braess. La neutralité de l'internet ?

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

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/

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.)

• 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.

• Année 2011-2012
• Année 2010-2011
• Année 2009-2010
• Année 2008-2009