THE EXPECTED NUMBER OF PAIRS OF CONNECTED NODES - PAIR-CONNECTED RELIABILITY

To date, the majority of researchers studying reliability and survivab ility in communication networks have been concerned either with the gl obal connectivity of a probabilistic network or the probability that t wo specified nodes s and t are connected. Several other reliability me asures have been proposed, but they receive comparatively little atten tion- We introduce here a general formula that encompasses the various reliability/survivability measures in the literature, and it makes cl ear the probabilistic rating of component failure and the ''penalty fu nction'' aspect of measuring the amount of disruption that is created by the failure of certain elements. Each instance of the general formu la can be interpreted as the expected value of a random variable. In p articular, global connectivity and two-terminal connectivity are insta nces for which the random variable is an indicator variable (taking on ly zero-one values). This probablistic formulation suggests a whole fa mily of reliability/survivability measures, with what we have called t he ''pair-connected'' measure being the expected value of a sum of ind icator variables. We present many introductory results concerning this pair-connected reliability.