Network tomography and the identification of shared infrastructure

This paper considers the problem of identifying network infrastructure, shared through a collection of end-hosts. This identification is valuable for assessment and design of content distribution systems as well as network performance estimation and simulator design. The network routing connects a set of sources to a set of receivers from a directed graph. This paper considers the identification of subgraphs shared by two or more sources. We take a system identification approach to the shared subgraph problem, comparing source inputs with receiver outputs. Sets of receivers are then associated with shared subgraphs using this novel multiple source probing scheme. Our methodology does not rely on special-purpose cooperation from internal network elements, and only requires end-to-end measurements that are easy to make. Experiments conducted on a local area network and the Internet demonstrate the potential for our approach.