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

HAL
open science

# Estimating network resilience, a performability metric

Gerardo Rubino

► To cite this version:

Gerardo Rubino. Estimating network resilience, a performability metric. MCM 2023 - 14th International Conference on Monte Carlo Methods and Applications, University of Paris VI, Jun 2023, Paris, France. hal-04389376

HAL Id: hal-04389376

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

Submitted on 11 Jan 2024

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.

Public Domain
<figure><img src="image_2.png" /></figure>

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

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

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

Estimating network resilience,
a performability metric

G. Rubino, Inria, Rennes, France

Paris, June 28

MCM'23

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

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

<figure><img src="image_8.png" /></figure>
<figure><img src="image_9.png" /></figure>

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

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

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

# Talk's content

1. The resilience metric

2. Monte Carlo standard and rare events

3. Back to the resilience

4. Conclusions

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

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

<figure><img src="image_15.png" /></figure>
<figure><img src="image_16.png" /></figure>

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

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

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

# Talk's content

1. The resilience metric

2. Monte Carlo standard and rare events

3. Back to the resilience

4. Conclusions

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

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_31.png" /></figure>
<figure><img src="image_32.png" /></figure>

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

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

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

# Introduction

* In the quantitative analysis of systems, two broad territories appear: performance analysis ("how much" the system does, *assuming it is perfect*) and dependability studies (how it behaves face to failures and in some cases repairs, *ignoring its work*).

* In some cases, we take simultaneously into account both aspects of systems, and we then speak about *performability*.

* In this work, we consider a dependability analysis on a static setting, and we work with an extension of classic reliability metrics to the performability family.

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

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

<figure><img src="image_38.png" /></figure>
<figure><img src="image_39.png" /></figure>

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

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

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

* The abstract model consists of a graph (assumed undirected here, to simplify), where nodes are perfect but edges fail independently of each other (the most used assumption; many other ones are possible).

* For each edge *i*, *r*ᵢ is the probability that it works and 1 - rᵢ is the probability that it doesn't, behaving as absent from the graph. This means a **binary world**.

* Classic reliability consider connectivity-based metrics such as

* $R_{s,t} = P(\text{there is at least a working path between nodes s and t})$,

* $R_{\text{all}} = P(\text{there is at least a working path between any pair of nodes})$.

* They are all-nothing measures. How to do better than that? We consider $R_{\text{all}}$ and instead of the zero-one associated property, we look at the number of pairs of nodes that can communicate (the # of pairs of nodes for which there is a working path connecting them).

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

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

<figure><img src="image_45.png" /></figure>
<figure><img src="image_46.png" /></figure>

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

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

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

Context

* Origin: project with Nokia on dependability propzrties of new types of 5G/6G radio networks.

* Observation: in this context, it is some times hard to discriminate between different architectures using reliability, because of rarity of system failures.

* 2 ideas here: move to performability, and move to conditional metrics (evaluate the metrics conditioning on the fact that something failed), and working if possible with static models.

* (In the project, we finally had to move to dynamical models – transient analysis of stochastic models.)

* Here, we keep the static context and discuss some work following the two ideas above.

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

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

<figure><img src="image_52.png" /></figure>
<figure><img src="image_53.png" /></figure>

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

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

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

# Resilience

* Let NCP = number of pairs of nodes that can communicate in G (obviously assumed to be connected).

* The resilience Res of the model is

$$Res = \mathbb{E}(NCP).$$

* This is a typical performability metric. Instead of a binary situation, we can distinguish between a large number of possibilities (of performance levels), from 1 to $1 + \binom{n}{2}$ if there are n nodes in the model.

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

<figure><img src="image_58.png" /></figure>
<figure><img src="image_59.png" /></figure>

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

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

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

Example

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

Figure: A widely used Arpanet topology in network reliability, from the history of this famous communication network.

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

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

<figure><img src="image_66.png" /></figure>
<figure><img src="image_67.png" /></figure>

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

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

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

# Some properties of resilience

* Range: $0 \le NCP \le \binom{n}{2}$.

* $\mathbb{P}(NCP = 0) = \Pi_{\text{all edge } i}(1 - r_i)$.

* $\mathbb{P}(NCP = \binom{n}{2}) = R_{\text{all}}$.

* $\text{Res}|_{\forall \text{ edge } i \text{ s.t. } r_i=0} = 0$, $\text{Res}|_{\forall \text{ edge } i \text{ s.t. } r_i=1} = \binom{n}{2}$.

* Immediate bounds: $\binom{n}{2} R_{\text{all}} \le \text{Res} \le \binom{n}{2}$.

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

<figure><img src="image_72.png" /></figure>
<figure><img src="image_73.png" /></figure>

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

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

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

* Define the r.v. $Y_{s,t} = 1$ (there is a path connecting nodes s and t). We have $R_{s,t} = \mathbb{P}(Y_{s,t} = 1) = \mathbb{E}(Y_{s,t})$ and then,

$$NCP = \sum_{\text{all nodes } s,t, s < t} Y_{s,t}$$

leading to

$$Res = \sum_{\text{all nodes } s,t, s < t} R_{s,t}$$

* We can normalize the metric, dividing $\mathbb{E}(NCP)$ by $\binom{n}{2}$, thus leading to an index in $[0, 1]$.

* The scaled resilience of the network, $ResScaled$, is then $ResScaled = 2Res/(n(n-1))$, and we have

$$R_{\text{all}} \leq ResScaled \ (\leq 1).$$

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

<figure><img src="image_78.png" /></figure>
<figure><img src="image_79.png" /></figure>

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

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

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

## Example: the bridge topology

<figure><img src="image_83.png" /><figcaption>Figure: The bridge topology</figcaption></figure>

* Homogeneous case.

* Using brute force (listing all 2⁵ possible links' states), we obtain
  $Res = r(5 + 8r - 14r^3 + 7r^4)$.

* $ResScaled = \frac{Res}{6} = \frac{5 + 8r - 14r^3 + 7r^4}{6}$.

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

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

<figure><img src="image_86.png" /></figure>
<figure><img src="image_87.png" /></figure>

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

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

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

## Example: a path with $n \ge 2$ nodes

<figure><img src="image_91.png" /><figcaption>Figure: A path with $n \ge 2$ nodes</figcaption></figure>

* Homogeneous case. Conditioning (factorization), we obtain

$$ \mathrm{Res}_n = \frac{r[n(1-r) - (1-r^n)]}{(1-r)^2} = \frac{r[n-1-r(n-r^{n-1})]}{(1-r)^2}. $$

* Scaling,

$$ \mathrm{ResScaled}_n = \frac{2r[n(1-r) - (1-r^n)]}{n(n-1)(1-r)^2}. $$

* After some more combinatorics, using $r = 1 - \varepsilon$, we have

$$ 1 - \mathrm{ResScaled}_n = 1 - \frac{n+1}{3}\varepsilon + O(\varepsilon^2). $$

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

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

<figure><img src="image_94.png" /></figure>
<figure><img src="image_95.png" /></figure>

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

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

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

## Example: a ring with $n \ge 3$ nodes

<figure><img src="image_99.png" /><figcaption>Figure: Here, a ring with 4 nodes</figcaption></figure>

* Homogeneous case. Using series-parallel formulas, we obtain (also holds if $n = 2$)

$$Res_n = nr\left(\frac{1-r^{n-1}}{1-r} - \frac{n-1}{2}r^{n-1}\right).$$

* Scaling, $Rescaled_n = \frac{2r(1-r^{n-1})}{(n-1)(1-r)} - r^n$.

* With $r = 1 - \epsilon$, $1 - Rescaled_n = 1 - \frac{n+1}{6}\epsilon^2 + O(\epsilon^3)$.

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

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

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

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

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

<figure><img src="image_105.png" /></figure>
<figure><img src="image_106.png" /></figure>

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

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

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

# Talk's content

1. The resilience metric

2. Monte Carlo standard and rare events

3. Back to the resilience

4. Conclusions

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

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

<figure><img src="image_112.png" /></figure>
<figure><img src="image_113.png" /></figure>

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

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

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

Standard Monte Carlo

• Let us consider a classic metric such that $R_{s,t}$ or $R_{all}$, here $R$.

• Let $X_i = 1$ (line $i$ works) and $Y = 1$ (the network **doesn't** work). We have $P(X_i = 1) = r_i$ and $P(Y = 1) = 1 - R = \gamma$ (the target).

• Let $E$ = # of edges (the components of the systems) and denote by $X$ the vector $X = (X_1, X_2, \dots, X_E)$.

• Make $N$ independent copies $X^{(1)}, X^{(2)}, \dots, X^{(N)}$ of $X$; for each copy $X^{(n)}$, compute the network state $Y^{(n)}$.

• We then estimate $\gamma$ by

$$ \tilde{\gamma}_N = \frac{1}{N} \sum_{n=1}^{N} Y^{(n)} . $$

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

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

<figure><img src="image_119.png" /></figure>
<figure><img src="image_120.png" /></figure>

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

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

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

* This works fine if $\gamma$ is not (too) close to 0, and becomes even useless when $\gamma \approx 0$ (the rare event case).

* The relative error of this estimation is $\Theta((N\tilde{\gamma}_N)^{-1/2})$, that $\to \infty$ as $\gamma \to 0$, for fixed $N$.

* This is typically resumed in sentences such as “the standard estimator behaves poorly in the rare event case”. We claim here that this is not precise enough, it depends on how we implement the estimator.

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

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

<figure><img src="image_126.png" /></figure>
<figure><img src="image_127.png" /></figure>

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

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

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

# A specific implementation

* Suppose we implement the standard Monte Carlo procedure the following (terrible) way:

* we will first build a (huge) $N \times (E+1)$ table with

* $N$ rows (think $N \gg 1$), one per realisation,

* and $E+1$ columns, one for each component's state and the last one for the system's state;

* we fill the $N$ rows ignoring column $E+1$;

* element $(n, i)$, $1 \le i \le E$, contains a realisation of the binary random variable $X_i^{(n)}$;

* once the first $E$ columns filled, column $E+1$ is filled with, at row $n$, the corresponding value of $Y^{(n)}$;

* once the table filled, we compute the estimation $\tilde{\gamma}_N$.

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

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

<figure><img src="image_133.png" /></figure>
<figure><img src="image_134.png" /></figure>

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

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

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

<table><thead><tr><th></th><th>X<sub>1</sub></th><th>X<sub>2</sub></th><th>...</th><th>X<sub>E</sub></th><th>Y</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1</td><td>...</td><td></td><td>0</td></tr><tr><td>2</td><td>1</td><td>1</td><td>...</td><td></td><td>0</td></tr><tr><td>3</td><td>1</td><td>1</td><td>...</td><td></td><td>1</td></tr><tr><td>...</td><td></td><td></td><td>...</td><td></td><td>...</td></tr><tr><td>N (>> 1)</td><td>1</td><td>1</td><td>...</td><td></td><td>1</td></tr></tbody></table>

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

<figure><img src="image_139.png" /></figure>
<figure><img src="image_140.png" /></figure>

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

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

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

# Remarks

* Consider the case of $r_i \approx 1$ for all $i$, so $R \approx 1$ as well, and $\gamma \approx 0$.

* Let's now look at the table but in a column-by-column way. Assume, to simplify the presentation, $N = \infty$.

* Let $F_i$ be the first element in column $i \in \{1, \dots, E\}$ with a '0'; we have $\mathbb{P}(F_i = f) = r_i^{f-1}(1 - r_i)$, $f \ge 1$.

* Let $M = \min\{F_1, \dots, F_E\}$; M is also geometric:

$$ \mathbb{P}(M = m) = r^{m-1}(1-r), \quad m \ge 1, \quad r = r_1 r_2 \cdots r_E. $$

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

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

<figure><img src="image_146.png" /></figure>
<figure><img src="image_147.png" /></figure>

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

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

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

# A different viewpoint

* This suggests a different way of implementing the same standard Monte Carlo estimator, using previous observations and the fact that the geometric r.v.s on $N_{\ge 1}$ are memoryless.

* Sample $M$. Call $m$ the obtained value. Interpretation: the first $m-1$ values of last column are all 0s.

* For row $m$, we need to sample vector $X$, knowing that in $F$ there is at least one component down (at least one $X_i$ is equal to 0).

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

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

<figure><img src="image_153.png" /></figure>
<figure><img src="image_154.png" /></figure>

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

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

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

* Let $J$ be the first component down in $X$ and denote by $Z$ the number of components down. We have ($j \ge 1$):

$$ \mathbb{P}(J = j | Z \ge 1) = \frac{r_1 r_2 \cdots r_{j-1} (1-r_j)}{1-r} $$

* For row $m$ we sample from this conditional distribution obtaining some $j \in \{1, 2, \dots, E\}$, we set to 1 the first $j-1$ values, to 0 the $j$th, and we sample the rest according to their Binary a priori law, and independently. Then, we can evaluate $Y^{(m)}$.

* After this first round, we sample $M$ again, obtaining $m'$, and repeat the process, "virtually filling" rows $m+1, m+2, \dots, m+m'''$ of the table, etc.

* We can then prove that the estimator obtained this way (truncating the "virtual infinite table" to its first $N$ rows), is the standard one (in distribution).

* So the variance remains identical, but the cost in time is reduced. We performed a **time reduction**, not a variance one.

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

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

<figure><img src="image_160.png" /></figure>
<figure><img src="image_161.png" /></figure>

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

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

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

# Cost

* The standard implementation of the standard Monte Carlo estimator needs $O(NE)$ operations.

* After some algebra, using $\mathbb{E}(M) = (1-r)^{-1}$, the new implementation needs $O(N(1-r)E)$ operations.

* Dividing, the gain is

$$ \approx \frac{NE}{N(1-r)E} = \frac{1}{1-r}. $$

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

<figure><img src="image_166.png" /></figure>
<figure><img src="image_167.png" /></figure>

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

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

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

# Talk's content

1. The resilience metric

2. Monte Carlo standard and rare events

3. Back to the resilience

4. Conclusions

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

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

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

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_184.png" /></figure>
<figure><img src="image_185.png" /></figure>

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

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

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

Standard estimator of *Res*

* Call *NCC* the number of connected components of the underlying graph. Evaluating *NCC* on a given graph costs *O*(*E*) (a single DFS or BFS does the job), and measuring their sizes (in # of nodes) has no complexity overhead (with respect to *E*).

* Suppose a given graph has *ncc* connected components, with sizes $c_1, c_2, \dots, c_{ncc}$. Then, the # of communicating pairs in the graph is

$$ncp = \sum_{h=1}^{ncc} \binom{c_h}{2}.$$

* Estimating *Res* using the standard estimator $\widehat{Res}$ provides the confidence interval at 95% ($\widehat{Res} \pm 1.96 S$), where

$$S^2 = \frac{1}{N(N-1)} \sum_{n=1}^{N} NCP^{(n)} - \frac{1}{N-1} \sum_{n=1}^{N} \widehat{Res}^2.$$

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

<figure><img src="image_190.png" /></figure>
<figure><img src="image_191.png" /></figure>

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

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

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

In a nutshell: improvement

* We can improve the proposed implementation of the standard estimator $\hat{\mathrm{Res}}$ following the same approach.

* For instance, assume that the breadth $b$ of the graph$^1$ (whose evaluation is polynomial) is known. Instead of defining $F$ as the first row in the virtual table where $Z \ge 1$, we can use $Z \ge b$, increasing the gain.

* Another possibility: find a covering tree of the underlying graph with minimal weight, where the weights are multiplicative (the elementary reliabilities). This is again, a polynomial task. Then, redefine $F$ accordingly. We also tested this idea and the gains can be considerable.

* Previous idea can be extended to finding several covering trees.

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

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

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

<footnote>$^1$= the size of any mincut of minimal size.</footnote>
<figure><img src="image_198.png" /></figure>

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

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

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

In a nutshell: sensitivities

* Computing sensitivities can be more interesting for the engineers than the metrics itself.

* In a nutshell, the “virtual table” view allows to do this task with very little overhead, by means of the result that follows.

* Define

$$ \sigma_i = \frac{\partial Res}{\partial r_i} \quad \text{and} \quad \sigma_{s,t;i} = \frac{\partial R_{s,t}}{\partial r_i}. $$

* Denote, similarly as for usual reliability metrics,

$$ Res_i^c = Res(\mathcal{G} | X_i = 1) $$

(this is $\neq Res(\mathcal{G}_i^c)$ where $\mathcal{G}_i^c$ is the result of contracting $i$ in $\mathcal{G}$), and

$$ Res_i^d = Res(\mathcal{G} | X_i = 0) = Res(\mathcal{G}_i^d). $$

<figure><img src="image_202.png" /></figure>
<figure><img src="image_203.png" /></figure>

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

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

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

* Theorem 1: $\sigma_i = \frac{Res_i^c - Res}{1 - r_i} = \frac{Res - Res_i^d}{r_i}$.

* Theorem 2: The expression

$$ \hat{\sigma}_i = \frac{X_i - r_i}{r_i(1 - r_i)} NCP $$

defines an unbiased estimator of $\sigma_i$.

* This means that the computation of the gradient of Res comes almost for free following the “virtual table” approach.

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

<figure><img src="image_208.png" /></figure>
<figure><img src="image_209.png" /></figure>

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

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

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

## More metrics

* In the rare event case, we obviously have *Res* very close to $\binom{n}{2}$.

* A different way of having a deeper view of what happens in this case is to explore the situation where there is something broken, given the fact that we are using performability metrics here.

* We propose to look, for instance, at conditional metrics such as $E(NCP | NCC \ge 2)$.

* Another possible direction to look at is to count the number of pairs of nodes between which there are at least 2 edge-disjoint working paths, which we denote by *NCP2* here, and, for instance, to explore the conditional metric $E(NCP2 | NCC \ge 2)$.

* Common point with previous metrics? Their evaluation (and that of their gradients) are immediate using the virtual table implementation of the standard estimator (and the costs are always polynomial).

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

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

<figure><img src="image_215.png" /></figure>
<figure><img src="image_216.png" /></figure>

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

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

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

An example

To provide a few illustrations of previous results, let us consider the
following model:

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

**Figure:** A widely used Arpanet topology in network reliability, from the history of this famous communication network.

Consider the i.i.c. case (independent and identical components), with
common elementary reliabilities = p.

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

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

<figure><img src="image_223.png" /></figure>
<figure><img src="image_224.png" /></figure>

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

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

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

* We take $p = 0.999$.

* Using the breadth, here $b = 2$, the gain with respect to the standard estimation of *Res* was of several hundreds, varying with the implementation, using a library for some computations (numpy) or not, python or C, etc.

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

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

<figure><img src="image_230.png" /></figure>
<figure><img src="image_231.png" /></figure>

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

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

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

<figure><img src="image_235.png" /><figcaption>Figure: A covering tree on the Arpanet model.</figcaption></figure>

* Using this tree, we moved the gain up to some more hundreds (typically to 500 or 600).

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

<figure><img src="image_237.png" /></figure>
<figure><img src="image_238.png" /></figure>

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

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

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

Conditional metrics

* To get an idea of the discriminatory power of the conditional metrics, look at this table (for the Arpanet graph, the number of nodes is $n = 21$ and $\binom{n}{2} = 210$):

<table><caption>Table: Three metrics on the Arpanet, i.i.c. case (homogeneous links).</caption><thead><tr><th>p</th><th>0.91</th><th>0.95</th><th>0.99</th><th>0.995</th><th>0.999</th></tr></thead><tbody><tr><td>E(NCC)</td><td>1.251</td><td>1.073</td><td>1.0027</td><td>1.00066</td><td>1.000026</td></tr><tr><td>E(NCP) = Res</td><td>199.8</td><td>207.2</td><td>209.9</td><td>209.977</td><td>209.9991</td></tr><tr><td>E(NCP | NCC ≥ 2)</td><td>160.3</td><td>167.6</td><td>174.5</td><td>175.2</td><td>175.5</td></tr></tbody></table>

<figure><img src="image_242.png" /></figure>
<figure><img src="image_243.png" /></figure>

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

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

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

# Sensitivities

Consider this graph:

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

**Figure:** Two bridges connected by a “bridge” link. We assume i.i.c., with elementary reliability $p = 0.999$.

For instance,

<table><tr><td>edge</td><td>{1, 2}</td><td>{2, 3}</td><td>{4, 5}</td></tr><tr><td>sensitivity</td><td>7.01 10<sup>-3</sup></td><td>3.79 10<sup>-5</sup></td><td>16.0</td></tr></table>

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

<figure><img src="image_249.png" /></figure>
<figure><img src="image_250.png" /></figure>

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

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

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

# Talk's content

1. The resilience metric

2. Monte Carlo standard and rare events

3. Back to the resilience

4. Conclusions

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

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

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

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

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

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

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

<figure><img src="image_261.png" /></figure>
<figure><img src="image_262.png" /></figure>

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

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

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

Some conclusions:

* Interest in a performability viewpoint.

* Power of the “virtual table” approach, and the idea that the problem of the standard estimator in the rare event case concerns the combination time-variance, not the variance alone.

* The method presented here offers a good improvement on the classic one, but of course, recent techniques (e.g. the so-called Zero Variance IS) go much further in efficiency. The method here has the interest of allowing a direct analysis of many other quantities, mentioned below.

* Results on sensitivity analysis.

* Idea of conditional performability metrics.

Talk based on the chapter “*Network Reliability, Performability Metrics, Rare Events and Standard Monte Carlo*”, in “Advances in Modeling and Simulation – Festschrift for Pierre L’Ecuyer”, edited by Zdravko Botev, Alexander Keller, Christiane Lemieux and Bruno Tuffin, published by Springer, December 1st, 2022, DOI https://doi-org.passerelle.univ-rennes1.fr/10.1007/978-3-031-10193-9.

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

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

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