Modeling and Analysis of the Survivability of an
Infrastructure-Based Wireless Network

Lang Xie, Poul E. Heegaard, Yuming Jiang

► To cite this version:

Lang Xie, Poul E. Heegaard, Yuming Jiang. Modeling and Analysis of the Survivability of an Infrastructure-Based Wireless Network. 18th European Conference on Information and Communications Technologies (EUNICE), Aug 2012, Budapest, Hungary. pp.227-238, 10.1007/978-3-642-32808-4_21. hal-01543165

HAL Id: hal-01543165

https://inria.hal.science/hal-01543165v1

Submitted on 20 Jun 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Modeling and Analysis of the Survivability of an
Infrastructure-based Wireless Network

Lang Xie, Poul E. Heegaard, and Yuming Jiang

Department of Telematics,
Norwegian University of Science and Technology,
N-7491 Trondheim, Norway
{langxie,Poul.Heegaard,jiang}@item.ntnu.no

**Abstract.** This paper focuses on survivability modeling to characterize the transient behavior of an infrastructure-based wireless network in the presence of disastrous failures and repairs. Two modeling approaches, an exact model and an approximate product-form model are presented. Numerical experiments with the two models demonstrates that the ap- proximative product-form approach obtain close to exact results with a significant lower computational complexity. The product-form approach has been applied to study the impact of various system parameters on the survivability of the studied network.

**Keywords:** survivability, analytical models, disastrous failures

## 1 Introduction

Network survivability has become a major concern of critical service providers and network operators. This includes infrastructure-based wireless networks such as IEEE 802.11 WLANs, IEEE 802.16 WiMAX, and cellular networks. Critical services in these networks should be continuously provided even when some unde- sired events such as attacks, natural disasters, and common failures has occurred. In general, infrastructure-based wireless networks rely on building infrastructure with access points (or base stations) to cover their service areas. Compared with wired networks, infrastructure-based wireless networks are less reliable and are vulnerable to various failures, especially failures occuring in access points. This gives rise to the need of specific survivable wireless network architectures and mechanisms. Furthermore, quantifying survivability metrics of wireless networks is important and necessary to meet the user requirements and compare different network designs.

During the last decade, the definitions, metrics, and quantification methods of survivability have been extensively studied in traditional telecommunication net- works [1], [2], [3]. Some related work in other wireless network types, for instance, ad-hoc networks [4], [5], can provide a good insight in network survivability
quantification. However, these works are not applicable in infrastructure-based
wireless networks. In the literature, some works study the survivability quantifi-
cation of wireless cellular networks. Tipper et al. [6] and Dharmaraja et al. [7]
make extensive study for various failure scenarios and their effects on wireless
cellular networks. However, these studies are limited in the structural aspects
of cellular networks. They do not capture the transient performance variation
from failure to normal mode. In addition, most of the above approaches assume
the number of failures is small (e.g. one or two), and far less research has been
conducted on scenarios of large-scale failures which may be caused by natural
disasters or malicious attacks. These events occur with a low frequency but with
severe consequences. It is necessary to take above rare events into account when
analyzing network survivability.

Survivability models with disasters may seem to be appropriate in telecom-
munication network dimensioning and planning phase. Jindal et al. [8] propose
an analytical survivability model for base station exposed to channel failures
and disastrous failures. Nevertheless, this model only considers one base station
without extending to network level. In addition, most existing works may be
limited in just one specific homogeneous wireless network scenario. However, in
practice the heterogeneous network is probably a more common scenario, such
as multimode handsets, overlay networks [9]. This network architecture further
complicates the survivability quantification.

In this paper, we conduct quantitative, model-based analysis of the surviv-
ability of a two-tier heterogeneous infrastructure-based wireless network subject
to disastrous breakdowns and system repair. Specifically, the focus is on charac-
terizing the transient behavior of the system immediately after disaster until the
system restores and stablizes again. Two modeling approaches, an exact model
and an approximate product-form model are presented. Furthermore, we com-
pare both approaches numerically and examine the effect of different modeling
assumptions on the defined performance measures.

The rest of this paper is organized as follows. In Section 2, the system model is given. Section 3 describes the disaster-based survivability model and two approaches for transient solution. Numerical results are presented in Section 4. Finally, Section 5 gives the closing remarks and discusses future research in this area.

## 2 System Model

Generally, the operation of infrastructure-based wireless networks relies on base
stations (or called access points in this paper), which are vulnerable to various
undesired events. The theme of this paper is survivability modeling and analysis
on infrastructure with access points. We first describe the system model in this
section.
## 2.1 Network Description

When local network operators decide to deploy infrastructure-based wireless networks in their communities, the first step is radio network dimensioning. This phase aims to estimate the number of required access points and is often based on the assumption of uniform distribution of user subscribers.

Consider the network deployed in one certain geographic area. It may be covered by more than one type of radio system which is in essence a survivable architecture. This means that if one radio system fails, other radio systems will maintain the service continuity provided that the subscriber terminals support multiple radio modes. For the sake of simplicity, the analysis is started from a two-tier radio system, network-1 and network-2 as shown in Fig. 1. Users uniformly distribute across this area and support to access both radio systems. In our context, network-1 is prioritized over network-2 from the users’ perspective.

The above simple wireless scenario is considered by operators to improve survivability. For example, Wireless Trondheim has deployed Wi-Fi networks and implemented an experimental Mobile WiMAX network in the downtown area of Trondheim to provide ubiquitous Internet access [10].

<figure><img src="image_2.png" /><figcaption>Fig. 1. Reference scenario</figcaption></figure>

## 2.2 Random Failure Model

In the dynamic wireless communication environment, access points of both network-1 and network-2 may have major or minor failures caused by a variety of undesired events. In this paper, we consider two types of failures as follows.

**Independent Random Node Failures**
Access points in infrastructure-based wireless networks can be viewed as a set of nodes. Suppose the network is subject to random node failures where each access point fails, along with all associated links, with a probability $q$, independently of other nodes.
**Disastrous Failures** We consider disastrous failures as external events. They have severe consequences. In this paper, only disastrous failures at which damages all network-1 access points are considered.

As we mentioned in the previous section, far less work has been conducted on the modeling and analysis of the transient behavior of an infrastructure-based wireless network subject to a disastrous failure scenario. The model in the next section aims at characterizing such disaster-based survivability.

# 3 Network Survivability Model

A model is required to quantitatively assess the network survivability. In this section, we present a continuous-time Markov chain (CTMC) model to characterize the transient network behavior after disaster until the system stabilizes again.

## 3.1 Survivability Definition

Survivability is defined as the system's ability to continuously deliver services in compliance with the given requirements in the presence of failures and other undesired events [3].

In this paper, our objective is to quantify the survivability of infrastructure-based wireless networks subject to disastrous failures. For this, we define the (i) *service* to be the connections between access points and subscribers, (ii) *service requirement* to be a minimum number of access points that need to be operational for the service to be available, (iii) *undesired events* to be access points failures caused by disastrous failures. The network survivability is quantified by the transient performance from the instant an undesired event occurs until its steady state is reached. Survivability quantification can be used to compare different network architectures and survivable mechanisms. In order to deal with survivability in a quantitative way, it is necessary to have a mathematical description of the above temporal process. We use the survivability quantification definition given by ANSI T1A1.2 [11]:

The measure of interest $M$ has the value $m_0$ before a failure occurs. The survivability behavior can be depicted by the following attributes: $m_a$ is the value of $M$ just after the failure occurs; $m_u$ is the maximum difference between the value of $M$ and $m_a$ after the failure; $m_r$ is the restored value of $M$ after some time $t_r$; and $t_R$ is the relaxation time for the system to restore the value of $M$.

Fig. 2 illustrates the above notations, which constitute the survivability quantification results. Since the breakdown of one access point may affect tens or hundreds of users, the connectivity of infrastructure-based wireless networks mostly depends on the operational status of access points. The measure of interest $M$ in this paper will be the expected unavailability. Since our focus is the connectivity in large networks, we do not consider the dynamics brought by routing and traffic flows further in this paper.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Temporal aspects of survivability (adapted from [3])</figcaption></figure>

**3.2 Assumptions and Notations**

Consider the two-tier hierarchical wireless network system described in Section 2. The following assumptions are made:

- Network-1 and network-2 access points have independent random node failures according to Poisson processes with rates $\lambda_1$ and $\lambda_2$, respectively.

- A faulty node can be recovered through repairment. The independent node repair times for network-1 and network-2 access points are exponentially distributed with parameters $\mu_1$ and $\mu_2$, respectively. Assuming that there is only one repairman for each access point type.

- The system suffers disastrous breakdown resulting in all network-1 access points lost. Upon disaster, a global repair process starts immediately. The global repair time is exponentially distributed with mean $1/\tau$.

- If too few network-1 access points are available, then network-2 access points will support the service.

Furthermore, a number of parameters related to the size of the system will affect the survivability, which include:

- *I*, the maximum number of network-1 access points in the system

- *J*, the maximum number of network-2 access points in the system

- *i*, the current number of operational network-1 access points in the system

- *j*, the current number of operational network-2 access points in the system

- *C*, the minimum required number of access points in the system

Performance metric is the steady state unavailability $U = P(i + j < C)$, which is the probability that less than *C* access points are available.
### 3.3 Disaster-based Survivability Model

Since the system we analyze resides in a dynamic environment, let $(N_i(t), N_j(t))$ define a continuous-time Markov chain (CTMC) with state space $\Omega = \{(i, j); 0 \le i \le I, 0 \le j \le J\}$, where $N_i(t)$ and $N_j(t)$ denote the number of operational network-1 access points and that of network-2 access points at time $t$, respectively. The state transition diagram of this Markov chain is illustrated in Fig. 3. It is required that a minimum number of access points, $C$ ($0 < C \le I + J$) are necessary for the system to be operational. The transition rate from state $(i, j)$ to state $(i-1, j)$ is $i\lambda_1$. It corresponds to a random node failure in any of network-1 access points. The transition from state $(i, j)$ to state $(i, j-1)$ denotes a random node failure of one network-2 access point. The corresponding transition rate is $j\lambda_2$. The transition from state $(i-1, j)$ to state $(i, j)$ corresponds to the repairment of one network-1 access point with rate $\mu_1$. The transition from state $(i, j-1)$ to state $(i, j)$ denotes the repairment of one network-2 access point with rate $\mu_2$.

For each state $(i, j)$, there is a certain possibility to have disastrous failure causing all network-1 access points down and then the system will enter state $(0, j)$. For disaster-based survivability analysis, particular attention should be given to the transient behavior after the disaster. This is the reason why disastrous failure is forced (dashed arc in Fig. 3). Specifically, a global repair restores the system to state $(I, j)$ with rate $\tau$ from state $(0, j)$. The various transition rates $q_{(i,j),(i',j')}$ of the process $(N_i(t), N_j(t))$ are

$$ 
\begin{aligned}
q_{(i,j),(i-1,j)} &= i\lambda_1, & i &= 1, 2, \dots, I, j &= 0, 1, \dots, J \\
q_{(i,j),(i,j-1)} &= j\lambda_2, & i &= 0, 1, \dots, I, j &= 1, 2, \dots, J \\
q_{(i-1,j),(i,j)} &= \mu_1, & i &= 2, \dots, I, j &= 0, 1, \dots, J \\
q_{(i,j-1),(i,j)} &= \mu_2, & i &= 0, 1, \dots, I, j &= 1, 2, \dots, J \\
q_{(0,j),(I,j)} &= \tau, & j &= 0, 1, \dots, J
\end{aligned}
\quad (1) $$

Based on the above transition rate regulations, the state transition rate matrix of this model can be obtained as $Q = [q_{(i,j),(i',j')}]$.

### 3.4 Survivability Analysis: Exact Model

Let $P(t) = [P_{(0,0)}(t) \cdots P_{(i,j)}(t) \cdots P_{(I,J)}(t)]$ denote a row vector of transient state probabilities at time $t$. In order to calculate $P(t)$, the Kolmogorov-forward equation expressed in the matrix form should be satisfied as follows:

$$ \frac{dP(t)}{dt} = P(t)Q \quad (2) $$

where $Q$ is the transition rate matrix. Then the transient state probability vector can be obtained as follows:

$$ P(t) = e^{Qt} \quad (3) $$
<figure><img src="image_4.png" /><figcaption>Fig. 3. State transition diagram for the reference scenario</figcaption></figure>

where $e^{Qt}$ is defined as follows:

$$e^{Qt} = \sum_{i=0}^{\infty} Q^i \frac{t^i}{i!} \qquad (4)$$

The simplest method to compute Eq. (4) is to truncate the summation to a large number (e.g., $K$), which can be expressed as follows:

$$e^{Qt} = \sum_{i=0}^{K} Q^i \frac{t^i}{i!} \qquad (5)$$

An alternative way to compute the transient probabilities is by using eigenvalues. In this method, $Q$ is assumed to be diagonalizable,

$$Q = UVU^{-1} \qquad (6)$$

where $V$ is a diagonal matrix of eigenvalues. The transient probabilities can be defined as follows:

$$V = \begin{bmatrix} e^{v_1 t} & & & \\ & e^{v_2 t} & & \\ & & \ddots & \\ & & & e^{v_N t} \end{bmatrix}$$
Then, the transition probabilities can be written as follows:

$$ 
\begin{aligned}
P(t) &= \mathbf{U}(\sum_{i=0}^{\infty} \mathbf{V} \frac{t^i}{i!})\mathbf{U}^{-1} \\
&= \mathbf{U}e^{\mathbf{V}t}\mathbf{U}^{-1}
\end{aligned} 
\quad (7) $$

Based on the above calculated transient probabilities, the measure of interest $M$, service unavailability is obtained as reward measures from the CTMC model ($N_i(t)$, $N_j(t)$). Let each state of the CTMC is associated with a reward rate. For a valid state $(i, j)$, if $i + j < C$, the reward rate is assigned 1; otherwise the reward rate is assigned 0. Let $U(t)$ represent the instantaneous reward rate of the model. Then, the expected instantaneous reward rate $E[U(t)]$ gives the service unavailability of the system at time $t$, which is expressed as follows:

$$ E[U(t)] = \sum_{i+j<C} P_{(i,j)}(t) \quad (8) $$

However, the above so called exact model approach for calculating the transition probabilities needs to visit each state and to repeat the transient state analysis, which could be computational challenging when the network size is growing.

## 3.5 Survivability Analysis: Product-Form Approximation

The transient analysis in the last section is too complex for a symbolic closed form solution, and even too difficult for a numerical solution. Since the random node failures and repairs of two types of access points are independent, we apply a decomposition approach to facilitate the calculation of the transient probability $P_{(i,j)}(t)$ for state $(i, j)$. This is a product-form approach as follows:

$$ P_{(i,j)}(t) = P(t, i) \cdot \pi(j) \quad (9) $$

where $P(t, i)$ is the transient probability of a state $i$ ($0 \le i \le I$), and $\pi(j)$ is the steady state probability of a state $j$ ($0 \le j \le J$). The closed-form steady state probabilities $\pi(j)$ can be derived:

$$ \pi(j) = \frac{1}{j!} \left(\frac{\mu_2}{\rho_2}\right)^j \pi(0) \quad (10) $$

where $\pi(0)$ can be obtained according to the normalization condition,

$$ \pi(0) = \frac{1}{\sum_{k=0}^{J} \frac{1}{k!} \left(\frac{\mu_2}{\rho_2}\right)^k} \quad (11) $$
In order to calculate the transient probability $P(t, i)$, the transition rate matrix $\Lambda = [a_{i,i'}]$ is reduced as follows:

$$ 
\begin{aligned}
a_{i,i-1} &= i\lambda_1, & i = 2, \dots, I \\
a_{i-1,i} &= \mu_1, & i = 2, \dots, I \\
a_{0,I} &= \tau
\end{aligned} 
\qquad (12) $$

Then, the expected service unavailability $E[U(t)]$ can be defined as follows:

$$ E[U(t)] = \sum_{i+j<C} P(t, i) \cdot \pi(j) \qquad (13) $$

In particular, this product-form approach requires only transient solution of evolution of network-1 access points, and the steady-state solution of evolution of network-2 access points.

# 4 Numerical Results

In this section, the numerical solutions to the proposed survivability quantification models in the above sections are presented using Mathematica [12]. To demonstrate the applicability of the proposed product-form solution, we compare it with the exact model approach. In addition, we examine the effect of different modeling parameters on the defined performance measures.

<table><caption>**Table 1.** Default values of failure/repair parameters</caption><thead><tr><th>Parameter</th><th>λ<sub>1</sub></th><th>λ<sub>2</sub></th><th>μ<sub>1</sub></th><th>μ<sub>2</sub></th><th>τ</th></tr></thead><tbody><tr><td>Value(hour<sup>-1</sup>)</td><td>0.01</td><td>0.005</td><td>2</td><td>2</td><td>0.02</td></tr></tbody></table>

## 4.1 Computational Complexity Analysis

Table 1 lists the default value of part of parameters. It is a natural assumption to say that $(\lambda_1, \lambda_2) < \tau \ll (\mu_1, \mu_2)$. The required minimum number of access points $C$ is defined as $(I + J)/3$.

To show the computational advantages of the product-form approach over the exact model approach, we compare the time needed for calculating transient probabilities using the two approaches. We run experiments with three network scales (case 1: $I = 2, J = 2$; case 2: $I = 3, J = 2$; case 3: $I = 3, J = 3$). In all the experiment cases, $n = 30$ runs are performed and the mean running time (unit: seconds) are recorded as shown in Table 2.

The observation from Table 2 suggests that the product-form approach is able to almost immediately give the transient probabilities. However, it may take
about 0.6 seconds by using the exact model approach in case 1. Similar results can be obtained from experiments case 2 and case 3. For the exact model approach, it takes more time (about 2 seconds in case 2 and 8 seconds in case 3) than case 1. The growing of network size has significant impact on the computational complexity of the exact model approach. With regard to the solution Eq. (8), the exact model approach has a state space that is proportional to $(I+1)(J+1)$. The product-form approach will reduce the state space of the transient solution to $(I+1)$ as indicated in Eq. (13). This explains why the product-form approach has advantages in transient solution computation than the exact model approach. For large-scale networks, it can be easily realized that the exact model approach will be tough in transient solution computation while the product-form approach may be applicable.

## 4.2 Effect of Parameters on Survivability Performance

In the following, both approaches are used to numerically obtain the system survivability performance. First, we consider a small network case ($I = 3, J = 3$). We plot in a log-time way as shown in Fig. 4(a), solid curves *I* and *II* represent the results of product-form approach while the dashed curves *III* and *IV* are the results of exact model approach. As this figure suggests, the survivability quantification notations are displayed as $m_a, t_R, m_0$.

We examine the way in which parameter $\tau$ affects the survivability model. When $\tau = 0.02(\text{hour}^{-1})$, the curve *I* coincides with *III*. However, when $\tau = 1(\text{hour}^{-1})$, there exist a relatively small difference gap between curves *II* and *IV*. The decomposition in the product-form approach is based on the assumption that the random node failures and repairs of two types of access points are independent. Thus, the above observation demonstrates that if the global recovery rate $\tau$ is not much less (i.e., more than one order of magnitude) than random single node repair rates $(\mu_1, \mu_2)$, the product-form approach is not perfectly but quite closely accurate. If $\tau$ is much less than single node repair rates, the product-form approach captures the exact results in the same way as the exact model approach. Therefore, the product-form approach is quite good in accuracy.

Then we extend the analysis to a larger network case ($I = 20, J = 15$). The survivability quantification results $m_a, t_R, m_0$ are shown as the notations in Fig. 4(b). Since it is quite time-consuming to calculate the transient solutions using exact model approach, only the results of the product-form approach are

<table><caption>**Table 2.** Comparison of computational time for transient probabilities using the two approaches under three cases (mean ± standard error, unit: seconds).</caption><thead><tr><th></th><th>case 1</th><th>case 2</th><th>case 3</th></tr></thead><tbody><tr><td>Exact model</td><td>0.581 ± 0.316</td><td>1.997 ± 0.890</td><td>7.899 ± 0.895</td></tr><tr><td>Product-form</td><td>0.021 ± 0.017</td><td>0.041 ± 0.026</td><td>0.041 ± 0.016</td></tr></tbody></table>
<figure><img src="image_5.png" /><figcaption>Fig. 4. Log-plot of unavailability $E[U(t)]$ versus time t</figcaption></figure>

plotted. In both figures, curve II reaches steady state much faster than curve I. Since the mean time for a global repair is much longer than the mean repair time of one access point is obvious, it is naturally assumed that $τ$ is much less than $(μ_1, μ_2)$. In summary, compared with the exact model approach which can be actually used for small size models only, the product-form approach is more scalable as well as quite good accuracy.

## 5 Conclusion

The CTMC analytical model for wireless network survivability quantification outlined in this paper enables us to model large-scale infrastructure-based wireless networks exposed to disastrous failures. Specifically, the focus has been on characterizing the transient behavior of the system immediately after the disaster until the system restores and stablizes again. In addition, numerical results have been presented to study the impact of the underlying system parameters and the explicit parametric relations.

Future work are considered in several directions. The recovery time in the current model has for simplicity been assumed to be exponentially distributed which may be not true in real scenario. More general model, like phase-type model or semi-Markov model can be used. In addition, the locations of users and access points, which play a important role in wireless communication, are not included in our studied scenario and defined system state. In the future, we will extend the system state by adding more dimensions representing geographical characterizations.

## References

1. Zolfaghari, A., Kaudel, F.J.: Framework for network survivability performance. Selected Areas in Communications, IEEE Journal on. 5, 46–51 (1994)

2. Yun, L., Mendiratta, V.B., Kishor, S.T.: Survivability analysis of telephone access network. In: IEEE 15th International Symposium on Software Reliability Engineering, pp. 367–377. IEEE Press, Bretagne (2004)
3. Heegaard, P.E., Kishor, S.T.: Network survivability modeling. Comput. Netw. 53, 1215–1234 (2009)

4. Dongyan, C., Sachin, G., Kishor, S.T.: Network survivability performance evaluation: a quantitative approach with applications in wireless ad-hoc networks. In: ACM 5th International workshop on Modeling analysis and simulation of wireless and mobile systems, pp. 61–68. ACM, New York (2002)

5. Fei, X., Wenye, W.: On the Survivability of Wireless Ad Hoc Networks with Node Misbehaviors and Failures. Dependable and Secure Computing, IEEE Transactions on. 7, 284–299 (2010)

6. Tipper, D., Charnsripinyo, C., Shin, H., Dahlberg, T.: Survivability analysis for Mobile Cellular Networks. In: Communication Networks and Distributed Systems Modeling and Simulation Conference, pp. 367–377. SCS, San Antonio (2002)

7. Dharmaraja, S., Jindal, V., Varshney, U.: Reliability and Survivability Analysis for UMTS Networks: An Analytical Approach. Network and Service Management, IEEE Transactions on. 5, 132–142 (2008)

8. Jindal, V., Dharmaraja, S., Kishor, S.T.: Analytical survivability model for fault tolerant cellular networks supporting multiple services. In: IEEE International Symposium on Performance Evaluation of Computer and Telecommunication Systems, pp. 505–512. IEEE Press, Calgary (2006)

9. James, P.G., Egemen, K., Mahmood, A., Abdul, J., Qian, S., Justin P.R.: Modelling and Analysis of Network Resilience (invited paper). In: IEEE 3rd International Conference on Communication Systems and Networks (COMSNETS), pp. 1–10. IEEE Press, Bangalore (2011)

10. Wireless Trondheim, http://tradlosetrondheim.no

11. ANSI T1A1.2 Working Group on Network Survivability Performance.: Technical Report on enhanced network survivability performance. Technical Report TR No. 68 (2001)

12. Mathematica Guide, http://reference.wolfram.com/mathematica/guide/Mathematica.html