Networking and Telecommunications Group
Abstract
Monitoring end-to-end paths in an overlay network is essential for evaluating end system performance and for troubleshooting
anomalous behavior. However, conducting measurements between all pairs of overlay nodes can be cumbersome
and expensive, especially in a large network. In this paper, we take a different approach and explore an additional
degree of freedom overlay measurements, in order to minimize the total cost of monitoring the network. We formulate an optimization problem that when solved identes the optimal set of native
and overlay links to monitor, and a feasible sequence of
arithmetic operations to perform for inferring characteristics
of the overlay links that are not monitored directly. We observe
that allowing native layer measurements consistently
reduces monitoring cost in cases where the monitoring cost
for an all-overlay solution is greater than the cost for an all-native
solution. Furthermore, we classify the optimal solution
for various types of topologies and investigate how different
topological properties affect the best monitoring strategy.