Distributed and Adaptive Routing Based on Game Theory

Baptiste Jonglez 1, 2, 3, 4 Bruno Gaujal 3
3 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
4 Drakkar
LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we present a new adaptive multi-flow routing algorithm to select end-to-end paths in packet-switched networks. This algorithm provides provable optimality guarantees in the following game theoretic sense: The network configuration converges to a configuration arbitrarily close to a pure Nash equilibrium. In this context, a Nash equilibrium is a configuration in which no flow can improve its end-to-end delay by changing its network path. This algorithm has several robustness properties making it suitable for real-life usage: it is robust to measurement errors, outdated information, and clocks desynchronization. Furthermore, it is only based on local information and only takes local decisions, making it suitable for a distributed implementation. Our SDN-based proof-of-concept is built as an Openflow controller. We set up an emulation platform based on Mininet to test the behavior of our proof-of-concept implementation in several scenarios. Although real-world conditions do not conform exactly to the theoretical model, all experiments exhibit satisfying behavior, in accordance with the theoretical predictions.
Type de document :
Communication dans un congrès
29th International Teletraffic Congress (ITC 29), Sep 2017, Genoa, Italy. 〈10.1109/ITC.2017.28〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01592833
Contributeur : Baptiste Jonglez <>
Soumis le : lundi 25 septembre 2017 - 15:08:41
Dernière modification le : vendredi 1 décembre 2017 - 01:04:08

Fichier

ITC2017-PID4869211 (1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Baptiste Jonglez, Bruno Gaujal. Distributed and Adaptive Routing Based on Game Theory. 29th International Teletraffic Congress (ITC 29), Sep 2017, Genoa, Italy. 〈10.1109/ITC.2017.28〉. 〈hal-01592833〉

Partager

Métriques

Consultations de la notice

74

Téléchargements de fichiers

11