Network capability in localizing node failures via end-to-end path measurements

File Description SizeFormat 
1509.06333v1.pdfAccepted version386.85 kBAdobe PDFView/Open
Title: Network capability in localizing node failures via end-to-end path measurements
Authors: Ma, L
He, T
Swami, A
Towsley, D
Leung, KK
Item Type: Journal Article
Abstract: We investigate 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 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. We demonstrate how measures 1) and 2) proposed for quantifying failure localization capability can be used to evaluate the impact of various parameters, including topology, number of monitors, and probing mechanisms.
Issue Date: 18-Jul-2016
Date of Acceptance: 1-Jul-2016
ISSN: 1063-6692
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Start Page: 434
End Page: 450
Journal / Book Title: IEEE/ACM Transactions on Networking
Volume: 25
Issue: 1
Copyright Statement: © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Sponsor/Funder: IBM United Kingdom Ltd
Funder's Grant Number: PO4603106973
Keywords: Science & Technology
Computer Science, Hardware & Architecture
Computer Science, Theory & Methods
Engineering, Electrical & Electronic
Computer Science
Network tomography
failure localization
identifiability condition
maximum identifiability index
Networking & Telecommunications
0805 Distributed Computing
Publication Status: Published
Appears in Collections:Faculty of Engineering
Electrical and Electronic Engineering

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx