1 Introduction

As a response to the growing threat of terrorism in the late 1990s, the U.S. federal government established the President’s Commission on Critical Infrastructure Protection (PCCIP) (E.O. 13010). In this executive order (E.O.) (1995), “infrastructure” was defined as:

The framework of interdependent networks and systems comprising identifiable industries, institutions (including people and procedures), and distribution capabilities that provide a reliable flow of products and services essential to the defense and economic security of the United States, the smooth functioning of government at all levels, and society as a whole (E.O. 13010).

More importantly, E.O. 13010 (1996) suggested that “... certain national infrastructures are so vital that their incapacity or destruction would have a debilitating impact on the defense or economic security of the United States.” The concept of “vital” or “critical” infrastructure is clearly an important one for establishing national security benchmarks. Basic inventories of critical infrastructure are often subdivided into sectors, and include (E.O. 13010, 1996; White House 2003): telecommunications, electrical power systems, gas and oil storage and transportation, banking and finance, transportation, water supply systems, emergency services (including medical, police, fire, and rescue), and continuity of government.

Given the vast array of infrastructure in these sectors, it is not surprising that fiscal constraints can limit the scope of protective measures applied to the nation’s critical infrastructure.Footnote 1 Moreover, the heightened concerns for security threats and the need to safeguard these sectors suggest that optimization-based approaches for identifying risk in networks of all sorts, ranging from gas and oil pipelines to transportation routes to telecommunication systems, are extremely important for prioritizing and evaluating fortification strategies to maintain the continuity of their functions (see White House 2003).

A common theme in the analysis and evaluation of network-based critical infrastructure is interdiction, where network elements (nodes or arcs) are disabled, intentionally or otherwise, disrupting the flow of valuable goods or services through the network. There has been much interest in examining vulnerabilities and risk in critical network infrastructure (Carlier et al. 1997; Soni and Pirkul 2000; Palmer et al. 2001; Carreras et al. 2002; Crucitti et al. 2004; Latora and Marchiori 2005; Chassin and Posse 2005; Grubesic and Murray 2006) and interdiction has been implicit, if not explicit, in most cases. Baran (1964) recognized that some network topologies provide a higher probability of survivability (or connectivity, more specifically) after an attack. In particular, distributed networks with higher levels of redundancy and diversity are good for ensuring connectivity, should interdiction take place. The topological properties of networks are further explored in examining “scale-free” networks (Albert et al. 2000; 2004; Barabasi et al. 2000, 2001). Results suggest that although scale-free networks like the Internet are very tolerant of random failures, a series of targeted attacks on the most highly connected nodes or “hubs” can be crippling. Nevertheless, performance of a network, viewed in terms of either vulnerability or survivability, ultimately centers on connectivity and whether flow can move between origins and destinations (see Bell 2000; Doyle et al. 2005). If interdiction to network-based critical infrastructure is to be guarded against or managed once it occurs, methods are needed for identifying and examining possible interdiction scenarios, a sentiment shared by Houck et al. (2004) and Salmeron et al. (2004).

The above discussion has highlighted that networks serve to deliver flow through a system of interconnected nodes and arcs and that planning for interdiction of this service is essential. With this in mind, this paper develops an integer programming model to evaluate the upper and lower bounds on flow disruption as a result of facility interdiction in a network. The next section provides a background review of previous modeling work in this area. An integer model formulation is then presented and discussed. An application analyzing potential interdiction of network components for the Abilene Internet2 backbone is given, highlighting the utility of the developed modeling approach. Finally, discussion and conclusions are provided.

2 Background

Optimization techniques have played a significant role in examining potential interdiction impacts, recognizing the insights they can provide for mitigating facility loss and prioritizing fortification efforts. Four categories of approaches are reviewed here: simulation, min-cut/shortest paths, network attributes, and system flow. Common to all categories is that nodes and/or arcs in the network may be interdicted. The differences in the categorical distinctions are the ways in which the network or its performance is evaluated.

Simulation has been an important optimization technique in general terms, and has proven valuable in the analysis of interdiction in critical network infrastructure. One benefit of simulation is that it typically allows for the examination of a range of impacts, with either implicit or explicit notions of optimized performance for a network. For example, Grubesic et al. (2003) examined basic graph theoretic measures of network connectivity, such as the degree of node and nodal centrality, for Internet backbone networks. As network elements were interdicted (or “removed”), the corresponding changes in network connectivity were documented. Latora and Marchiori (2005) also simulated the removal of nodes in a networked system, assessing performance and the criticality of each node individually. Crucitti et al. (2004) examined individual nodal capacities for a network and their ability to handle additional/excess information when other network elements (nodes) are lost. Similarly, Albert et al. (2004) apply this logic to simulations of node-based attacks on the North American power grid. In their simulations, consideration for secondary failures spawned by the initial attack is also addressed. These “cascading” failures are represented using a rank, remove, and recomputation method, similar to Holme et al. (2002). In this aforementioned work, assessment of origin–destination (O–D) flows is not addressed. Recently, however, Doyle et al. (2005) argue that O–D interaction is in fact an important component of engineered systems and explore a standard metric for network performance that examines end-user traffic demands between all pairs of end vertices (nodes) in a system. While the loss or removal of critical arcs/nodes in these systems can be instructive for identifying the varying levels of connectivity for networks, evaluating individual links independent of the presence or absence of all other network elements (arcs and nodes) can be myopic or misleading.

Another category for network evaluation involves assessing impacts relative to altering the maximum flow or shortest path for a given O–D pair. For example, one strategy for network interdiction is to maximize network disruption by removing the links with the greatest total value in a system (e.g. Wollmer 1964; Ratliff et al. 1975; Ball et al. 1989; Wood 1993). Similarly, one can also seek to maximize network disruption by removing the nodes most critical to system operation (Corley and Chang 1974; Corley and Sha 1982; Nardellia et al. 2003). The notion of flow (and its disruption) is implicit in many of these optimization-based approaches given the focus on altering the maximum O–D flow. However, recent research highlights the importance of explicitly modeling O–D flows (Myung and Kim 2004).

A third category of optimization modeling work characterizes impacts in terms of system performance or network characteristics. For example, Church et al. (2004) consider average service costs and coverage reduction in this context using median and covering location models, respectively. Grubesic and Murray (2006) examine nodal interdiction outcomes quantified as the total attributes (e.g., capacity) of arcs impacted. Extending this, Grubesic et al. (2006) model node and arc attributes, simultaneously, in the context of interdiction for a telecommunication backbone. Yet, while these models can approximate impact to network connectivity, they do not account for O–D flows in the network.

The final category is system flow. A more recent interest in interdiction studies is examining connectivity and O–D flow in networked systems. While maximum flow approaches seek to identify interdiction schemes that reduce the capacity of a particular O–D pair to interact, system flow approaches focus on the interaction between all O–D pairs. To address system flow Myung and Kim (2004) present an integer program to identify those arcs whose removal results in an upper bound on network failure and discuss an algorithm for finding a lower bound. Their formulation relies on identifying feasible paths for each O–D pair and tracking the availability of facilities involved in each path. A preprocessing technique is employed to focus only on O–D pairs that can be interdicted given the removal of a specified number of arcs. Ultimately, however, both the upper and lower bounds are heuristically derived.

Of interest in this paper is this fourth category, focusing on the explicit representation of O–D flow in a network. To this end, an optimization model is presented to identify optimal upper and lower bounds for potential network interdiction scenarios, with the intent to support management and planning efforts oriented toward assessing vulnerability and reliability in networked systems.

3 Modeling flow interdiction

From a planning and management perspective, an optimization model is necessary for identifying an interdiction scenario that maximizes or minimizes total flow disrupted. In this context, a network component is interdicted, rendering it inoperable, as commonly assumed in the literature. For modeling and discussion purposes, interdiction is limited to nodes in the network, though the work that follows can readily be extended to account for arc interdiction as well. Without loss of generality, the number of facilities interdicted is specified in advance. Given any general network G = (N,A), where N denotes the set of nodes and A the set of component arcs or linkages, it is assumed that all feasible, non-redundant paths in the network can be identified for any interacting pair of nodes. This assumption is not unlike that made to model flow capture (see Hodgson et al. 1996), network design (see Kalvenes et al. 2004), or arc interdiction (see Myung and Kim 2004). The following notation is used to formulate a model for the evaluation of flow interdiction:

k :

index of paths, entire set denoted K

j :

index of facilities, entire set denoted J

o :

index of origins, entire set denoted Ω

d :

index of destinations, entire set denoted \( \Lambda \)

N od :

set of paths enabling OD flow

f od :

flow observed between OD

p :

number of facilities to remove

φ k :

set of facilities along path k

X j :

\( \left\{ \begin{aligned}{} & 1{\text{ if facility }}j{\text{ is interdicted}} \\ & {\text{0 otherwise}} \\ \end{aligned} \right. \)

Y k :

\( \left\{ \begin{aligned}{} & 1{\text{ if path }}k{\text{ remains uneffected by interdiction}} \\ & {\text{0 otherwise}} \\ \end{aligned} \right. \)

Z od :

\( \left\{ \begin{aligned}{} & 1{\text{ if no flow possible between }}OD \\ & {\text{0 otherwise}} \\ \end{aligned} \right. \)

3.1 Flow interdiction model

Maximize or Minimize

$$ {\sum\limits_o {{\sum\limits_d {f_{{od}} Z_{{od}} } }} } $$
(1)

Subject to:

$$ {\sum\limits_{k \in N_{{od}} } {Y_{k} + Z_{{od}} \ge 1} }\quad \quad \forall o,d $$
(2)
$$ Z_{{od}} \le (1 - Y_{k} )\quad \quad \forall o,d{\text{,}}k \in N_{{od}},k $$
(3)
$$ Y_{k} \ge 1 - {\sum\limits_{j \in \Phi _{k} } {X_{j} } }\quad \quad \forall k $$
(4)
$$ Y_{k} \le (1 - X_{j} )\quad\quad\forall k,j \in \Phi _{k} $$
(5)
$$ {\sum\limits_j {X_{j} } } = p $$
(6)
$$ \begin{aligned}{} & X_{j} = {\left\{ {0,1} \right\}}\;\forall j \\ & Y_{k} = \{ 0,1\} \;\forall k \\ & Z_{{od}} = \{ 0,1\} \;\forall o,d \\ \end{aligned} $$
(7)

Objective (1) maximizes or minimizes total flow interdicted. Constraints (2) and (3) account for the existence of paths between a given O–D. Constraints (4) and (5) track whether a path is impacted by an interdiction scenario. Constraints (6) specify that p nodes are to be interdicted. Finally, Constraints (7) impose binary integer restrictions on decision variables.

The FIM is a unified model, structured to identify interdiction schemes that maximize or minimize total flow disruption in the network. It does this by accounting for nodes interdicted, and the subsequent elimination of particular paths between O–D pairs utilizing these nodes. For example, consider three nodes, o, j, and d, with a link connecting o and j and a link connecting j and d, and assume there is flow between od only. If node j is interdicted, then it is inoperable and X j  = 1. Assume, without loss of generality, that path k is the only path for od, node j is on path k, and j is the only interdicted node. Given this, Constraint (4) is Y k  ≥ 1–1, or simply Y k  ≥ 0. With the objective of maximizing flow disruption, Z od will seek to equal 1 if at all possible. This means that Y k will equal zero, e.g., Y k  = 0, as Constraints (2) and (3) allow Z od  = 1 only if no path exists for this O–D pair, which it does not in this case because \( {\sum\nolimits_{{k}\ifmmode{'}\else$'$\fi \in N_{{od}} } {Y_{{{k}\ifmmode{'}\else$'$\fi }} = Y_{k} = 0} } \) in Constraint (2) and Y k  = 0 in Constraint (3). When minimizing flow disruption, (1) will seek out Z od  = 0, which can only be attained when Y k  = 1 as there is only one path. In this case, Constraints (5) are in place to ensure that if any node on path Y k is interdicted, Y k is unavailable. Thus, the decision variables and constraints work as intended to account for flow disruption, which is why this is conceived of as a unified approach. While it would be possible to separate this one model into two models for addressing the respective maximum or minimum case, one approach is capable of addressing both concerns as the two cases are of interest in management and planning contexts.

4 Application

The developed model was applied to the Abilene Internet2 network backbone shown in Fig. 1 to assess interdiction risk. The Abilene backbone is a high performance fiber-optic telecommunication network, consisting of 14 linkages that integrate 11 routers (network nodes), primarily intended to facilitate transmissions between research institutions in the U.S. (Abilene 2005). Flow data (in bytes) observed at network routers was collected by Abilene using Cisco NetFlow (Abilene 2005). Each router serves as both an origin and destination node, resulting in 121 O–D pairs including intra-nodal flow. Given infrastructure capacities, all network elements were considered uncapacitated.

Fig. 1
figure 1

Flow activity on Abilene Internet2 backbone

Full size image

The analysis was carried out on a personal computer with a Xeon 3.0 GHz processor and 4 GB RAM. TransCAD, a commercial geographical information system (GIS) package, was used to manage the Abilene data and extract arc and node incidence relationships. A C++ program was written to enumerate all simple O–D paths using arc/node data exported from TransCAD. For the Abilene network, 907 paths were identified (896 inter-nodal + 11 intra-nodal). However, removing path redundancies reduced the number of necessary paths to 151 (an 83.4% reduction). Path identification required less than one second of computing time. The associated FIM problem instance was then structured, consisting of 228 decision variables and 1,065 constraints. The C++ program then calls ILOG CPLEX 10.01, a commercial optimization package, to solve all instances of the FIM reported in this paper.

The FIM was used to identify potential worst-case and best-case nodal interdiction scenarios. Consistent with much of previous research, we initially evaluate network connectivity using FIM. This is done assuming only a single unit of flow between interacting O–D pairs (e.g., removing f od from the objective) so that all O–D relationships are valued equivalently in the model. Following this, actual observed total flow between interacting O–D pairs is examined using the FIM. Both connectivity and actual flow instances are solved for the entire range of node interdiction possibilities, p = 1–11, the results of which are discussed below.

Connectivity results are provided in Table 1, giving solution details for each level of potential interdiction. Fig. 2 plots the objective function as the number of nodes interdicted increases. The problems required little computational effort, with the greatest effort being for p = 1. When one node is interdicted, Indianapolis is identified as the location that, if rendered inoperable, would disrupt the greatest number of O–D pairs (21), some 17% of the 121 interacting pairs. If two nodes are interdicted, we find that Kansas City and Houston would cause a disruption of 80 O–D pairs, or approximately 66% of all interacting pairs. Certainly both cases represent a significant potential impact on the network, but even one additional interdicted node (p = 3) would bring the total impact to over 80% of interacting O–D pairs.

Table 1 FIM solutions for maximum connectivity interdiction (unit flow on each O–D pair)
Full size table
Fig. 2
figure 2

Connectivity reduction for each interdiction scenario

Full size image

Altering the focus slightly, flow interdiction results are provided in Table 2, giving solution details for each scenario level. As was found in Table 1, the problems solved in Table 2 required little computational effort. In contrast to the interdiction of connectivity, we find that explicitly accounting for flow transmission yields very different interdiction scenarios. Table 2 shows that interdicting Washington, D.C. would be the single node causing the greatest impact, representing a decrease in flow of over 37% (total O–D flow is 48,728,171,337,750 bytes). If two nodes are interdicted (p = 2), then Washington, D.C. and Indianapolis are found to cause the greatest decrease in flow (over 73%). The tradeoff curve for nodes interdicted versus total flow disrupted is shown in Fig. 3, summarizing the results given in Table 2. To illustrate the spatial impacts of an interdiction scenario, Fig. 4 depicts the p = 3 solution from Table 2, a configuration that disrupts over 81% of total system flow. These results highlight an important difference between interdiction of connectivity and interdiction of flow. As can be discerned from the Abilene network, the loss of any single node (p = 1) will equivalently impact network connectivity. Similarly, several optimal solutions to the disruption of two nodes (p = 2) exist for the case of connectivity (Kansas City and Atlanta; Indianapolis and Houston; and Kansas City and Houston). Multiple optima are expected when O–D connectivity is of interest given that O–D pairs are given equitable treatment. In such cases, alternate optima could possibly be identified through incorporating Dantzig-type cuts as is done in ReVelle and Rosing (2000). The existence of multiple optimia changes when impacts to system flow are considered, however. Interdiction impact does not necessarily depend upon level of connectivity, but rather flow between origins and destination. For instance, the two-node interdiction scenario maximizing damage discussed earlier (Washington D.C. and Indianapolis) does not maximize connectivity damage. In fact, six other scenarios cause a greater impact to system flow than this particular interdiction set (Matisziw et al. 2005), highlighting that connectivity and system flow are very different performance issues.

Table 2 FIM solutions for maximum flow interdiction (actual O–D flow)
Full size table
Fig. 3
figure 3

Flow reduction for each interdiction scenario

Full size image
Fig. 4
figure 4

Maximal flow interdiction (p = 3)

Full size image

Table 3 and Fig. 2 detail the results for minimizing impact to O–D connectivity. In the best-case scenario, the FIM identified Houston as the location with minimal connectivity loss. As can be observed in Table 3, more computational effort is required when computing a minimum. The results for minimizing impact to O–D flow are shown in Table 4 and Fig. 3. Here, removal of Kansas City impacts system flow the least. Figure 5 illustrates the resulting minimum impact to flow given the interdiction of three nodes. In this case, Indianapolis, Denver, and Kansas City are interdicted.

Table 3 FIM solutions for minimum connectivity interdiction (unit flow on each O–D pair)
Full size table
Table 4 FIM solutions for minimum flow interdiction (actual O–D flow)
Full size table
Fig. 5
figure 5

Minimal flow interdiction (p = 3)

Full size image

5 Discussion and conclusions

This paper has introduced an unified spatial optimization formulation, the flow interdiction model (FIM), for examining risk and vulnerability associated with network interdiction. The FIM can be used to identify either worst-case or best-case impacts to system flow given any specified interdiction scenario, providing upper and lower bounds on potential system degradation. Myung and Kim (2004) implicitly attempted to establish such bounds when network arcs were interdicted, but ultimately could do so only heuristically. Specifically, they address system flow interdiction by introducing an integer program and heuristic solution method to identify scenarios maximizing flow disruption. Their model, however, is a special case of the FIM in that it does not permit minimization of system impact, though a lower bound heuristic is suggested. The work of Myung and Kim (2004) highlights the need for the FIM as it provides a unified approach to derive exact bounds on possible network interdiction impacts. The application results highlight the capabilities of the FIM to derive these bounds using commercial optimization software, requiring little computational effort. For the system evaluated here both path enumeration and model solution were easily handled. Though the network application was not particularly large, the developed approach is feasible and valid for examining interdiction risk and vulnerability in network infrastructure.

Another point to elaborate on is the relationship between connectivity and flow, as the applications of the FIM to the Abilene network display some subtle differences. A close examination of Tables 1 and 2 suggests that node combinations associated with maximal system flow interdiction do not correspond to the same nodal combinations when maximizing O–D connectivity interdiction. Obviously the difference is due to the fact that connectivity is not equivalent to total system flow. For example, if we examine the scenario where one node is to be interdicted, the loss of Washington, D.C. disrupts the most flow (p = 1 in Table 2) while the loss of Indianapolis disrupts the greatest O–D connectivity (p = 1 in Table 1). This is not completely unexpected given the basic flow information and topological characteristics of the network. This is a very important observation for several reasons. First, and most obvious, nodal interdiction combinations for maximizing flow and connectivity disruptions rarely coincide completely. Thus, considering previous work on the attack tolerance and overall robustness of the Internet and other scale-free networks (Albert et al. 2000, 2004; Barabasi et al. 2000, 2001), it is clear that much of the complexity associated with network interaction remains unaddressed. In other words, high nodal connectivity (degree) does not necessarily correspond to an equally high level of network flow or utilization. Second, from a geographic perspective, the nodes identified for interdiction by FIM in the various scenarios are quite interesting. For example, while Denver appears to play an important role in both connectivity and flow for the network (Fig. 1), it is not identified as a high priority interdiction node until p ≥ 5 in either case. This is somewhat surprising given its relatively central geographic location on the network. In contrast, while Washington is an extremely critical node for network flow, appearing in the interdiction sets for p = 1–3 (Table 2), it is not a connectivity priority until p ≥ 6. Again, this suggests that high levels of network interaction for a node do not necessarily correspond to a high degree of connectivity to the network. Moreover, the implications are that both criteria need to be considered when evaluating the characteristics of a network. These differences might play a more important role when examining the survivability requirements of a network, particularly if the fortification or protection of node-based network elements is being considered.

The FIM was applied to the Abilene network, illustrating its feasibility and validity. Perhaps most significant in this application was that non-intuitive scenarios are found, precisely what we look to optimization models to help us find. Though physical characteristics of networks are typically modeled as interdiction targets, more dynamic and less observable characteristics further increase the level of complexity involved. This is especially true given consideration of multiple origins and destinations and their patterns of spatial interaction. The threat of facility attack is a reality shared by many types of critical network infrastructures, and preparing for such a possibility is challenging. Here an optimization problem was formulated to address such a need. However, application of the FIM is not limited to planning for network survivability, but can also be useful in the location of facilities to monitor flow activity, such as weigh stations, surveillance points, traffic control, checkpoints, etc.