Resilience of Routing in Parallel Link Networks

Eitan Altman 1 Aniruddha Singhal 2 Corinne Touati 2 Jie Li 3
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 Inria Grenoble - Rhône-Alpes
3 University of Tsukuba
Abstract : We revisit in this paper the resilience problem of routing traffic in a parallel link network model with a malicious player using a game theoretic framework. Consider that there are two players in the network: the first player wishes to split its traffic so as to minimize its average delay, which the second player, i.e., the malicious player, tries to maximize. The first player has a demand constraint on the total traffic it routes. The second player controls the link capacities: it can decrease by some amount the capacity of each link under a constraint on the sum of capacity degradation. We first show that the average delay function is convex both in traffic and in capacity degradation over the parallel links and thus does not have a saddle point. We identify best responses strategies of each player and compute both the max-min and the min-max values of the game. We are especially interested in the min max strategy as it guarantees the best performance under worst possible link capacity degradation. It thus allows to obtain routing strategies that are resilient and robust. We compare the results of the min-max to those obtained under the max-min strategies. We provide stable algorithms for computing both max-min and min-max strategies as well as for best responses.
Keywords : zero-sum games
Type de document :
Communication dans un congrès
Quanyan Zhu ; Tansu Alpcan; Emmanouil Panaousis; Milind Tambe ; William Casey GameSec 2016 - 7th International Conference on Decision and Game Theory for Security, Nov 2016, New York, United States. Springer, 9996, pp.3 - 17, 2016, Lecture notes in computer science. 〈10.1007/978-3-319-47413-7_1〉
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01249188
Contributeur : Corinne Touati <>
Soumis le : jeudi 20 octobre 2016 - 15:27:43
Dernière modification le : samedi 27 janvier 2018 - 01:31:44

Fichier

gamesec-CR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA

Citation

Eitan Altman, Aniruddha Singhal, Corinne Touati, Jie Li. Resilience of Routing in Parallel Link Networks. Quanyan Zhu ; Tansu Alpcan; Emmanouil Panaousis; Milind Tambe ; William Casey GameSec 2016 - 7th International Conference on Decision and Game Theory for Security, Nov 2016, New York, United States. Springer, 9996, pp.3 - 17, 2016, Lecture notes in computer science. 〈10.1007/978-3-319-47413-7_1〉. 〈hal-01249188v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

277

Téléchargements de fichiers

212

Contact


archive-ouverte@inria.fr