Research On Unicast End-to-end Measurements Based Network Performance Parameters Estimation Methods

With the rapid development of network technology, the scale and the complexityof Internet are constantly increasing. In order to successfully manage and optimize thenetwork, it is essential to accurately and timely understand the network internalperformance parameters (e.g., network topology, link loss, link delay, etc) and theirdynamic change characteristics. By introducing the methods which are successfullyapplied in the fields such as medicine and seismology to the problem of internalperformance parameter measurement in communication network, network tomographyobtains end-to-end performance parameters via sending active probe packets, andestimates the network internal performance parameters using sophisticated tomographymethods. The great strength of this method is that it can accomplish the measurementof network internal performance parameters without the cooperation of internal nodes,hence network tomography has attracted many attentions from academic and industrysince it had been proposed, and has became one of the most important research aspectsin the area of network measurement.Network tomography can send multicast probe packets, and can also send unicastprobe packets. Due to routers treat the multicast and unicast packets differently, theinternal performance parameters of actual unicast traffic can only be estimated byusing unicast probe packets. This thesis studies how to use unicast probe packets andnetwork tomography to estimate network internal performance parameters. Theinnovative achievements in this thesis are as follows:1. Research on network topology estimation methodThis thesis presents a maximum likelihood based network topology estimationmethod, which regards the topology estimation as a dynamic nodes inserting process.From a simplest binary tree with two leaf nodes, the method inserts the leaf nodes intothe tree one by one in order to construct estimated topology, and estimates the insertingposition of each leaf node using maximum likelihood method. The presented methodcan effectively reduce the computational cost of the maximum likelihood based topology inference method, and guarantees to obtain high precision estimated results.2. Research on temporal dependence network link packet loss estimationThis thesis presents k-th order Markov chain (k>1) based network link packet lossestimation methods. By using k-th order Markov chain, the temporal dependencecharacteristic of link packet loss can be precisely captured, which is of benefit toobtain accurate packet loss probability estimates. The k-th order Markov chain isintroduced to model the link packet loss process in the problem of network link packetloss inference, and the maximum pseudo likelihood based method and the constrainedoptimization based method are proposed to estimate the parameters of the k-th orderMarkov chain link packet loss model. Compared with tranditional methods, theproposed methods yield more accurate packet loss probability estimates.3. Research on network link delay high-order statistical characteristic estimationThis thesis presents a method to estimate link delay high-order cumulants (secondorder or above) using network tomography. The presented method obtains theend-to-end delays by sending general unicast back-to-back packets, and estimates linkdelay high-order cumulants by constructing linear system equations according to thecharacteristics of cumulant. Compared with existing methods, the presented method iscapable of accurately estimating link delay high-order cumulants without thecooperation of internal nodes, and obtains more link delay statistical information.4. Research on non-stationary network link loss rate estimationThis thesis presents a non-stationary network link loss rate estimation method.The method based on the idea of sliding time window analysis, which divides themeasurement time into a set of time slots, and each time slot represents a short periodof time. In a time slot, time-varying link loss rates are approximated by k-th ordercontinuous differentiable functions (k>1), then the time-varying loss rates of the entiremeasurement time are estimated via using inverse distant square weighted algorithm.Analytical and simulation results indicate that the presented method is capable ofapproximating the actual time-varying link loss rates accurately, and is superior totraditional link loss rate estimation methods. Furthermore, this thesis improves atraditional probe packet sending method called three-packet stripe. The improvedthree-packet stripe is capable of reducing the end-to-end measurement errors resulted from imperfect correlation of the unicast probe packets, and obtaining more accuratelink loss rate estimates.