Reliability of failsoft and fault-tolerant ring networks

A unified formula is presented to solve the previously open problem of obtaining closed-form polynomial expressions for K-terminal reliability in ring topology computer communication networks with directed graph G. K-terminal reliability is the probability {dollar}Rsb{lcub}K{rcub}(G){dollar} that a subset of K specific terminal stations in G can communicate. We define the concept of K-minimal Eulerian circuit and use combinations of these circuits to obtain K-graphs and their resulting dominations. A K-graph is a subgraph of G from which terms in a polynomial reliability expression can be determined; the dominations are coefficients of the reliability terms. Distinct K-graphs having a nonzero sum of dominations are called noncanceled K-graphs and correspond exactly to terms in closed-form polynomial expressions of {dollar}Rsb{lcub}K{rcub}(G){dollar}.; Four ring network topologies with and without nodal bypass switches are considered. These topologies are (1) counterrotating dual rings, (2) tree rings, (3) rings of trees, and (4) dual rings with dual-homed stations. We define a station addressing convention that facilitates calculation of the numbers of links and intermediate stations connecting the K stations of interest in K-graphs with wiring concentrators that may each have differing numbers of ports. We then derive and present closed-form polynomial expressions for both K-terminal reliability and terminal-pair reliability for the first three topologies under both heterogeneous (distinct for each component) and homogeneous (the same for like components) failure probabilities. These K-terminal reliability expressions can be evaluated in worst case time O({dollar}Nsp4{dollar}) for heterogeneous failure probabilities and time O(N) for homogeneous failure probabilities. It is shown that deriving {dollar}Rsb{lcub}K{rcub}{dollar}(G) for the dual ring with dual-homed stations is NP-hard. However, closed-form terminal-pair reliability expressions are derived for the single-level dual-homed network.; Furthermore, both worst case terminal-pair reliability expressions and mean time to failure expressions are derived and presented for all four topologies. The utility of these results is illustrated by evaluating the expressions parametrically under various scenarios and by making reliability comparisons.; The results are applicable to all token rings and other ring networks that operate using fixed routes for network traffic between the occurrence of reconfiguration events such as startup or fault recovery.