Robust monitor placement for network tomography in dynamic networks

File Description SizeFormat 
2016_12_Tomography_Ting_He.pdfAccepted version468.27 kBAdobe PDFView/Open
Title: Robust monitor placement for network tomography in dynamic networks
Authors: He, T
Gkelias, A
Ma, L
Leung, KK
Swami, A
Towsley, D
Item Type: Conference Paper
Abstract: We consider the problem of placing the minimum number of monitors in a dynamic network to identify additive link metrics from path metrics measured along cycle-free pa ths between monitors. Our goal is robust monitor placement, i.e ., the same set of monitors can maintain network identifiabilit y under topology changes. Our main contribution is a set of mon i- tor placement algorithms with different performance-comp lexity tradeoffs that can simultaneously identify multiple topol ogies occurring during the network lifetime. In particular, we sh ow that the optimal monitor placement is the solution to a generaliz ed hitting set problem, for which we provide a polynomial-time algo- rithm to construct the input and a greedy algorithm to select the monitors with logarithmic approximation. Although the opt imal placement is NP-hard in general, we identify non-trivial sp ecial cases that can be solved efficiently. Our secondary contribu tion is a dynamic triconnected decomposition algorithm to compu te the input needed by the monitor placement algorithms, which is the first such algorithm that can handle edge deletions. Ou r evaluations on mobility-induced dynamic topologies verif y the efficiency and the robustness of the proposed algorithms.
Issue Date: 28-Jul-2016
Date of Acceptance: 10-Apr-2016
DOI: https;//
ISSN: 1063-6692
Publisher: IEEE
Journal / Book Title: INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, IEEE
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
Conference Name: 35th IEEE Annual International Conference on Computer Communications (IEEE INFOCOM)
Keywords: Science & Technology
Computer Science, Information Systems
Computer Science
0805 Distributed Computing
Networking & Telecommunications
Publication Status: Published
Start Date: 2016-04-10
Finish Date: 2016-04-14
Conference Place: San Francisco, CA, USA
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