Il existe de nombreuses méthodes d'optimisation du routage réseau en général. Dans cette thèse nous nous intéressons au développement d'algorithmes distribués permettant une stabilisation, au sens de Nash, des flux réseaux. Nous rappelons tout d'abord brièvement le contexte général d'Internet aujourd'hui et quelques notions de théorie des jeux. Nous présentons un jeu de tarification simple à deux joueurs, que la méthode des joueurs fictifs permet de faire converger. Puis nous présentons un jeu de routage plus complexe, à n joueurs, basé sur le modèle de Wardrop, ainsi qu'un algorithme de comportement distribué qui permet au système de converger vers un équilibre de Wardrop (équilibre social). Ces équilibres sont confondus avec les équilibres de Nash dans le cas limite où un joueur représente une partie infinitésimale du trafic. Nous présentons ensuite un raffinement de notre représentation initiale du problème, qui permet une diminution de sa complexité, en terme de dimension des espaces de stratégies et de temps de calcul. Nous montrons qu'il s'agit d'une bonne heuristique d'approximation de la première méthode trop coûteuse, sa qualité dépend d'un unique paramètre. Enfin, nous concluons par la présentation de résultats de simulation qui montrent que notre méthode distribuée est effectivement capable d'apprendre les meilleurs équilibres du système.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00605791 |
| Date | 16 February 2010 |
| Creators | Boussaton, Octave |
| Publisher | Université Henri Poincaré - Nancy I |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds