The Fault-Finding Capacity of the Cable Network When Measured Along Complete Paths



We look into whether or not it is possible to find the exact location of a broken node in a communication network by using the binary state (normal or failed) of each link in the chain. To find out where failures are in a group of nodes of interest, it is necessary to link the different states of the routes to the different failures at the nodes. Due to the large number of possible node failures that need to be listed, it may be hard to check this condition on large networks. The first important thing we've added is a set of criteria that are both enough and necessary for testing in polynomial time whether or not a set of nodes has a limited number of failures. As part of our requirements, we take into account not only the architecture of the network but also the positioning of the monitors. We look at three different types of probing methods. Each one is different depending on the nature of the measurement paths, which can be random, controlled but not cycle-free, or uncontrolled (depending on the default routing protocol). Our second contribution is an analysis of the greatest number of failures (anywhere in the network) for which failures within a particular node set can be uniquely localized and the largest node set within which failures can be uniquely localized under a given constraint on the overall number of failures in the network. Both of these results are based on the fact that failures can be uniquely localized only if there is a constraint on the overall number of failures. When translated into functions of a per-node attribute, the sufficient and necessary conditions that came before them make it possible for an efficient calculation of both measurements.


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.

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.

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

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.

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.

S. Zarifzadeh, M. Gowdagere, and C. Dovrolis, “Range tomography: Combining the practicality of Boolean tomography with the resolution of analog tomography,” in Proc. ACM IMC, 2012, pp. 385–398.

A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C.-N. Chuah, and C. Diot, “Characterization of failures in an IP backbone,” in Proc. 23rd IEEE INFOCOM, Mar. 2004, pp. 2307–2317.

N. Duffield, “Simple network performance tomography,” in Proc. 3rd ACM IMC, 2003, pp. 210–215.

N. Duffield, “Network tomography of binary network performance characteristics,” IEEE Trans. Inf. Theory, vol. 52, no. 12, pp. 5373–5388, Dec. 2006.

H. Zeng, P. Kazemian, G. Varghese, and N. McKeown, “Automatic test packet generation,” in Proc. ACM CoNEXT, 2012, pp. 241–252.

Full Text: PDF


  • There are currently no refbacks.

Copyright © 2012 - 2023, All rights reserved.|

Creative Commons License
International Journal of Innovative Technology and Research is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJITR , Permissions beyond the scope of this license may be available at