Loading...
Please wait, while we are loading the content...
Similar Documents
Node Failure Localization in Communication Networks via Network Tomography
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ma, Liang He, Ting Swami, Ananthram Towsley, Don Leung, Kin K. Lowe, Jessica |
| Copyright Year | 2014 |
| Abstract | We investigate the problem of localizing node failures in a communication network from end-to-end path measurements, under the assumption that a path behaves normally if and only if it does not contain any failed nodes. To uniquely localize node failures, the measurement paths must show different symptoms under different failure events, i.e., for any two distinct sets of failed nodes, there must be a measurement path traversing one and only one of them. This condition is, however, impractical to test for large networks due to the combinatorial numbers of paths and failure sets. Our first contribution is a characterization of this condition in terms of easily verifiable conditions on the network topology with given monitor placements under three families of probing mechanisms, which differ in whether measurement paths are (i) arbitrarily controllable, (ii) controllable but cyclefree, or (iii) uncontrollable (i.e., determined by the default routing protocol). Our second contribution is a characterization of the maximum identifiability of node failures, measured by the maximum number of simultaneous failures that can always be uniquely localized. Specifically, we bound the maximal identifiability from both the upper and the lower bounds which differ by at most one, and show that these bounds can be evaluated in polynomial time. Finally, we quantify the impact of the probing mechanism on the capability of node failure localization by numerically comparing the maximum identifiability under different probing mechanisms on both random and real network topologies. We observe that despite a higher implementation cost, probing along controllable paths can significantly improve a network’s capability to localize simultaneous node failures. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://researcher.watson.ibm.com/researcher/files/us-the/NodeFailureIdentifiability-AFM-long.pdf |
| Alternate Webpage(s) | http://researcher.watson.ibm.com/researcher/files/us-maliang/NodeFailureIdentifiability-long.pdf |
| Alternate Webpage(s) | http://researcher.watson.ibm.com/researcher/files/us-the/NodeFailureIdentifiability-AFM-long.pdf |
| Alternate Webpage(s) | http://researcher.ibm.com/researcher/files/us-maliang/NodeFailureIdentifiability-long.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
