Multiple source, multiple destination network tomography

The problem of identifying topology and inferring link-level performance parameters such as packet drop rate or delay variance using only end-to-end measurements is commonly referred to as network tomography. This paper describes a collaborative framework for performing network tomography on topologies with multiple sources and multiple destinations, without assuming the topology to be known. Using multiple sources potentially provides a more accurate and refined characterization of the internal network. We present a novel multiple source active measurement procedure using a semirandomized probing scheme and packet arrival order measurements which do not require precise synchronization between the participating hosts. A decision-theoretic framework is developed enabling the joint characterization of topology and internal performance. We design a statistical test based on the generalized likelihood ratio test and Wilks´ theorem. The test quantifies the tradeoff between network topology complexity and performance estimation, and identifies when measurements made by the two sources can be combined to achieve reduced variance performance estimates. The performance and efficacy of the algorithm are assessed through ns-2 simulations and experiments over the Internet