Accurate and Interval Estimates of the Probability of Network Service Availability for Communication Networks

Abstract

One of the important and universal characteristics of the network performance for both a user and a network owner is the probability of the network service availability at any time. To obtain an accurate estimate of the probability of a particular network service availability in the class of binary stochastic models, effective methods of structure function decomposition are used. The paper discusses the issues of obtaining accurate estimates of the probability of network service availability for arbitrary pairs of network nodes. Lower bound and upper bound estimates for the probability of network service availability are constructed for large dimension networks with a complex structure.

Educational Scientific Complex “Institute for Applied System Analysis”.

1 Introduction

Over recent decades, problems of network structures reliability belong to the priority areas of research in the reliability theory.

Formally, the communication network is interpreted as a weighted graph without loops. The graph can be both unoriented and oriented. Elements of the graph are weighted by weight parameters. Weight values are usually assigned to the edges, assuming that the nodes are absolutely reliable. Weights can be also assigned to nodes.

For networks with renewal, the role of weight parameters is played by the factors of network elements availability. Failures of elements are caused by technical problems and external influences.

For practice, it is important to know that any pair of network subscribers can get a connection despite the failure of the elements (network service availability).

The availability of a network service means the ability to provide communication for any user at any time.

A few formal definitions of the availability of network services are given below:

• 1. The network has the (s-t) availability property at time t, if there is at least one simple path from node s to node t.

• 2. The network has the property of full availability at time t, if there is at least one simple path for any pair of network nodes.

• 3. The network has the property of full availability at time t, if there is at least one network spanning tree.

• 4. The network has the property of full availability at time t, if at least one available element exists in each of the cutting sets of the network.

Of course, the definitions (2–4) are equivalent, but they represent the structure of the connectivity property of a network in different ways.

The probability of network service availability allows to objectively define which of the compared networks is better suited to its purpose. Monitoring of this characteristic makes it possible to make timely necessary adjustments to the operation and development of the network.

The task of assessing the network service availability belongs to the class of so-called “computationally hard” problems of combinatorial logic of properties and classes. For this reason, it is not always possible to obtain an accurate estimate of the availability of a network service for very large networks, and upper bound and lower bound estimates are used instead of it.

Availability of networks can be characterized by assessment methodologies [1] such as Reliability Block Diagram (RBD), Fault Tree Analysis (FTA) [2] and so on.

Typical algorithms for computing network availability include the state enumeration method [3], sum of disjoint products method [4], factorization method [5], minimal cuts method [6] and cellular automata [7, 8].

In this paper formalization of the problem of assessing the probability of network service availability in the form suitable for machine implementation is based on the isomorphism of the Boolean properties algebra (predicates) and the corresponding Boolean classes algebra. The predicate of the network service availability is represented by the corresponding structure function.

We consider the problem of estimating the stationary probability of a pair network connection. It is important to note that the concept of the network (s-t) connectivity is closely related to transport flow tasks. The stationary probability of the network (s-t) connectivity can be considered as one of the upper bound estimates for the stationary probability of a full network connectivity [9]. The stationary probability of a full network connectivity can be considered as a guaranteed lower bound for the probability of connectivity of any pairs of nodes.

2 Binary Stochastic System Model

• 1. Let $C = \{1, 2, \dots , n\}$ be an indexed finite set of the system elements.

  The number |C| is called the order of the system.

  Binarity means that the elements and the whole system take values in the set $B_2 = \{1, 2\}$.

  The evolution of the i-th element in time is modeled by the corresponding alternating renewal process $x_i(t), i= 1, 2, \dots , n$.

  $$ x_i(t) = \{ \begin{array}{ll} 1, &{} \textit{if at the moment t i-th element is operable} \\ 0, &{} otherwise\end{array} \} .$$

  We need some results of the renewal theory in a convenient interpretation.

  For the i-th element, the probability to be in an accessible state at time t is called the non-stationary availability factor and is denoted by

  $$P\{x_i(t)=1\}=P_i(t),i= 1, 2, \dots , n.$$

  As t increases, the nonstationary availability factor tends to a constant value - the stationary availability factor of the i-th element. Its value is defined as the ratio of the average length of the availability interval of the i-th element to the average length of the cycle of the i-th alternating process:

  $$\lim _{t\rightarrow \infty } P\{x_i(t)=1\}=\frac{M[\theta _{x_i}]}{M[\theta _{x_i}]+M[\xi _{x_i}]}=P_i,i= 1, 2, \dots , n.$$

• 2. Let the vector of the elements state

  $$X(t)={(x_1(t),x_2(t),\dots ,x_n(t))}$$

  uniquely determine the state of the system. The corresponding function (two-valued predicate) is called the structure function of the system:

  $$ \varphi (x_1(t),\dots ,x_n(t)) = \{ \begin{array}{ll} 1, &{} \textit{if at the time t the system is operable} \\ 0, &{} otherwise \end{array} \} .$$

  Formally, the role of a truth (false) set can be performed by any function of the logic algebra, with the exception of function-constants. Most systems have the monotonicity property, so we consider only the case when the structure function $\varphi (x_1(t),\dots ,x_n(t))$ is monotone.

• 3. Deterministic properties of structure functions are as follows:

  • (a)
    $$ \bigwedge _{i=1}^n x_i \le \varphi _s(x_1(t),\dots ,x_n(t)) \le \bigvee _{i=1}^n x_i $$

    (all variables are significant).

  • (b) Reservation scale theorem:

    $$\begin{aligned}&\varphi _s(x_1\vee \tilde{x}_1,x_2\vee \tilde{x}_2,\dots ,x_n\vee \tilde{x}_n) \ge \varphi _s(x_1,x_2,\dots ,x_n)\vee \varphi _s(\tilde{x}_1,\tilde{x}_2,\dots ,\tilde{x}_n), \\&\varphi _s(x_1\wedge \tilde{x}_1,x_2\wedge \tilde{x}_2,\dots ,x_n\wedge \tilde{x}_n) \le \varphi _s(x_1,x_2,\dots ,x_n)\wedge \varphi _s(\tilde{x}_1,\tilde{x}_2,\dots ,\tilde{x}_n). \end{aligned}$$

  • (c) Any monotone structure function is uniquely representable in the following form:

    $$ \bigvee _I f_i (x_1, \dots , x_n)\equiv \varphi _s(x_1,\dots ,x_n)\equiv \bigwedge _J\psi _j^d(x_1, \dots , x_n), $$

    where:

    $\ I=\{f_1 (x_1, \dots , x_n),\dots , f_m (x_1, \dots , x_n)\}$ - full set of first implicants of the function $\varphi _s(x_1,\dots ,x_n)$,

    $J=\{\psi _1 (x_1, \dots , x_n),\dots , \psi _r (x_1, \dots , x_n)\}$ - full set of first implicants of the function $\varphi _s^d(x_1,\dots ,x_n)$.

    $$\begin{aligned}&\varphi _s^d(x_1,\dots ,x_n)= \bar{\varphi }(\bar{x}_1,\dots ,\bar{x}_n). \\&\psi _s^d(x_1,\dots ,x_n)= \bar{\psi }(\bar{x}_1,\dots ,\bar{x}_n). \end{aligned}$$

From property (c) and the properties of two dual automorphisms

$$\begin{aligned}&H:U\rightarrow U | \forall Q \in U, H(Q)=\bar{Q}, \\&D:U\rightarrow U | \forall Q \in U, D(Q)= Q^d \end{aligned}$$

we obtain immediate results:

$$\begin{aligned} \bigvee _J \psi _j(x_1, \dots , x_n) \equiv \varphi _s^d(x_1,\dots ,x_n) \equiv \bigwedge _I f_i^d(x_1, \dots , x_n), \end{aligned}$$

(1)

$$\begin{aligned} \bigvee _J \psi _j(\bar{x}_1, \dots , \bar{x}_n) \equiv \bar{\varphi }_s(x_1,\dots ,x_n) \equiv \bigwedge _I f_i^d(\bar{x}_1, \dots , \bar{x}_n), \end{aligned}$$

(2)

$$\begin{aligned} \bigvee _I f_i(\bar{x}_1, \dots , \bar{x}_n) \equiv \bar{\varphi }_s^d(x_1,\dots ,x_n) \equiv \bigwedge _J \psi _j^d(\bar{x}_1, \dots , \bar{x}_n), \end{aligned}$$

(3)

$$\begin{aligned} \bigvee _{I_1\subset {I}} f_i( x_1, \dots , x_n)< \varphi _s(x_1,\dots ,x_n)<\bigwedge _{J_1\subset {J}} \psi _j^d( x_1, \dots , x_n), \end{aligned}$$

(4)

$$\begin{aligned} \bigvee _{{J_1}\subset {J}} \psi _j(\bar{x}_1, \dots , \bar{x}_n)< \bar{\varphi }_s(x_1,\dots ,x_n) < \bigwedge _{I_1\subset {I}} f_i^d(\bar{x}_1, \dots , \bar{x}_n). \end{aligned}$$

(5)

Using these properties makes it possible to construct all possible lower bounds and upper bounds estimates for the network connectivity probability. It is sufficient to use Boolean lattice inequalities from properties (4) and (5).

The axioms of Boolean algebra are consistent with the laws of intuitive logic for sets, propositions, and object properties (predicates).

The process of system functioning is a discrete-continuous process of random walk along a Boolean vector lattice. The time of transition from this state to the neighboring state is neglected.

As a characteristic of system functioning quality, we consider the probability of the network service availability

$$P\{\varphi (x_1,\dots ,x_n)=1\}.$$

The formalization of the problem of estimating the stationary probability of pair connectivity in the form suitable for machine implementation is based on the isomorphism of Boolean algebra of functions representing properties

and the corresponding Boolean class algebra

$$U_K=\langle P(B_2^n);\cap ;\cup ;{'}\rangle ,$$

where:

• $\{x_1, \dots , x_n\}$ - generators of Boolean algebra of functions;

• $B_2^n$ - Boolean vector lattice (vector space of network elements);

• $|B_2^n|=2^n; dim(B_2^n)=n$.

3 Problem Formulation

Given:

• G(Y, X) - network structure;

• $Y=\{y_1,\dots ,y_l\}$ - set of network nodes;

• $X=\{x_1,\dots ,x_n\}$ - set of network channels;

• $s,t\in Y$ - two arbitrary vertices of the network;

• $\theta _{x_i}$ - random time intervals of availability of the i-th network channel;

• $\xi _{x_i}$ - random time intervals of unavailability of the i-th network channel;

• $p_i$ - factor of stationary availability of the i-th channel of the network:

  $$ p_i=\frac{M[\theta _{x_i}]}{M[\theta _{x_i}]+M[\xi _{x_i}]}, \ \bar{p}_i=1-p_i=q_i.$$

For the sake of simplicity, we will consider all nodes to be absolutely reliable.

Assumptions:

• 1. Dependence between random variables $\{\theta _{x_i}\}$ and $\{\xi _{x_i}\}$, $i=1,\dots ,n$, can be neglected.

  $$\exists M[\theta _{x_i}]<\infty \text { and } \exists M[\xi _{x_i}]<\infty .$$

• 2. The vector of the network elements state uniquely determines the (s-t)-connectivity ((s-t)-availability) of the network.

• 3. The network is viewed as a renewable system with fully available renewal.

• 4. For a given mode of information load on the network (small, medium, large), a stationary mode is set up.

• 5. The network status relatively to $\varphi _{s,t}$-accessibility (unavailability) is determined by the resource state of its elements at a given load on the network.

Required to find the stationary probability of the network (s-t)-connectivity:

$$P\{\varphi _{s,t}(x_1,\dots ,x_n)=1\}.$$

To solve the problem, the following algorithms are proposed:

• algorithm for finding all shortest (s-t)-paths of the network;

• algorithm for finding all minimal (s-t)-cuts of the network;

• algorithm for orthogonalization of the connectedness function in its most compact representation.

As a result of orthogonalization, we obtain a computational scheme for estimating the probability of (s-t)-connection, which is minimal from the point of view of the computational complexity.

By assigning values $p_i$ to variables $x_i$ in the orthogonalized minimal disjunctive normal form (MDNF)

$$\varphi _{s,t}(x_1,\dots ,x_n)=1,$$

and $q_i$ to variables with negations $\bar{x}_i$, we get the representation of the (s-t)-connection probability as a function of the availability of the network elements.

4 Algorithm for Finding the Representation of (s-t)-Connection Relation on a Graph G(Y,X)

A formal representation of (s-t)-connection relation $(s,t\in Y)$:

$$\varphi _{s,t}(x_1,\dots ,x_n) = \bigvee _{\{f_i\}\in I} (\bigwedge _{k_i\in \{f_i\}}x_{k_i}),$$

where $\{f_i\}$ is a list of indices of the variables forming a simple (s-t)-path (the minimal carrier of the connectedness property).

$I= \{\{f_1\},\{f_2\},\dots ,\{f_m\}\}$ - complete list of all (s-t)-paths.

Let us consider an example of algorithms for finding (s-t)-paths and (s-t)-cuts in the network graph (see Fig. 1).

Fig. 1.

Graph G(Y,X).

4.1 Algorithm for Finding Network (s-t)-Paths

Input information: the logical adjacency matrix of the graph $M_G$ (see Fig. 2).

• $N_v=4$ - number of vertices;

• $Y=\{y_1,\dots , y_l\}=\{y_1,y_2,y_3,y_4\}$ - set of vertices;

• $N_a=5$ - number of arcs;

• $X=\{x_1,\dots , x_n\}=\{x_1,x_2,x_3,x_4,x_5\}$ - set of arcs.

Find: (s-t)-paths from $y_1$ to $y_4$ (s = $y_1$, t = $y_4$).

Fig. 2.

Adjacency matrix for graph G(Y,X).

• 1. If the value of (s, t)-element in the logical adjacency matrix $M_G$ is not equal 0, then there is a path of length 1 from vertex s to vertex t, we store it into memory. In this example, $(y_1,y_4)=0$. Thus, paths of length 1 do not exist.

• 2. Iterations start with $N=1$, where N is an iteration variable.

  $y_s^{(1)}$ equals to the s-th row of the matrix $M_G$.

• 3. We multiply (logically) row $y_s^{(N)}$ by $M_G$ and get a new row.

• 4. If the number of iterations N is less than the number of vertices minus one $(N_v-1)$, then go to step 3, otherwise - the end of the algorithm.

For our example first iterations are as follows.

We multiply row $y_s^{(1)}$ by $M_G$:

$$ (0 \ 1 \ 3 \ 0) \left( \begin{array}{l} \, 0 \ 1 \ 3 \ 0 \\ \, 1 \ 0 \ 5 \ 2 \\ \, 3 \ 5 \ 0 \ 4 \\ \, 0 \ 2 \ 4 \ 0 \end{array}\right) =(0;\ 3\wedge 5;\ 1\wedge 5;\ (1\wedge 2)\vee (3\wedge 4)). $$

The result is stored in row $y_s^{(2)}$. Further, we analyze the value of the t-th element of $y_s^{(2)}$.

In our case, it is $(1\wedge 2)\vee (3\wedge 4)$ - two shortest paths of length 2.

The value of the t-th element of $y_s^{(2)}$ equals zero:

$$y_s^{(2)}=(0; \ 3\wedge 5; \ 1\wedge 5;\ 0).$$

Output information:

For this example, 4 shortest paths were found

$$\varphi _{14}(x_1, x_2,x_3,x_4,x_5)=(x_1\wedge x_2)\vee (x_3\wedge x_4) \vee (x_1 \wedge x_4 \wedge x_5) \vee (x_2 \wedge x_3 \wedge x_5).$$

List of (s-t)-paths:

$$ \{f_1\}=\{1,2\}; \ \{f_2\}=\{3,4\}; \ \{f_3\}=\{1,4,5\}; \{f_4\}=\{2,3,5\}.$$

4.2 Algorithm for Finding (s-t)-Cuts of the Network in General Case

Input information:

MDNF representation $\varphi _{s,t}(x_1,\dots ,x_n)$.

Find: (s-t)-cuts of network.

The algorithm consists in finding the dual function

$$\varphi _{s,t}^d(x_1,\dots ,x_n)$$

for $\varphi _{s,t}(x_1,\dots ,x_n)$, represented in MDNF.

The indices of the variables forming the first implicants of the dual function $\varphi _{s,t}^d(x_1,\dots ,x_n)$ are minimal (s-t)-cuts.

$$\varphi _s^d(x_1,\dots ,x_n)=\bar{\varphi }(\bar{x}_1,\dots ,\bar{x}_n) .$$

$J=\{\{\psi _1\},\{\psi _2\},\dots \{\psi _r\}$ - a complete list of all (s-t)-cuts,

where $\{\psi _j\}$ - j-th (s-t)-cut, $j=1,\dots ,r$.

For the given graph G(Y, X) in Fig. 1 it is necessary to find a dual function $\varphi _{y_1,y_4}^d(x_1,\dots ,x_5)$ and to represent it in the minimal conjunctive normal form (MCNF). Using the result of the previous problem, we obtain a complete list of (s-t)-cuts:

$$ \begin{array}{c} \displaystyle \varphi _{y_1,y_4}^d(x_1,\dots ,x_5)=(x_1\vee x_2)\wedge (x_3\vee x_4) \wedge (x_1 \vee x_4 \vee x_5) \wedge (x_2 \vee x_3 \vee x_5)\\ \displaystyle =(x_1 \vee x_2x_4 \vee x_2x_5)\wedge (x_3\wedge x_2x_4 \vee x_4x_5)=x_2x_4\vee x_1x_3 \vee x_1x_4x_5\vee x_2x_3x_5\\ \displaystyle \varphi _{y_1,y_4}(x_1,\dots ,x_5)=\varphi _{y_1,y_4}^{dd}(x_1,\dots ,x_5)\\ \displaystyle = \bigwedge _{\{\psi _j\} \in J} (\bigvee _{r_j \in \{\psi _j\}}x_{r_j}). \end{array}$$

List of (s-t)-cuts:

$$ \{\psi _1\}=\{2,4\}; \ \{\psi _2\}=\{1,3\} \ \{\psi _3\}=\{1,4,5\}; \{\psi _4\}=\{2,3,5\}.$$

4.3 Algorithm for Orthogonalization of the Connectedness Function in General Case

Input information: MDNF (MCNF) representation

$$\varphi _{s,t}(x_1,\dots ,x_n)$$

and

$$\varphi _{s,t}^d(x_1,\dots ,x_n).$$

Find: Orthogonal MDNF (MCNF) $\varphi _{s,t}$ and $\varphi _{s,t}^d$.

• 1. Choose one of the representations

  $$\varphi _{s,t}(x_1,\dots ,x_n)$$

  or

  $$\varphi _{s,t}^d(x_1,\dots ,x_n),$$

  which contains the minimal number of characters (the most compact). The selected representation is orthogonalized.

• 2. The generalized De Morgan formula is applied to the chosen function: for function $\varphi _{s,t}(x_1,\dots ,x_n)$ represented in MDNF:

  $$\varphi _{s,t}(x_1,\dots ,x_n)=f_1\vee \dots \vee f_m =f_1+\bar{f_1}f_2+\bar{f_1}\bar{f_2}f_3+\dots +\bar{f_1}\dots \bar{f}_{m-1}f_m,$$

  where: $f_i$ - i-th network (s-t)-path; m - the number of network (s-t)-paths.

You can also apply the generalized De Morgan formula for orthogonalization of the MCNF representation:

$$\varphi _{s,t}(x_1,\dots ,x_n)=f_1^d\wedge \dots \wedge f_m^d =f_1^d-f_1^d \bar{f}_2^d-f_1^df_2^d\bar{f}_3^d-\dots -f_1^d \dots f_{m-1}^d \bar{f}_m^d.$$

For a function $\varphi _{s,t}^d(x_1,\dots ,x_n)$, presented in MDNF:

$$\varphi _{s,t}^d(x_1,\dots ,x_n)=\psi _1\vee \dots \vee \psi _r=\psi _1+\bar{\psi }_1\psi _2+\bar{\psi }_1\bar{\psi }_2\psi _3+\dots +\bar{\psi }_1\dots \bar{\psi }_{r-1}\psi _r,$$

where:

• $\psi _i$ - i-th (s-t)-cut of the network;

• r - the number of (s-t)-cuts.

Fig. 3.

Graph of network.

5 Estimation of (s-t)-Connection Probability of Communication Network

Task definition: we have the communication network and nodes s and t (see Fig. 3).

For each channel, an availability factor is

$$p_i=0.8, i=1,\dots ,12.$$

Required to find:

• 1. List of all shortest (s-t)-paths.

• 2. List of all shortest (s-t)-cuts.

• 3. Orthogonal representation form.

• 4. The probability of the (s-t)-connection.

To solve this problem it is necessary to construct a matrix of logical adjacency for a given graph structure (see Fig. 4).

Fig. 4.

Matrix of logical adjacency.

The adjacency matrix is the input for a corresponding computer program, which we have used to find paths and cuts. We obtain the following result (Tables 1 and 2).

Table 1. List of (s-t)-paths.

Table 2. List of (s-t)-cut sets.

For orthogonalization we choose a function

$$\varphi _{s,t}^d(x_1,\dots ,x_{12}),$$

since the representation

$$ L(\varphi _{s,t}^d(x_1,\dots ,x_{12}))$$

is simpler than

$$L(\varphi _{s,t}(x_1,\dots ,x_{12})).$$

The calculation formula:

$$\begin{aligned} \begin{array}{c} h(p_1,\dots ,p_{12})=1-q_1q_2-(1-q_1q_2)q_{11}q_{12}\\ -p_2(1-q_{11}q_{12})q_1q_3q_8\\ -(1-q_{11}q_{12})(1-q_1q_2-p_2q_1q_3)q_5q_6q_8\\ -p_1p_5p_8p_{12}q_2q_4q_6q_{10}q_{11}\\ -p_2p_5p_8p_{11}q_1q_3q_7q_9q_{12}\\ -p_{11}(1-q_1q_2-p_2q_1q_3q_8\\ -(1-q_1q_2-p_2q_1q_3)q_6q_8)q_5q_9q_{12}\\ -p_1p_8(1-q_{11}q_{12}-p_{11}q_9q_{12})q_2q_4q_5q_6\\ -p_5p_{12}(1-q_1q_2-p_2q_1q_3)q_6q_8q_{10}q_{11}. \end{array} \end{aligned}$$

(6)

To find the probability of (s-t)-connectivity, we substitute the values of availability factors in formula received (6).

Finally, the probability of (s-t)-connectivity:

$$h(p_1,\dots ,p_{12})=0{,}9003.$$

To assess and analyze the probability of availability of network services in large-scale networks, one can use known lower and upper bound estimates. These estimates can be constructed on the basis of the deterministic properties of the monotonic structures.

6 Conclusion

The approach for estimating the probability of (s-t)-accessibility is proposed. It is based on the isomorphism of properties algebra and classes algebra, also some order considerations.

The idea is also suitable for estimating the probability of full connectivity of large-dimensional communication networks.

The found probability of pairing and full connectivity allows you to analyze the availability properties with changing network load.

For a comparative analysis of the network structures reliability it is necessary to be able to calculate the probabilities of their full connectivity. The structure with higher probability is more preferable.

In the case of excessively large network dimension, when an accurate estimate is impossible, lower and upper bound estimates are constructed formally using inequalities (4), (5). The error in the estimate is determined by the difference between the boundary estimates (upper and lower).

This approach is suitable for future scientific search:

• to solve problems of designing networks with specified properties;

• to estimate an average time, when a network is steady and a service is available;

• to assess the importance of network elements [10].

The importance of an element shows the degree of its influencing the network availability ratio when providing a network service.