TY - GEN
T1 - Robust network tomography in the presence of failures
AU - Tati, S.
AU - Silvestri, S.
AU - He, T.
AU - Porta, T. La
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/8/29
Y1 - 2014/8/29
N2 - In this paper, we study the problem of selecting paths to improve the performance of network tomography applications in the presence of network element failures. We model the robustness of paths in network tomography by a metric called expected rank. We formulate an optimization problem to cover two complementary performance metrics: robustness and probing cost. The problem aims at maximizing the expected rank under a budget constraint on the probing cost. We prove that the problem is NP-Hard. Under the assumption that the failure distribution is known, we propose an algorithm called RoMe with guaranteed approximation ratio. Moreover, since evaluating the expected rank is generally hard, we provide a bound which can be evaluated efficiently. We also consider the case in which the failure distribution is not known, and propose a reinforcement learning algorithm to solve our optimization problem, using RoMe as a subroutine. We run a wide range of simulations under realistic network topologies and link failure models to evaluate our solution against a state-of-the-art path selection algorithm. Results show that our approaches provide significant improvements in the performance of network tomography applications under failures.
AB - In this paper, we study the problem of selecting paths to improve the performance of network tomography applications in the presence of network element failures. We model the robustness of paths in network tomography by a metric called expected rank. We formulate an optimization problem to cover two complementary performance metrics: robustness and probing cost. The problem aims at maximizing the expected rank under a budget constraint on the probing cost. We prove that the problem is NP-Hard. Under the assumption that the failure distribution is known, we propose an algorithm called RoMe with guaranteed approximation ratio. Moreover, since evaluating the expected rank is generally hard, we provide a bound which can be evaluated efficiently. We also consider the case in which the failure distribution is not known, and propose a reinforcement learning algorithm to solve our optimization problem, using RoMe as a subroutine. We run a wide range of simulations under realistic network topologies and link failure models to evaluate our solution against a state-of-the-art path selection algorithm. Results show that our approaches provide significant improvements in the performance of network tomography applications under failures.
UR - http://www.scopus.com/inward/record.url?scp=84907764717&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84907764717&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2014.56
DO - 10.1109/ICDCS.2014.56
M3 - Conference contribution
AN - SCOPUS:84907764717
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 481
EP - 492
BT - Proceedings - International Conference on Distributed Computing Systems
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014
Y2 - 30 June 2014 through 3 July 2014
ER -