Distributed and Adaptive Routing based on Game Theory
B. Jonglez, and B. Gaujal. 29th International Teletraffic Congress (ITC 29), Genoa, Italy, (2017)
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.
%0 Conference Paper
%1 Jonglez.2017
%A Jonglez, Baptiste
%A Gaujal, Bruno
%B 29th International Teletraffic Congress (ITC 29)
%C Genoa, Italy
%D 2017
%K itc itc29
%T Distributed and Adaptive Routing based on Game Theory
%U https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc29/Jonglez.2017.pdf?inline=true
%X 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.
@inproceedings{Jonglez.2017,
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.},
added-at = {2017-10-05T16:41:49.000+0200},
address = {Genoa, Italy},
author = {Jonglez, Baptiste and Gaujal, Bruno},
biburl = {https://www.bibsonomy.org/bibtex/2f1c75078aa381daf6c6738291b53cb31/itc},
booktitle = {29th International Teletraffic Congress (ITC 29)},
interhash = {b43d9f9c089ab46ce55d7280423268bc},
intrahash = {f1c75078aa381daf6c6738291b53cb31},
keywords = {itc itc29},
timestamp = {2020-04-30T18:18:14.000+0200},
title = {Distributed and Adaptive Routing based on Game Theory},
url = {https://gitlab2.informatik.uni-wuerzburg.de/itc-conference/itc-conference-public/-/raw/master/itc29/Jonglez.2017.pdf?inline=true},
year = 2017
}