Two terminal reliability

Con two terminal reliability, in italiano affidabilità di due nodi, si definisce la probabilità che due nodi (s,t) continuino a poter comunicare per un certo tempo t.

Diversi sono i metodi applicabili per il suo calcolo, e tutti vengono ripresi successivamente nella All terminal reliability.

State-Space Enumeration

Fig.1, modello della rete di esempio

Indubbiamente il metodo più semplice (nonché il meno efficiente, sicuramente, per l'applicazione a casi reali) per il calcolo dell'affidabilità della comunicazione tra due nodi consiste nell'enumerare tutte le possibili combinazioni di archi e considerando questi funzionanti o non funzionanti. Il risultato sarebbe dunque una tabella contenente combinazioni di archi nei loro diversi stati ed ognuna di queste rappresenterebbe un evento che, per definizione, è mutuamente esclusivo con ognuno degli altri eventi elencati.

Così definito lo spazio degli eventi, l'affidabilità risulta essere la probabilità che uno qualunque degli eventi che consento ad s e t di comunicare si verifichi, risultando nell'unione della probabilità che ogni evento interessato abbia luogo. Per chiarezza, riferendoci alla semplice rete rappresentata dal grafo in [Fig. 1], la corrispondente tabella di $2^{4}$ eventi sarebbe, intendendo con è l'arco non funzionante:

Tabella degli eventi riferita a Fig. 1

Come derivabile dalla tabella sopra riportata, il verificarsi di certi eventi porta d,c a non comunicare: essi sono, in particolare, [E5, E6, E8, … , E16], nei quali nessun percorso è possibile per portare un'informazione da d fino a c.

Essendo l'analisi indirizzata alla comunicazione tra i nodi c e d, è chiaro come un qualunque evento che escluda d, ossia uno qualunque in cui l'arco 4 fallisca, di fatto taglia la comunicazione a causa della topologia in cui la rete è stata pensata.

L'affidabilità è dunque semplicemente la somma della probabilità dell'unione di ogni evento che consente che la comunicazione si verifichi, dunque:

$R_{cd}=P(E_{1}+E_{2}+E_{3}+E_{4}+E_{7})\,$

ed essendo ogni evento mutuamente esclusivo con ogni altro, questa risulta essere la somma delle singole probabilità di ogni evento (poiché l'intersezione (vedi Principio di inclusione-esclusione) degli eventi in questo caso è nulla):

$R_{cd}=P(E_{1})+P(E_{2})+P(E_{3})+P(E_{4})+P(E_{7})\,$

Supponendo dunque che la probabilità di funzionamento di un arco (e quindi anche quella di rottura) sia la medesima per ognuno di essi, e fissandola a p=0,94 (q=1-0,94=0,06), sostituendo nella formula sopra indicata si ottiene

$R_{cd}=p^{4}+3qp^{3}+q^{2}p^{2}=0,94^{4}+3*0,06*0,94^{3}+0,06^{2}*0,94^{2}=0,93343504\,$

Sebbene il calcolo in questo caso sia relativamente semplice, sia a causa dell'esiguo numero di archi sia per la particolare tipologia della rete che di fatto ne semplifica lo spazio degli eventi positivi, è immediato comprendere come questo approccio sia del tutto inadeguato in una prospettiva in cui in esame ci sia una rete reale o anche semplicemente più complessa di questa. Già con soli 10 archi la casistica da analizzare comprenderebbe 1024 eventi, difficilmente gestibili con carta e penna. In una prospettiva di applicazione reale su una rete fisica, peraltro, il numero degli archi sarebbe indubbiamente molto più alto, portando la complessità (che in questo caso è esponenziale, poiché ci si trova ad analizzare $2^{e}$ eventi, rendendo il problema di complessità O($2^{e}$)) a livelli troppo elevati per una pratica realizzazione computazionale, anche se automatizzata.

Metodi con Cut/Tie Sets

Metodi con Cut e Tie Set

Un possibile metodo di riduzione della complessità rispetto al caso di analisi precedente è rappresentato dalla computazione dell'affidabilità sulla base di cut e tie sets minimi.

In un grafo, i tie set sono un gruppo di archi la cui presenza garantisce la connessione tra due nodi s, t. Per contro, un cut set è definito come un gruppo di archi che, se non presenti, di fatto impossibilitano qualunque connessione tra i due nodi in analisi. Entrambi si possono dire minimali se al loro interno non contengono alcun cut / tie set.

Nel caso l'analisi voglia vertire sui tie set, l'affidabilità è la probabilità che si verifichi l'unione dei tie set:

$R_{st}=P(T_{1}+T_{2}+..+T_{i})\,$

mentre per i cut set è:

$R_{st}=1-P(C_{1}+C_{2}+..+C_{l})\,$

La tabella dei Tie / Cut sets minimi per la coppia (d, c) nel grafo in [Fig.1] è:

Tabella degli eventi riferita a Fig. 1

Ancora una volta, data la semplicità della rete e la scarsità di collegamenti tra i nodi, la casistica non è poi così ampia. Normalmente sarebbe opportuno effettuare una scelta tra il set più conveniente, ma in questo caso la differenza è davvero minima in termini di calcolo. Per questo motivo, entrambi i casi verranno sviluppati, anche per avere una controprova della correttezza dei calcoli dell'altro e del primo metodo.

Iniziamo dai tie set [T1,T2]. Essi sono composti dagli archi 4;2 e 4;1;3: essendo tie sets, il metodo da utilizzare è

$R_{cd}=P(T_{1}+T_{2})\,$

$R_{cd}=P(42+413)\,$

$R_{cd}=P(42)+P(413)-P(1234)\,$

nuovamente, ipotizzando che tutti gli archi abbiano la stessa probabilità di funzionare (p=0,94):

$R_{cd}=p^{2}+p^{3}-p^{4}=0,93343504\,$

che ovviamente è lo stesso risultato ottenuto precedentemente utilizzando lo spazio degli eventi per il calcolo dell'affidabilità.

Un'ulteriore verifica è possibile rifacendo il calcolo mediante l'utilizzo dei cut set, andando quindi a sostituire questo caso nella formula

$R_{cd}=1-P(C_{1}+C_{2}+C_{3})$

$R_{cd}=1-P(4'+1'2'+2'3')$

$R_{cd}=1-[P(4')+P(1'2')+P(2'3')]-[P(1'2'4')+P(2'3'4')+P(1'2'3')]+[P(1'2'3'4')]$

$R_{cd}=1-[q+2*q^{2}]-[3*q^{3}]+[q^{4}]=0,93343504\,$

il quale, ancora una volta, corrisponde perfettamente al risultato precedentemente ottenuto con i tie set e mediante l'enumerazione degli eventi, confermandone la correttezza.

Nonostante il metodo sopra descritto sia più rapido rispetto all'enumerazione, poiché i casi da sviluppare sono i < e, con i il minore tra il numero di cue e tie set, ed e il numero di archi, resta il problema della complessità in network particolarmente complessi.

Infatti non è complicato da immaginare un grafo il cui i sia in realtà comunque troppo grande perché le $2^{i}$ combinazioni vengano analizzate. È inoltre da non dimenticare la complessità degli algoritmi per trovare i cut ed i tie set, che è di ordine polinomiale; in ogni caso, la complessità del problema del calcolo dell'affidabilità con questo metodo è dominata dalla complessità dell'inclusione-esclusione, che è appunto esponenziale [O($2^{i}$)].

Quel che a questo punto è possibile fare è accontentarsi di una precisione di calcolo minore, ma comunque molto realistica, appoggiati da un controllo della percentuale di errore che indica la bontà dell'approssimazione.

Questa approssimazione è possibile effettuarla in tre diversi modi:

• Eliminando i termini meno significativi dell'espansione dell'espressione dei cut/tie set
• Eliminando i cut/tie set meno significativi
• Utilizzando entrambe le approssimazioni precedenti.

Bibliografia

• Reliability of Computer Systems and Networks - Fault Tolerance, Analysis, and Design (Martin L. Shooman), ed. Team Fly

Voci correlate

• Network survivability
• All terminal reliability
• Network reliability