This condition is difficult to test on large networks due to the need to enumerate all possible node failures. Our first contribution is a set of sufficient/necessary conditions for identifying a bounded number of failures within an arbitrary node set that can be tested in polynomial time. In addition to network topology and locations of monitors, our conditions also incorporate constraints imposed by the probing mechanism used. We consider three probing mechanisms that differ according to whether measurement paths are: (i) arbitrarily controllable; (ii) controllable but cycle-free; or (iii) uncontrollable (determined by the default routing protocol). Our second contribution is to quantify the capability of failure localization through: 1) the maximum number of failures (anywhere in the network) such that failures within a given node set can be uniquely localized and 2) the largest node set within which failures can be uniquely localized under a given bound on the total number of failures. Both measures in 1) and 2) can be converted into the functions of a per-node property, which can be computed efficiently based on the above sufficient/necessary conditions.




Existing work can be broadly classified into single failure localization and multiple failure localization. Single failure localization assumes that multiple simultaneous failures happen with negligible probability. Under this assumption,  and propose efficient algorithms for monitor placement such that any single failure can be detected and localized. To improve the resolution in characterizing failures, range tomography in  not only localizes the failure, but also estimates its severity (e.g., congestion level).




Multiple failure localization faces inherent uncertainty. Most existing works address this uncertainty by attempting to find the minimum set of network elements whose failures explain the observed path states.

Under the assumption that failures are low-probability events, this approach generates the most probable failure set among all possibilities.




We propose efficient testing conditions and algorithms to quantify the capability of localizing node failures in the entire network; however, we did not consider the case that even if some node states cannot be uniquely determined, we may still be able to unambiguously determine the states of some other nodes. 

We thus investigate the relationships between the capability of localizing node failures and explicit network properties such as topology, placement of monitors, probing mechanism, and nodes of interest, with focus on developing efficient algorithms to characterize the capability under given settings.



A proposes a two stage solution which first estimates the failure (loss rate above threshold) probabilities of different links and then infers the most likely failure set for subsequent measurements. 

By augmenting path measurements with (partially) available control plane information (e.g., routing messages),  and  propose a greedy heuristic for troubleshooting network unreachability in multi-AS (Autonomous System) networks that has better accuracy than benchmarks using only path measurements.




Evaluations on random and real network topologies showed that probing mechanisms that allow monitors to control the routing of probes have significantly better capability to uniquely localize failures.




Ford−Fulkerson algorithm

Our key observation is that requiring each connected component in G−V _ that contains a node in S to have a monitor is equivalent to requiring each such component in G −M − V _

(i.e., after removing all monitors) to contain a neighbor of a monitor. Thus, if we extend G − M by adding a virtual monitor m_ and virtual links connecting m_ and all neighbors

of monitors to obtain an auxiliary graph G∗ := G − M +


{m_}, N(M)





System : Pentium IV 2.4 GHz.

Hard Disk                  : 40 GB.

Floppy Drive : 1.44 Mb.

Monitor             : 15 VGA Colour.

Mouse : Logitech.

Ram           : 2 Gb.




Operating system : Windows XP/7.

Coding Language :,

Tool                 : Visual Studio 2010

Database                : SQL SERVER 2008




[1] R. R. Kompella, J. Yates, A. Greenberg, and A. C. Snoeren, “Detection and localization of network black holes,” in Proc. 26th IEEE INFOCOM, May 2007, pp. 2180–2188.

[2] A. Coates, A. O. Hero, III, R. Nowak, and B. Yu, “Internet tomography,” IEEE Signal Process. Mag., vol. 19, no. 3, pp. 47–65, May 2002.

[3] D. Ghita, C. Karakus, K. Argyraki, and P. Thiran, “Shifting network tomography toward a practical goal,” in Proc. ACM CoNEXT, 2011,Art. no. 24.

[4] Y. Bejerano and R. Rastogi, “Robust monitoring of link delays and faults in IP networks,” in Proc. 22nd IEEE INFOCOM, Mar./Apr. 2003, pp. 134–144.

[5] J. D. Horton and A. López-Ortiz, “On the number of distributed measurement points for network tomography,” in Proc. 3rd ACM IMC,2003, pp. 204–209.


Leave a comment