Research on Topology Discovery in the Overlay Multicast

In the overlay multicast, hosts perform the topology discovery and build multicast tree by themselves. This may ruthlessly wastes network resources if the overlay paths mismatch the underlay paths. Otherwise, it will be improved. In this paper, an active topology discovery method based on the random directed graph is analyzed. It is shown that if each node chooses Θ(logn) nodes randomly to test, the topology will be non-strong connective, and if each node chooses 2.997×n\-\{0.5312\} nodes randomly to test, the length from the source host to any hosts will be at most two times the length of directed unicast path. The simulations show that the path will not be improved obviously with the increase of k value, after the k reaches a certain value.