Network Tomography Based on Adaptive Measurements in Probabilistic Environments

We discuss network tomography in stochastic environments. In real-world communication networks, routing may exhibit stochastic behavior due to load balancing mechanisms and other factors, and the states of network components, such as links, may fluctuate. In such environments, identifying the internal state of the network from end-to-end measurements typically requires a huge number of measurements. To overcome this difficulty, we propose a network tomography method that efficiently narrows down the state with a limited number of measurements by repeatedly updating the posterior information of the network state. In our method, we introduce the mutual information as an indicator of the effectiveness of the measurement. This allows us to design a combination of measurement paths that is critically effective for state identification, thereby significantly reducing redundant measurements that would generate excessive costs. We show that our method theoretically guarantees the approximation ratio <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1-1/\mathrm {e})$ </tex-math></inline-formula> on the basis of submodularity analysis. Numerical evaluations show that our method can identify network states with far fewer measurements than existing methods.