Multicast-based inference for topology and network-internal loss performance from end-to-end measurements

The use of multicast traffic as measurement probes is effective to infer network-internal characteristics. In this paper, we propose novel approaches to infer multicast network topology and link loss performance from end-to-end measurements. First, we present a new algorithm, binary hamming distance classification algorithm (BHC), that identifies multicast network topology based on the hamming distance of the sequences on receipt/loss of probe packets maintained at each pair of nodes. It is proved by analysis and simulation that BHC can infer the topology at a higher accuracy and efficiency than the previous algorithms with a finite number of probe packets. We also propose a new statistical approach to infer network-internal link loss performance based on the inferred topology. The inferred link loss rate is proved to be consistent with the real loss rate as the number of probe packets tends to infinity. Our new approach makes it possible to infer multicast network topology and loss performance simultaneously. We extend our algorithms for both multicast topology and loss performance inference in binary trees to general trees, and present a new method of loss rate-based scheme for general tree topology inference so that the inferred topology can correctly converge to the true topology which was difficult to achieve previously.