Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [71 references]  Display  Hide  Download
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


Files produced by the author(s)


  • HAL Id : tel-01748222, version 1



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⟩



Record views


Files downloads