Game Theoretic Model for Designing the Optimal Network Topology | Lucideus Research

Network topology is the structure in which the nodes or systems are connected with the local area network or to other nodes. There is a significant amount of cost attached to the spanning trees which the manager to choose given a specific topology. Along with the cost of spanning trees, if the concept of critical set (weakest link in the network) is considered, then the security of the network can be enhanced.

In this blog, I am going to describe the idea that is presented in the research article titled “Design of Network Topology in an adversarial Environment”, and my take on the same. It examines the strategic interaction between the network manager, who chooses the spanning tree of the network of communication infrastructure, and an attacker, who tries to  break the communication network by attacking a link. The network manager aims to minimise the chances of attacker being successful in breaking the network and on the other side the attacker aims to maximise the chances of breaking the communication network.

Game Description:
The scenario is modelled as a zero sum game, where the gain to the attacker is the loss to the network manager. Generally, there is always a cost attached to the spanning tree. Along with this, the attacker also incurs cost for attacking a link in the network. So, in adversarial environment the network manager will choose to go with the spanning tree having the lowest cost and the attacker will choose to attack the minimum cost spanning tree and will disrupt the network easily. In order to avoid the bias of players towards the minimum cost, the cost to the attacker is assumed to be zero and the cost associated with each spanning tree is assumed to be the same to the network manager. The basic notation which are used to define the game is listed below:

Notations:

Network topology:  = (ν, ع)

|ν| = n nodes

|ع| = m links

E ⊆ ع is a subset of links, out of which the attacker chooses one to attack

イ is the set of spanning trees and |イ| = N

А := {α ∈ R+N | ΣT∈イ αT = 1} is the mixed strategy of the network manager or the probability with which he is going to choose a spanning tree, T ,from the set of the spanning trees

B := {β ∈ R+N | Σe∈ع βe = 1} is the mixed strategy of the attacker

Assuming that the network manager and attacker both have complete knowledge about the network topology, but the attacker doesn’t know the spanning tree chosen by the defender. A tree gets disrupted if the link attacked by the attacker belongs to the spanning tree chosen by the network manager. The loss to the manager is given by the following expression:

Since it is a zero sum game, the loss to the manager is the gain to the attacker. So, the attacker would want to maximise the above expression whereas the manager would want to minimise it.

Critical Set:

Characterising the subset of edges which are most vulnerable to be attacked which are defined to be a critical set. Considering a non-empty subset of edges E ⊆ ع. The set of minimum number of the links E has in common with the spanning tree is denoted by M(E).

Here ϑ(E) is the vulnerability of the of subset of edges E. It is defined as the minimum fraction of links that E has in common with the spanning tree. E is characterised to be critical if the following equation is satisfied:

For each E ⊆ ع defining イE ⊆ イ by:

Any T ∈ イE is known to be as an E-minimal spanning tree. This implies that the set of E-minimal spanning trees consists of trees having minimal number of edges contained in the set E. In other words it consists of spanning trees with the lowest probability of getting disconnected or the most secure spanning trees given E. Fig 1 illustrates a few examples to explain the concept of critical set. Diagram 1(a) depicts a graph with the bridge(middle link). Any spanning tree is required to go through the dotted link. So, if E is the set with only that link then the vulnerability given E is 1. So, if the attacker attacks this link he gets the maximum benefit since every spanning tree is going to contain that link. So E is said to be critical in this scenario.

Fig 1: Illustrative network examples

Moving to a non-trivial critical set. In 1(b), if E is defined to be a set containing links 6 and 8, in that case every spanning tree is going to go through any one of those two links. So, the vulnerability of this network is ½. And this minimum cut set is critical.

Critical subset attack theorem:

This theorem provides a structure of one particular class of Nash equilibrium. The statement of the theorem is:

“For each critical subset of edges, E, there exists a NE under which the attacker uniformly and exclusively targets the edges of the critical subset E and the network manager chooses only trees inside the set of E-minimal spanning trees. Specifically, the strategy of the attacker is:

and the strategy of the manager is α ∈ A such that

The corresponding optimal payoff is equal to ϑ(E).” As per the computation of the solution of this game, the attacker will choose any of the link in the critical set E with equal probability since in this game the attacker attacks on only one link and in order to maximise the gains out of attack, the chances of the attacked link is belonging to the spanning tree has to be maximised. Since the attacker attacks only one of the link in the critical set with uniform probability, network manager would like to minimise the number of links which belong to the critical set to be a part of spanning tree, thereby choosing the E-minimal spanning tree. Knowledge of the critical subset is important for the network manager in order to optimise the type of spanning tree given the optimal strategy of the attacker. Let us consider an illustration of the above mentioned optimisation on the spanning tree choice.

Fig 2: Critical subset and topology design

Fig 2 illustrates a scenario where the knowledge of critical set will reduce the chances of the network getting disrupted given the strategy of the attacker. The dotted lines here depict the critical set. In 2(a), ϑ(E) = ¾. Now suppose the network manager has a decision to make about the exact place where he can add link to the network with the aim of reducing the vulnerability. If he adds the link at a place shown in 2(b) then the vulnerability decreases to ⅗. Whereas, if the link is added at a place shown in 2(c), then the vulnerability increases to ⅔ from ¾. As now the critical set is being changed thereby the probability of attack corresponding to a particular link increases. Now the network becomes less robust.

Conclusion:

Decision regarding the network topology is a critical and crucial move to make. The decision is more robust if the several characteristics and possible moves of the attacker is defined. In this blog, the optimal action of the attacker is defined and corresponding to that the best response of the network manager is computed. Here, the game is considered to be one-shot and 1-connection game where attacker only attacks one link. The game can be further modified to generalise it to repeated game with k-connection under attack.  

References:

A. Gueye, J.C. Walrand, and V. Anantharam: Design of Network Topology in an Adversarial Environment. In: Decision and Game Theory for Security: First international Conference, pp. 1-20 (2010)

Awerbuch, B., Richa, A., Scheideler, C.: A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks. In: PODC 2008: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp. 45–54 (2008)  

Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (March 2004)

Catlin, P.A., Lai, H.-J., Shao, Y.: Edge-Connectivity and Edge-Disjoint Spanning Trees. Discrete Mathematics 309(5), 1033–1040 (2009)

Chopra, S.: On the Spanning Tree Polyhedron. Operations Research Letters 8(1), 25–29 (1989)

Commander, C.W., Pardalos, P.M., Ryabchenko, V., Uryasev, S., Zrazhevsky, G.: The Wireless Network Jamming Problem. J. Comb. Optim. 14(4), 481–498 (2007)

Cordovil, R., Fukuda, K., Moreira, M.L.: Clutters and Matroids. Discrete Math. 89(2), 161–171 (1991)

Cornuejols, G.: Combinatorial Optimization: Packing and Covering. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2001)

Cunningham, W.H.: Optimal Attack and Reinforcement of a Network. J. ACM 32(3), 549–561 (1985)

Edmonds, J., Fulkerson, D.R.: Bottleneck Extrema. Journal of Combinatorial Theory (8), 299–306 (1970)