~srini

/Research

/Students

/Publications

/Sponsors

/Teaching

/Misc

Fault localization using monitoring cycles and paths

Given the location of monitoring stations, the goal is to compute paths and cycles (that start and end at monitoring stations), such that every link and/or SRLG failure results the failure of a unique combination of cycles/paths. The figure shows an example network and the cycles established. Table 1 shows the set of cycles affected by single failures.

Figure 1. Example network with three cycles established.

Table 1. Cycles affected by links.

Figure 2 shows an example network with two SRLG failures, in addition to single link failure, along with four establsihed cycles. Table 2 shows the set of cycles affected by single link failures and SRLG failures. Obsersve that each failure scenario results in a unique set of cycles to fail.

Figure 2. Example network with four cycles established to localize all single link failures and two SRLG failures.

 

Table 2. Cycles affected by all single link failures and two SRLG failures.

In the INFOCOM 2008 paper, we also derive the necessary and sufficient conditions on the placement of monitors along with computing the minimum number of monitors required to localize all failures uniquely. Result: To uniquely localize all possible failures involving up to T links, every k connected component with degree T+1 or less must have a monitor, for k = 1, 2, 3, ..., T+2.

Consider the example network shown below. The goal is to identify how many monitoring stations are needed; and where they need to be placed, in order to uniquely localize all single-link failures (T= 1). First, we decompose the network into three-connected components (as in Figure 3a). Every component with degree two or less must have a monitor. If a component has more than one node, select a random node from the component and assign it as a monitoring station. Now, decompose the network into two-connected components (as shown in Figure 3b). If a component with degree two or less does not already have a monitor, then select a node from the component at random and assign it as a monitor. Figure 3b shows the final placement of monitors (marked with red circles).

(a) Decomposition into 3-connected components.
(b) Decomposition into 2-connected components.
Figure 3. Placement of monitors by decomposing the network into k-connected components, starting from K =T+2 until 2, where T denotes the number of simultaneous link failures. At any step, a component that has degree T+1 or less requires a monitor inside it.