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

https://hal.inria.fr/hal-01249188
Contributor : Corinne Touati <>
Submitted on : Thursday, October 20, 2016 - 3:27:43 PM
Last modification on : Thursday, March 5, 2020 - 5:45:44 PM

File

gamesec-CR.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

363

Files downloads

504