Descriptif
Ce cours a pour but de fournir 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.
Référence bibliographique :
"Réseaux : contrôle distribué et phénomènes émergents", Laurent Massoulié, 2016
Cours dispensé en anglais
effectifs minimal / maximal:
/56Diplôme(s) concerné(s)
- Programmes d'échange internationaux
- M1 Mathématiques Jacques Hadamard
- M1 Innovation, Entreprise et Société
- Titre d’Ingénieur diplômé de l’École polytechnique
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade réduitPour les étudiants du diplôme M1 Mathématiques Jacques Hadamard
L'UE est acquise si Note finale >= 10- Crédits ECTS acquis : 5 ECTS
Pour les étudiants du diplôme M1 Innovation, Entreprise et Société
L'UE est acquise si Note finale >= 10- Crédits ECTS acquis : 5 ECTS
Pour les étudiants du diplôme Titre d’Ingénieur diplômé de l’École polytechnique
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Pour les étudiants du diplôme Programmes d'échange internationaux
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
Programme détaillé
Le plan sera le suivant :
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Description et analyse de quelques réseaux de files d'attente: réseaux de Jackson, transferts dans Internet, réseaux à priorités.
- Modèles épidémiques SI et SIS.
