网络链路时延估计及其在选播路由中的应用

【作者】 张婷；

【导师】 胡光岷；

【作者基本信息】 电子科技大学 ， 通信与信息系统， 2008， 硕士

【摘要】 随着互联网的飞速发展,网络结构也在发生深刻变化,要成功设计、控制和管理网络,就需要了解和掌握网络的内部特性。其中链路时延和链路丢包率是重要的网络性能参数。由于网络日益向着大型化、异构化、分布化发展,通过直接进行网络测量的方法来获得网络内部链路的时延和丢包率参数就变得越来越困难,网络层析成像方法作为一种通过端到端的测量数据来推断网络链路性能参数的技术正成为研究的热点之一。链路时延估计是网络层析成像的重要研究内容之一。本文以链路时延估计为重点,研究了频率域链路时延的估计算法,该算法利用频率域的特征函数来进行时延估计,降低了计算的复杂度,提高了估计算法的灵活性,能够获得较好的估计效果。但是在实际的网络中,由于测量的准确性依赖诸多种条件的限制,不可避免存在干扰和误差,使测量数据发生畸变。这种畸变的测量数据会使现有方法采用的最大似然法或最小二乘法不稳定,即较小的测量误差可能引起较大的估计误差。针对上述问题,本文采用约束最优化方法,提出一种频率域的约束最优化方法链路时延估计算法,在保证较低计算复杂度的同时,提高了估计算法的稳定性和灵活性以及估计结果的精确性。仿真验证了本方法在存在较大测量误差的情况下,仍能获得精度较高的链路时延估计。实际网络是较复杂的网状拓扑,而不是网络层析成像链路时延估计算法所假设的树状拓扑。本文利用图论的基本原理,将网状拓扑分解成树状网络的集合,再利用链路时延估计算法分别对集合中的生成树进行时延估计,并将估计得到的链路时延应用于多目标最优化选播路由选择。围绕选播路由问题,本文针对传统的单目标最优化选播路由算法存在的问题,提出了基于链路时延估计的多目标最优化选播路由算法,通过层析成像的相关算法估计出的网络链路时延以构造最主要的目标函数,同时对多个最优化选播目标进行优化,并在MPLS网络模型中对该算法进行了有效性分析,仿真证明基于链路时延估计的多目标最优化选播路由算法所选出的最优路径的性能指标相对于MPLS原路径有较大提高,使选播能满足更多应用的需求。更多还原

【Abstract】 The knowledge of network parameters allows network engineers to improve the network design, control and operate. For instance, the Internet users may estimate the link level characteristics such as loss and delay from end-to-end measurements, which are important parameter of Internet’s performance. Due to the size and the decentralized nature of the Internet, monitoring its behaviors and diagnose its performance degradation is challenging. Network tomography has been regarded as one of the most promising methodologies for performance evaluation and diagnosis of the massive and decentralized Internet.The estimation of the link level delay is one of the most important study part in Network tomography. In this paper, we study a novel estimation approach for the network tomography problem. Unlike previous methords, this approach does not work with the model distribution directly, but rather it works with the its characteristic function that is the Fourier transform of the distribution. And this algorithm is computationally more efficient and yields more accurate results than previous methods under some some perfect and hypothetical conditions. Unfortunately, the real situation is complicated and there is some difference between the actual end-to-end measurement data and the ideal ones. Furthermore, it makes the evaluated results fluctuating badly. In this paper, we introduce a new constraint Network Tomography to solve this problem, which adds some constraint information collecting with the help of some partial internal nodes to the Fourier Domain model. In fact, the constraint network tomography can improve the precision of evaluated parameters better than the other method. Comparing with the results, it proves that applying constraint optimization method to Network Tomography of Fourier Domain is very effective. The new method has a number of advantages over the existing ones including more stability and flexibility, more accurate estimation and identifiability. Finally, the simulation result demonstrate the performance of the propose approach when there are some obvious errors in the measured-data.The networks always are not trees but reticulations in real situation. In this paper, we divide the reticulate networks into single trees whose link level delay could be estimated through the methord named constraint link delay estimaton in Fourier Domain. Then we apply the estimation results in anycast routing which used the multi-objective optimization algotithms. Especially, both the constraint link delay in Fourier Domain inference and application are investigated. In chapter 3 , we introduce how to build the mathematical model for these problems and the steps to the estimated final results Besides this, in chapter 4, how to validate the routing algorithms using NS2 tools is also discussed.Regarding the problems the single-objective optimization anycast routing algorithm has, we introduce a novel multi-objective optimization anycast routing algorithm which based on the link level delay estimation. We will propose some new methods and ideas which combine the constraint estimation technology of link delay and the anycast routing algorithm. The results of the estimation are used in constructing the main optimization function of the anycast routing model. Finally, we validate its performance using extensive NS2 simulations in MPLS network model and its affectivity is proved by experiments.更多还原