Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication




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 : theses.sciences@scd.uhp-nancy.fr




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