一种基于链路流量的路由算法模型

《一种基于链路流量的路由算法模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1一种基于链路流量的路由算法模型李鹏赵峥嵘杨洋王昊宇兰巨龙(信息工程大学，国家数字交换系统工程技术研究中心，河南，郑州450002)摘要：依靠流量工程技术解决端到端延迟的问题是在网络业务流量已知的前提下，不适合未来网络业务类型的不确定性和流量需求的突发性。本文提出了一种通过链路实时流量控制节点状态来选择路由的思想，给出了算法的数学模型，探讨了该算法对业务流量的适应性，为下一步的研究提出了新的课题和思路。关键词：流量工程技术位势函数文章编号中图分类号文献标识码ADynamicTraffic-Based

2、RoutingAlgorithmModelLiPeng,ZhaoZhengrong,Yangyang,WangHaoyu,LanJulong(NDSC,InformationEngineeringUniversity,Zhengzhou45002,Henan)[Abstract]Usingtrafficengineering(TE)toaddressend-to-enddelayassumesthattrafficdemandsareknownapriori，whichdoesn’tadapttov

3、aryingtrafficpatternsanddemands。Thispaperbringsforwardadynamicroutingalgorithmdeterminingroutesthroughnodevaluechangedbyrealtraffic，presentsitsbasicmodel，anddiscussesitsadaptabilitytofuturenetworks，whichputforwardsthenewdirectionandmethods。[Keywords]tr

4、afficengineering，potentialfunction1．引言当前网络拥塞问题大多由端到端控制机制解决，如TCP拥塞控制机制，通过调整发送端的发送速率来实现。但该机制带来了端到端延迟的问题。如果多条数据流共用一条链路，每条只能分得链路带宽的一小部分，即使是当前网络可提供另一条路由。显然在拥塞链路上的排队延迟将增加端到端延迟。同时业务流量的不确定性也使得排队延迟不稳定。而解决端到端延迟是结合基于链路的路由算法采用流量工程技术（TE）。在假设发送端到接收端之间的流量需求是已知的前提下，计算

5、满足流量需求的端到端路径。沿着该路径，利用资源预留协议（如RSVP），建立端到端链路。这种基于链路的路由算法是有问题的。首先，如果业务源是突发式的（实际上，网络中大都是这种情况），预留资源的策略就不起作用。其次，链路的流量需求是很难估计的。再者，未来的业务需求是无法预料的，如果业务类型发生改变，很可能要重新计算最佳路由，同时很难保证现在的路由算法能适用未来的业务需求。本文提出了一种基于流量的路由算法。把链路流量反映到节点上，由节点的特定状态决定下一跳。该算法继承了逐级跳路由原理，无须事先了解节点间的

6、流量需求。2.算法基本思想称这种基于节点位势值的算法为NP算法。为网络中每个节点定义一个状态值—位势（nodepotential）。然后，在每个节点处，计算出位势值下降最快的方向，作为下一跳。显然，如果把节点的位势值定义为该节点至目的节点之间最短路径(由最短路径算法得到)的单调增函数，标准的最短路径算法就是该思想的一个特例。若节点的位势值考虑了该节点处的流量的话，该算法就是基于流量而动态变化的。本文作的主要工作如下：首先给出了算法的数学模型，证明了算法的基本性质，然后初步研究了如何为网络定义一个位势

7、函数，最后给出了NP算法的一个具体应用。3．算法模型把一个由双向链路连接的节点组成的网络视作一个有向图GNE=(,)。节点由N表1基金项目：国家863计划（2003AA103510）资助项目。1示。E则对应节点之间的链路。其中，e表示由节点u到节点v的有向边，该边的花销为c，uvuv为一正数。链路是双向的，则有若边e∈E，则e∈E。任一个节点都可作为一个业务uvvu源。每个节点v都有许多邻居节点Z()v，记为nbrv()。3.1节点的位势NP算法定义，节点v的位势值是关于v和目的节点d的函数，即节点

8、与惟一的位势d值Vv()相对应。目的节点d变了，那v的位势值函数也随之改变。本文是在假设目的节点d固定的情况下，来推导算法的性质的，直接用Vv()表示节点v的位势值。假设节点v处的数据包p（目的节点是d），为了到达d，数据包p必须跳到Z()v中的一个节点。为了确定这个“下一跳”节点，利用节点v的位势值和邻居节点，给数据包p定义一个“前进”的“力”。V()－V()vw对于个邻居节点wnbrv∈()，定义“力”：F＝（1）vw→cvw现在就是要寻找使得F最大且为正的邻居节