PaperlayerView exact revision on arXiv

Source-linked AI summary

Robustness of Interdependent Networks: The case of communication networks and the power grid

Marzieh Parandehgheibi, Eytan Modiano

arXiv:1304.0356v1math.OCcs.NI

TL;DR

The paper asks how to assess and design robustness when power-grid and communication-network states depend on each other, especially for preventing total blackout. It models minimum removals that trigger total failure, characterizes computational complexity under different dependency directions, and applies the results to Italy. Unidirectional dependencies yield an NP-complete hitting-cycle problem with polynomial-time suboptimal heuristics, while bidirectional dependencies reduce to polynomial-time vertex cover; the Italian network is robust to total failure but contains vulnerable parts.

  • Problem

    Interdependent power and communication networks can cascade failures between one another, while real networks with known topologies remain insufficiently modeled for robustness analysis.

  • Method

    The paper models total failure through minimum node or edge removals, relates unidirectional dependencies to hitting cycles, and uses greedy polynomial-time heuristics for node removals.

  • Results

    Unidirectional Node-MTFR is NP-complete, polynomial-time heuristics provide suboptimal solutions, and bidirectional dependencies are equivalent to bipartite vertex cover, which is polynomial-time solvable.

  • Takeaways & Limitations

    The Italy case is robust to total failure, but parts of the network are highly vulnerable, including a regional case where removing three routers causes blackout in one third of the power grid.

  • Takeaways & Limitations

    The real-network interdependency analysis assumes each substation uses its nearest router and each router uses its nearest substation.

Abstract

from arXiv · show

In this paper, we study the robustness of interdependent networks, in which the state of one network depends on the state of the other network and vice versa. In particular, we focus on the interdependency between the power grid and communication networks, where the grid depends on communications for its control, and the communication network depends on the grid for power. A real-world example is the Italian blackout of 2003, when a small failure in the power grid cascaded between the two networks and led to a massive blackout. In this paper, we study the minimum number of node failures needed to cause total blackout (i.e., all nodes in both networks to fail). In the case of unidirectional interdependency between the networks we show that the problem is NP-hard, and develop heuristics to find a near-optimal solution. On the other hand, we show that in the case of bidirectional interdependency this problem can be solved in polynomial time. We believe that this new interdependency model gives rise to important, yet unexplored, robust network design problems for interdependent networked infrastructures.

I. INTRODUCTION

Interdependent infrastructure networks can amplify local failures into widespread cascades, yet most prior reliability work studied isolated or random networks. The paper introduces a topology-aware model focused on power-grid and communication-network interdependency.

  • Motivation: Failures in one infrastructure network can cascade repeatedly through dependent elements in another, causing catastrophic widespread failures.The 2003 Italian blackout affected fifty-five million people and is presented as an example of this interdependency.
  • Related work: Prior reliability studies largely examined single networks in isolation, whose behavior differs from that of coupled networks because of cascading failures.Related work also modeled interdependent random graphs and examined giant components and reduced dependency.
  • Contribution: The paper defines a model for power-grid and communication-network interdependency and analyzes their robustness, including a new robustness metric.The paper’s roadmap covers the model, star-topology analysis, a real-network evaluation, and conclusions.
  • Motivation: Smart-grid control requirements increase the power grid’s dependence on communication networks for monitoring and control.The paper links future wide-area measurement and control systems to the need for robust cyber-physical network design.
  • Contribution: Unlike random-network models, real power and communication networks have known topologies that must be incorporated when designing robust interdependent infrastructures.The paper presents its model as a first attempt to study this setting and notes that the approach can extend to other cyber-physical networks.

II. CYBER-PHYSICAL INTERDEPENDENCY MODEL

The model couples a power grid and a Control and Communication Network through mutual operational dependencies. Substations require power and communication control, while routers require communication connectivity and power from substations.

  • Network model: The power grid contains generators and substations linked by power lines, while the CCN contains control centers and routers linked by communication lines.Figure 1 distinguishes power lines from communication lines using dotted and solid representations, respectively.
  • Operational dependencies: A substation operates only when connected to a generator and to a router for data transmission and control.The operational definition requires both power connectivity and communication connectivity.
  • Operational dependencies: A router operates only when connected to a control center and to a substation for power.Thus, failures can propagate from the power grid to the CCN and from the CCN to the power grid.
  • Operational dependencies: The CCN controls substations to prevent overloading, whereas an uncontrolled substation may become overloaded and fail.This gives communication connectivity a direct role in power-grid operation.
  • Assumptions: The model assumes generators have internal control and control centers have backup generators, making them robust to failures.It also abstracts away power-flow equations and power quantities, focusing only on connectivity.

A. Effect of a Single Failure

The paper illustrates how one substation failure can trigger repeated failures across both networks, whereas the isolated power grid would not continue failing. It formalizes this phenomenon through the MTFR robustness metric.

  • Cascade example: A single failure at substation S4 propagates through routers and substations until all nodes in both networks fail.The cascade proceeds through four steps involving loss of power, control, control-center connectivity, and generator connectivity.
  • Comparison: Without dependence on the CCN, failure of S4 leaves every other power-grid substation connected to the generator, so no further failure occurs.The comparison indicates that interdependency increases vulnerability while remaining essential to operation.
  • Metric: Total Failure means that all nodes in both networks fail after cascading, and MTFR is the minimum number of removals that causes it.The paper considers both Node-MTFR and Edge-MTFR metrics.
  • Single-network baseline: A star topology is robust for a single network because all nodes connect directly to the source.In that setting, disconnecting all nodes requires removing the nodes directly connected to the source.

III. INTERDEPENDENCY BETWEEN NETWORKS WITH STAR TOPOLOGIES

With star topologies, failures arise only through interdependency, and under unidirectional dependencies total failure reduces to removing nodes that hit every cycle. This establishes NP-completeness for Node-MTFR.

  • III. INTERDEPENDENCY BETWEEN NETWORKS WITH STAR TOPOLOGIES: Star topologies isolate failures within the interdependency: substations connect directly to the generator, routers directly to the control center, and each can fail when it loses its cross-network connection.Thus, the interdependent system is represented as a bipartite graph whose cycles capture stable operating structures.
  • III. INTERDEPENDENCY BETWEEN NETWORKS WITH STAR TOPOLOGIES: Under unidirectional interdependency, finding Node-MTFR is NP-complete because it is equivalent to Feedback Vertex Set on general bipartite graphs.The interdependency edges are directed, and Feedback Vertex Set removes the smallest node set that makes a graph acyclic.
  • III. INTERDEPENDENCY BETWEEN NETWORKS WITH STAR TOPOLOGIES: A network with operating nodes must contain a cycle, while nodes in a cycle can operate through incoming edges from other nodes in that cycle.Nodes reachable from an operating cycle can also operate when they receive incoming edges directly or through paths from that cycle.
  • III. INTERDEPENDENCY BETWEEN NETWORKS WITH STAR TOPOLOGIES: To stop a cycle from operating, at least one node in the cycle must be removed; stopping one cycle does not necessarily remove every node inside it.If cycle nodes receive incoming edges from outside the cycle, additional removals may be required to make all of them fail.
  • III. INTERDEPENDENCY BETWEEN NETWORKS WITH STAR TOPOLOGIES: For total failure, at least one node from every cycle must be removed, so Node-MTFR is the minimum cycle-hitting set.Theorem 1 identifies this cycle-hitting number as the optimal Node-MTFR solution.

1) Problem Formulation:

The Node-MTFR problem is formulated as a binary integer program that minimizes node removals while requiring every cycle to contain a removed node.

  • 1) Problem Formulation:: The formulation uses a binary vector N in which Nj=1 indicates that node j is removed and Nj=0 otherwise.Matrix A maps cycles to nodes, with Aij=1 when cycle i contains node j, and e is a vector of ones.
  • 1) Problem Formulation:: The objective is to minimize the number of node removals.The decision variables are restricted to binary values.
  • 1) Problem Formulation:: The constraint A × N ≥e requires at least one removed node to hit every cycle.Each row corresponds to one cycle and enforces coverage by the selected removals.

2) Heuristics:

The paper develops two polynomial-time heuristics for the cycle-hitting formulation: one based on enumerated cycles and another based on node degrees and cascading failures.

  • 2) Heuristics:: The cycle-based heuristic greedily removes the node shared by the maximum number of remaining cycles until no cycle remains.It treats each cycle as a set of nodes and applies a greedy hitting-set strategy.
  • 2) Heuristics:: Because a graph may contain exponentially many cycles, the second heuristic uses the adjacency matrix rather than requiring all cycles as input.This avoids the explicit cycle-enumeration requirement of the first algorithm.
  • 2) Heuristics:: The degree-based heuristic prunes edges outside cycles, removes the node with maximum outgoing degree, propagates resulting failures, and repeats.After each cascade, it updates the adjacency matrix until no node remains.
  • 2) Heuristics:: The evaluation generates 100 random bipartite graphs for each N while restricting generated cycles to size 6 or smaller.Small N is used because enumerating all cycles requires exponential time.

3) Minimum Edge Removals:

For unidirectional interdependency, total failure requires removing edges that hit every cycle. The resulting Edge-MTFR problem is NP-complete.

  • Minimum Edge Removals: Removing at least one edge from every cycle yields total failure in the unidirectional model.The Edge-MTFR objective is to stop every cycle from operating.
  • Minimum Edge Removals: The minimum number of edges hitting all cycles is the optimal Edge-MTFR solution.
  • Minimum Edge Removals: Finding minimum edge removals for total failure in star networks with unidirectional interdependency is NP-complete.The problem is identified with Feedback Edge Set, which is NP-complete for general graphs and bipartite tournaments.

B. Bidirectional Interdependency

With bidirectional interdependency, each dependency edge forms a two-node cycle, making minimum node removals equivalent to bipartite vertex cover. This problem is polynomially solvable, while Edge-MTFR requires removing all edges.

  • Bidirectional Interdependency: Bidirectional interdependency requires each power-to-router dependency to be reciprocated by a router-to-power dependency.
  • Bidirectional Interdependency: Minimum node removals are polynomially solvable in star networks with bidirectional interdependency.The problem reduces to minimum vertex cover in a bipartite graph and then to maximum matching.
  • Bidirectional Interdependency: For Edge-MTFR, all edges must be removed because every edge is a cycle in the bidirectional star-network model.

C. Comparing the interdependency models

The paper compares unidirectional and bidirectional interdependency under matched network topologies. Bidirectional dependency requires more node removals across all tested network sizes and is therefore more robust to failures.

  • Comparing the interdependency models: Under different interdependency models, the same intentional removal can produce different cascading behavior.The paper uses two networks with the same topology to explain why unidirectional analysis is more difficult than bidirectional analysis.
  • Comparing the interdependency models: The comparison uses identical random-graph topologies under unidirectional and bidirectional dependency models.Optimal solutions are computed using hitting set for unidirectional graphs and vertex cover for bidirectional graphs.
  • Comparing the interdependency models: For all values of N, bidirectional-dependency networks require more node removals and are more robust to failures.

IV. DISCUSSION

The Italian-network discussion applies Node-MTFR to selected power-grid substations and communication routers under a nearest-node interdependency assumption. Although total failure requires 13 removals, three routers can cause a blackout in one third of northwest Italy.

  • IV. DISCUSSION: The Italian-network analysis considers generator-connected substations and control-center-connected routers as the critical nodes.The study measures Node-MTFR on the Italian topology and assumes control centers occupy highly connected router clusters.
  • IV. DISCUSSION: Each substation is assumed to receive control from its nearest router, while each router receives power from its nearest substation.Figure 6 maps the power grid, CCN, and their interdependency across Italy.
  • IV. DISCUSSION: 13 nodes must be removed simultaneously to cause total failure because the Italian network’s cycles are short and mostly isolated.
  • IV. DISCUSSION: Three router removals can cause a blackout in one third of northwest Italy, despite the network’s resistance to total failure.This motivates measuring the effects of removals on partial network failures.

V. CONCLUSION

The paper models cyber-physical interdependency between power and communication networks and determines the minimum removals needed to trigger total cascading failure. Unidirectional dependencies yield an NP-complete equivalent, while bidirectional dependencies admit polynomial-time solutions.

  • The cyber-physical model makes power-grid nodes depend on communication information and communication nodes depend on the grid’s physical output.
  • The minimum node-removal problem is equivalent to the hitting cycles problem and is NP-complete for unidirectional dependencies.The paper also presents polynomial algorithms producing suboptimal solutions in this case.
  • For bidirectional dependencies, the problem is equivalent to bipartite vertex cover and is solvable in polynomial time.
  • The Italian network is robust to total failure but contains parts that are highly vulnerable to failures.
Loading 1304.0356v1…