Resilience of Routing in Parallel Link Networks - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2015

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

Fichier principal
Vignette du fichier
resilience2.pdf (217.32 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01249188 , version 1 (30-12-2015)
hal-01249188 , version 2 (20-10-2016)

Identifiers

  • HAL Id : hal-01249188 , version 1

Cite

Eitan Altman, Aniruddha Singhal, Corinne Touati, Jie Li. Resilience of Routing in Parallel Link Networks. [Research Report] Inria Grenoble Rhône-Alpes, Université de Grenoble. 2015. ⟨hal-01249188v1⟩

Collections

LARA
240 View
292 Download

Share

Gmail Facebook X LinkedIn More