电子信息工程毕业论文IP网络中的快速路由微环避免算法Word下载.docx

电子信息工程毕业论文IP网络中的快速路由微环避免算法Word下载.docx

《电子信息工程毕业论文IP网络中的快速路由微环避免算法Word下载.docx》由会员分享，可在线阅读，更多相关《电子信息工程毕业论文IP网络中的快速路由微环避免算法Word下载.docx（11页珍藏版）》请在冰点文库上搜索。

A

Abstract：

WhenalinkweightchangesinnetworkwithInternetProtocol（IP），routingloopsmayoccur.Suchloopsincreasethenetworklatencyandcausepacketlosses，whichcannotmeettheneedsofhighlevelrealtimeservice.Afastroutingmicroloopavoidancealgorithmusingaweightsequencewasproposed.Thelinkweightswerereallocatedaccordingtotheweightsequencesothatnoloopswouldoccurduringconvergencephase.Inordertocalculatetheweightsequence，asafetyweightintervalwasdefinedtodescribetheconditionforavoidingloops，thenthesafetyintervalwasusedtosearchasetofsafetyweightranges.Duringcalculation，theprunningtechnologywasusedtoreducesearchrangeandimproveefficiency.Atlast，thefinalweightsequencewasobtainedfromtheseranges.Thesimulationtestresultsusingtypicalnetworktopologyalgorithmshowthatinaveragefivetimesoflinkweightreallocationcansuccessfullyavoidloopsin87%oftopologies.Inaddition，comparedwithotherexistingalgorithmsusingiterativeadjustmentlinkweightstosolvetheroutingmicroloop，thecomputationalcomplexityoftheproposedalgorithmwasgreatlyreducedbyanorderofmagnitudeandthecomputationalefficiencywasimprovedby30%-80%.Theproposedalgorithmcangreatlyshortenthecalculationtimeandmoreefficientlysolvetheproblemofroutingmicroloop，whichwillavoidnetworklatencyandpacketlosstoprovideahighlevelofservicequality.

英文关键词Keywords：

InternetProtocol（IP）network；

routingmicroloop；

microloopavoidance；

reconvergence

0引言

网络实时业务对网络服务在传输延迟和服务可靠性等指标上的要求日趋提高，但是在IP（InternetProtocol）网络中常常为了修复设备故障、优化流量工程、节能等目的而改变拓扑的链路权重，这样的变化通常导致网络运营商无法提供承诺的高质量网络服务。

因为拓扑发生改变后，网络将发布新的链路状态信息，网络中的节点收到新信息后独立重新计算路由并更新转发信息库（ForwardingInformationBase，FIB），然而由于硬件性能差异和内外环境等原因，各节点收到拓扑更新信息及启用新转发表的时刻不尽相同，于是分散的节点对网络拓扑认知不一致，从而导致各节点转发路径间可能产生微环，继而引发时延增加、丢包等问题。

目前，针对微环问题，业界已提出一些解决方法，主要包括：

建立隧道的方法[1]，控制转发信息库有序更新的方法[2-3]，利用快速重路由的方法[4]、利用多拓扑路由技术的方法[5]和迭代调整链路权重的方法[6-8]等。

其中，建立隧道法在网络拓扑发生变化前，预先为各节点及链路计算备份路径，即隧道，网络拓扑发生变化后，直接将业务转发至对应隧道，从而避开拓扑发生变化的地方。

该方法是一种本地保护机制，能够快速地响应拓扑的变化并实现微环避免的目的；

然而，该方法机制复杂，需要维护大量隧道信息，同时存在一些无法应对的拓扑变化场景。

控制转发信息库有序更新的方法通过控制节点FIB的更新时间，使得各节点有序地更新路由，从而保证网络无环收敛；

不过，该技术需要对开放式最短路径优先（OpenShortestPathFirst，OSPF）和中间系统到中间系统（IntermediateSystemtoIntermediateSystem，ISIS）协议进行较为复杂的扩展，并对时间进行精准控制，因此难以在当前网络中得到实现与应用。

利用快速重路由避免微环的方法，主要通过使用如无环替代路（LoopFreeAlternative，LFA）等快速重路由技术，预先计算备份路径，当检测到失效后立即将受影响的业务转移到备份路从而避免微环产生；

但该方法只能应对链路发生故障或恢复的场景，无法避免链路权重发生变化时可能产生的微环。

利用多拓扑路由技术避免微环时，网络中的每个节点维护多个独立的逻辑拓扑，每个逻辑拓扑拥有一套自己的链路权重，能够对不同链路和节点进行保护。

网络发生变化后，对应节点将业务切换到合适的逻辑拓扑，几乎无时延的切换和无间断的转发避免了可能出现的路由微环。

显然，在该方法中各节点路由器不仅需要维护大量逻辑拓扑信息，同时路由器必须支持多拓扑路由技术以进行拓扑切换，对网络中硬件设备要求较高。

迭代调整链路权重法则通过将链路的权重值有序地从初始值调整到目标值，使得每次调整时的路由重收敛过程中没有微环产生。

链路权重调整法能够应对任意链路权重改变的场景，其调整操作过程简单。

同时该方法依靠路由协议的重收敛机制，无需对现网协议进行修改，易于在现网中实现和应用。

因此迭代调整链路权重法是现有的几种解决方案中较好的一种。

在迭代调整链路权重法的应用中存在两方面的挑战：

其一是如何计算更短的权重调整序列，以保证对链路进行较少的调整操作；

其二是如何降低权重序列计算复杂度。

在以迭代调整链路权重法为基础的算法中，文献[6-7]提出的微环避免算法，能够解决单链路权重变化场景下的微环问题，同时保证权重序列最短，但是该算法计算复杂度过高，在求解大规模的网络拓扑时性能较差。

针对路由微环避免问题的复杂性以及现有工作的计算复杂度高的不足，本文提出一种快速路由微环避免（FastRoutingMicroloopAvoidance，FRMA）算法。

该算法基于链路权重迭代调整技术，以快速地设计出尽量短的权重序列为目标。

仿真结果表明，FRMA算法能够快速地避免路由微环问题，仿真中87%的网络拓扑均可在几十毫秒内完成计算，比文献[6-7]中提出的算法低一个数量级。

1微环问题描述

首先简单阐述网络中链路权重变化时的微环问题。

如图1所示，链路AB的初始权重为10，目标权重130。

AB链路的权重为10时，由最短路算法可以知道，E将接收到的发往目的节点D的数据包转发给C。

链路权重为130时，C将接收到的发往目的节点D的数据包发往E。

当链路AB的权重由10直接改变为130时，如果C先于E更新FIB并启用新转发路径，而E未更新FIB，那么此时C和E分别认为对方是去往目的节点D的下一跳，于是目的节点是D的数据包在到达C和E后，将在C和E之间反复转发，形成路由微环。

在E更新FIB前，如果数据包的生存周期到期，那么它们将被丢弃。

此外，陷入微环的数据包将会消耗大量带宽，当链路CE的带宽被耗尽后，发往该链路的数据包也将被丢弃。

事实上，在图1的例子中，A和C、F和G之间都有可能产生微环。

研究发现[9]，陷入路由微环的数据包有90%左右都会被丢弃，只有10%左右的数据包最终能够到达目的地。

由此可见，网络拓扑中的链路权重发生变化后，重收敛过程中可能产生的路由微环问题将导致网络性能显著下降，因此网络中需要方法来指导权重改变，从而避免路由微环。

从图1的例子可以看出，拓扑发生变化后，网络中的一些节点必须先于另外一些节点改变转发路径才能确保网络中没有微环产生。

但是由于硬件性能差异和内外环境等原因，网络中各节点改变转发路径的时刻并不可控，于是导致节点间可能产生微环。

如果通过适当的方法，控制节点有序地改变路径，那么微环问题将得到解决。

如果将链路AB的权重由初始权重10增加至61，此时G和E将首先更新FIB，改变到目的节点D的路径。

当权重由61增加至101时，F和C更新FIB，并使用新的路径到达D，最后当链路AB的权重设置为121时，A也将不再使用链路AB到达D，此时可以安全地将AB的权重设置为130。

由此可知，通过对链路AB的权重逐步进行调整，网络节点将在合适的时刻依次有序更新FIB并改变路径，能够避免微环产生。

上述调整过程正是链路权重迭代调整技术的基本思想。

文献[6]中已经证明，对于权重发生变化的链路，存在一个离散权重序列，能够保证网络节点有序地改变转发路径，且每次中间更新过程不会引起微环，最终全网无环收敛。

因此，如果能够为权重发生变化的链路找到一个合适的离散权重序列，那么就能够避免该链路权重变化时可能引起的路由微环问题。

2快速路由微环避免算法

本文针对IP网络下单链路权重变化时可能出现的微环问题，提出快速路由微环避免算法（FRMA）。

该算法设计一个权重序列，将链路权重按照该序列有序地重新设置，使得链路权重被重置后的路由重收敛过程中没有微环产生。

在计算权重序列时，算法首先定义安全权重区间的概念来描述避免路由微环产生的条件，随后利用该条件搜索出一组安全权重范围，最后从各范围中取出一个值组成最后的权重序列。

FRMA算法的输入参数有两个，分别是网络拓扑G（N，E，w）和权重发生变化的单链路L=AB，其中：

N和E分别表示图中节点集合和链路集合，w表示链路的正值权重函数，L的初始权重为Kinit，SPT为最短路径树（ShortestPathTree），RSPT为反向最短路径树（ReverseSPT）。

算法输出一个离散权重序列，用mSeq表示。

表1为算法中使用到的符号说明。

FRMA算法主要分为三步。

步骤1计算链路L权重改变后，路径受到影响的源节点集合X和目的节点集合Y。

步骤2针对目的节点Yj，求出源节点Xi改变路径时，链路L的权重所满足的范围。

合并所求得的范围并进行简化，得到目的节点Yj对应的一组安全权重范围序列seq（Yj），该序列保证所有源节点Xi无环地改变到目的节点Yj。

步骤3合并所有目的节点Yj的权重范围序列seq（Yj），得到一组全局安全权重范围序列gSeq，对gSeq进行简化得到序列aSeq。

从aSeq中的每个权重范围中任意取一个值，组成离散权重序列mSeq。

2.1源目节点集合

FRMA算法的步骤1，计算链路L权重改变后，转发路径受到影响的源节点集合X和目的节点集合Y。

定义1集合X。

由于链路L权重改变，转发路径中包含L的节点可能改变其路径，这些节点构成集合X。

集合X由RSPT（B）中节点A及其儿子节点构成。

定义2集合Y。

集合Y表示可能受到影响的目的节点集合。

由于链路L权重改变，其他节点到目的节点Yj的转发路径可能发生改变。

集合Y由RSPT（A）中节点B及其儿子节点构成。

2.2计算权重范围序列seq（Yj）

FRMA算法的步骤2，计算关于目的节点Yj的一组权重范围序列seq（Yj）。

为了计算序列seq（Yj），首先需要确定源节点Xi改变到目的节点Yj时链路L的权重范围。

根据图1的例子可以看出，要保证链路L权重改变时没有微环产生，使用L的源节点必须依次有序改变其转发路径，新的路径中将不再包含链路L。

定义3源节点Xi到目的节点Yj新旧路径的差值delta。

delta（Xi，Yj）=D′（Xi，Yj）-D（Xi，Yj）；

Xi∈X，Yj∈Y

链路L的权重设置为delta（Xi，Yj）+Kinit时，节点Xi将同时使用包含L的旧路径和至少一条不包含L的新路径到达Yj。

因此当L的权重大于该值时，Xi开始使用不包含L的新路径，不再使用包含L的旧路径到达Yj。

与此相反，L的权重小于该值时，Xi仅使用包含L的旧路径到达Yj。

如果在RSPT（Yj）中，Xi的父节点Xf位于Xi到达Yj的路径上，同时在RSPT′（Yj）中，Xi与Xf的父子关系颠倒，即Xi位于Xf到达Yj的路径上，那么在重收敛过程中当Xf先于Xi改变转发路径时，Xi与Xf之间将产生微环。

根据上面的分析可知，如果首先将L的权重设置为大于delta（Xi，Yj）+Kinit且小于delta（Xf，Yj）+Kinit的值，此时Xi将改变到达Yj的路径，而Xf不变。

接着将L的权重设置为大于delta（Xf，Yj）+Kinit的值时，Xf将改变路径。

由于Xi先于Xf改变路径，因此Xi与Xf之间将不会产生微环。

定义4Xi改变到Yj路径时L的权重范围。

权重范围下限：

COST（Xi，Yj，min）=delta（Xi，Yj）+Kinit

权重范围上限：

COST（Xi，Yj，max）=COST（Xf，Yj，min）

其中Xf是链路L权重未改变时在RSPT（Yj）中Xi的父亲节点。

当链路L的权重设置在（COST（Xi，Yj，min），COST（Xi，Yj，max））范围内时，Xi将改变到目的节点Yj的路径，不再使用包含链路L的旧路径，且不会与其他节点产生微环。

根据定义4，可以为每个Xi确定改变路径时链路L必须满足的COST范围，将这些范围合并及简化后得到权重范围序列seq（Yj），该序列保证所有源节点Xi改变到Yj的路径时网络能够无环收敛。

算法1和算法2给出了计算该序列的具体过程。

算法1中根据RSPT（Yj）和RSPT′（Yj），求出所有Xi节点的delta值，进而得到Xi安全改变路径的COST范围。

算法2中将这些COST范围合并及简化得到seq（Yj）。

在算法1中为了计算Xi的delta值，需要分别计算RSPT（Yj）和RSPT′（Yj）。

然而当Y集合规模较大时，算法中计算RSPT的部分将会消耗较多时间，因此本文引入一个剪枝技术：

通过去除不受影响的目的节点Yj，缩小Y集合规模，提高算法计算效率。

根据集合Y的定义，它表示“可能受影响的目的节点”的集合，所以该集合存在一些不受链路L变化影响的目的节点，如图2拓扑所示，当链路AB的权重由50增加到200时，网络中只有源节点A到目的节点D的转发路径发生了变化。

单节点的转发路径改变不会导致微环产生，因此可以认为链路L的变化并未对目的节点D产生影响。

由动态最短路算法[10]可知，在RSPT上如果边E的权重增加，那么只有边E的头节点及其子树上的后继节点到根的最短路径可能发生变化。

分析链路权重变化前以D为根的RSPT可以发现，在RSPT（D）中链路AB的头节点A的后继为空，因此链路AB权重的变化只对节点A的最短路产生影响，必然不会产生微环，可以将目的节点D从Y集合中删除。

因此根据RSPT（Yj）的特点，能够识别出目的节点Yj是否真正受到链路L变化的影响。

其具体方法是：

先计算RSPT（Yj），如果在该反向最短路径树上，链路L头节点A的后继节点为空，则可认为目的节点Yj不受L变化的影响，将Yj从Y集合中删除，减少RSPT′（Yj）及之后相关计算。

算法1计算源节点COST范围。

根据算法1，可以得到源节点Xi的COST范围，由于链路L的权重在该范围内时Xi将改变到Yj的路径，因此该范围内的任意一个值均能保证Xi改变路径。

显然，对于COST范围有重叠的不同Xi，可以共同使用公共范围内的一个权重值。

所以在算法2中，引入另一个剪枝技术，通过不断地找出有区间重叠的COST范围，并使用一个公共区间代替它们，即可大幅度减小权重范围序列的长度。

在Clad等[6]提出的算法中，用数值delta（Xi，Yj）+Kinit表示Xi改变路径的条件。

因此在简化权重序列时，需要重新构造链路L在不同权重时的新拓扑，并计算对应的反向最短路径树，然后通过合并不同权重下的RSPT并检测合并图中是否有环，判断当前一次链路L的权重调整是否有效，从而去除权重序列中可能被其他权重代替的冗余权重。

这样构图检测冗余权重的方法明显增加算法的计算复杂度。

而FRMA算法中，使用区间表示节点改变路径时链路L的权重必须满足的条件，通过查找节点COST范围的重叠区间，可以在线性时间内快速地简化权重序列，能够有效地降低算法复杂度。

2.3计算全局权重范围序列

在2.2节中得到的权重范围序列seq（Yj），能够保证所有源节点改变到目的节点Yj的路径时无环收敛。

但是链路的变化对网络中节点转发路径的影响是同时产生的，因此必须保证每一次调整链路L的权重时，任意Xi改变到任意Yj的路径均可无环收敛。

FRMA算法的步骤3，计算一组全局权重范围序列aSeq，确保网络中各节点同时改变到不同目的节点的路径时无环收敛。

最终得到权重序列mSeq。

具体做法是：

将所有seq（Yj）合并得到gSeq，并使用与算法2相同的思想对gSeq进行简化，得到一组全局权重范围序列aSeq，最后在aSeq的每个权重范围中选择一个值，组成权重序列mSeq，得到算法输出。

3仿真与分析

3.1仿真环境说明

3.1.1仿真拓扑

其中：

ID为仿真拓扑编号；

|N|和|E|分别表示拓扑节点数目和链路数目；

dm表示拓扑中最大度数；

w给出了权重分布范围。

拓扑1和4是星型和环形拓扑；

拓扑2、3是由Rockfuel通过traceroute推断得到的拓扑结构[11]；

拓扑5、6和8是根据幂率分布生成的拓扑[12]；

拓扑7是现网AT&

T拓扑。

本文中拓扑1、2、3、4、5、6、7、8分别为star、Abovenet、Sprint、circle、Pow1、Pow2、AT&

T、Pow3。

其中拓扑7取实际网络带宽倒数作为权重，其余拓扑的权重分布均是100以内的整数随机值。

3.1.2性能指标

首先进行微环风险测试，以说明网络拓扑变化时发生路由微环的高风险性，以及对路由微环避免算法进行研究的必要性。

其次进行算法的性能测试，对FRMA算法和文献[6]中的算法（以下称为Graceful算法）进行性能比较，主要评估算法的时间复杂度、空间复杂度、序列mSeq的准确性和长度，以及算法计算时间。

算法的输入参数有两个，分别是网络拓扑G（N，E，w）和拓扑中权重发生变化的单链路L=AB。

拓扑1～8模拟了由小到大不同规模和不同权重分布的网络拓扑，该参数的变化对仿真结果的影响，主要体现在拓扑不同规模和权重分布对输出结果的最优性及计算时间所产生的影响。

每个拓扑进行|E|次测试，每次随机选择一条链路作为算法输入的另一个参数，即权重发生变化的单链路L=AB，且保证拓扑中每条链路仅被选中一次。

为保证链路权重发生变化的场景一致，在仿真中链路的目标权重均设置为无穷大，即关闭链路。

分析单次链路L的选择对算法性能的影响并无较大实际意义，因此本文讨论每个拓扑下多次仿真测试后的输出结果统计分布情况，重点关注输入拓扑的规模及权重分布对算法性能的影响。

3.2微环风险测试

微环风险测试中，每个拓扑进行1000次测试且随机选择待关闭链路，统计可能出现微环的次数，对网络出现微环的可能性进行评估。

测试中，以下几种情况均认为待关闭链路L不会导致网络中出现微环，即没有微环风险：

1）关闭L后网络不连通，导致业务中断；

2）关闭L后Y集合为空；

3）关闭L后X集合中元素个数小于等于1。

其他情况均认为有微环风险，即需要使用算法计算权重序列逐步关闭链路L。

图3给出1000次仿真测试中各拓扑有微环风险的百分比。

由图3可以看出，88%的拓扑中，超过50%的情况都存在微环风险。

这说明网络拓扑发生变化时，网络中出现路由微环的风险很高，所以对路由微环避免算法的研究非常有必要。

3.3性能比较

3.3.1时间复杂度对比

对FRMA算法和Graceful算法的最坏时间复杂度进行简单分析及对比。

两种算法均可大致分为两步，第一步中针对具体某个目的节点Yj计算权重序列，第二步中将各目的节点的权重序列合并，得到全局的最终序列。

假设由于网络拓扑发生变化，转发路径受到影响的源目节点集合中元素数量分别为|X|和|Y|。

分别对以上两个步骤的最坏时间复杂度分析，结果如表3所示。

根据表3可以看出，两种算法在第一步针对某个目的节点Yj计算权重序列时的最坏时间复杂度相同，但在第二步对多个序列进行合并时FRMA算法的时间复杂度至少比Graceful算法低一个数量级。

随着受影响的目的节点数量增加，以及网络拓扑中链路数目增加，FRMA算法在时间复杂度上的优势更加显著。

3.3.2空间复杂度对比

与时间复杂度类似，对FRMA和Graceful算法的最坏空间复杂度分析按照计算目的节点Yj的权重序列和合并各目的节点的权重序列两个步骤进行分析：

在第一步计算目的节点Yj的权重序列时，主要考虑计算不同目的节点的最短路径树所占用空间；

第二步合并多个目的节点的权重序列时，重点考虑多个权重序列所占用的空间，以及合并计算过程中的空间开销。

如表3所示，在第一步中，FRMA算法与Graceful算法的空间开销相同，而在合并序列过程中，由于FRMA算法不需要额外开辟部分空间以构造不同权重下的新拓扑，因此FRMA算法空间开销较小。

3.3.3序列长度评估

根据FRMA算法计算得到的权重序列对权重发生变化的链路进行调整，均能够确保网络无环收敛。

由于较短的序列使得对链路进行较少的调整次数，反之亦然，因此权重序列好坏的主要评估标准是序列长度。

对序列长度的评估分为以下两个方面：

首先给出FRMA算法|E|次仿真测试中序列长度分布的统计结果，以说明在大部分情况下只需要很短的权重序列就能够对链路进行调整，确保网络无环收敛，同时对可能影响序列长度的因素进行分析；