Name
Abstract | ||
|---|---|---|
We consider the problem of placing the minimum number of monitors in a communication network with possible topology changes to identify additive link metrics from path metrics. The core of our solution is a suite of robust monitor placement algorithms with different performance-complexity tradeoffs that guarantee network identifiability for the multiple possible topologies. In particular, we show that the optimal (i.e., minimum) monitor placement is the solution to a generalized hitting set problem, where we provide a polynomial-time algorithm to construct the input. Although the optimal placement is NP-hard in general, we identify non-trivial special cases that can be solved efficiently. We further demonstrate how the proposed algorithms can be augmented to handle unpredictable topology changes and tradeoffs between monitor cost and adaptation cost. Our evaluations on mobility-induced dynamic topologies verify the effectiveness and robustness of the proposed algorithms. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/INFOCOM.2016.7524374 | IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications |
Keywords | Field | DocType |
network tomography,dynamic networks,communication network,robust monitor placement algorithms,performance-complexity tradeoffs,polynomial time algorithm,unpredictable topology | Telecommunications network,Suite,Identifiability,Computer science,Network topology,Robustness (computer science),Network tomography,Distributed computing | Conference |
ISSN | ISBN | Citations |
0743-166X | 978-1-4673-9954-8 | 6 |
PageRank | References | Authors |
0.44 | 17 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ting He | 1 | 716 | 44.82 |
| Liang Ma | 2 | 104 | 8.75 |
| Athanasios Gkelias | 3 | 162 | 13.88 |
| Kin K. Leung | 4 | 2463 | 183.60 |
| Swami, A. | 5 | 5105 | 566.62 |
| Don Towsley | 6 | 18693 | 1951.05 |