Robust monitor placement for network tomography in dynamic networks

摘要

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.