K-terminal reliability in ring networks

The authors present a new formula for computing K-terminal reliability in a communication network whose stations and links (vertices and edges) form a network graph G having a ring topology, where K-terminal reliability is the probability R_K(G) that a subset of R specific terminal stations in G can communicate. This new formula is applied to three Fiber Distributed Data Interface (FDDI) ring-network topologies, and for each topology the authors derive closed-form polynomial expressions of R_K(G) in terms of the failure probabilities of links, network ports, and station common units. The authors define the concept of the K-minimal Eulerian circuit and use combinations of these circuits to obtain K-graphs and their resulting dominations, thus extending the use of K-graphs to ring networks in which data messages, tokens, or other control frames traverse operative network links with an Eulerian tour. 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 R_K(G). The authors show that trees have only one K-graph and that counter-rotating dual rings and rings of trees have at most 2K+1 noncanceled R-graphs. These results contribute the first closed-form polynomial R-terminal reliability expressions for the ring-of-trees topology. The results are useful in evaluating dependability, reliability, availability, or survivability of token rings and similar networks