Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Resilience of Routing in Parallel Link Networks

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
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Corinne Touati Connect in order to contact the contributor
Submitted on : Thursday, October 20, 2016 - 3:27:43 PM
Last modification on : Tuesday, July 5, 2022 - 8:38:48 AM


Files produced by the author(s)




Eitan Altman, Aniruddha Singhal, Corinne Touati, Jie Li. Resilience of Routing in Parallel Link Networks. GameSec 2016 - 7th International Conference on Decision and Game Theory for Security, Nov 2016, New York, United States. pp.3 - 17, ⟨10.1007/978-3-319-47413-7_1⟩. ⟨hal-01249188v2⟩



Record views


Files downloads