betaFeedback

WorksMathematics

Capacity-Aware Redistribution Control for Mitigation of Cascading Failures in Networks

Abstract

This paper studies the control of irreversible cascading failures in networks with finite node capacities. Each node carries a nonnegative divisible quantity, referred to as load, and fails irreversibly when its load exceeds its capacity. The network dynamics are represented by topology-dependent row-stochastic matrices. When nodes fail, these matrices must be updated. However, directly deleting rows and columns corresponding to failed nodes can reduce the total load in the network. We therefore introduce a topology update that preserves unit row sums and quantifies any unserved load explicitly. We derive the resulting load-balance relation and a necessary and sufficient condition for lossless redistribution after simultaneous failures. Based on these results, we formulate a two-stage optimization problem: the first stage minimizes unserved load, and the second stage minimizes the highest capacity utilization among the surviving nodes. Simulations on grid and Barabasi-Albert networks show that, unlike the standard equal and residual-capacity redistribution approaches, the proposed method prevents secondary failures in all tested cases, with a tradeoff against served load on scale-free networks.

Introduction

Many networked systems, such as power, transportation, communication, and service networks, move a conserved quantity, hereafter referred to as load, among nodes with finite capacities such as substations, stations, or routers. When the load at a node exceeds its capacity, the node fails permanently, and its load is either transferred to surviving nodes or remains unserved. Redistribution may overload further nodes and trigger a cascade of failures [1, 2, 3]. Each failure also changes the network topology and thereby alters subsequent load transfers.

Capacity-based models [1], [2] describe how overload and changes in network flows can lead to propagating failures. Decentralized redistribution using neighboring information is proposed in [4], and optimal reassignment of failed-link loads in multilayer networks is studied in [5]. Related cascade models and mitigation strategies have been studied in the complex-networks literature [6, 7, 8]. For local redistribution, equal sharing can be used. It requires no optimization, but ignores the residual capacities of surviving nodes. It also does not coordinate transfers from simultaneously failing nodes that share a receiver, i.e., a surviving neighbor.

In power networks, the method in [9] computes load-shedding schedules over successive cascades using linearized power-flow equations. For a similar application, homogeneous load reduction, optimized shedding, and a tree heuristic approach are compared in [10]. For networks with external inflows, [11] investigates distributed routing under irreversible link failures and reductions in link capacities. For continuous-time flow networks, throughput and overload properties under monotone distributed routing are derived in [12]. Generally, existing cascade models typically change load only at failures and treat each failed node separately. Moreover, the optimization-based and robust approaches in [9, 10, 11, 12] rely on power-flow models or on flow networks with external inflows, and are thus not directly applicable when a finite node load is reassigned at failures. It therefore remains unclear how load transfers between failures should adapt to node removal, and under which conditions the loads of simultaneously failing nodes can be reassigned without overloading shared receivers.

In this work, we consider a finite divisible load held at the nodes, with no continuing external inflow. Nominal transfers follow a topology-dependent row-stochastic matrix, whereas loads of failed nodes are reassigned among surviving neighbors. When nodes fail, directly deleting the corresponding rows and columns can reduce the total load before redistribution. We propose an alternative to this strategy. In this context, our contributions are as follows. First, we show that our alternative topology update preserves row stochasticity after single or simultaneous failures and derive the corresponding total-load balance. Second, when the nominal surviving-node loads have enough capacity, we give a necessary and sufficient condition for lossless redistribution after simultaneous failures and determine the minimum load that must remain unserved. Third, we formulate a two-stage linear program that first minimizes unserved load and then minimizes the highest surviving-node capacity utilization. We give a necessary and sufficient condition under which no further failures occur. Fourth, in simulations with grid and scale-free networks, we compare our approach with standard heuristics, i.e., equal and residual-capacity redistribution, after two initial failures with a common surviving neighbor occur, and redistribution requires accounting for shared receiver capacities.

Network Model and Failure Dynamics

Consider an undirected weighted graph G=(V,E)G=(V,E) with nodes V={1,…,n}V=\{1,\ldots,n\} and edges E⊆V×VE\subseteq V\times V with nonnegative weights. An edge (i,j)∈E(i,j)\in E allows load transfer between nodes ii and jj. Load is a nonnegative divisible quantity assigned to the nodes and can be divided among neighbors. The fixed capacity ci>0c_i > 0 is the maximum load that node ii can carry. The load and capacity vectors are denoted by x(k)=[x1(k) ⋯ xn(k)]T∈R≥0n\boldsymbol{x}(k) = [x_1(k)\ \cdots\ x_n(k)]^{\mathsf{T}} \in\mathbb{R}_{\ge0}^{n} and c=[c1 ⋯ cn]T∈R>0n\boldsymbol{c} = [c_1\ \cdots\ c_n]^{\mathsf{T}} \in\mathbb{R}_{>0}^{n}, respectively. Let A(k)\mathcal{A}(k) be the set of nodes active before the detection of failures at time kk, with A(0)=V\mathcal{A}(0) = V. The newly failed and previously failed set of nodes respectively belong to

F(k)={i∈A(k):xi(k)>ci},(1)\mathcal{F}(k) = \{i \in\mathcal{A}(k) : x_i(k) > c_i\}, \tag*{(1)}
R(k)=V∖A(k).(2)\mathcal{R}(k) = V \setminus\mathcal{A}(k). \tag*{(2)}

The active graph G(k)=G[A(k)]G(k) = G[\mathcal{A}(k)] contains the active nodes and all edges of GG between them. Failures are irreversible, so A(k+1)=A(k)∖F(k)\mathcal{A}(k + 1) = \mathcal{A}(k) \setminus\mathcal{F}(k) and xi(h)=0 ∀i∈R(k+1)x_i(h) = 0\ \forall i \in\mathcal{R}(k + 1) and h≥k+1h \ge k + 1. All nodes in F(k)\mathcal{F}(k) are detected from x(k)\boldsymbol{x}(k) and handled simultaneously, since a sequential order would change the outcome when they share surviving neighbors.

Let P(k)∈R≥0n×nP(k) \in\mathbb{R}_{\ge0}^{n \times n} with entries pij(k)p_{ij}(k) be the load-transfer matrix before failure detection at step kk. For an active node ii, pij(k)p_{ij}(k) is the fraction of its load sent to neighbor jj, and pii(k)p_{ii}(k) is the fraction retained at ii. Each row sums to one because these fractions account for all of that node’s load. Thus, P(k)P(k) is row stochastic. In summary, G(k)G(k) specifies the available connections and P(k)P(k) specifies the transfer fractions along them. At a failure-free step, the nominal load dynamics are

x(k+1)=P(k)Tx(k).(3)\boldsymbol{x}(k + 1) = P(k)^{\mathsf{T}}\boldsymbol{x}(k). \tag*{(3)}

Let 1∈Rn\boldsymbol{1} \in\mathbb{R}^{n} denote the vector of all ones. Since P(k)1=1P(k)\boldsymbol{1} = \boldsymbol{1},

1Tx(k+1)=1TP(k)Tx(k)=1Tx(k),(4)\boldsymbol{1}^{\mathsf{T}}\boldsymbol{x}(k + 1) = \boldsymbol{1}^{\mathsf{T}}P(k)^{\mathsf{T}}\boldsymbol{x}(k) = \boldsymbol{1}^{\mathsf{T}}\boldsymbol{x}(k), \tag*{(4)}

so nominal transfers preserve total load. In order to construct the matrix PP and to assign transfer weights along the edges of a given network GG, let A∈R≥0n×nA \in\mathbb{R}_{\ge0}^{n \times n} with entries aija_{ij} be its weighted adjacency matrix, D=diag⁡(A1)D = \operatorname{diag}(A\boldsymbol{1}) the degree matrix with diagonal entries diid_{ii}, L=D−AL = D - A, and dmax⁡=max⁡i∈Vdiid_{\max} = \max_{i \in V} d_{ii}. For dmax⁡>0d_{\max} > 0, the initial load-transfer matrix is

P(0)=I−εL,0≤ε≤1/dmax⁡.(5)P(0) = I - \varepsilon L,\qquad0 \le\varepsilon\le1/d_{\max}. \tag*{(5)}

This diffusion-type update is used in consensus dynamics [13]. The bound on ε\varepsilon ensures nonnegative entries pij(0)p_{ij}(0), as well as the row-stochasticity, i.e., every row sums to one. When dmax⁡=0d_{\max} = 0, we have P(0)=IP(0) = I.

Topology update at failure

Let S(k)=A(k)∖F(k)S(k) = \mathcal{A}(k) \setminus\mathcal{F}(k) be the surviving nodes. Their graph is G(k+1)=G[S(k)]G(k + 1) = G[S(k)]. The matrix P+(k)P^{+}(k) retains dimension n×nn \times n associated with the initial node set VV. For i∈S(k)i \in S(k), the entries read

pij+(k)={0,if j∉S(k),pii(k)+∑ℓ∈F(k)piℓ(k),if j∈S(k), j=i,pij(k),if j∈S(k), j≠i.(6)p_{ij}^{+}(k) = \begin{cases} 0, & \text{if } j \notin S(k),\\ p_{ii}(k) + \sum_{\ell\in\mathcal{F}(k)} p_{i\ell}(k), & \text{if } j \in S(k),\ j = i,\\ p_{ij}(k), & \text{if } j \in S(k),\ j \ne i. \end{cases} \tag*{(6)}

For every i∈F(k)∪R(k)i \in\mathcal{F}(k) \cup\mathcal{R}(k), the entries read

pij+(k)={1,if j=i,0,otherwise.(7)p_{ij}^{+}(k) = \begin{cases} 1, & \text{if } j = i,\\ 0, & \text{otherwise}. \end{cases} \tag*{(7)}

By (5a) and (6), also pij+(k)=0p_{ij}^{+}(k) = 0 for i∈F(k)∪R(k)i \in\mathcal{F}(k) \cup\mathcal{R}(k), j≠ij \ne i. The intermediate load vector is computed as

x^(k)=P+(k)Tx(k).(8)\widehat{\boldsymbol{x}}(k) = P^{+}(k)^{\mathsf{T}}\boldsymbol{x}(k). \tag*{(8)}

This vector gives the load distribution after the matrix update and before the newly failed-node loads are reassigned. By (5b), the transfer weight previously assigned from a surviving node to a newly failed node is retained by that survivor as self-weight, which is consistent with the weight handling of consensus iterations over switching topologies [13]. In contrast, naive row–column deletion without this reassignment can lead to unnecessary loss of load under the nominal dynamics. For a three-node complete graph with ε=1/3\varepsilon= 1/3, failure of node 2 would give

Pnaive=13[101030101],P+=13[201030102].(9)P^{\mathrm{naive}} = \frac{1}{3} \begin{bmatrix} 1 & 0 & 1\\ 0 & 3 & 0\\ 1 & 0 & 1 \end{bmatrix}, \qquad P^{+} = \frac{1}{3} \begin{bmatrix} 2 & 0 & 1\\ 0 & 3 & 0\\ 1 & 0 & 2 \end{bmatrix}. \tag*{(9)}

The surviving rows of PnaiveP^{\mathrm{naive}} sum to 2/32/3, so nominal transfers loose (x1+x3)/3(x_1 + x_3)/3. In P+P^{+}, diagonal compensation preserves unit row sums and therefore also total load before redistribution.

Failed-load redistribution and state update

We now define how the load of each newly failed node is redistributed. We assume that this load remains available for a one-time reassignment using the node’s connections immediately before removal. Only surviving neighbors can receive it and these incident connections are excluded from subsequent nominal transfers. For i∈F(k)i \in\mathcal{F}(k), define the active receiving-neighbor set as

Ni(k)={j∈S(k):(i,j)∈E}.(10)\mathcal{N}_i(k) = \{j \in S(k) : (i,j) \in E\}. \tag*{(10)}

Let qij(k)≥0q_{ij}(k) \ge0 be the load transferred from failed node ii to j∈Ni(k)j \in\mathcal{N}_i(k), and let si(k)≥0s_i(k) \ge0 be its shed or unserved load. All newly failed nodes satisfy the failed-load balance

∑j∈Ni(k)qij(k)+si(k)=xi(k),for all i∈F(k).(11)\sum_{j \in\mathcal{N}_i(k)} q_{ij}(k) + s_i(k) = x_i(k),\qquad\text{for all } i \in\mathcal{F}(k). \tag*{(11)}

Thus, every part of newly failed-node load is either assigned to an admissible receiver or marked explicitly as unserved. At each time step, the state is updated in the following order. First, F(k)\mathcal{F}(k) is derived from x(k)\boldsymbol{x}(k) with (1a). The load-transfer matrix is then updated to P+(k)P^{+}(k), and the intermediate load vector x^(k)\widehat{\boldsymbol{x}}(k) is computed with (7). Then a redistribution scheme determines qij(k)q_{ij}(k) and si(k)s_i(k). For each j∈S(k)j \in S(k), let Lj(k)={i∈F(k)∣j∈Ni(k)}\mathcal{L}_j(k) = \{i \in\mathcal{F}(k) \mid j \in\mathcal{N}_i(k)\} denote the set of newly failed nodes that can transfer load to jj. Then the state update is

xj(k+1)=x^j(k)+∑i∈Lj(k)qij(k),for j∈S(k),(12)x_j(k + 1) = \widehat{x}_j(k) + \sum_{i \in\mathcal{L}_j(k)} q_{ij}(k),\qquad\text{for } j \in S(k), \tag*{(12)}
xi(k+1)=0,for i∈F(k)∪R(k).(13)x_i(k + 1) = 0,\qquad\text{for } i \in\mathcal{F}(k) \cup\mathcal{R}(k). \tag*{(13)}

(12) dispatches the load at each surviving node, whereas (11b) sets all failed-node states to zero. Then the update A(k+1)=A(k)∖F(k)\mathcal{A}(k+1)=\mathcal{A}(k)\setminus\mathcal{F}(k) and P(k+1)=P+(k)P(k+1)=P^{+}(k) is performed. This update order is used throughout the analyses and simulations.

Remark 1: The update (11a)–(11b) can be equivalently written as x(k+1)=P+(k)Tx(k)+ϕ(k)\boldsymbol{x}(k+1)=P^{+}(k)^{\mathsf{T}}\boldsymbol{x}(k)+\boldsymbol{\phi}(k), where ϕ(k)∈Rn\boldsymbol{\phi}(k)\in\mathbb{R}^{n} accounts for failed-load removals and redistribution. Its entries are

ϕj(k)={∑i∈Lj(k)qij(k),if j∈S(k),−xj(k),if j∈F(k),0,if j∈R(k).(14)\phi_j(k)= \begin{cases} \sum_{i\in\mathcal{L}_j(k)}q_{ij}(k), & \text{if }j\in\mathcal{S}(k),\\ -x_j(k), & \text{if }j\in\mathcal{F}(k),\\ 0, & \text{if }j\in\mathcal{R}(k). \end{cases} \tag*{(14)}

At a failure-free step, F(k)=∅\mathcal{F}(k)=\varnothing implies P+(k)=P(k)P^{+}(k)=P(k) and ϕ(k)=0\boldsymbol{\phi}(k)=0, so the full update reduces to (2).

Load Balance and Lossless Redistribution

In this section, we first show that the proposed matrix update preserves row stochasticity and derive the resulting total-load balance. We then characterize when the loads of simultaneously failed nodes can be fully redistributed without exceeding the capacities of the surviving nodes.

We start by showing that (5b) preserves the stochastic structure required by (3).

Proposition 1: If P(k)P(k) is nonnegative and row stochastic, then the update (5a)–(6) produces a nonnegative, row-stochastic P+(k)P^{+}(k). If P(k)P(k) is also symmetric, then P+(k)P^{+}(k) is symmetric and doubly stochastic.

Proof: Nonnegativity follows because the update only retains nonnegative entries, sets entries to zero or one, and adds removed nonnegative weights to diagonal. For entries i∈S(k)i\in\mathcal{S}(k), summing the updated rows gives

∑j∈Vpij+(k)=pii+(k)+∑j∈S(k)∖{i}pij+(k)+∑j∉S(k)pij+(k)\sum_{j\in\mathcal{V}}p_{ij}^{+}(k) =p_{ii}^{+}(k)+\sum_{j\in\mathcal{S}(k)\setminus\{i\}}p_{ij}^{+}(k)+\sum_{j\notin\mathcal{S}(k)}p_{ij}^{+}(k)
=pii(k)+∑ℓ∈F(k)piℓ(k)+∑j∈S(k)∖{i}pij(k)=∑j∈F(k)∪S(k)pij(k)=∑j∈Vpij(k)=1,(15)=p_{ii}(k)+\sum_{\ell\in\mathcal{F}(k)}p_{i\ell}(k)+\sum_{j\in\mathcal{S}(k)\setminus\{i\}}p_{ij}(k) =\sum_{j\in\mathcal{F}(k)\cup\mathcal{S}(k)}p_{ij}(k) =\sum_{j\in\mathcal{V}}p_{ij}(k)=1, \tag*{(15)}

since entries pij(k)p_{ij}(k) associated with previously failed nodes j∈R(k)j\in\mathcal{R}(k) are already zero outside their diagonals. For i∈F(k)∪R(k)i\in\mathcal{F}(k)\cup\mathcal{R}(k), the updated row is an identity row and therefore also sums to one. If P(k)P(k) is symmetric, all surviving off-diagonal pairs remain unchanged and both entries incident to a failed node are set to zero. Hence P+(k)P^{+}(k) remains symmetric. Symmetry and unit row sums then imply unit column sums.

Thus, the updated matrix preserves total load under the nominal dynamics, whether one or several nodes fail at the same time. The next proposition gives the resulting total-load balance.

Proposition 2: In the state update (11a)–(11b), suppose that redistribution flows and unserved loads satisfy (10). Then,

1Tx(k+1)=1Tx(k)−∑i∈F(k)si(k).(16)\mathbf{1}^{\mathsf{T}}\boldsymbol{x}(k+1)=\mathbf{1}^{\mathsf{T}}\boldsymbol{x}(k)-\sum_{i\in\mathcal{F}(k)}s_i(k). \tag*{(16)}

Proof: By Proposition 1, P+(k)1=1P^{+}(k)\mathbf{1}=\mathbf{1}. So, by (7),

1Tx^(k)=1TP+(k)Tx(k)=(P+(k)1)Tx(k)=1Tx(k).\mathbf{1}^{\mathsf{T}}\widehat{\boldsymbol{x}}(k)=\mathbf{1}^{\mathsf{T}}P^{+}(k)^{\mathsf{T}}\boldsymbol{x}(k) =(P^{+}(k)\mathbf{1})^{\mathsf{T}}\boldsymbol{x}(k) =\mathbf{1}^{\mathsf{T}}\boldsymbol{x}(k).

The isolated column of each newly failed node i∈F(k)i\in\mathcal{F}(k) gives

x^i(k)=∑j∈Vpji+(k)xj(k)=(5a),(6)xi(k).(17)\widehat{x}_i(k)=\sum_{j\in\mathcal{V}}p_{ji}^{+}(k)x_j(k)\overset{\text{(5a),(6)}}{=}x_i(k). \tag*{(17)}

Previously failed nodes i∈R(k)i\in\mathcal{R}(k) have zero load by the irreversible-failure rule, and their isolated identity form also gives x^i(k)=0\widehat{x}_i(k)=0. Since S(k)\mathcal{S}(k), F(k)\mathcal{F}(k), and R(k)\mathcal{R}(k) partition V\mathcal{V}, the intermediate load on surviving nodes is

∑j∈S(k)x^j(k)=1Tx^(k)−∑i∈F(k)x^i(k)−∑i∈R(k)x^i(k)\sum_{j\in\mathcal{S}(k)}\widehat{x}_j(k) =\mathbf{1}^{\mathsf{T}}\widehat{\boldsymbol{x}}(k)-\sum_{i\in\mathcal{F}(k)}\widehat{x}_i(k)-\sum_{i\in\mathcal{R}(k)}\widehat{x}_i(k)
=1Tx(k)−∑i∈F(k)xi(k).(18)=\mathbf{1}^{\mathsf{T}}\boldsymbol{x}(k)-\sum_{i\in\mathcal{F}(k)}x_i(k). \tag*{(18)}

By (11b), we have that

1Tx(k+1)=∑j∈S(k)xj(k+1)\mathbf{1}^{\mathsf{T}}\boldsymbol{x}(k+1)=\sum_{j\in\mathcal{S}(k)}x_j(k+1)
=∑j∈S(k)x^j(k)+∑j∈S(k)∑i∈Lj(k)qij(k)=\sum_{j\in\mathcal{S}(k)}\widehat{x}_j(k)+\sum_{j\in\mathcal{S}(k)}\sum_{i\in\mathcal{L}_j(k)}q_{ij}(k)
=∑j∈S(k)x^j(k)+∑i∈F(k)∑j∈Ni(k)qij(k)=\sum_{j\in\mathcal{S}(k)}\widehat{x}_j(k)+\sum_{i\in\mathcal{F}(k)}\sum_{j\in\mathcal{N}_i(k)}q_{ij}(k)
=1Tx(k)−∑i∈F(k)xi(k)+∑i∈F(k)(xi(k)−si(k))=\mathbf{1}^{\mathsf{T}}\boldsymbol{x}(k)-\sum_{i\in\mathcal{F}(k)}x_i(k)+\sum_{i\in\mathcal{F}(k)}\bigl(x_i(k)-s_i(k)\bigr)
=1Tx(k)−∑i∈F(k)si(k).(19)=\mathbf{1}^{\mathsf{T}}\boldsymbol{x}(k)-\sum_{i\in\mathcal{F}(k)}s_i(k). \tag*{(19)}

This completes the proof.

If si(k)=0s_i(k)=0 for every i∈F(k)i\in\mathcal{F}(k), then (14) gives lossless redistribution. Otherwise, total load decreases by ∑i∈F(k)si(k)\sum_{i\in\mathcal{F}(k)}s_i(k), which is precisely the amount that could not be redistributed.

We next characterize whether all newly failed loads can be transferred without immediately overloading a survivor. Define the residual capacity after the transfers x^(k)=P+(k)Tx(k)\widehat{\boldsymbol{x}}(k)=P^{+}(k)^{\mathsf{T}}\boldsymbol{x}(k) by

rj(k)=[cj−x^j(k)]+.(20)r_j(k)=[c_j-\widehat{x}_j(k)]_{+}. \tag*{(20)}

where [z]+=max⁡{z,0}[z]_{+}=\max\{z,0\}. For U⊆F(k)\mathcal{U}\subseteq\mathcal{F}(k), let

N(U,k)=⋃i∈UNi(k)(21)\mathcal{N}(\mathcal{U},k)=\bigcup_{i\in\mathcal{U}}\mathcal{N}_i(k) \tag*{(21)}

denote the set of active receivers adjacent to at least one node in U\mathcal{U}.

Theorem 1: Let F(k)\mathcal{F}(k) be the set of nodes that fail simultaneously at time kk, and assume that x^j(k)≤cj\widehat{x}_j(k)\le c_j for every

j∈S(k)j \in\mathcal{S}(k). A redistribution with nonnegative flows only to j∈Ni(k)j \in\mathcal{N}_i(k), satisfying (10) with si(k)=0s_i(k)=0 and xj(k+1)≤cjx_j(k+1)\le c_j for every j∈S(k)j \in\mathcal{S}(k), exists if and only if

∑i∈Uxi(k)≤∑j∈N(U,k)rj(k)for every U⊆F(k).(22)\sum_{i\in\mathcal{U}}x_i(k)\le\sum_{j\in\mathcal{N}(\mathcal{U},k)}r_j(k)\quad\text{for every }\mathcal{U}\subseteq\mathcal{F}(k). \tag*{(22)}

Moreover, the minimum unavoidable unserved load is

σ⋆(k)=max⁡U⊆F(k)[∑i∈Uxi(k)−∑j∈N(U,k)rj(k)]+.(23)\sigma^\star(k)=\max_{\mathcal{U}\subseteq\mathcal{F}(k)}\left[\sum_{i\in\mathcal{U}}x_i(k)-\sum_{j\in\mathcal{N}(\mathcal{U},k)}r_j(k)\right]_+. \tag*{(23)}

Proof: If F(k)=∅\mathcal{F}(k)=\varnothing, both claims hold with σ⋆(k)=0\sigma^\star(k)=0. Otherwise, let M=∑i∈F(k)xi(k)>0M=\sum_{i\in\mathcal{F}(k)}x_i(k)>0. The idea is to represent the redistribution as a flow from the failed nodes to the receivers and to apply the max-flow/min-cut theorem [14].

First, we construct an auxiliary directed network as illustrated in Figure 1. To distinguish it from GG, we refer to its elements as vertices and arcs. Connect the source to each i∈F(k)i\in\mathcal{F}(k) with capacity xi(k)x_i(k), vertex ii to each j∈Ni(k)j\in\mathcal{N}_i(k) with capacity MM, and each receiver j∈S(k)j\in\mathcal{S}(k) to the sink with capacity rj(k)r_j(k). Since M≥xi(k)M\ge x_i(k), the failed-to-receiver arcs never restrict a transfer.

Auxiliary flow network for the connections in Example 1

Figure 1. Auxiliary flow network for the connections in Example 1. Edge labels indicate the corresponding capacities.

Then, we relate flows in this network to redistributions. A feasible flow is nonnegative, respects arc capacities, and conserves flow at every vertex except the source and sink. Its value is the total flow leaving the source. Let the flow on arc (i,j)(i,j) be qij(k)q_{ij}(k). Conservation at ii makes the source-to-ii flow equal to ∑j∈Ni(k)qij(k)\sum_{j\in\mathcal{N}_i(k)}q_{ij}(k). Defining si(k)s_i(k) as the unused capacity of this arc, i.e., xi(k)x_i(k) minus this flow, gives the failed-load balance (10). Conservation at jj makes the jj-to-sink flow equal to ∑i∈Lj(k)qij(k)\sum_{i\in\mathcal{L}_j(k)}q_{ij}(k). Since x^j(k)≤cj\widehat{x}_j(k)\le c_j, we have rj(k)=cj−x^j(k)r_j(k)=c_j-\widehat{x}_j(k), so by (11a) the capacity of this arc is respected if and only if xj(k+1)≤cjx_j(k+1)\le c_j. Thus, feasible flows correspond to admissible redistributions within the receiver capacities. A flow of value MM saturates every source arc and is equivalent to lossless redistribution.

Finally, we determine the maximum flow value. A source–sink cut partitions the vertices with the source and sink on opposite sides. Its capacity is the sum of capacities of the arcs, directed from the source side to the sink side crossing it. The max-flow/min-cut theorem equates the maximum flow value and the minimum cut capacity. The cut with only the source on its side has capacity MM, and any cut crossing a failed-to-receiver arc has capacity at least MM. Consider a cut crossing no such arc. Let U\mathcal{U} contain the failed vertices on the source side. Every receiver in N(U,k)\mathcal{N}(\mathcal{U},k) must then also lie on that side. For fixed U\mathcal{U}, placing only these receivers on the source side minimizes the cut capacity. The crossing arcs run from the source to failed vertices in F(k)∖U\mathcal{F}(k)\setminus\mathcal{U} and from receivers in N(U,k)\mathcal{N}(\mathcal{U},k) to the sink, giving

C(U)=∑i∈F(k)∖Uxi(k)+∑j∈N(U,k)rj(k)=M−∑i∈Uxi(k)+∑j∈N(U,k)rj(k).(24)\begin{aligned} C(\mathcal{U})=\sum_{i\in\mathcal{F}(k)\setminus\mathcal{U}}x_i(k)+\sum_{j\in\mathcal{N}(\mathcal{U},k)}r_j(k) \\ &=M-\sum_{i\in\mathcal{U}}x_i(k)+\sum_{j\in\mathcal{N}(\mathcal{U},k)}r_j(k). \tag*{(24)} \end{aligned}

Hence, the maximum flow value is min⁡U⊆F(k)C(U)\min_{\mathcal{U}\subseteq\mathcal{F}(k)}C(\mathcal{U}), which equals MM exactly when (20) holds. By (22), the minimum unserved load is therefore

σ⋆(k)=M−min⁡U⊆F(k)C(U)=max⁡U⊆F(k)[∑i∈Uxi(k)−∑j∈N(U,k)rj(k)]+.\begin{aligned} \sigma^\star(k)=M-\min_{\mathcal{U}\subseteq\mathcal{F}(k)}C(\mathcal{U}) \\ &=\max_{\mathcal{U}\subseteq\mathcal{F}(k)}\left[\sum_{i\in\mathcal{U}}x_i(k)-\sum_{j\in\mathcal{N}(\mathcal{U},k)}r_j(k)\right]_+. \end{aligned}

The following example shows why comparing total failed load with total residual capacity is insufficient when the admissible transfers are restricted by the network topology.

Example 1: Consider two simultaneously failed nodes i1i_1 and i2i_2, each carrying 0.80.8 units, and two active receivers j1j_1 and j2j_2 with residual capacities rj1=ρr_{j_1}=\rho and rj2=1r_{j_2}=1. Let i1i_1 be connected only to j1j_1, while i2i_2 is connected to both receivers. The aggregate residual capacity is sufficient when ρ≥0.6\rho\ge0.6. However, applying (20) to U={i1}\mathcal{U}=\{i_1\} gives the tighter condition ρ≥0.8\rho\ge0.8. Moreover, equal redistribution sends 0.80.8 from i1i_1 to j1j_1 and 0.40.4 from i2i_2 to j1j_1, so it violates that receiver’s capacity unless ρ≥1.2\rho\ge1.2. Hence, aggregate residual capacity does not capture the topology-induced bottleneck.

Remark 2 (Single-node case): Under the assumptions of Theorem 1, for F(k)={i}\mathcal{F}(k)=\{i\}, lossless redistribution within receiver capacities exists if and only if xi(k)≤∑j∈Ni(k)rj(k)x_i(k)\le\sum_{j\in\mathcal{N}_i(k)}r_j(k).

Optimization-Based Redistribution Control

This section presents a two-stage linear programming approach for redistributing newly failed-node loads. The first stage minimizes unserved load, while the second stage minimizes the maximum capacity utilization among surviving nodes. As opposed to equal redistribution, we consider residual capacities and coordinate failed nodes sharing a receiver by actively selecting the redistribution flows. Let q(k)q(k) collect qij(k)q_{ij}(k) for i∈F(k)i\in\mathcal{F}(k) and j∈Ni(k)j\in\mathcal{N}_i(k), and let s(k)s(k) collect si(k)s_i(k) for i∈F(k)i\in\mathcal{F}(k).

Stage 1: Minimum shedding

The first stage finds the minimum unserved load σ⋆(k)\sigma^\star(k) consistent with the surviving-node capacities.

Problem 1 (Minimum-shedding redistribution): When F(k)≠∅\mathcal{F}(k)\ne\varnothing, let us compute σ⋆(k)\sigma^\star(k) as follows:

minimize⁡q(k), s(k)∑i∈F(k)si(k)(25)\underset{q(k),\,s(k)}{\operatorname{minimize}}\quad\sum_{i\in\mathcal{F}(k)}s_i(k) \tag*{(25)}

subject to

x^(k)=P+(k)Tx(k),(26)\hat{x}(k)=P^{+}(k)^{\mathsf{T}}x(k), \tag*{(26)}
x^j(k)+∑i∈Lj(k)qij(k)≤cj,j∈S(k),(27)\hat{x}_{j}(k)+\sum_{i\in\mathcal{L}_{j}(k)}q_{ij}(k)\le c_{j},\quad j\in\mathcal{S}(k), \tag*{(27)}
∑j∈Ni(k)qij(k)+si(k)=xi(k),i∈F(k),(28)\sum_{j\in\mathcal{N}_{i}(k)}q_{ij}(k)+s_{i}(k)=x_{i}(k),\quad i\in\mathcal{F}(k), \tag*{(28)}
q(k)≥0,s(k)≥0.(29)q(k)\ge0,\qquad s(k)\ge0. \tag*{(29)}

Constraint (23c) enforces capacity constraints, whereas (23d) permits load to leave only through si(k)s_i(k). Under the nominal survivor-feasibility assumption x^j(k)≤cj\hat{x}_j(k)\le c_j of Theorem 1, Problem 1 is always feasible for qij(k)=0q_{ij}(k)=0 and si(k)=xi(k)s_i(k)=x_i(k). If x^j(k)>cj\hat{x}_j(k)>c_j for any surviving node before redistribution, Problem 1 is infeasible because the nonnegative redistribution flows qij(k)q_{ij}(k) cannot reduce that node’s existing load. No capacity guarantee is made in this case. Note, that problem 1 leads to σ⋆(k)=0\sigma^{\star}(k)=0 if lossless redistribution is feasible, and σ⋆(k)>0\sigma^{\star}(k)>0 if a minimum load that must remain unserved exists.

Stage 2: Utilization balancing

Stage 2 minimizes maximum capacity utilization while allowing a total unserved load of at most σ⋆(k)+δLP\sigma^{\star}(k)+\delta_{\mathrm{LP}}, where δLP>0\delta_{\mathrm{LP}}>0 is a small tolerance that accounts for the numerical precision of the solver. This maximizes the smallest unused capacity fraction 1−xj(k+1)/cj1-x_j(k+1)/c_j.

Problem 2 (Utilization-balanced redistribution): Given σ⋆(k)\sigma^{\star}(k) from Problem 1, solve

minimize⁡q(k),s(k),ηη(30)\begin{aligned} \underset{q(k),s(k),\eta}{\operatorname{minimize}}\quad&\eta \tag*{(30)} \end{aligned}

subject to

x^(k)=P+(k)Tx(k),(31)\hat{x}(k)=P^{+}(k)^{\mathsf{T}}x(k), \tag*{(31)}
x^j(k)+∑i∈Lj(k)qij(k)≤ηcj,j∈S(k),(32)\hat{x}_{j}(k)+\sum_{i\in\mathcal{L}_{j}(k)}q_{ij}(k)\le\eta c_{j},\quad j\in\mathcal{S}(k), \tag*{(32)}
∑j∈Ni(k)qij(k)+si(k)=xi(k),i∈F(k),(33)\sum_{j\in\mathcal{N}_{i}(k)}q_{ij}(k)+s_{i}(k)=x_{i}(k),\quad i\in\mathcal{F}(k), \tag*{(33)}
∑i∈F(k)si(k)≤σ⋆(k)+δLP,(34)\sum_{i\in\mathcal{F}(k)}s_{i}(k)\le\sigma^{\star}(k)+\delta_{\mathrm{LP}}, \tag*{(34)}
q(k)≥0,s(k)≥0,η≥0.(35)q(k)\ge0,\qquad s(k)\ge0,\qquad\eta\ge0. \tag*{(35)}

Since cj>0c_j>0, η\eta bounds the largest normalized surviving-node load after redistribution. Problem 2 is feasible because any optimizer of Problem 1, together with η=1\eta=1, satisfies all its constraints. Let η⋆(k)\eta^{\star}(k) denote the optimal value of Problem 2. Hence, η⋆(k)≤1\eta^{\star}(k)\le1, and every surviving node remains within its capacity. The Stage 2 solution is therefore also feasible for Stage 1. Stage 2 provides

σ⋆(k)≤∑i∈F(k)si(k)≤σ⋆(k)+δLP.(36)\sigma^{\star}(k)\le\sum_{i\in\mathcal{F}(k)}s_i(k)\le\sigma^{\star}(k)+\delta_{\mathrm{LP}}. \tag*{(36)}

Thus, balancing receiver utilization increases the unserved load by at most the desired numerical tolerance. When F(k)≠∅\mathcal{F}(k)\ne\varnothing, Problem 1 is solved first, and Problem 2 is then solved using σ⋆(k)\sigma^{\star}(k). Both problems concern only the current redistribution.

For subsequent nominal updates, let B=[pij+(k)]i,j∈S(k)B=[p_{ij}^{+}(k)]_{i,j\in\mathcal{S}(k)} be the surviving-node block, and let cSc_{\mathcal{S}} and xS(h)x_{\mathcal{S}}(h) denote the capacity and load vectors only containing the values of S(k)\mathcal{S}(k).

Proposition 3 (Failure-free invariance): Suppose S(k)≠∅\mathcal{S}(k)\ne\varnothing, B≥0B\ge0 is row stochastic, and cS>0c_{\mathcal{S}}>0. With BB fixed and no further external input, the nominal updates xS(h+1)=BTxS(h)x_{\mathcal{S}}(h+1)=B^{\mathsf{T}}x_{\mathcal{S}}(h) preserve 0≤xS(h)≤cS0\le x_{\mathcal{S}}(h)\le c_{\mathcal{S}} for every initial state within these bounds if and only if

BTcS=cS.(37)B^{\mathsf{T}}c_{\mathcal{S}}=c_{\mathcal{S}}. \tag*{(37)}

If the condition holds and Problem 1 is feasible, applying the Stage 2 solution gives no additional failures at any h≥k+1h\ge k+1.

Proof. Nonnegativity of BB gives

0≤BTxS(h)≤BTcS=cS,0\le B^{\mathsf{T}}x_{\mathcal{S}}(h)\le B^{\mathsf{T}}c_{\mathcal{S}}=c_{\mathcal{S}},

so the condition is sufficient by induction. Necessity follows by taking the feasible state xS(h)=cSx_{\mathcal{S}}(h)=c_{\mathcal{S}}, which requires BTcS≤cSB^{\mathsf{T}}c_{\mathcal{S}}\le c_{\mathcal{S}}. Since B1=1B\mathbf{1}=\mathbf{1}, both vectors have the same sum. Since no entry on the left can be larger, none can be smaller either, so equality holds componentwise. Finally, the bound η⋆(k)≤1\eta^{\star}(k)\le1 resulting from Problem 2 places the state after redistribution within these invariant bounds.

Uniform capacities with a doubly stochastic BB, as in Section V, satisfy this condition, whereas for unequal capacities a redistribution within all capacities at step kk can still lead to later overloads. Under this condition, the surviving nodes also satisfy x^S(k)=BTxS(k)≤cS\hat{x}_{\mathcal{S}}(k)=B^{\mathsf{T}}x_{\mathcal{S}}(k)\le c_{\mathcal{S}}, so Problem 1 is always feasible.

Remark 3 (Directed networks): Propositions 1 and 2, Theorem 1, and Problems 1 and 2 do not rely on symmetry. They also hold for a directed graph GG in which an edge (i,j)(i,j) only allows load transfer from ii to jj, if Ni(k)\mathcal{N}_{i}(k) denotes the set of surviving out-neighbors of node ii and P(0)=I−εLP(0)=I-\varepsilon L is constructed with the out-degree Laplacian L=Dout−AL=D_{\mathrm{out}}-A and 0≤ε≤1/dmax⁡out0\le\varepsilon\le1/d_{\max}^{\mathrm{out}}. In this case, however, BB is in general not doubly stochastic. Hence, the condition of Proposition 3 may fail even for uniform capacities, and a redistribution within all capacities at step kk can still lead to later overloads.

Numerical evaluation

This section compares equal redistribution, residual-capacity redistribution, and controlled redistribution on grid and scale-free networks. The evaluation focuses on secondary failures and unserved load.

Simulation setup and metrics

We consider the following networks: 10×1010\times10 grid and scale-free networks with n=100n=100, ci=1 ∀i∈Vc_i=1\ \forall i\in V, baseline load xi=0.1 ∀i∈Vx_i=0.1\ \forall i\in V, and P(0)P(0) as in (5) with fixed ε=0.5/dmax⁡\varepsilon=0.5/d_{\max}. In each scenario, we consider two nodes, with a common surviving neighbor. Both of them receive an additional load Δ∈{1,1.25,2,3,4.5}\Delta\in\{1,1.25,2,3,4.5\} causing them to fail simultaneously. Their common surviving neighboring node ensures that the two failed nodes compete for at least one receiver. On the 10×1010\times10 grid, we consider all 322 such node pairs, which gives 1610 scenarios per redistribution method over all values of Δ\Delta. For each of 30 Barabasi–Albert graphs [15] with attachment parameter 2, we sample 20 such pairs uniformly without replacement, which gives 3000 scenarios per method.

We compare equal redistribution, residual-capacity proportional redistribution, and the controlled redistribution of § 4. The residual-capacity method distributes each failed-node load among its active receivers in proportion to the residual capacities rj(k)r_j(k) defined in (18). If all corresponding residual capacities are zero, it uses equal redistribution. The optimization problems associated with controlled redistribution are solved with scipy.optimize.linprog using HiGHS. Let F0\mathcal{F}_0 be the set of initially disturbed nodes, and let Fe\mathcal{F}_e contain all nodes that fail during the cascade. The secondary-failure fraction is fsec=∣Fe∖F0∣/(n−∣F0∣)f_{\mathrm{sec}} = \lvert\mathcal{F}_e \setminus\mathcal{F}_0\rvert/(n-\lvert\mathcal{F}_0\rvert). The unserved-load fraction is defined as the total unserved load accumulated over the cascade divided by the initial total load. For the uniform-capacity simulations, Proposition 3 ensures that, once a step produces no new failure, subsequent nominal updates cannot cause another one. All runs pass the state, flow, stochasticity, and balance checks, and no solver fails or iteration limit is reached.

Simulation results and discussion

For the grid network, Figure 2(a)–(Figure 2b) shows the results. Controlled redistribution produces no secondary failures over the tested range. At the largest tested disturbance, Δ=4.5\Delta= 4.5, it also leaves less load unserved on average than either of the equal redistribution or the residual capacity redistribution. Equal redistribution passes on all failed-node load whenever a surviving neighbor remains, even if that neighbor lacks sufficient capacity. The resulting overload can cause further failures and if a newly failed node has no surviving neighbor, its load remains unserved. Residual-capacity redistribution uses the available spare capacity, but treats each failed node separately. When several failed nodes share a receiver, the sum of their transfers may exceed its residual capacity. Controlled redistribution instead selects all transfers together and respects each receiver’s capacity.

Comparison of the three redistribution methods

Figure 2. Comparison of the three redistribution methods after two simultaneous initial failures with a common surviving neighbor. Curves show mean secondary-failure and unserved-load fractions for the grid in (a)–(b) and scale-free networks in (c)–(d).

For the scale-free networks, Figure 2(c)–(Figure 2d) shows a trade-off. Controlled redistribution again produces no secondary failures. However, at the largest tested disturbance, Δ=4.5\Delta= 4.5, it leaves more load unserved on average than either heuristic. Thus, avoiding further failures does not necessarily preserve more served load. The two optimization problems enforce receiver capacities at the current step, but do not minimize total unserved load over the complete simulation horizon, since a redistribution that is optimal at the current step can increase unserved load later.

Conclusion

We proposed a topology update approach for irreversible node failures that preserves row stochasticity and makes unserved load explicit. We also derived a condition for lossless redistribution after simultaneous failures and formulated a two-stage controller to minimize unserved load and balance receiver utilization. For two initial failures with shared receivers, the controller avoided secondary failures in all tested cases. At the largest disturbance, it left less load unserved than both heuristics on the grid network, but more on the scale-free networks. The benefit in served load therefore depends on the network and disturbance, rather than mitigation of failures alone. Future work will consider multi-step and robust formulations that account for future cascade stages.

References

  1. [1]A. E. Motter and Y.-C. Lai, “Cascade-based attacks on complex networks,” Phys. Rev. E, vol. 66, no. 6, p. 065102, 2002.pubmed.ncbi.nlm.nih.gov/12513335
  2. [2]P. Crucitti, V. Latora, and M. Marchiori, “Model for cascading failures in complex networks,” Phys. Rev. E, vol. 69, no. 4, p. 045104, 2004.pubmed.ncbi.nlm.nih.gov/15169056
  3. [3]I. Dobson, B. A. Carreras, V. E. Lynch, and D. E. Newman, “Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization,” Chaos, vol. 17, no. 2, p. 026103, 2007.pubmed.ncbi.nlm.nih.gov/17614690
  4. [4]S. Al-Takrouni and A. V. Savkin, “A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks,” Physica A, vol. 392, no. 23, pp. 6135–6145, 2013.
  5. [5]R. Kumar, S. Kumari, and M. Bala, “Minimizing the effect of cascade failure in multilayer networks with optimal redistribution of link loads,” J. Complex Netw., vol. 9, no. 6, p. cnab043, 2021.
  6. [6]L. D. Valdez, L. Shekhtman, C. E. La Rocca, X. Zhang, S. V. Buldyrev, P. A. Trunfio, L. A. Braunstein, and S. Havlin, “Cascading failures in complex networks,” J. Complex Netw., vol. 8, no. 2, p. cnaa013, 2020.DOI
  7. [7]S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, and S. Havlin, “Catastrophic cascade of failures in interdependent networks,” Nature, vol. 464, no. 7291, pp. 1025–1028, 2010.arxiv.org/abs/1012.0206
  8. [8]A. E. Motter, “Cascade control and defense in complex networks,” Phys. Rev. Lett., vol. 93, no. 9, p. 098701, 2004.pubmed.ncbi.nlm.nih.gov/15447153
  9. [9]D. Bienstock, “Optimal control of cascading power grid failures,” in Proc. IEEE CDC-ECC, Orlando, FL, USA, 2011, pp. 2166–2173.DOI
  10. [10]S. Pahwa, C. Scoglio, S. Das, and N. Schulz, “Load-shedding strategies for preventing cascading failures in power grid,” Electr. Power Compon. Syst., vol. 41, no. 9, pp. 879–895, 2013.DOI
  11. [11]K. Savla, G. Como, and M. A. Dahleh, “Robust network routing under cascading failures,” IEEE Trans. Netw. Sci. Eng., vol. 1, no. 1, pp. 53–66, 2014.
  12. [12]G. Como, E. Lovisari, and K. Savla, “Throughput optimality and overload behavior of dynamical flow networks under monotone distributed routing,” IEEE Trans. Control Netw. Syst., vol. 2, no. 1, pp. 57–67, 2015.
  13. [13]R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proc. IEEE, vol. 95, no. 1, pp. 215–233, 2007.
  14. [14]L. R. Ford, Jr. and D. R. Fulkerson, “Maximal flow through a network,” Can. J. Math., vol. 8, pp. 399–404, 1956.
  15. [15]A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.

Paper details

vlnc:W_3yqkvxyz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents