Fault Diagnosis in IP Networks via Noiseless Multicast Probing

In this paper, we address the problem of fault diagnosis using multicast-based probing. Specifically, we introduce a disjunctive fault model for multicast-based probing wherein a receiver probe records a faulty measurement if and only if at least one of its ancestor nodes is in a faulty state. Using this fault model, we derive key results concerning the most probable fault scenario and the most likely fault given the observed probe values. These results provide a basis for efficient computational procedures to determine the nodes that are most likely to have been in a faulty state, and can be used as part of test strategies for network fault diagnosis.. These procedures exploit the underlying structure of the multicast tree and are significantly more efficient than generic computational procedures for probabilistic inference.