Ce cours a pour but de fournir au lecteur des outils pour mieux appréhender les réseaux au sens large, allant des réseaux de communications qui sous-tendent l'Internet aux réseaux sociaux (en ligne ou non).

Il s'agit de proposer :

  • des modèles des systèmes et des phénomènes d'intérêt,
  • des méthodes algorithmiques pour leur contrôle (idéalement décentralisé),
  • des outils mathématiques pour l’analyse du comportement et de la performance de ces systèmes.

Le plan sera le suivant :

  1. Allocation de ressources en réseaux : critères d’équité pour le contrôle de congestion. Algorithmes de gradient comme méthode de contrôle distribué. Interprétation du protocole TCP comme un tel algorithme. Outils : systèmes dynamiques, stabilité par méthode de Lyapunov, dualité Lagrangienne.
  2. Contrôle distribué d’accès aléatoire à un canal : protocoles randomisés de type Aloha et leur stabilité. Outils : Chaînes de Markov à temps discret, leur ergodicité, et le critère d’ergodicité de Foster-Lyapunov.
  3. Politiques d’ordonnancement stabilisantes pour les routeurs et les réseaux sans fils. Notion de région de stabilité. Modèle de switch généralisé, et stabilité optimale de la politique de poids maximal.  Politique de « back-pressure » pour les réseaux multi-bonds.
  4. Modélisation de systèmes de files d’attente à temps continu. Outils : processus de Poisson et ses propriétés fondamentales. Processus Markoviens de sauts (ergodicité et réversibilité). Le modèle d’Erlang de réseau à pertes.
  5. Réseaux de Jackson et files d’attente à priorités. Critère de Foster en temps continu. Modèle d’Internet avec allocation équitable de bande passante. Propriété de stabilité optimale des allocations équitables.
  6. Phénomènes épidémiques : modèle SI de propagation. Processus de branchement de Galton-Watson et transition de phase associée. Epidémie SIR, lien avec les graphes aléatoires d’Erdös-Rényi, et émergence du composant géant. Outils : inégalité de Chernoff.
  7. Emergence de la connectivité dans les graphes d’Erdös-Rényi. Propagations épidémiques sur des graphes généraux : impact de la topologie du graphe sur le comportement. Outils : approximation poissonnienne, constructions de couplage.
  8. Topologies de réseaux particulières : modèle de Barabasi-Albert d’attachement préférentiel et graphes en loi de puissance. Réseaux dits « navigables » et phénomène de petit monde. Outils : inégalité d’Azuma-Hoeffding.
  9. Détection de communautés. Modèle de graphe « stochastique par blocs ». Méthodes spectrales pour la reconstruction des communautés. Outils : contrôle de perturbation de spectre de matrices hermitiennes, contrôle de rayon spectral de matrices aléatoires.


Référence bibliographique :

"Réseaux : contrôle distribué et phénomènes émergents", Laurent Massoulié, 2016

Cours dispensé en anglais

Langue du cours : Anglais

Credits ECTS : 4