Research Of Congested Link Location And Performance Inference Algorithm In IP Network

The traditional IP network management systems usually adopt the passive detection methods.The network fault is often diagnosed by the correlation analysis technology.With the expansion of the network scale and the diverse network structure,the passive detection methods involve user privacy with poor security,and due to the higher cost of deployment of the hardware/software,it is hard to guarantee the accuracy and the real-time ability.However,the active detection technology doesn’t involve the user’s privacy,and only uses part of end-to-end(E2E)path performance detection results,the set of congested links and their performance can be inferred by the tomography technology according to IP network topology relationship,therefore,the active detection methods have gradually attracted the attentions of many experts and scholars worldwide.Although there are many advantages by using the active detection to diagnose the IP network fault and to inference the network performance,some problems still exist: 1)Part of link information missing will cause location failure due to the limitation of Internet Control Message Protocol(ICMP);2)The E2 E active detection technology will bring additional network flow load,which affect the network performance;3)The algorithm performance of the present congested link location and performance inference based on the Bayesian network model will become worse because of the dynamic routing in IP network;4)The location accuracy rate by using traditional algorithms based on the expert knowledge or Smallest Cover Set(SCS)method will decline in the multiple link congestion IP network;5)The accuracy of loss rate solution method in the single time slot E2 E path detection will descend because of the clock synchronous problem.With regards of these disadvantages,many researches were carried out these theses.To avoid the influence of loss link on the congested link fault diagnosis and performance inference,a kind of RWR algorithm based on the restart random walk model is proposed to infer the set of loss links,and experiments proved that it is the most suitable algorithm with higher accuracy and robustness under power-law IP network with a certain link loss.Other innovative research contributions in this paper list as follows:1)Aiming at more detection routes which lead to the increasing of IP network load,a kind of efficient IP network E2 E probe selection algorithm is proposed.The new algorithm can cover links as much as possible through inducing degree threshold value without adding more probe deployment cost.Experimental results have shown that comparing with the existing traditional algorithm based on the leaf nodes as probes,the new algorithm takes into account the link coverage and probe deployment cost,and reduces the extra load as much as possible.2)Aiming at the problem of decrease in fault detection rate in multiple link congestion IP network,an improved Lagrange slack subgradinet algorithm is proposed based on Bayesian Maxium A-Posteriori(MAP).A kind of performance relationship static model between the E2 E paths and traversing links is built.Based on this model,according to the multi-slot E2 E detection,a kind of Symmetric Successive Over-Relaxation Preconditioning Conjugate Gradient(SSORPCG)algorithm is proposed to iterative solve link congestion prior probabilities.Experiments verified that the proposed algorithm had higher accuracy and robustness.3)Aiming at the dynamic routing character of IP network,a variable structure discrete dynamic Bayesian model is built,and based on its simplified model obtained by introducing the assumptions of first-order markov property and homogeneity,two kinds of improved congested link location algorithms are proposed.Experimental results proved that the new algorithms are suitable to the congested link location in dynamic routing IP network.Compared with the traditional algorithms,the proposed algorithms have higher accuracy and better robustness.Under the multiple link congested circumstance,the performance of the improved Lagrangian relaxation sub-gradient algorithm is superior to the algorithms based on the SCS method.4)Aiming at the problem of link performance inference in multiple link congestion IP network,a kind of loss rate range inference algorithm based on the path performance cluster is proposed.Compared with the traditional link performance inference algorithm based on the Boolean algebra,the new algorithm has higher accuracy and resolution.The proposed algorithm is based on the multi-slot E2 E measurement,which avoids the strong dependence of clock synchronization in the single-slot E2 E measurement.And the loss rate range of each congested link can be inferred by adopting paths cluster method,which avoiding the complicated linear equation inversion process in the traditional algorithm.Experimental results have shown that the proposed algorithm can provide favorable accuracy and robustness.