Network Performability, Rare Events and Standard
Monte Carlo

Gerardo Rubino

► To cite this version:

Gerardo Rubino. Network Performability, Rare Events and Standard Monte Carlo. LACIAM 2023 - First Latin American Congress on Industrial and Applied Mathematics, Jan 2023, Rio De Janeiro, Brazil. pp.1-33. hal-04381155

HAL Id: hal-04381155

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

Submitted on 9 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_1.png" /></figure>

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

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

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

# Network Performability, Rare Events and Standard Monte Carlo

G. Rubino, Inria, Rennes, France

Rio de Janeiro, February 1, 2023

Laciam'23

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

<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>

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_12.png" /></figure>

<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>

# 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_18.png" /></figure>

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

<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>

# 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, its performance*).

* 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_34.png" /></figure>

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

<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>

* 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*<sub>*i*</sub> is the probability that it works and 1 - *r*<sub>*i*</sub> is the probability that it doesn't, behaving as absent from the graph. This means a **binary world**.

* Classic reliability metrics 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?
Consider $R_{\text{all}}$. Instead of using this metric, we can work with the number of pairs of nodes that can communicate (the # of pairs of nodes having a working path between its 2 components).

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

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

<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>

# Resilience

* Let NCP = number of pairs of nodes that can communicate in G.

* The resilience Res of the model is then

$$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), $\le 1 + \binom{n}{2}$ (from 0 to $\binom{n}{2}$) if there are n nodes in the model.

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

<figure><img src="image_49.png" /></figure>
<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>

## Some properties of resilience

* Observe first that $0 \le NCP \le \binom{n}{2} = \frac{n(n-1)}{2}$. Then,

* $P(NCP = 0) = \prod_{\text{all edge } i}(1 - r_i)$,

* $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_54.png" /></figure>

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

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

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

<figure><img src="image_59.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_60.png" /></figure>
<figure><img src="image_61.png" /></figure>

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

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

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

# Example: the bridge topology

<figure><img src="image_65.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_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>

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

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

* Homogeneous case.

* Using conditioning, 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{Res scaled}_n = \frac{2r[n(1-r) - (1-r^n)]}{n(n-1)(1-r)^2}. $$

<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>

<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>

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

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

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

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

* Homogeneous case.

* Using using series-parallel formulas, we obtain (the formula 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,

$$ResScaled_n = \frac{2r(1-r^{n-1})}{(n-1)(1-r)} - r^n.$$

<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>

<figure><img src="image_91.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_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>

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 $\mathbb{P}(X_i = 1) = r_i$ and $\mathbb{P}(Y = 1) = 1 - R = \gamma$.

* 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_99.png" /></figure>

<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>

* This works fine if $\gamma$ is not 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 always 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_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>

# A specific implementation

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

* first, we build a table with $N$ rows and $E+1$ columns (think $N \gg 1$);

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

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

* the estimation $\tilde{Y}_N$ of $R$ can then be computed "at the end" (nothing changed so far).

<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>

<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>0</td><td></td><td>1</td></tr><tr><td>...</td><td></td><td></td><td>...</td><td></td><td>...</td></tr><tr><td>N</td><td>1</td><td>1</td><td>1</td><td>...</td><td>1</td></tr></tbody></table>

<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>

# Remarks

* Consider the case of $r_i \approx 1$ for all $i$, and thus $R \approx 1$ as well, so, $\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)$, $m \ge 1$, $r = r_1 \cdots r_E$.

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

<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>

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 (one $X_i$ equal to 0).

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

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

<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>

* 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. Last, we compute $Y^{(m)}$ to fill column $E+1$.

* Then, we sample $M$ again, obtaining $m'$, and repeat the process, "virtually filling" rows $m+1, m+2, \dots, m+m''$, etc.

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

* 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_136.png" /></figure>

<figure><img src="image_137.png" /></figure>
<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>

Cost

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

* After some algebra, using $\mathbb{E}(M) = (1-r)^{-1}$, 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_142.png" /></figure>

<figure><img src="image_143.png" /></figure>
<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>

# 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_148.png" /></figure>

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

<figure><img src="image_150.png" /></figure>
<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>

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}.$$

* The cost of this evaluation is then $O(E)$.

* 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_155.png" /></figure>

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

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

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

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

In a nutshell: improvement

* We can *improve* the proposed implementation of the standard estimator *Res* following the same approach.

* For instance, assume that the breadth *b* of the graph (whose evaluation is polynomial) is known. Instead of defining *F* as the first row in the virtual table where *Z* ≥ 1, we can use *Z* ≥ *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_161.png" /></figure>

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

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

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

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

<figure><img src="image_167.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 is ideal to do this task, with minimal overhead, by means of a result presented here.

* 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 the reliability metrics,

$$Res_i^c = Res(\mathcal{G} | X_i = 1) \quad (\neq Res(\mathcal{G}_i^c) \text{ if the graph is } \mathcal{G})$$

and

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

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

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

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

<figure><img src="image_172.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_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>

## 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.

<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>

An example

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

<figure><img src="image_186.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_187.png" /></figure>

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

<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>

* 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_194.png" /></figure>

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

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

<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" /><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_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>

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

<figure><img src="image_208.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_209.png" /></figure>
<figure><img src="image_210.png" /></figure>

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

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

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

# Sensitivities

Consider this graph:

<figure><img src="image_214.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_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>

<figure><img src="image_220.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_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>
<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>

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, other recent techniques (e.g. the so-called Zero Variance IS) go further in efficiency. The method here has the interest of allowing direct analysis of many other quantities, mentioned below.

* Results on sensitivity analysis.

* Idea of conditional performability metrics.

Talk based on my 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_232.png" /></figure>

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

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