Research On Non-stationary Network Loss Tomography Based On Partical Filtering

In order to effectively control, manage and optimize the network requiresaccurately and timely understanding of a variety of performance parameters of theinternal network, such as, network topology, link loss rate, and link delay. Networktomography is an effective method to get the performance parameters of the internalnetwork. It doesn’t require the cooperation of internal network nodes, and can be usedto estimate performance parameters of the internal network through the end-to-endmeasurements. Traditional network tomography usually assumes link performanceparameter is constant over the entire measurement cycle, i.e. the status of the networklink is stationary, therefore is called stationary network tomography. But the burst ofreal network traffic will make the link performance parameters changing constantly, sothe traditional method to estimate the results does not correspond exactly with the actualsituation. Non-stationary network tomography estimates time-varying performanceparameters of network internal by releasing the stationary link state assumption, whichcan get a more accurate estimation result.At first, the thesis introduces an estimation framework of the time-varying link lossrates to estimate link loss rates of the non-stationary network. The framework usesknown priori information and background traffic to estimate link loss rates. Itsadvantage is not to send any probe packets or just to send a small amount of probepackets in the training phase to obtain time-varying link loss rates. So it can monitor thechange of the link loss rates under the condition that it doesn’t bring any burden orbring burden to the network as low as possible. Besides, we obtain the prioriinformation using Gibbs Sampling and sending back-to-back probe packets, and thelatter is more accurate than the former. Based on the estimation framework of the linkloss rates, the thesis mainly studied estimation methods of the time-varying link lossrates. The main innovation consisted of two aspects.(1) The thesis proposes an estimation method to estimate time-varying link lossrates based on particle filtering. Since the particle filtering can deal with problems ofnon-linear and non-Gaussian, we apply it to the non-stationary network loss tomography to estimate the time-varying link loss rates. First, the method extractedparticles from the priori information. Then, it used the observation equation to obtainthe particle weights. At last, the values of weighted average of particles are substitutedinto the state transition equation to obtain time-varying link loss rates.(2) The thesis proposes an estimation method to estimate time-varying link lossrates fastly. Since the estimation method based on particle filtering will cause highalgorithm complexity when estimate the complex topology link loss rates. In order tobalance the algorithm complexity and the estimation accuracy, the tree of split methodis applied to time-varying link loss rate estimations. Firstly, the complex topology splitinto a series of simple sub-tree. It applied the estimation method based on particlefiltering to the sub-tree. Finally, we got the time-varying link loss rates of complextopology according to the relationship of link between complex topology and sub-tree.Then, we realized a fast estimate of link loss rates.We carried on NS2simulation to simulate the two proposed methods in this thesis.Simulation results demonstrated that the two proposed methods can effectively track thechanges of the network link loss rates, and were both superior stationary estimationresults. Also verified the priori information obtained by sending back-to-back probepackets is more accurate than the priori information using Gibbs Sampling. Finally, weidentified the various application scenarios by comparing the two proposed methods.