Noise Reduction Techniques for Network Topology Discovery

Topology discovery techniques based on a network tomography approach can be successfully adopted in almost all scenarios, in that they infer the internal characteristics of a network without any cooperation from the internal nodes. Out of the many tomographic topology discovery techniques proposed in the literature, those based on the use of packet sandwich probes (a special kind of packet trains) present some particularly attractive features. The rationale of such approaches is to take advantage of end-to-end measurements to infer the logical topology of the network through hierarchical clustering algorithms. Typically, due to the interference with cross traffic, such measurements are affected by a zero-mean noise which, in turn, may cause the wrong reconstruction of the network topology. This paper analyzes the causes of certain noise patterns (which have actually been observed during experiments) and proposes a noise reduction algorithm to sort out this issue. Such an algorithm does not rely on any assumption about the statistical model of the cross-traffic noise and its effectiveness has been tested through a campaign of ns2 simulations.