Research On Segmentation Method Of Network Topology Estimation Based On Multi-path Routing And Realization Of Measurement Platform

Network topology inference is a very important issue of concern in the field of computer networks.The precise understanding of the internal structure of the network is of great significance for monitoring the network running status and the design of network applications.For the topology inference of the network,due to there are a large number of nodes that can not provide measurement cooperation within the network,the network topology estimation method based on tomography can only collect the network end-toend performance parameters(such as delay and packet loss rate)at the edge node of the network,and then use the collected end-to-end performance parameters for data analysis and statistical feature extraction,finally can infer the network topology.Most of the existing network tomography studies are carried out under the assumption that the network topology is a tree topology.However,with the application of load balancing technology,there are more and more multipath routing networks in the Internet.At this time,there are multiple reachable paths between network nodes,and the topology is no longer a traditional tree topology.Traditional tomography method is no longer applicable,so this thesis mainly study on multi-path routing topology estimation of network tomography problems.In addition,we designed and built a set of tomography measure platform based on PlanetLab and NS-3 is.The main work and innovation of this thesis is summarized as follows:(1)An end-to-end path number identification algorithm based on packet arrival order: It is important to identify the number of multipath routes in a network for network topology inference under multipath routing.First According to the arrival order of the packets in the packet group,the set of probe flow constants is obtained,and the constrained K-means algorithm is clustered at different K values to obtain the minimum K value without violating the constraint.And we cluster the probe flow with the traditional K-means clustering algorithm.Then we judge the different clustering results starting from the minimum K value by the relevant criterion.Finally we can get the number of multipath routes.(2)Multi-path routing network topology estimation algorithm: We proves the discernibility of multipath routing topology by decomposing multipath routing topology into a single source tree topology and several multi-source tree topology.Firstly,we restore the topology of the single-path routing node in the network by the traditional method.Then,we can locate the branch node with the correlation between the multipath routing path and other single-path routing,so as to finally restore the multi-path routing network topology.(3)The tomography measurement platform based on PlanetLab and NS-3 : The measurement platform combine the measurement in the actual network with the simulation of the network.We can easily carry out the actual network of multi-path routing network identification and the actual network of end-to-end performance parameters measurement work.In addition,the related algorithm under multi-path routing can be simulated by using this platform.The simulation results also prove that the algorithm has good accuracy in different network load conditions.