Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

Dynamique et algorithmique des réseaux (48h, 6 ECTS)

Responsables : François Baccelli et Jean Mairesse

Objectifs

Le but de ce cours est double :

• donner les bases scientifiques sur la théorie de la dynamique des réseaux ;
• illustrer cette théorie par des exemples concrets dans le domaine des communications.

Plan du cours et intervenants prévus pour 2007-2008

1. Réseaux markoviens à forme produit, (12h, F. Baccelli)
2. Réseaux Max-Plus et Network Calculus, (12h, J. Mairesse)
3. Algorithmique des réseaux (12h, L. Viennot)
4. Graphes aléatoires: pair-a-pair et épidémies, (12h, C. Magnien)

Résumé des cours 2007-2008

1. Réseaux markoviens à forme produit

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.

2. Réseaux Max-Plus et Network Calculus

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éenements 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.

3. Algorithmique des réseaux

- Routage : bases, itérations asynchrones, ad hoc réactif/proactif, analyse des routes obtenues par flooding. - Sous-topologies en adhoc (multipoints relais, connected dominating set), diffusion et link state optimisé - Sur-topologies : Tables de hachage distribuées, routage petit monde à la Kleinberg, arbres disjoints et streaming peer-to-peer. - Métriques : métriques doublantes et distances dans Internet.

4. Graphes aléatoires, analyse, modélisation et diffusion d'épidémies

La diffusion d'épidémies intéresse les informaticiens pour plusieurs raisons. Les virus et vers se propagent dans l'Internet de manière similaire à une épidémie "classique"; il en va de même pour la diffusion d'information dans certains réseaux sociaux, ou encore pair-à-pair.

Cette partie du cours introduira des modèles classiques d'épidémies. Le comportement d'épidémies sur un graphe complet sera étudié, en exploitant la relation entre ce comportement et les propriétés des graphes aléatoires d'Erdos-Renyi. En particulier, on analysera la taille des composantes connexes, la connectivité et le diamètre de ces graphes aléatoires.

Des modèles plus réalistes de topologies de réseaux seront introduits, en particulier le modèle de "petit monde" des physiciens Watts et Strogatz. Le modèle de graphes aléatoires "scale-free" de Barabasi et Albert sera aussi introduit, et on analysera comment un mécanisme d'attachement préférentiel conduit à une loi de puissance pour les degrés des noeuds du graphe.

On présentera également des résultats généraux sur le comportement d'épidémies sur un réseau de topologie arbitraire, montrant comment des descripteurs de la topologie tels que le "rayon spectral", et la "constante isopérimétrique" du réseau affectent le comportement d'épidémies.

Page Web courante du cours

Sur cette page, vous trouverez le plan détaillé du cours, des informations sur les examens, le travail de lecture d'articles, ainsi que des documents pédagogiques, des feuilles d'exercices... Lien vers la page

Plan du cours

Le cours est structuré en 5 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).
• 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 (graphe du web: page ranking, graphe d'Internet) et modèles d'épidemies (propagation d'informations ou de virus).
• Algorithmique des réseaux ad-hoc et pair-à-pair (routage dans les réseaux ad-hoc, recherche et échange de fichiers dans les réseaux pair-à-pair).

Pré-requis

Probabilités discrètes, chaînes de Markov, fonctions caractéristiques, simulation à événements discrets, graphes et algorithmes de graphes.

Bibliographie

• Simulation et Modélisation des Réseaux de Communication, F. Baccelli et P. Brémaud, Cours École Polytechnique 2002- 03.
• Synchronization and Linearity, F. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Wiley 1992.
• Data networks, D. Bertsekas and R. Gallager, Prentice Hall 1992.
• Performance Guarantees in Communication Networks, C.S. Chang, Springer Verlag, 1999.
• Statistical Mechanics of Complex Networks, Réka Albert and Albert-László Barabási. Reviews of Modern Physics 74, 47. 2002. http://arxiv.org/abs/cond-mat/0106096
• Random Graphs and Complex Networks. R. van der Hofstad. Material for the course: Information for Random Graphs and Complex Networks, available at http://www.win.tue.nl/~rhofstad/RGCN.html.

Les années précédentes

• Année 2009-2010
• Année 2008-2009
• Année 2007-2008
• Année 2006-2007

Équipe pédagogique