Designing virus-resistant networks: a game-formation approach

Abstract : Forming, in a decentralized fashion, an optimal network topology while balancing multiple, possibly conflicting objectives like cost, high performance, security and resiliency to viruses is a challenging endeavor. In this paper, we take a game-formation approach to network design where each player, for instance an autonomous system in the Internet, aims to collectively minimize the cost of installing links, of protecting against viruses, and of assuring connectivity. In the game, minimizing virus risk as well as connectivity costs results in sparse graphs. We show that the Nash Equilibria are trees that, according to the Price of Anarchy (PoA), are close to the global optimum, while the worst-case Nash Equilibrium and the global optimum may significantly differ for small infection rate and link installation cost. Moreover, the types of trees, in both the Nash Equilibria and the optimal solution, depend on the virus infection rate, which provides new insights into how viruses spread: for high infection rate tau , the path graph is the worst- and the star graph is the best-case Nash Equilibrium. However, for small and intermediate values of tau , trees different from the path and star graphs may be optimal.
Type de document :
Communication dans un congrès
IEEE 54th Annual Conference on Decision and Control (CDC), Dec 2015, Osaka, Japan. Proceedings of the IEEE 54th Annual Conference on Decision and Control (CDC)
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01204628
Contributeur : Eitan Altman <>
Soumis le : jeudi 24 septembre 2015 - 11:55:14
Dernière modification le : jeudi 31 mai 2018 - 16:58:02
Document(s) archivé(s) le : mardi 29 décembre 2015 - 09:47:00

Fichier

cdc-stojan.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01204628, version 1

Collections

Citation

Stojan Trajanovski, Fernando Antonio Kuipers, Yezekael Hayel, Eitan Altman, Piet Van Mieghem. Designing virus-resistant networks: a game-formation approach. IEEE 54th Annual Conference on Decision and Control (CDC), Dec 2015, Osaka, Japan. Proceedings of the IEEE 54th Annual Conference on Decision and Control (CDC). 〈hal-01204628〉

Partager

Métriques

Consultations de la notice

274

Téléchargements de fichiers

128