High Impact Factor : 4.396 icon | Submit Manuscript Online icon |

Capability of Network in Localizing Node Failures via Scalable landmark End-to-End Path Measurements


Chokkapu Narayanarao , Raghu Institute of Technology; P Vineela, Raghu Institute of Technology; G Poojitha, Raghu Institute of Technology; G Nikitha Sai, Raghu Institute of Technology; A R L Santosh, Raghu Institute of Technology


Identifiability Condition, Maximum Identifiability Index, Network Tomography, Failure localization


This Paper aims to examine the capability of localizing node failures in communication networks from binary states (normal/ failed) of end-to-end paths. Given a set of nodes of interest, uniquely localizing failures within this set requires that different observable path states associate with different node failure events. However, this condition is difficult to test on large networks due to the need to enumerate all possible node failures. Our primary goal 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 the maximum number of failures (anywhere in the network) such that failures within a given node set can be uniquely localized, and the largest node set within which failures can be uniquely localized under a given bound on the total number of failures. Both measures in can be converted into functions of a per-node property, which can be computed efficiently based on the above sufficient/necessary conditions. We demonstrate how measures can be proposed for quantifying failure localization capability can be used to evaluate the impact of various parameters, including topology, number of monitors, and probing mechanisms.

Other Details

Paper ID: IJSRDV5I120105
Published in: Volume : 5, Issue : 12
Publication Date: 01/03/2018
Page(s): 207-208

Article Preview

Download Article