Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ICDCS.2014.56 | Distributed Computing Systems |
Keywords | DocType | ISSN |
computational complexity,computer network management,learning (artificial intelligence),optimisation,telecommunication network topology,NP-hard,RoMe,budget constraint,expected rank,failure distribution,link failure models,network element failures,optimization problem,probing cost,realistic network topologies,reinforcement learning algorithm,robust network tomography,state-of-art path selection algorithm,Network Analytics,Network Measurements,Network Monitoring | Conference | 1063-6927 |
Citations | PageRank | References |
10 | 0.50 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Srikar Tati | 1 | 13 | 0.88 |
| Simone Silvestri | 2 | 10 | 0.50 |
| He, T. | 3 | 10 | 0.50 |
| Thomas F. La Porta | 4 | 53 | 6.24 |