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.
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.
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
effectifs minimal / maximal:
/56Diplôme(s) concerné(s)
- Echanges PEI
- M1 - Mathematiques Jacques Hadamard
- Titre d’Ingénieur diplômé de l’École polytechnique
- Non Diplomant
Parcours de rattachement
Format des notes
Numérique sur 20Littérale/grade réduitPour les étudiants du diplôme M1 - Mathematiques Jacques Hadamard
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS
Pour les étudiants du diplôme Echanges PEI
Le rattrapage est autorisé (Note de rattrapage conservée)- 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 Non Diplomant
Le rattrapage est autorisé (Note de rattrapage conservée)- Crédits ECTS acquis : 5 ECTS