Two terminal reliability

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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[modifica | modifica wikitesto]

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

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

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

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 eventi, rendendo il problema di complessità O()) a livelli troppo elevati per una pratica realizzazione computazionale, anche se automatizzata.

Metodi con Cut/Tie Sets[modifica | modifica wikitesto]

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

mentre per i cut set è:

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 è

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

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

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 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()].

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[modifica | modifica wikitesto]

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

Voci correlate[modifica | modifica wikitesto]