Diagnosing network states through intelligent probing

The methodology of probing is useful in fault localization, in periodic auditing of functionality of network elements, and in measuring the overall quality of network performance. Probes resulting in binary responses have been proposed in the literature to diagnose the up or down status of network nodes. A sharp upper bound is obtained for the probability that the most probable explanation (MPE) of the network states computed on the basis of probe results does not coincide with the true network state. This upper bound supplements a lower bound available in the literature. In considering the diagnosis of a set of priority nodes, two indices are introduced to assess the reliability of the probe results in the leaky noisy-AND model. These indices are useful in deciding whether or not the result of a binary probe should be followed up, by individual testing of the priority nodes. Some problems for future research are outlined.