Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Quantifying Network Topology Robustness Under Budget Constraints



Assane Gueye, Aron Lazska


To design robust network topologies that resist strategic attacks, one must first be able to quantify robustness. In a recent line of research, the theory of network blocking games has been used to derive robustness metrics for topologies. A network blocking game takes as input the communication model and the topology of the network and models the strategic interactions between an adversary and the network as a two- player game. However, these previous works did not consider the budget constraints of the network operator. In this paper, we generalize blocking games by introducing a budget limit on the operator and propose two constraint formulations: the maximum and the expected cost constraints. For practical applications, the greatest challenge posed by blocking games is their computational complexity. Therefore, we show that the expected cost constraint formulation leads to games that can be solved efficiently and the maximum cost constraint leads to NP-hard problems.
Proceedings Title
The 43th Annual IEEE/IFIP International Conference on Dependable Systems and Networks
Conference Dates
June 24-27, 2013
Conference Location
Conference Title
Performance and Dependability Symposium (PDS)


network topology robustness, robustness metrics, game theory, blocking games, computational complexity


Gueye, A. and Lazska, A. (2013), Quantifying Network Topology Robustness Under Budget Constraints, The 43th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Budapest, -1, [online], (Accessed May 20, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created June 24, 2013, Updated February 19, 2017