Improved Algorithm For Network Topology Tomography Study

Network topology identification is meaningful to network monitoring, management, control and estimation of internal link parameters. There are generally two methods for network topology identification: the traditional method needing cooperation of internal nodes and network tomography. Since network tomography does not need the collaboration of internal nodes, it attracts great attention in academia and industry.Of all the current network topology tomography identification algorithms, we focus on two of them: the maximum likelihood based estimation algorithm and neighbor joining tree topology estimation algorithm. Both of the two algorithms have a high estimation accuracy of the topology, whereas they both have disadvantages: the former has a great amount of computation when identifying a large-scale network topology, and the latter greatly depends on the selection of threshold, a good threshold can not only reduce the number of probe packets but also improve the accuracy of topology estimation. To solve the problems of the two algorithms, this paper presents three improved network topology identification algorithms, specific tasks are as follows:1. To reduce the computational amount of the maximum likelihood based estimation algorithm, we propose an improved maximum likelihood based fast topology estimation method, which reduces the computational complexity. Its main tasks are: 1) Prove that topology estimation likelihood function is single-peaked and peak value is the global maximum value. 2) According to the single-peaked characteristic of the topology estimation likelihood function, the search for optimal tree only needs to search along the direction where the value of likelihood function increases. By using this way of search, we can find the global optical tree. Since the improved algorithm reduces the number of trees searched and computation amount mainly induced by the computation of likelihood function value of the tree searched, computation is thus reduced. 3) Model based simulation and Ns2 simulation verify the performance of the improved algorithm.2. Current network topology tomography identification algorithms assume that all internal nodes are not cooperative, however, there may exist some internal nodes cooperative in the network. If these cooperative nodes are used, then the efficiency of network topology tomography identification algorithms may be improved. This paper proposes a fast inference of network topology using end-to-end measurements, which uses the cooperative information. The main work includes: 1) Extract collaborative information by sampling data stream on the internal collaborative nodes. 2) Construct constraints using collaborative information. During the search, if a searched tree does not meet the constraints, then it is directly discarded and its likelihood value does not need to be computed, so the computation amount is reduced. 3) Combine the single peak characteristic of the topology estimation likelihood function and the constraints of collaborative information to further reduce the amount of calculation. 4) Model based simulation and Ns2 simulation verify the performance of the algorithm.3. In order to reduce the number of the probe packets, this paper proposes a threshold leveled neighbor joining tree topology inference algorithm which improves the neighbor joining tree topology inference algorithm, the main work includes: 1) Determine the experience threshold according to experience. 2) Divide the threshold to n levels. For each threshold level, use the neighbor joining tree topology inference algorithm to estimate the appropriate topology, and then use the maximum likelihood method to calculate the maximum likelihood function value of the topology. 3) Compare the obtained n likelihood function values, topology with the maximum likelihood value is the best topology, and the corresponding threshold is the best threshold. 4) Model based simulation and NS2 simulation results show that, to maintain the same accuracy of topology estimation, threshold leveled neighbor joining tree topology inference algorithm needs less probe packets compared to neighbor joining tree topology inference algorithm.