1(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080) 2(Graduate University of Chinese Academy of Sciences, Beijing 100080)
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.
Yuan Xinpan, Long Jun, Zhang Zuping, Luo Yueyi, Zhang Hao, and Gui Weihua. Connected Bit Minwise Hashing[J]. Journal of Computer Research and Development, 2013, 50(4): 883-890.