Research On Link Performance Parameter Estimation Methods Based On Network Tomography

With the rapid development and wide application of the Internet technologies, the scale and complexity of the networks are constantly increasing. The difficulty of managing and maintaining the networks is also increasing and thus obtaining the network-internal link performance parameters as well as their dynamic characteristics accurately and timely turns in to an important research goal of network measurement. For security concerns, the traditional network measurement technologies, which need the cooperations of network-internal nodes, are more and more limited. Therefore, the tomographic methodologies which have been successfully applied in medical science and seismic science are introduced to communication networks, where they use the path-level performance parameters obtained by end-to-end measurement at the periphery of networks to infer the link-level performance parameters. Network tomography can obtain the network-internal performance parameters without the collaborations of internal nodes, which coincides with some characteristics of the Internet such as non-cooperation, heterogeneity, edge-based control. Therefore, it attracts a lot of attentions since it has been proposed and becomes one of the most popular research topics in the field of network measurement.According to the estimation targets, the problems of estimating link performance parameters based on network tomography fall into two categories: estimating the quantitative parameters and estimating the qualitative parameters. The former aims to obtain the accurate values of some link performance parameters, and thus it needs rigorous measuring and inferring methods. In some scenarios, it is enough to know the status of the links(e.g., whether it is congested/neutral or not), and thus there is no need to get the accurate values. Therefore, simpler methods can be used for the later problem. This dissertation studies both of them and obtains the following innovative achievements:1. For the link delay estimation problem, considering the diversity of the delay characteristics of the links, this dissertation proposes a discrete delay model with variable bin size. It estimates the upper bounds of the link delays according to end-to-end measurements and then designates different bin sizes to different links according to the estimated upper bound. After that, this dissertation proposes a fast inference algorithm for link delays based on the two-level binary tree structure. This algorithm calculates the delay distribution of each link by explicit computation, and thus it is computationally simpler than existing algorithms. Simulation results show that this algorithm can estimate the link delay distributions faster than existing algorithms and it can also infer the average link delays more accurately when combining with the delay model with variable bin size.2. For the problem of identifying congested links based on a single measurement interval, this dissertation proposes two methods that exploit the congestion degrees of the end-to-end paths to improve the identification accuracy:(1) Congested link identification based on multiple state model: first we map the paths with different congestion degrees into different congestion states according to multiple path thresholds, and model the relationship between the link states and the path states under the multiple state model. In order to minimize the sum of the link states, we then recast the problem of identifying link states into an optimization problem with multiple constraints. After that, an up-bottom algorithm is proposed to solve the optimization problem.(2) Congested link identification based on congested sub-tree division: In order to overcome the error issues caused by inappropriate path thresholds in the multiple state model, a congested link identification approach based on congested sub-tree division is proposed. According to the relative magnitude of the path performance parameters, this approach partitions each congested sub-tree into several smaller ones. Then it identifies the congested links in each sub-tree respectively. Simulation results show that, compared with existing approaches, this approach can improve the identification accuracy significantly.3. The congested link identification methods based on a single measurement interval assume that all the links are congested with the same probability. If this assumption is violated in practice, these methods are not quite accurate. For this sake, this dissertation studies the problem of identifying congested links based on multiple measurement intervals and proposes a novel approach to infer the link prior probability of being congested. This approach is based on the maximum likelihood method. It transforms the global maximum likelihood problem into several maximum likelihood problems for a series of sub-trees, and then solves each of them by explicit computation. The accuracy of this approach is guaranteed by maximizing the likelihood function of each sub-tree. Meanwhile, as this approach involves only explicit computation of the measurement data, its computational complexity is low. After that, we combine the inferred congestion probabilities of the links with the path states in subsequent intervals to estimate the maximum a posteriori estimation of the link states. Compared with the methods based on a single measurement interval, this approach can further improve the identification accuracy.4. Most existing network tomographic technologies are based on neutral networks, while there is few attention on identifying whether the network neutrality is violated. With the wide application of non-neutral networks, detecting the network neutrality becomes an attractive problem in network measurement. This dissertation exploits the network tomography methodology to infer the neutrality of a network and its internal links for the first time. We use a system of linear equations to model the relationships between the congestion probabilities of the links and those of the paths and then prove the sufficient condition that when can we disclose the neutraltiy a network based on the existence of the solutions of this linear system. The proposed condition is then applied to some part of the network, where non-neutral link sequences in this part can be identified according to the existence of the solutions of the linear system corresponding to this sub-network. Based on the above idea, we propose a basic and an improved algorithm for locating non-neutral links and verify their validity through experiments.