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.
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 {\displaystyle 2^{4}} eventi sarebbe, intendendo con è l'arco non funzionante:
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 c d = P ( E 1 + E 2 + E 3 + E 4 + E 7 ) {\displaystyle 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 c d = P ( E 1 ) + P ( E 2 ) + P ( E 3 ) + P ( E 4 ) + P ( E 7 ) {\displaystyle 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 c d = p 4 + 3 q p 3 + q 2 p 2 = 0 , 94 4 + 3 ∗ 0 , 06 ∗ 0 , 94 3 + 0 , 06 2 ∗ 0 , 94 2 = 0 , 93343504 {\displaystyle 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 {\displaystyle 2^{e}} eventi, rendendo il problema di complessità O( 2 e {\displaystyle 2^{e}} )) a livelli troppo elevati per una pratica realizzazione computazionale, anche se automatizzata.
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 s t = P ( T 1 + T 2 + . . + T i ) {\displaystyle R_{st}=P(T_{1}+T_{2}+..+T_{i})\,}
mentre per i cut set è:
R s t = 1 − P ( C 1 + C 2 + . . + C l ) {\displaystyle 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] è:
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 c d = P ( T 1 + T 2 ) {\displaystyle R_{cd}=P(T_{1}+T_{2})\,}
R c d = P ( 42 + 413 ) {\displaystyle R_{cd}=P(42+413)\,}
R c d = P ( 42 ) + P ( 413 ) − P ( 1234 ) {\displaystyle R_{cd}=P(42)+P(413)-P(1234)\,}
nuovamente, ipotizzando che tutti gli archi abbiano la stessa probabilità di funzionare (p=0,94):
R c d = p 2 + p 3 − p 4 = 0 , 93343504 {\displaystyle 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 c d = 1 − P ( C 1 + C 2 + C 3 ) {\displaystyle R_{cd}=1-P(C_{1}+C_{2}+C_{3})}
R c d = 1 − P ( 4 ′ + 1 ′ 2 ′ + 2 ′ 3 ′ ) {\displaystyle R_{cd}=1-P(4'+1'2'+2'3')}
R c d = 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 ′ ) ] {\displaystyle 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 c d = 1 − [ q + 2 ∗ q 2 ] − [ 3 ∗ q 3 ] + [ q 4 ] = 0 , 93343504 {\displaystyle 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 {\displaystyle 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 {\displaystyle 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:
