Application de la théorie des jeux à l'optimisation du routage réseau : solutions algorithmiques, Game theory applied to routing in networks : algorithmic solutions

Octave Boussaton

Description

Sous la direction de Dominique Barth, Johanne Cohen
Thèse soutenue le 16 février 2010: Nancy 1
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.
-Réseaux d'ordinateurs
-Traitement réparti
-Equilibre de Nash
-Algorithmes EM
-Equilibre de Wardrop
-Fonction de potentiel
-Routage
-Apprentissage distribué
-Wardrop
-Routage égoiste
There are several approaches for optimizing network routing in general. In this document, we are interested in developping distributed algorithms able to stabilize the network flows in the sense of Nash. We introduce the general context of the Internet today along with a few key-notions in game theory. We show a simple two-player tarification game that the fictitious player dynamics is able to solve. Then, we introduce a more complex routing game with n players based on the Wardrop model and a distributed learning algorithm that allows the system to converge towards Wardop equilibria (social equilibrium). These equilibria also are Nash equilibria in the limit case where a player is an infinitesimal part of the network flow. We present a refinement of our initial representation of the problem that narrows down its complexity, in terms of the size of the strategy space and computation time. We show that it is a good heuristic for approximating the previous method, its quality relies upon only one parameter. Finally, we conclude with simulations results, showing that our distributed method is able to learn the best equilibriua of the system.
Source: http://www.theses.fr/2010NAN10002/document

Sujets

• Équilibre de Nash
• Routage

Informations

• Publié par: Thesee
• Nombre de lectures: 126
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.


➢ Contact SCD Nancy 1 : [e-mail]




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm



Application de la théorie des jeux à l'optimisation du
routage réseau – solutions algorithmiques

THESE

Soutenue publiquement le 16 Février 2010

Pour l’obtention du

Doctorat de l’université Henri Poincaré
(spécialité informatique)

par

Octave Boussaton


Composition du jury

Rapporteurs: Sébastien Tixeuil Professeur, Paris VI
Bruno Tuffin Chargé de recherches INRIA


Examinateurs: Jean-Claude Konig Professeur, Montpellier II
Dominique Barth Professeur, Université de Versailles
Johanne Cohen Chargé de recherches CNRS
Nicolas Lesauze Ingénieur R&D, Alcatel Lucent
Président du jury: Dominique Mery Professeur, Nancy I




Laboratoire Lorrain de Recherche en Informatique et ses Applications – UMR 7503
Application de la theorie des jeux a l’optimisation du routage
reseau - solutions algorithmiques
Octave Boussaton
16 fevrier 20102Remerciements
Je remercie du plus profond de mon coeur, Solene Jouault, qui m’a aide de fa con ines-
timable et qui m’a supporte, dans tous les sens du terme, pendant cette these. Je souhaite
egalement remercier de nombreuses personnes pour avoir contribue, a titres divers, a l’ela-
boration de ce document, j’adresse mes remerciements les plus chaleureux et sinceres :
{ A mes collegues et amis que j’ai cotoyes tout au long de ces trois annees, dans l’ordre
a-peu-pres chronologique : Matthieu Kaczmarek, Emmanuel Hainry, Romain Pechoux,
Anne Bonfante, Florent Garnier, Philippe Beaucamps, Daniel Reynaud, Wadie Gui-
zany, Mathieu Hoyrup et Joan Calvet.
{ A mon directeur de these Dominique Barth et mon encadrante Johanne Cohen pour
leur encadrement et pour m’avoir donne de bonnes pistes et intuitions de recherche,
ainsi qu’a Olivier Bournez pour son aide precieuse.
{ Aux membres de l’equipe CARTE au sein de laquelle j’ai travaille pendant trois ans
et avec lesquels j’ai pu echanger des idees, Jean-Yves Marion, Guillaume Bonfante et
Isabelle Gnaedig.
{ Aux membres du PRiSM que j’ai cotoyes et avec qui j’ai eu des echanges tres enrichis-
sants : Thierry Mautor, Sandrine Vial, Sylvie Delaet, Franck Quessette et Chahinez
Hamlaoui.
{ A Sebastien Tixeuil, Jean-Claude Konig et Bruno Tu n qui ont accepte d’^etre les
rapporteurs de mon manuscrit.
{ Aux autres membres de mon jury de these, Dominique Mery et Nicolas Lesauze.
{ A mes parents, mes freres et mes amis de longue date qui m’ont toujours beaucoup
aide, Fulbert, Evariste, Maarten, Jean-Marc, Fabrice, Fred, Hieub, Jerome, Raphael,
Sylvain, Dogan, Delphine, Naomi, Mathieu, Melanie, Maxime et quelques autres
iiiTable des matieres
1 Introduction 1
2 Contexte 5
2.1 Les bases de la communication reseau . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Les reseaux IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Le reseau local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Internet et le routage interdomaine . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Une vue globale d’ Internet . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Le protocole BGP (Border Gateway Protocol) . . . . . . . . . . . . . . . . . 12
2.3.1 Nature des accords entre operateurs . . . . . . . . . . . . . . . . . . 12
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Notions de theorie des jeux 21
3.1 Quelques champs d’application . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Representation des jeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2.1 Strategie dominante, theoreme du minimax . . . . . . . . . . . . . . 25
3.2.2 Le concept d’utilite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Jeu constituant et jeux repetes . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1 Le jeu constituant . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.3.2 L’equilibre de Nash pur . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.3 Les strategies dans les jeux repetes . . . . . . . . . . . . . . . . . . . 30
3.3.4 L’equilibre de Nash mixte . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
iiiiv TABLE DES MATIERES
4 Jeux de tarications 33
4.1 Jeu de tarication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.1.1 Modele general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.1.2 Speci cation d’un jeu de tari