In this section
@article{He:2017:10.1109/TNET.2016.2642185,
author = {He, T and Gkelias, A and Ma, L and Leung, KK and Swami, A and Towsley, D},
doi = {10.1109/TNET.2016.2642185},
journal = {IEEE/ACM Transactions on Networking},
pages = {1732--1745},
title = {Robust and efficient monitor placement for network tomography in dynamic networks},
url = {http://dx.doi.org/10.1109/TNET.2016.2642185},
volume = {25},
year = {2017}
}
TY - JOUR
AB - 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 paths between monitors. Our goal is robust monitor placement, i.e., the same set of monitors can maintain network identifiability under topology changes. Our main contribution is a set of monitor placement algorithms with different performance-complexity tradeoffs that can simultaneously identify multiple topologies occurring during the network lifetime. In particular, we show that the optimal monitor placement is the solution to a generalized hitting set problem, for which we provide a polynomial-time algorithm to construct the input and a greedy algorithm to select the monitors with logarithmic approximation. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. Our secondary contribution is a dynamic triconnected decomposition algorithm to compute the input needed by the monitor placement algorithms, which is the first such algorithm that can handle edge deletions. Our evaluations on mobility-induced dynamic topologies verify the efficiency and the robustness of the proposed algorithms.
AU - He,T
AU - Gkelias,A
AU - Ma,L
AU - Leung,KK
AU - Swami,A
AU - Towsley,D
DO - 10.1109/TNET.2016.2642185
EP - 1745
PY - 2017///
SN - 1063-6692
SP - 1732
TI - Robust and efficient monitor placement for network tomography in dynamic networks
T2 - IEEE/ACM Transactions on Networking
UR - http://dx.doi.org/10.1109/TNET.2016.2642185
UR - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000403825400033&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
VL - 25
ER -
