Network tomography is an elegant approach to network troubleshooting: just as medical tomography observes an organ from different vantage points and combines the observations to get knowledge of the organ’s internals without dissecting it, so does network tomography observe the characteristics of different end-to-end network paths and combines the observations to infer the characteristics of individual network elements without probing them. In principle, this approach could enable a network operator to troubleshoot a network even if she does not have direct access to its elements, hence cannot directly monitor their behavior.
On the other hand, there are reasons to be skeptical about the usefulness of network tomography in practice. Even though it was invented more than 10 years ago and is still a topic of active research, it has not seen any real deployment. We believe the reason is that existing tomography algorithms make certain simplifying assumptions that do not always hold in a real network, which means that the algorithms’ results may be inaccurate.
The goal of this project is to narrow the divide between the theory and practice of network tomography. We want to understand which network properties affect the accuracy of network tomography, hence when (in which practical scenarios) tomography can yield accurate results. We also want to understand what kind of problems we can accurately solve with tomography under realistic assumptions.
Results
Shifting Network Tomography Toward a Practical Goal, Denisa Ghita, Can Caracus, Katerina Argyraki, and Patrick Thiran. This work shows how to apply network tomography in a particular practical scenario: an ISP operator wants to assess the quality of a peer’s network. In this scenario, state-of-the-art tomography algorithms are not accurate enough to be useful; we attribute this not to the limitations of the algorithms, but to the inherent difficulty of classic tomography problems. We show that, in this scenario, it makes more sense to solve a new tomography problem — compute the frequency with which the peer’s links are congested — because that can be done accurately under more realistic assumptions. In CoNEXT 2011.
Network Tomography on Correlated Links, Denisa Ghita, Katerina Argyraki, and Patrick Thiran. This work shows that network tomography can be useful even when network links are “correlated” (the status of one link may depend on the status of other links). Prior tomography work assumes no link correlation, even though it does occur in several practical scenarios. We formally prove that, under certain well-defined conditions, we can use network tomography to identify the frequency with which links are congested, even in the presence of correlated links. In IMC 2010.
Netscope: Practical Network Loss Tomography, Denisa Ghita, Hung Nguyen, Maciej Kurant, Katerina Argyraki, and Patrick Thiran. This work presents Netscope, a new tomography algorithm that infers the loss rates of network links. Netscope’s novelty is a combination of first- and second-order moments of end-to-end measurements that are used to identify and characterize the links that cannot be (accurately) characterized through existing practical tomography algorithms. In a simulatiom scenario involving 4000 links, 20% of them lossy, Netscope correctly identifies 94% of the loss links with a false-positive rate of 16% — a significant improvement over the existing alternatives. In INFOCOM 2010.