Network Topology Discovery Based on a Finite Set of Hypotheses

Tomographic techniques allow for the reconstruction of network topologies with no need for cooperation from internal routers. Traditional tomographic techniques infer the internal network layout by clustering nodes into tree structures that, in many cases, reveal only a partial graph structure of the network. This paper proposes a novel approach to network topology discovery by means of packet sandwich probes; the underlying theoretical basis relies on the application of Decision Theory to a finite set of possible topological hypotheses. The decision process is however disturbed by the interaction of probes with regular cross traffic, which results in a background noise that afflicts the measurements. To cope with this phenomenon, a model-free noise reduction technique is also used. The algorithms presented in the paper are validated through extensive simulations in several network scenarios. The results show that such a methodology allows to retrieve a complete picture of the network that includes the detection of all the internal nodes along with the values of capacities of the interconnecting links.