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

Abstract : 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.
Document type :
Theses
Complete list of metadatas

Cited literature [71 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-01748222
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 11:28:55 AM
Last modification on : Tuesday, April 24, 2018 - 1:52:07 PM
Long-term archiving on : Friday, September 14, 2018 - 8:55:34 AM

File

SCD_T_2010_0002_BOUSSATON.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01748222, version 1

Collections

Citation

Octave Boussaton. Application de la théorie des jeux à l'optimisation du routage réseau : solutions algorithmiques. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 2010. Français. ⟨NNT : 2010NAN10002⟩. ⟨tel-01748222⟩

Share

Metrics

Record views

18

Files downloads

83