2 - Fundamental Conditions for Additive Network Tomography

Summary

Additive network tomography, which addresses the inference of link/node performance metrics (e.g., delays) that are additive from the sum metrics on measurement paths, represents the most well-studied branch in the realm of network tomography, upon which a rich body of seminal works have been conducted. This chapter focuses on the case in which the metrics of interest are additive and constant, which allows the network tomography problem to be cast as a linear system inversion problem. After introducing the abstract definitions of link identifiability and network identifiability using linear algebraic conditions, the chapter presents a series of graph-theoretic conditions that establish the necessary and sufficient requirements to achieve identifiability in terms of the number of monitors, the locations of monitors, the connectivity of the network topology, and the routing mechanism. It also contains extended conditions that allow the evaluation of robust link identifiability under failures and partial link identifiability when the network-wide identifiability condition is not satisfied.