Fault Diagnosis in IP Networks via Noiseless Multicast Probing

Newtork tomography using multicast-based probing has been the focus of considerable research activity. Estimating probability distributions of performance measures associated with individual network elements from end-to-end measurements can be rather difficult, and typically requires cumbersome mathematical analysis. However, very often, one's interest is rather limited: The end-to-end measurements indicate a problem and one is interested in identifying the most likely cuase of that problem. It is this problem that we address in this paper. 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 pert of test strategies for network fault diagnosis. These procedures exploit the underlying structure of the multicats tree and are significantly more efficient than generic computational procedures for probablistic interference.