Metrics For Networked Systems Design In A Network-Centric Warfare Context

Introduction

This paper discusses modelling networked systems of services and users. Expressions for robustness are derived for realistic military situations. The methods are not limited to low failure probabilities so they are suitable for vulnerable and robust systems.

The goal of this paper is to develop a general framework for studying and comparing different networked systems when network links (edges) and nodes (vertices) become non-functional. The models presented here have a common viewpoint that one connection is enough for two parties to communicate, two connections are enough for three parties and so on. Here we use the term connection when there is a path between nodes—that is, connectivity is maintained. When all the nodes break down during the same time period, the system is down for the next time period. It is possible that during the repair period the nodes are destroyed again.

In the basic model, all the functional nodes in the system can do the same job. This is crucial when network metrics are calculated and makes a big difference to another definition of network metrics used in [6], where all the possible connections and nodes have been summed and weighted with values of links and nodes.

A networked system comprises three different elements: network links, functional network nodes, and technical network nodes. Functional network nodes are computer centres, command centres, users of networked services, and so on. Technical nodes are, for example, network routers and there are no applications for end users. Destroying a functional network node is usually more serious than destroying a technical network node. [7]

The framework consists of the following four steps:

• Evaluate the failure probability p for a general target, a node or a link.
• Evaluate the failure probability for a system of several nodes (Section 3).
• Evaluate the failure probability for a network connection (several links) (Sections 4 and 5).
• Evaluate the failure probability for a combined system of nodes and connections (Section 6).

In the first step the failure probability is evaluated for one target where firing theory is the tool if weapons are used against infrastructure [15]. Computer viruses and technical errors have to be taken into account by different methods. At the end of this step failure probabilities for functional nodes and links have been evaluated.

In step two, scenarios for one or several nodes are studied where, in the case of a node breakdown, a task transfer to another node can occur. The receiving node can be a standby node or a non-standby node. Task transfer to a standby node happens automatically and immediately after the failure. Task transfer to a non-standby node can occur after manual operations or rebuilding of the system. The main difference is that a transition to a standby node happens directly without delays and a transition to a non-standby node requires a preparation phase.

The goal in Section 3 is to construct a model sufficiently general to allow different modifications. The theory behind is discrete or continuous time Markov processes [5]. For Markov processes future states of the system are not influenced by the past of the system, only the current state is important. The limiting distribution is calculated as a first model but given the initial state, time dependence can be studied easily. Markov matrices serve also as a visualization tool for understanding the system’s behaviour.

Step three is analogous to step two but the system is composed of network links. The probability for a connection between functional nodes is evaluated and a method is presented for the computation. Section 4 introduces some basic concepts of network connectivity. Section 5 presents a method to compute a measure of robustness for military networks or civilian networks under the threat of terrorist attacks. In the model attacks are not random but targeted so as to cause maximum damage to a network and unequal failure probabilities for network links are considered. Markov matrices or limiting processes are not used in Section 5 but the results can be utilized in Section 6 for limiting distributions. Alternatively, time-dependent solutions can be calculated by iterating waves of attacks with the methods of Section 5 alone.

In step four the system is regarded as a collection of functional nodes and links. The total failure probability for the system can be calculated. This is also a measure for comparing networks and networked systems. The survival probability of the system or the entire network is suggested as a new network metric (Equation (6.4)).

In the long run, if no repair takes place, the system will eventually break down. But if the number of spare parts or nodes is sufficiently large, compared to the time of hostile activity, the networked system can still operate until the end of the war. In this case the probability is fairly easy to compute. The probability distribution for the system in operation is given by the binomial distribution.

Models 1 and 2, in Section 3, give the limiting distributions π₀ and π for the probabilities for the system not in operation and in operation respectively. In the models Q is the ratio of uptime to downtime of the system and it is a function of the number of replaceable nodes of the system. If in the system planning phase, a requirement for Q is given, a lower bound for the number of nodes can be solved.

Related work

Network robustness has been studied in the areas of graph theory, telecommunications network reliability, and percolation theory. Recently there has been some interest in combining networking and information systems in modelling military command systems. References to related work are given in this section and comparisons to this paper are provided in Section 7.

In [1,2] robustness of network topologies are examined with graph-theoretic concepts. Robustness of the topology will come from the presence of alternate paths, which ensure that communication remains possible in spite of damage to the network. The authors suggest that it is important for robust networks to satisfy two conditions: node-similarity (or symmetry) and optimal connectivity. Optimal connectivity is defined by κ = λ = d_min, where κ is node connectivity, λ is link connectivity, and d_min is the minimum degree of the graph. Node (link) connectivity, κ, is the smallest number of nodes (links) whose removal results in a disconnected or single-node graph. The degree of a node is the number of outgoing links and d_min is the minimum degree of the graph. Node connectivity is suggested as a measure for network robustness.

Modelling random failures have been studied, for example, in References [9,10,12]. In [12] independent link failure and repair probabilities are incorporated into network reliability calculations. Using Markov chains is common in reliability analysis and the method has been used in [12]. Different targeted attack strategies against networks have been examined in [4] where the importance of the network structure changes during targeted attacks is emphasized. Betweenness centrality (defined in Equations 4 and 5 in [4]) and degree of the node (link) have been used as the selection criteria for targeted attacks against nodes (links). Betweenness and degree are correlated but not always removing nodes (links) with high centrality or high degree have the same effect on the network robustness.

There has been much interest in random and targeted attacks against large networks in percolation theory [13]. In targeted attacks nodes are removed in the order of descending degree and in random attacks nodes are removed in random. A typical question is whether or not there exists a ‘giant component’ in the limit of large system size. The size of the largest connected subgraph is an important quantity and it has been used also in [4] as a measure of network robustness. Conditions for the critical fraction of nodes p_c that needs to be removed before the network disintegrates have been derived for various networks structures such as random and power law networks. Optimization of network robustness to waves of targeted (fraction p_t) and random (fraction p_r) attacks gives a bimodal degree distribution [13]. The fraction r of the nodes has degree $k_2=\left(⟨k⟩-1+r\right)/r$ and the remainder of the nodes have degree $k_1=1$, where $⟨k⟩$ is the average degree of all the nodes and the optimal value of r is of the order of $p_t/p_t$ for $p_t/p_r\text{<<}1$.

In [6] a connectivity measure of a military network is defined as the sum of the value of all the nodes and their connections scaled by the lengths of the routes and their directionality. Metrics for assessing the value of networking and information in the battlefield have been discussed with a method where network metrics and decision-action rate have been related. In [7,8,11] the measure of total network performance quantifies the effects of information sharing across a cluster on information completeness and accuracy, whereas plecticity measures positive and negative effects of redundant information and the degree of information access.

For networks of more than about 25 links optimized algorithms or simulation methods are necessary because of time and memory complexity. Examples of algorithms are given in [3,14].

Recovery of command centres

Because military systems may be targets for hostile attacks special actions are necessary to increase robustness of systems. One obvious way is to replicate application servers. If one copy of the system is destroyed another takes the task and so on. In this section we study robustness of the replicated system and in later sections networking is included in the model.

Next we present a mathematical model based on Markov chains for a system of nodes which are destroyed or where a technical error occurs at random times. The actions to get the system operational again are to repair or to replace the node. There are many scenarios that can be described with this model.

Our model is based on Markov chains [5]. The limiting distribution is:

The distribution is unique for regular transition probability matrices (P_kj) [5, Theorem IV.1.1]. The number of states is N+1. The convergence means that, in the long run, the probability of finding the Markov chain in state j, is approximately π_j, no matter in which state the chain began at time 0. The system has reached the stationary state.

Imagine a situation that one command centre is completely destroyed but with the help of advanced technology another command centre takes over in almost real time and users of the system are completely unaware of what has happened. In addition, it is assumed that the nodes not in operation are repaired in the background during the same time period. This is why the number of nodes n is kept constant. In state 0 nodes are still vulnerable and can be destroyed again during the repair period. This assumption may be unrealistic in practice and a more accurate model could be constructed. Later in this paper more refined Models 2 and 2B will be presented where more states of the system will be introduced.

The parameters of the model are p, p_r and p_t where p is the failure probability during the specified time interval, p_r is the conditional probability to repair or replace the system during the time period and p_t is the conditional probability of task transfer of a node.

The model is a simplification of the real world system in several respects. We assume that the process is a Markov process with constant parameters p, p_t, and p_r. The model for repairing the system is approximate because the distribution for the duration of the repair time is usually not known. An effect of discrete time is that the system always stays one time step or period in the state where it arrives, before it makes another transition

Fast task transfer to another node is studied in Model 1. States 1 and 2 are defined as a combination of several nodes: one or more of the n nodes are not destroyed. The only difference between states 1 and 2 is that they have different history. Transition to state 0 occurs when the last of the n nodes is destroyed. The Markov matrix becomes:

The ratio of uptime to downtime of the system Q(n) can be solved from the limiting distribution of (3.1)

The variables π₀ and π = π₁ + π₂ =1–π₀ give the probabilities for the system not operating and operating:

The values with parameters p_r = p_t = 0.01 of Q(n), n=2, 3, 4, 5 have been shown as a function of the failure probability p in Figure 1.

In [8] a network penalty factor has been introduced to account for negative effects of information overload. Heuristic logistic shape equation g(C) with parameters a and b has been introduced to account for additional network connectivity:

C is the total number of network links accessed by nodes on the critical path. The approach is opposite to this presentation where vulnerability is considered as a central phenomenon in networked systems. In our model no heuristic penalty functions are necessary because additional nodes and links are redundant and the only effect is to improve reliability of the network. (3.3) can be compared to the logistic penalty function of [8]. (3.4) gives n as a function of Q(n)

For an example Q=50 (2% not in operation) and p=0.2, p_r=p_t=0.1, the result from (3.4) is $n\approx 3\text{.}5$—that is, four nodes are needed to maintain the system at 98% capacity. For a low value of Q=5 (20% not in operation) two nodes are almost enough to maintain the system at 80% level. In Figure 1 these examples have been marked with dots.

In Model 2, the state space is larger than before, also the limiting probabilities for n, n–1, n–2, …, 1 nodes in operation will be calculated. In the basic model, constant repair time is assumed. For example, if there are three nodes in the system the Markov matrix is:

The elements of the matrix are the probabilities $P\left\{X=k\right\}=\left(n\right|)$ of binomial distribution with parameters n and p. The states of the system are labelled according to the number of nodes in operation i=0, 1, 2, 3. The limiting distribution is:

The general equations for n nodes for the limiting distribution are:

and the normalization equation is ${\sum }_{i=0,n}{\pi }_i=1$. By Theorem [5, IV.1.1] the solution is unique for $0<p<1$ and we get:

where: $\left(n\right|)$

Equation (3.7) can be verified by substitution into (3.6). The factor $1/{\left(1+p\right)}^n$ is for normalization. When p<1 and $n\to \infty$ the probability of no operation ${\pi }_0\to 0$ for Models 1 and 2. The striking difference is that ${\pi }_0\to 1$, in Model 1, and ${\pi }_0\to 1/2^n$, in Model 2, when $p\to 1$. As the number of nodes increases the probability for a system not in operation goes to zero in Model 2. The difference is due to the higher repair activity of Model 2 compared to Model 1. In Figures (2a) and (2b) Models 1 and 2 are compared for the parameter values p_r = p_t = 0.1. The probabilities of no operation have been shown as a function of the failure probability p with n=1,..,15 replaceable nodes in the system.

For realistic applications more accurate models may be necessary. In Model 2B, the repair time of nodes will be taken into account. The 4×4-matrix corresponding to (3.5) is:

The limiting distribution for n nodes in the system is:

The theory can be generalized in many ways. For example combined states of nodes and links can be considered or history of the system can be included in the model. Also different failure or repair rates can be incorporated for different number of broken nodes resulting in different values of p and p_r on matrix lines in (3.8).

Probability for an operative connection

Our next step is to connect the command centres in a wide area network. The same model can be applied for connecting computers in a local area network or people with telephone lines and so on. We assume that there is a connection between two sites if there is at least one connection, or path, in operation. Figure 3a shows two simple networks which we take as examples. A general method to calculate the failure probability will be presented based on the first example. [10] In Section 5 the second test network is studied in more detail.

We assume that the failure probability for every link in the graph is p_l during the specified time period and the probability is independent of the length of the link. We investigate the first test network of Figure 3a. To make the situation practical we can list all the combinations of broken links. There are 32 all together, when the case with no broken links, is also counted. The probability that one link is broken is $p_l{\left(1-p_l\right)}^4$, the probability that two links are broken is $p_{l^2}{\left(1-p_l\right)}^3$ and finally the probability that all the links are broken is $p_{l^5}$. There are one, five, ten, ten, five and one combinations for zero, one, two, three, four and five broken links. This is the familiar Pascal triangle rule. The normalization is:

In our example if only one link fails there is a connection between all the nodes. For two link failures two there are two possibilities of no connection, and so on. The link connectivity is two for the network. We calculate the probability of no connection between the marked nodes one and four of the first test network of Figure 3a as:

where, in the parenthesis, the probabilities of no connection have been subtracted. If we think that the failure probability for one link is small, it is a good approximation, to take only the first powers of p_l. In the example $p_L\approx 2p_{l^2}$ if p_l is small. Generally, for low values of p_l we have $p_L\approx A_C{p}_{l^C}$where C is the link connectivity and A_C is given later in (5.3). In Figure 3b the probability of no connection between nodes one and four for the first test network and nodes four and nine for the second test network are shown as a function of the link failure probability. The connection in the first network is more robust than the connection in the second network.

Note that the theory presented in Section 3 applies also for links in the network. For example from (3.9) the probability of operation is:

and the ratio:

In system design, the lower bound for links n, can be solved from (4.3) when the value of required Q is given.

The probabilities p_L,uj should be computed for different connections between nodes u and j in the network. Usually, in real networks, the probabilities p_L,uj are different for each connection, as a result of the network structure. This problem is studied for random and not random failure probabilities in Section 5. As an example, consider a system of a user u and two nodes 1 and 2 where the user needs a connection L_u1 or L_u2 to one of the nodes. Equation (3.8) for three states transforms into:

where p_L,u1 and p_L,u2 are the failure probabilities for the connections L_u1 and L_u2. The analysis for the model proceeds as before and the quantities ${\pi }_0,{\pi }_1,{\pi }_2,\pi ,Q,\text{.}\text{.}\text{.}$ can be solved.

Targeted attacks against network links

In Section 4 the failure probability p_l is equal for every link of the network. [9,10] This may be a sufficient model if hostile attacks against links are random or every link is attacked with uncertain success. If a network is targeted so as to cause maximum damage we need to go further and construct a model where failure probabilities are unequal for network links. [12]

As a practical application of the theory we show how to calculate the probability of no connection between two nodes, for example, a user and a service in the network. Because we don’t expect hostile forces to have exact information about the locations of services we define an average metric for a general network topology. The model works also for specific situations where the locations of users and services are known but the average metric is suitable to show the general behaviour of the network under targeted attacks.

First we construct the mathematical theory. We start from the general equation for the probability P_L,ab of no connection between two nodes a and b of a network [10,12]:

where N_L is the number of links in the network and p_i is the failure probability for link i. The terms in the parenthesis correspond to events of no links destroyed, one link destroyed and so on. The value of the indicator function $I_{\text{ab},\left\{i,j,\text{.}\text{.}\text{.}\right\}}$ is one if there is a connection between nodes a and b when links i,j,… have been removed, otherwise $I_{\text{ab},\left\{i,j,\text{.}\text{.}\text{.}\right\}}$ is zero. Equation (5.1) applies for three node systems if the indicator functions are replaced by corresponding three node terms $I_{\text{abc},\left\{i,j,\text{.}\text{.}\text{.}\right\}}$. If the network is connected or there is a connection between a and b the first indicator function $I_{\text{ab},\left\{\right\}}$ is one.

From (5.1) we get, as a special case, when the failure probabilities are equal p_i=p_l, i=1,…,N_L.

where:

and H_s is the sum of indicator functions when s links are removed. Equation (5.2) is a polynomial of maximum order of N_L. For example, we get (4.1) with N_L=5 and H₀=1, H₁=5, H₂=8, H₃=2, H₄=0, H₅=0. But if the probabilities are not equal (5.1) does not simplify and we have to use it directly.

Before we proceed into results we define a measure for the network robustness as an average over every two node pairs in the network:

Again, the average P_L is a polynomial in p_i, i=1,..,N_L but for unequal probabilities we compute the numerical values from (5.1).

Our goal is to find for military networks, or civilian networks under terrorist attacks, the strategy for maximum damage. Network topology, link failure probabilities and number of attacks are used to calculate the exact probabilities P_L,ab for connections between two nodes a and b of the network. We use the average metrics of (5.4). Usually military networks are small with at most tens of nodes and tens of links. For larger networks (5.1) and (5.2) can be truncated when the wanted accuracy is gained. The first terms are suitable for approximations if the failure probabilities are small. If the failure probabilities are high the last terms of (5.1) are suitable for computation.

In this section, one hostile action against a link is called an attack and attacks are assumed to be independent with probabilities of success p_i against link i. For example, an attack may be a bomb dropped from an airplane or an electromagnetic disturbance against a wireless network link. In our examples we assume that for the first attack the probabilities are the same p_i = p_l, i=1,..,N_L and for the k’th attack.

where P(1) = p_l. If previous attacks affect the success of future attacks the equation for P(k) should be modified correspondingly. The general method, given in this section, still applies without change. Note that for small p_l the ‘penalty’ term p_lP(k-1) is negligible and for p_l close to one the effect is large. This has a considerable effect on the results. In fact, the network topology and the model for P(k), together, explain the phenomena of the results given below. We denote the number of attacks against the link i of the network as n_i and define the strategy of the attack as the vector $\left(n_1,n_2,\text{.}\text{.}\text{.},n_{N_L}\right)$.

In Figure 4a the average metric of (5.4) for the first network topology of Figure 3a is shown for the four strategies (1,1,1,1,1), (3,2,0,0,0), (1,1,0,1,1), and (2,2,0,0,0). One attack against each link of the network is conducted in the first case, three attacks against the first and two against the second link in the second case and so on. In the last two examples total number of attacks is less than the number of links of the network. In cases where one or more links remain without attacks the values of P_L are less than one when p_l=1—that is, total destruction is not achieved. Naturally, the number of attacks may be larger than the number of links but the most significant results are found from our simple examples. When fever attacks are conducted the attacks must be more effective to reach the same P_L and this is demonstrated with the shift of the last two curves to the right.

The most important result is that the optimal strategy changes when the probability of the success of the attack changes. The thresholds for five attacks and for four attacks are indicated by the two arrows in the figure. In the case of five attacks the optimal strategy is to attack all the five links if the failure probability is more than 0.45 for one link. If the probability is less than 0.45 more damage is caused if the attacks are shifted to the first and second links or because of symmetry to the links four and five. Exactly the same behaviour is seen from the four attack strategies where the optimal strategy is one attack for the links one, two, four and five—that is, (1,1,0,1,1) when p_l is larger than 0.64. Note, that the strategy (1,1,1,1,0) is not optimal for any value of p_l because nodes one and four are of degree two and nodes two and three of degree three. The priority is on the weakest links. We still find something interesting, for values of p_l less than 0.3 the four attack strategy (2,2,0,0,0) is a little more effective than the five attack strategy (1,1,1,1,1). This is due to the interplay between the network topology and the model for P(k) in (5.5).

In Figure 4b some relevant five attack strategies are shown for p_l between 0.28 and 0.46. We know from Figure 3a that the threshold between the strategies (1,1,1,1,1) and (3,2,0,0,0) is in this interval. In fact, there is only one threshold in our simple test network and five attacks. But when we investigate strategies that are not optimal we find same kind of phenomena as we discussed above. For example, when p_l is below 0.315 the second optimal strategy is (2,2,1,0,0) where a shift towards weaker links is occurs. In the simple test network the strategy (3,2,0,0,0) is already more optimal but in more complicated networks this kind of intermediate strategies may be optimal for some values of p_l.

To show that this can occur we look at Figure 5a where 13 attack strategies for the second test network of Figure 2a are shown for p_l between 0.48 and 0.64. Three thresholds are indicated with arrows for the optimal strategies (1,1,1,1,1,1,1,1,1,1,1,1,1), (2,1,0,1,0,2,0,1,1,1,2,1,1), (2,2,0,1,0,2,0,0,1,2,2,1,0) and (3,2,0,0,0,2,0,0,2,2,2,0,0) when p_l is in range (1, 0.622), (0.622, 0.588), (0.588, 0.510) and (0.510, 0.150) respectively. Between (0.050, 0.150) the strategy (3,2,0,0,0,3,0,0,2,2,1,0,0) is optimal and below 0.05 (3,3,0,0,0,3,0,0,1,3,0,0,0) is optimal. If we examine carefully low values of p_l we may find even more thresholds but they give same values for the metric in two or three decimals. In some applications, for example nuclear safety, small probabilities are important and exact results are needed for all values of p_l. Figure 5b shows optimal strategies for 26 attacks against the second test network. Targeted attacks shift from evenly distributed strategies towards weaker links, as before.

Finally, we note that there are many ways to extend the method of calculating the metrics where the link failure probabilities are unequal. Some examples are given below.

Attacks against the network may be conducted in wages and repairing of damaged links may occur between the wages. If damage against the network is observed before the next wave the network topology has changed—that is, some links are destroyed—and the new topology is input for the next calculation [4].

If hostile forces have more information about the systems in the network, for example, the probabilities for the nodes where command and control systems are, the two node metrics in the average metric of (5.4) should be weighted with these probabilities. In addition, more important and valuable nodes can be given more weight [8]. In the beginning of this paper we introduced the concepts of technical and functional nodes. Functional nodes have applications and, if we have this information only, we should include the functional nodes and the nodes where users connect the network in the metric. In this respect, a user is considered as a functional node.

If we study users in nodes i and applications in nodes j, (5.4) becomes:

where the probabilities for applications to be in node j is P_F,j and the weighting factors for the value of the nodes are W_F,j.

Networked command centres

The last step is to combine the results of the previous sections. A networked system is composed of nodes and connections where failure probabilities for individual nodes and connections are denoted by p_N (notation p in Section 3) and p_L,ij correspondingly. Consider a combination of one node and a connection between the node and a user in the network (second node is a user). The failure probability for the networked system is:

For the first example network of Figure 3a and the connection between the nodes one and four

where p_l is the link failure probability. Usually, the failure probabilities are different for the networked system states, because of the network structure. The values of p_L,ij are different on each line of the Markov matrix, for example, from (5.2):

between nodes one and two and:

between nodes two and three.

As a simple example consider the Markov matrix where the time period is the approximate repair time as in Model 2 in Section 3:

where $p_1=p_{N=4,\text{14}}$ and $p_2=p_{N=2,\text{12}}$ from (6.1). Node one is the user of the system. The model states are described in Table 1.

The stationary distribution of the example is:

Generally, the metric for an entire network can be computed as:

where S is the number of independent systems or applications in the network, N is the number of operational states in the system and state zero is the non operational state. The metric M takes values between zero and one where values near one indicate robustness of the networked system. The limiting probabilities $1-{\pi }_{0s}$, of Models 1 or 2, are used in (6.3). The failure probability p for a system of a node and a connection is given in (6.1). If users of the system connect to the network from different locations, the average over connection points should be included in (6.3).

Higher weights for critical applications may be used. Because weights for applications are difficult to evaluate, the metric M works better comparing alternate structures of a networked system. For one system s the value $M=1-{\pi }_{0s}$ gives the metric which depends on the network topology of nodes and links.

If no repairing occurs, for example during targeted attacks, the metric can be computed for a specified time period with the methods of Section 5. From (5.4) the metric is $M=1-P_L$. Without repairing the stationary distribution gives the state where finally all the systems have failed and this is not useful information for comparing robustness of systems.

If the links are invulnerable the results of Section 3 are used and the network topology has no effect. In rare situations where the network is symmetric and symmetry is approximately maintained, $p_{N,\text{ij}}\approx p$ in (6.1) for all nodes and connections and the methods of Section 3 are suitable.

The main results of Section 3 have been collected in Table 2. The first row is the probability for the system in operation, the second row gives the fraction Q of operation for n nodes and the third row gives the lower bound for the number of nodes if the capacity level Q has been given as a planning principle.

The steps of the method have been summarized here:

Step 1: Calculate or evaluate the failure probabilities for individual nodes and links. Firing theory or simulation can be used.

Step 2: (Section 3) Calculate the limiting distribution of failure probabilities for several replaceable nodes. Markov chains are used as a tool. (If more than one node is necessary for the system to operate then calculate the probability for the relevant combination of nodes by the same method.)

Step 3: (Sections 4 and 5) Calculate or evaluate the failure probabilities for connections of the system. One connection comprises of one or more links. (If more than one node is necessary for the system to operate then calculate the probability for the relevant combination of links by the same method.)

Step 4: (Section 6) Calculate the failure probabilities for pairs of a node and a link of the system. (If more than one node and one connection is necessary for the system to operate calculate the probability for the relevant combination of nodes and links by the same method.) In Step 4 each combination of a node and a link is considered as a ‘combined node’ and the new probability is inserted into the analysis of Step 2. Alternatively a specified time period can be investigated by the method of Section 5 if no repairing occurs or the assumption of stationary state distribution is not suitable. This may occur in targeted attacks of Section 5.

Comparison with related work

Next we compare the methods and results of this work with the references given in Section 2. As a summary, in this paper we study random and targeted attacks against links of small networks where the measure of robustness is the average of operating connections over all the pairs of the network in (5.4). If several attacks are aimed at the same link the joint probability of the events is calculated from (5.5). A result of this paper is that the optimal attack is against all the network links when the probability of success is above a threshold. Below the threshold the attacks against links of nodes of lower degree are more optimal and usually this occurs via several intermediate thresholds for different configurations of links as explained in Section 5.

In [1,2] a symmetric network is suggested as a robust network against attacks. This is in good agreement with the results of this paper because the attacker is unable to take advantage of the degree distribution of the nodes what ever the probability of a successful attack is. A result of this paper is that if the number of attacks is high enough and the probability of success is above the threshold the network structure has no effect. If the number of attacks is less than the number links in the network the attacker should concentrate his limited attacks against the links of lower degree nodes.

In [4] different attack strategies have been examined and as a measure of robustness the size of the giant component or the average characteristic path length has been used because the ultimate aim is to disintegrate the network. The destruction probability is one for attacked nodes (edges) and when the fraction of nodes (edges) reaches the threshold value the network fails. The measure of robustness in this paper is the average connectivity of (5.4). Of course, if the information systems require connectivity to a large set of nodes the size of the giant component is a good measure. But this is a special case of (5.4) because of the comment given after (5.1) about three node systems (or more than three).

When using percolation theory it is assumed that the network is large and usually the measure of robustness is the size of the giant component. Despite the fact that percolation theory does not work for small networks the results in this paper are not in contradiction with the results of percolation theory. It is interesting to conduct a numerical exercise associated with the example of Figure 5 in [13] with the number of nodes N=100 and $⟨k⟩$=2.1. The bimodal distribution given in Section 2 gives for r=0.1 the result rN=10 “hub” nodes of degree k₂=12 and for r=0.2 the result rN=20 “hub” nodes of average degree k₂=6.5. If we keep the sum constant p_t+p_r=0.11 we get p_r=0.1, p_t=0.01 and p_r=0.092, p_t=0.018 when r=0.1 and r=0.2 respectively. Thus if the fraction of targeted attacks against high degree nodes increases the number of the hubs increases. This makes the network more resilient against high degree node attacks because the network is more symmetric. In this paper the measure of robustness is different but we can make similar conclusions. For example in Figure 4a, if the link failure probability is below the threshold 0.45 it is optimal for an attacker to destroy the links of low degree nodes and as a counter measure the defender should plan his network more symmetric to increase the network robustness in (5.4). Above the threshold the attacker is superior and the network is vulnerable for all values of link failure probability. In this situation protection based on other means than the structure of the network is needed in order to lower the link failure probability. Optimal methods are selected by maximizing robustness and minimizing cost.

Summary

The main results of this paper are the techniques of incorporating services, users, and the network topology in the same model and the calculation of targeted attacks against the network structure.

A networked system is studied in the network-centric warfare scenario. Failure probabilities for a system of several replaceable nodes have been calculated and a method for calculating failure probabilities for connections between nodes has been given.

A networked system is composed of nodes and connections where a connection has one or more links. The probabilities are for the worst case scenario, and as a baseline the networked system is assumed to be in operation, if only one node and one connection, or path, is in operation. The same model can be applied for systems of several nodes if the nodes are not replaceable. Markov chains and stationary system states have been used as a tool.

The theory presented in this paper gives the fraction of uptime $1-{\pi }_{0s}$ to downtime ${\pi }_{0s}$ of the networked system s. In system design the lower bound for the number of replaceable nodes n can be computed when a specified ratio of uptime to downtime Q is required for the system. A new network metric can be computed as the normalized average of the values of $1-{\pi }_{0s}$ of Section 6. The metric can be computed for a system or for the entire network. In a network-centric warfare scenario, systems and networks can be compared using metric values.

Targeted attacks against nodes and links can be taken into account as described in Section 5. We show that for hostile forces to cause maximum damage, if locations of services in the network are unknown, is to attack all the network links for high values of link failure probability. For lower failure probabilities, below a threshold value, it is optimal for the attacker to shift the attacks against lower degree nodes. Usually the optimal set of links goes through several intermediate thresholds depending on the network structure. The threshold values of link failure probabilities for different combinations of links of the network are valuable information in planning and constructing robust network structures.

References

Author

Vesa Kuikka works at the CIS Centre of the Finnish Defence Forces. He is a Licentiate of Philosophy (Physics) 1986 from the University of Helsinki. He also holds a Licentiate of Philosophy (Mathematics) degree from the Åbo Academy since 2004. Address Finnish Defence Forces, CIS Centre, Kutojankulma 2, PL 210, 02631 Espoo, Finland, e-mail vesa.kuikka@mil.fi.