Active Probing Strategies for Problem Diagnosis in Distributed Systems

1 Introduction

Accurate diagnosis in a complex, multi-component system by making inferences based on the results of various tests and measurements is a common practical problem. Devel­ oping cost-effective techniques for diagnosis in such systems requires that high accuracy be achieved with a small number of tests. In this work we present a generic approach to this problem and apply it specifically to the area of distributed systems management.

The key component of our approach is an "active" mea­ surement approach, called probing. A probe is a test transac­ tion whose outcome depends on some of the system's com­ ponents. Diagnosis is performed by appropriately selecting the probes and analyzing the results. For distributed systems, a probe is a program that executes on a particular machine (called a probe station) by sending a command or transaction · to a server or network element and measuring the response. The ping program is probably the most popular probing tool that can be used to detect network availability. Other probing tools, such as IBM's EPP technology, provide more sophisti­ cated, application-level probes. For example, probes can be sent in the form of test e-mail messages, web-access requests, and so on.

Previous work studied the problem of probe-selection [Brodie eta/., 2001], [Ozmutlu et al., 2002] and efficient di­ agnosis from probe outcomes using approximate inference in Bayesian networks [Rish eta/., 2002], but the NP-hardness of probe-selection and the idea of active probing were not con­ sidered there.

2 Pre-Planned Probing

In pre-planned probing, given an initial set of probes, we want to compute the smallest subset of probes such that each sys­ tem state will produce a different set of probe outcomes, al­ lowing the state to be uniquely determined.

Proposition 1 Probe-set selection is NP-hard.

Proof: The proof is via a reduction from 3-Dimensional Matching (defined in [Garey and Johnson, 1979]). Details can be found in [Brodie et a/., 2003].

We implemented two approximation algorithms for pre­ planned probing - greedy (quadratic) search and subtractive (linear) search. Greedy search starts with the empty set and adds at each step the "best" of the remaining probes - the probe which maximizes the information gained about the sys­ tem state. Computational complexity is quadratic in the size of the initial probe set. Subtractive search starts with the com­ plete set of available probes, considers each one in tum, and discards it if it is not needed. Computational complexity is linear in the size of the initial probe set. Neither algorithm is optimal in general - empirical results are provided below.

3 Active Probing

Active probing, allows the selection oflater probes to depend on the results of earlier probes. An active probing system is outlined in Figure 1. Probe-stations issue probes which tra­ verse different parts of the network. The results of the probes are analyzed to infer what problems might be occurring. If additional information is needed in order to locate the prob­ lem, the "most-informative" probe, which provides the largest information gain about the true state of the system, is com­ puted and sent. When additional probe results are received further inferences are made, and the process repeats until the fault is localized. The algorithm is described in Figure 2.

Active probing allows fewer probes to be used than if the entire probe set has to be pre-planned, though more complex inferential machinery is needed to support it.

4 Results

Simulation results, using randomly generated networks, are shown in Figure 3a (small networks) and Figure 3b (large net­ works, where finding the true minimum is impractical). The approximation algorithms for finding the smallest probe set perform well and are close to the true minimum set found by exhaustive search. It is also clear that active probing consid­ erably reduces the size of the probe set when compared with pre-planned, or "passive", probing.

In Figure 4, we report the results on a real network. This network, supporting e-business applications, includes many servers and routers, and its performance and availability de­ pend on a number of software components. A set of29 probes was manually selected by an expert. Exhaustive search shows that the minimum number of probes is actually only 24 probes, a saving of 17%. Greedy search returned 24 probes, while subtractive search found 25 probes. For active probing, Figure 3c shows the number of probes needed for localiza­ tion for each of the different single faults. The number of probes needed never exceeds 16 probes and averaged only 7.5 probes, a large improvement over the 24 probes used by pre-planned probing.

(b) Large Networks (simulations)

Figure 4: Active probing averages 7.5 probes in a real appli­ cation where pre-planned probing requires 24 probes.