路由基于链路状态快速感知环路避免技术精灵论文

链路层劫持时间:2021-01-28 阅读:()

基于链路状态快速感知的环路避免技术精灵论文

基于链路状态快速感知的环路避免技术

阳碧云

(北京邮电大学网络与交换技术国家重点实验室北京100876)摘要:随着计

算机网络通信技术的发展人们对于通信质量的要求越来越高。但是网络的生存能力面临着

各种威胁因素增强网络在自然灾害、人为损害等情况下的生存能力成为一项非常重要的任

务。网络的生存能力可通过故障处理机制来保证运行动态路由协议的IP层通过路由协议

自身的路由收敛来实现对故障的处理如链路状态路由协议的路由收敛机制但是这样的故

障处理方式具有一定的局限性。例如:通过对OSPF协议的研究发现在其路由收敛过程中

必定存在一些不可用路由这些路由在收敛过程中无法使用但是这些不可用路由中存在一

部分含有环路的路由这些含有环路的路由在一定条件下却是可以避免的。

“基于链路状态快

速感知的环路避免技术”正是通过避免链路状态路由协议在路由收敛过程中的环路提高

OSPF的故障处理能力从而提高IP层故障处理能力提高网络的生存能力。路由收敛过

基础但是其一般性规律、适用网络环境及故障场景程中的环路避免技术已经有了一定理论

都还待进一步研究。 “基于链路状态快速感知的环路避免技术”是对这一技术的进一步的扩展

它在自适应路由控制系统的基础上充分利用自适应路由控制系统提供的条件 提出了一种

适用范围更广效率更高的避免路由收敛过程中的环路的方法。

关键词:网络生存性;OSPF;环路避免

中图分类号:TP393

Loop Avoiding Technology Based On Link-state Quickly

Perception

YANG Biyun

(State Key Lab of Networking and Switching Technology,Beijing University of Postsand

Telecommunications,Beijing 100876)

Abstract:With the development of computer network communication technology,people's requirements of the quality of communication is higher and higher.However, theviability of the network faces various threats,and to enhance the viability of the network innatural disasters or man-made damage become a very important task.The viability of thenetwork can be guaranteed by the error processing mechanism, the IP layer of the runningdynamic routing protocol achieve their own treatment of the fault through the routingprotocol convergence, such as the convergence routing mechanism of the link state routingprotocol,but such way of error treatment has some limitations.For example, through theresearching on OSPF protocol,we found that there will be some unavailable routing in the

route convergence processthere will be some route that contains a loop, these route can be avoided under certainconditions. "Loop avoiding technology based on link-state quickly perception" improve theability of error treatment of OSPF through avoiding the loop in route convergence processof link-state routing protocols,and it can improve the capacity of the troubleshooting of IPlayer,enhance the viability of the network.The technology to avoid loop in routeconvergence process has a certain theoretical basis,but the general rule and the adaptabilityof the network environment and the error scenarios are still to be further researched.

Key words:Network Survivability;OSPF; loop avoid

0引言

[1]OSPF路由协议是一种典型的链路状态路由协议通过路由器之间通告网络接口状态

[1]来建立链路状态数据库生成最短路径树每个OSPF路由器使用这些最短路径构造路由

作者简介:阳碧云(1986-) 女固网IGP路由技术.E-mail:

表。在网络拓扑发生变化时 OSPF路由协议会根据当前网络拓扑对路由表进行调整。路由

[1] [2] [3]调整过程也可称之为路由收敛过程。这个过程从网络发生故障开始包括检测故障全网洪范故障信息路由重计算等一系列环节直到新的路由表生成。在路由收敛过程中存

[4]在不可用的路由含有环路的路由也是其中一种。这样的含环路由在收敛过程中产生随收敛的结束而结束。因而避免路由收敛过程中产生环路可以提高OSPF路由协议的性能。

本文通过对路由收敛过程中环路产生的原因进行分析分析得出环路避免的基本原理 并利用此基本原理开发出基于网络状态快速感知的环路避免技术最后在仿真平台上实现了

行评估。该项技术并对其仿真性能进

本文第一章介绍了OSPF路由收敛过程中含环路由产生的原因第二章介绍了含环路由的避免方法和环路避免的基本原理第三章介绍了环路避免机制在OSPF路由协议控制系统上的实现方法第四章介绍了在仿真平台上实现的环路避免机制并对其性能进行了分析。

1环路产生原因

[1]OSPF路由协议是一个内部网关协议在一个运行OSPF协议的自治系统内所有网络节点都维持着一个相同的、完整的链路状态数据库此数据库描述了这个自治系统内部的所有链路信息每个节点都是利用自己维护的链路状态数据库形成路由表。当网络拓扑发生变

[1]化时路由器将检测到新的链路状态信息并在网络中洪范发现网络拓扑改变的路由器将对路由表进行重计算。但是网络中各个路由器发现拓扑改变的时间是不可能完全同步的一般来说离故障处近的路由器会较早收到路由改变信息这就造成了个路由器所维护的链路状态数据库不一致根据不一致的链路状态数据库进行了路由重计算就会可能产生一些不能

[4] [5] [6]用的路由。含环路由正是因此而产生的。下面来分析一个网络在故障发生之后的路由重计算的过程中环路的产生情况。

如下图所示的网络中如果IP->KC在某个时间发生故障之后按照链路状态路由协议进行收敛。

图1网络拓扑1

Fig. 1 first network topology

在故障发生之前从WA到KC、DN、 ST及SV的路由下一跳都是NY;而在发生故障之后收敛完毕之后将得到的最终的路由表中NY到KC、DN、 ST及SV的路由下一跳将是WA。

那么在路由表收敛的过程中则可能出现两种情形:如果NY比WA先重新计算路由

表那么在NY重新计算路由表之后到WA重新计算

路由表之前NY与WA之间将出现环路;如果WA比NY先重新计算路由表那么NY与WA

不会出现环路。

OSPF路由协议并不约束路由表的计算次序路由重计算次序是随机的所以环路的产生也是随机的。

2环路避免原理

从图1所示的例子可以看出环路的产生与路由重计算的次序紧密相关。如果让OSPF自由收敛WA与NY的收敛顺序将是随机的那么在这个收敛过程中就有可能出现环路;但是如果能让WA比NY先更新路由表则可以避免收敛过程中的NY与WA之间的环路。

也就是说收敛过程中含环路由的出现与否由路由表更新次序决定。如果在网络拓扑发生改变之后先让网络中所有路由器快速获取到所有故障链路的信息然后根据这些信息确定符合环路避免要求的路由表更新次序就能够避免在收敛过程中出现路由环路实现环路避免。实现环路避免的关键问题就在于确定路由器的路由表更新次序。那么网络拓扑发生改变之后怎样的更新次序才能避免环路的产生呢,

在同个路由表中不同的路由条目可能受到不同的故障链路的影响 因而不同路由条目符合环路避免要求的更新时间可能不相同。所以需要对一个路由器中的每一条路由条目考虑其合适的更新次序。

图2为任一路由表中某条路由条目的示意图。

图2任意一条路由条目(R0-d)

Fig.2 a route entry(R0-d)

假设在路由器R{l1, l2,…,ls}中有路由条目R0->d用SPath(R0 d)表示故障发生前或故障恢复后的最短路径。即当链路权值增大或发生故障时最短路径S P ath(R0 d)将会在路由重计算之后改变;而当链路权值减小或故障恢复时最短路径S P ath(R0 d)将会在进行更新之后被添加到新的路由表中。

在S P ath(R0 d)上:

1)N是下一跳;

2)S={R1  R2,…,Ri}所有到目的网段d的最短路径包含S P ath(R0 d)这一段的路由器包含直接与R0相邻和不相邻的所有路由器;

3)S n={R1  R2,…,Rm}所有到目的网段d的最短路径包含S P ath(R0 d)这一段且直接与R0相邻路由器;

4)L={l1,l2,…,lj}所有SPath(R0 d)上发生变化的链路;

5)T={N,…,D}在S Path(R0 d)上从源节点R0之后的节点N开始到目的网段d之前的节点D结束的所有路由节点集合。

假设拓扑发生变化的链路L={l 1,l2,…,lj}在最短路径SPath(R0 d)上并且最短路径S P ath(R0 d)是链路权值增大或发生故障之前的原始最短路径或者链路权值减小或故障恢复之后的新的最短路径。称集合S中的节点R1~Ri为上游节点集合T中的节点N~D为下游节点。

2.1环路避免方法

在链路权值增大或发生故障的情形下最短路径S P ath(R0 d)改变之后的下一跳也许将会是上游节点中的某一个。如果R0比上游节点先更新那么就有可能出现环路了。因而 若想保证绝对不出现环路则必须保证R0在所有的上游节点之后更新。同理 R0要在所有下游节点之前更新。

在链路权值减小或故障恢复的情形下最短路径S P ath(R0 d)的下一跳也许是上游节点中的某一个。如果上游节点比R0先更新那么就有可能出现环路了。因而若想保证绝

保证R0在所有的上游节点之前更新。同理 R0要在所有下游节点之对不出现环路则必须

后更新。

从以上两节的分析中还可以得知任意一条包含事件链路的路由条目的更新时间总是处于上游邻居路由器与下游邻居路由器相同路由条目的更新时间中间。

2.2路由更新次序计算原理

在一个自治系统内部根据故障发生前或故障恢复后的网络拓扑可以确定其中所有路

[4]由器中每一路由条目符合环路避免要求的更新序列次序。用Rank值来表示此更新次序例如 Rank(R d)表示路由器R目的网段d的Rank值。假设Rank(R d)等于0表示路由器R中目的网段为d的路由条目可以在最先更新不需要等任何其他路由器。假设Rank(R d)等于5表示路由器R要等Rank值小于5的所有其他路由器中Rank值小于5的路由条目更新完毕才能进行更新。

如图2所示 当链路权值增大或发生故障时,R0->d这个路由条目合适的更新时机就是S集合中的所有路由器完成到目的网段d的路由条目的更新之后。 R0->d的更新等级则是S集合中所有路由器的等级的最大值再加1。当链路权值减小或故障恢复时,R0->d这个路由条目合适的更新时机就是S集合中的所有路由器完成到目的网段d的路由条目的更新之前。 R0->d的更新等级则是S集合中所有路由器的等级的最小值减1 。

下面给出故障发生或恢复这两种情形下Rank(R d)的计算公式。

(一)链路权值增大或发生故障

Rank(R d)=min{depth(R rS PTold(lk)) | lk?Paths(R d)}

其中 rSPTold(lk)表示所有经过lk的最短路径组成的一棵逆向树 depth(RrSPTold(lk)表示R在逆向树中中的深度。证明:假设链路权值增大或发生故障之前的路由表中路由

器N是路由器R到目的网段d的最短

路径上的任意路由器。

假设{l1, l2,…,ls}在Paths(N d)上而{ls+1, ls+2,…,ls+t}仅在Paths(R d)上。

Rank(N d)=min{depth(N rSPTold(li)) | 1?i?s}

Rank(R d)=min{depth(R rSPTold(li)) | 1?i?s+t}

因为任取i(1?i?s) depth(R rSPTold(li))<depth(N rSPTold(li))

所以 Rank(R d)<Rank(N d) 所以能保证R比任意N都要先更新到目的网段d的路由条目。

(二)链路权值减小或故障恢复