A game theoretic approach to identify critical components in networked systems

Abstract

Networked systems are pervasive in the current Internet age and they manifest in several ways such as online and enterprize social networks, data center networks, cloud service networks, and global business networks. Such networked systems generally consist of entities and connections (or edges) among these entities. As services or applications are deployed over these networks, the success of any service or application is crucially dependent on the high availability of the components (namely, entities and connections) in the network. This calls for an important problem of identifying the critical components in the network to improve the quality of the services offered over these networks. We propose a novel and generic game theoretic framework to identify critical components with respect to a given task (or service or application) in the network. In particular, we apply the proposed generic game theoretic framework to determine critical edges in the context of k-edge connectivity between certain pairs of nodes in a given network. We call a pair of nodes in a network k-edge connected if there exists k edge disjoint (shortest) paths between these nodes. Identifying critical edges in the setting of the k-edge connectivity is an extremely important problem especially in the context of data center networks and cloud service networks. The following are the specific contributions of this paper: (1) We first formally define a game theoretic model for the k-edge connectivity between certain pairs of nodes in the network. We refer to this as k-edge connectivity game. We then define the criticality of any edge to be the value of its Banzhaf power index in the k-edge connectivity game. In this setting, identifying critical edges boils down to the computation of Banzhaf power index in the k-edge connectivity game; (2) We then show that computing the Banzhaf power index for any edge in the k-edge connectivity game is #P-complete. We show this result by reducing the problem of counting the number of perfect matchings in a given graph to an instance of computing the Banzhaf power index for an edge in the k-edge connectivity game. This implies that the computation of Banzhaf power index for an edge in the k-edge connectivity game is computationally hard; (3) To alleviate this computational issue, we propose an approximation algorithm and also we present a simple heuristic based on the notion of Shapley value in cooperative game theory; (4) We then derive a closed form expression for computing the Banzhaf power index of any edge in the k-edge connectivity game, when the network structure is a tree; and (5) We finally evaluate the proposed approach using thorough experimentation on certain real world network data sets. © 2012 IEEE.