有关基于LSP路径规划的自适应流量分配---电子科技大学通信信息工程学院毕业论文写作资料-论文写作网

简介:关于本文可作为路径算法方面的大学硕士与本科毕业论文路径算法论文开题报告范文和职称论文论文写作参考文献下载。

路径算法论文范文

摘要：随着网络流量大规模的增长,ISP (Internet ServiceProvider)在骨干网中大量部署MPLS[1]网络以解决各种网络问题提高性能.在MPLS网路中流量工程技术被广泛应用,其中多路径自适应流量分配算法可是流量工程[中一项关键技术.在本文中对自适应流量算法M AT E进行了分析,提出了它的不足,通过最小化最大链路重叠度对LSP(Label Switch Path)进行路径规划,将静态离线算法和自适应动态在线算法结合起来,仿真实验证明这一结合提高了动态算法的收敛速度和稳定性.

关键词：路径规划：在线动态算法：流量工程．K最短路

中图分类号：TP301

文献标识码：A

文章编号：1673-1131(2010)03-016-03

一、引言

当前大规模网络应用快速发展．ISP骨干网上流量成倍增加．而ISP如果不断地对网络扩容将会带来巨额成本开支.如何有效利用好已有的网络资源成为降低成本的有效途径.根据IETF对TE(Traffic Engineering)的定义：一种可以提高优化网络性能的工具.具体来讲就是如何将流量合理地映射到网络上.MPLS的出现为实现TE提供了全新的技术.MPLS网络通过现实路由计算出LSP．网络汇聚节点将收到的数据根据事先规定好的策略转发到相应LSP.数据包在LSP不再像lP网络那样基于跳到跳路由,而是根据定义好的LSP直接被转发.为了提高MPLS网络资源利用率和容错度,通常源宿节点对之间有多条LSP.而如何将汇聚的流量合理的分配到各条LSP就成为问题研究的关键.

当前研究关于多条路径如何分流的研究主要有两种方式.第一种为离线静态方法：通过收集网络数据．周期性（一天或者一周）地利用离线算法计算出流量分配最优值对应的参数,然后配置到网络节点上以达到网络性能最好.当前已经有关于此类方法的研究,例如．MPLS muti-commodity flow optimizer&,acute,8].离线算法通过线性规划求解实现比较简单稳定,但是此方法必须事先对流量预测,不可知的突发流量对网络带来承重负担,当超出预设值时将导致网络瘫痪.第二种为在线动态方法,算法实时运行在网络节点上,可以动态地根据流量大小调整分配比,以到达网络性能最好,例如,早期的ARPAnet. Srikanth Kandula[6]提出的TEXCP和Anwar Elwalid的MATE.在线算法可以动态跟踪流量变化,应对网络突发故障：但是在线算法实现复杂,收敛速度慢,而且容易产生振荡效应.

在线动态算法可以解决问题广泛性成为现在研究的热点,然而在线动态算法的性能问题是目前需要解决的关键难点.在本文中利用数学模型建模,通过最小化Link重叠度来规划LSP路径,将离线静态和在线动态算法结合起来．使得算法的性能更优：在收敛时间,全网Cost等性能参数上得到极大改善.

本文的下面内容安排如下：第二节分析了现有自适应在线动态MATE的理论模型和实现过程；第三节从两种模式描述了两种不同的路径规划方法．K最短路径规划和本文提出的基于最小化最大链路重叠度的路径规划：第四节针对拓扑和业务模型进行仿真并对结果进行分析,最后．是对文章的一个总结和下一研究方向.

二、自适应流量分配算法

在多路径在线动态算法中．MATE算法以其部署的简易型著称,它不需要中间节点重新更换硬件设备或者协议更新．端到端的控制只需要在源和目的节点做出改动全网就可以实现分布式自适应动态流量分配.然而MATE由于收敛时间和稳定度存在一定的缺憾,通过对LSP路径的规划将会使得性能方便得到提升.

三、LSP路径规划

3.1基于K最短路的路径规划

K最短路算法是网络中源目节点对求解多路径时最常用的算法.在文献阐述了算法具体思想.第一步：计算出源目节点对之间的最短路径,第二步：最短路径上Link分离,生成一个多路径树：第三步：对生成的多路径树进行深度优先遍历．找出最短的前K条路径.

在当前光纤骨干网络中传播延迟很小,对网络性能影响最大的传输延时,当用K最短路算法计算出的k条路径如果有多个Link公用,将会带来很大传输延时,甚至当流量突发增大时可能造成拥塞.在本文中提出的基于Link重叠度最小的LSP规划就是针对此问题的解决方案.

3.2基于最小化最大链路重叠度的LSP路径规划数学模型

研究的问题是为了找出n条Link重叠度最小的路径,为了建模方便和求解容易．在本文中的线性规划模型中虚拟出源目节点对的业务量,通过(3)式虚拟流均分为n份,这n份子流在网络中通过(5)式搜索出Link重用度最小的一组路径集合.

路径规划算法:[第17集] 最短路径算法：Dijkstra算法，广度优先搜索

x流量需求(i,j)是否经过链路,为整数变量,流过时为1,否则为0.

n：需要的路径条数

Link重用度定义：两条路径同时经过一条Link的次数.

250M的M/M/l源流量分别从节点2和节点9加载,初始化时在图2和图3的节点对间的两条LSP任选一条将流量全部灌入.测试全网结果如下：图3的路径规划比图2的路径规划收敛时间节省了30%,全网平均包时延减少0.23ms.此结果说明,虽然在基于最小化最大重叠度的路径规划中,出现的路径可能比K最短规划的路径长,但是因为前一种路径Link互相影响度降低,在路径上传输延时的节省值比传播延时的增加值大,所以全网平均包延时减小,性能得到提高.

五、结论

本文在在线动态算法的基础上提出了最小化最大Link重叠度的路径规划模型,将两者有机地结合在一起,仿真结果可以看出,同通常的K最短路径规划相比,提出的模型算出的路径使得网络性能得到更大的提高,但是本文中测试的网络拓扑还不够大,在大型拓扑中的结果还有待于深入研究,同时结合在线动态算法中多路径上流量初始化分配比多性能的影响将是接下来要研究的方向.

总结：本文是一篇关于路径算法论文范文，可作为相关选题参考,和写作参考文献。

路径规划算法引用文献: