Fundamental Properties of Routing Matrices and Their Implications for Network Tomography
Hung Nguyen, Denisa Ghita, Maciej Kurant, Katerina Argyraki, Patrick Thiran · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2009
Network performance tomography establishes linear relationships of the form Y = R · X between the characteristics of individual links (X) and those of end-to-end paths (Y) through a routing matrix R. A fundamental question is whether these relationships are sufficient for inferring the characteristics of links from end-to-end path measurements; there has been evidence, though not proof, that this is not the case due to R’s structure. In this paper, we formally prove that the routing matrix R is always rank deficient, in particular, Rank(R) ≤ |E| − |V|, where |E| is the number of links (also columns in R) and |V| the number of routers in the network. We identify a class of networks for which this upper bound is provably attainable. We also identify a (wider) class, which includes all real topologies we were able to collect using PlanetLab, for which we prove a lower bound on R’s rank. Using insights from our analysis, we develop an accurate algorithm that infers the loss rates of individual links from end-to-end path measurements. Unlike other work, we do not make any assumptions regarding the temporal correlation between measurement probes or the distribution of link loss rates. Using our algorithm, we built a PlanetLab-based network tomographer, which we use to experimentally validate the correctness of the routing-matrix rank bounds and demonstrate the accuracy of our link-loss inference.