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.
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01592833
Contributor : Baptiste Jonglez <>
Submitted on : Monday, September 25, 2017 - 3:08:41 PM
Last modification on : Wednesday, December 4, 2019 - 10:38:46 AM

File

ITC2017-PID4869211 (1).pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

473

Files downloads

309