基于惩罚机制的OSPF路由振荡抑制算法

刘嵩 马琳 刘福强 海军装备研究院,北京 100036

基于惩罚机制的OSPF路由振荡抑制算法

刘嵩 马琳 刘福强 海军装备研究院,北京 100036

在当今的互联网中，路由振荡越来越成为影响网络服务质量的重大因素。为了解决此问题，提出了一种适用于开放式最短路径优先协议(OSPF)的路由振荡抑制算法。该算法借鉴边界网关协议(BGP)中的路由振荡抑制机制，引入惩罚值的概念，并结合OSPF的特点，将路由振荡抑制转化为相邻路由器之间的链路振荡抑制。仿真模拟显示，本算法可以有效地屏蔽振荡中的链路，大大减少了网络中LSA的产生数量，增加了网络的稳定性。

路由振荡；链路振荡；抑制

route flapping；link flapping；suppress；OSPF；BGP

路由表中的路由条目间断性的消失和再现的现象，称为路由振荡。路由振荡会导致路由器在互联网内周期性的更新、洪泛的更新或撤销链路消息，占用大量的网络带宽，同时不断的链路状态更新会引起频繁的最短路径优先路由重计算，加重CPU的负荷，严重时引起错误的路由重计算，导致大量丢包。

OSPF是一种专门为IP网络开发且广泛应用在单一自治系统内的路由协议，目前已成为事实上的域内路由协议标准。现有的OSPF中并无可靠的路由振荡抑制机制，而主要依靠若干定时器来削弱路由振荡带来的影响。如思科公司的路由产品在RFC2328标准外额外定义了延缓路由重计算的定时器SPFDelay，以减少路由振荡时的最短路径重计算。但这延长了收敛过程，易引起错误的路由重计算，极端情况下甚至适得其反。而且无法真正屏蔽路由振荡源，是一种消极的手段[1]。

域间路由协议BGP中基于惩罚机制的路由振荡抑制机制，在实践中被证明是行之有效的[2]。但OSPF是链路状态协议，BGP是距离矢量协议，这个根本不同点使BGP的路由振荡抑制算法无法直接应用在OSPF协议中。本文通过分析OSPF协议的特点，将路由振荡避免转化为链路振荡避免[3]。对不稳定链路进行惩罚，从而较好的改善网络性能。

1 OSPF原理

OSPF是一种分布式的链路状态协议（link state protocol）[4]，每个路由器向外通告与本路由器相邻的所有路由器的链路状态，最终所有的路由器都建立一个全网统一的链路状态数据库（link state database），这个数据库实际上就是全网的拓扑结构图。每一个路由器根据收敛后的链路状态数据库，以自己为起点，采用最短路径优先算法计算与目的节点之间的最佳路由，独立的构造出自己的路由表。

OSPF链路状态信息通过链路状态广播LSA（link state advertisement）表示，包括路由器ID、接口IP地址和相邻接口的IP地址、链路代价、序列号、年龄和校验和等内容。有多种LSA，用来描述不同的对象。其中路由器LSA最为重要，用来表示该路由器的各个端口所连接的对象和代价等信息。

路由器启动后，通过接口向外组播Hello分组，用以探测邻居，并开始建立邻接关系。经过确认主从关系、交换链路数据库摘要、请求新的LSA、发送和确认LSA等阶段后，链路状态数据库将完全一致，即达到完全邻接状态（Full Adjacent）。当链路状态改变或链路刷新时间到，路由器就更新和扩散LSA，同时接收其它节点洪泛的LSA，以保持全网的链路状态数据库是最新的。

OSPF同时定义了一些定时器来抑制过于快速的数据洪泛。如定义HelloInterval来禁止过快的Hello包发送，定义MinLsInterval来禁止过快的LSA更新，定义SPFDelay来禁止过于频繁的最短路径重计算。这也是目前OSPF抑制快速路由振荡的主要方法，但效果并不是很好。

2 路由振荡转化为链路振荡

图1 LSA平均更新数量比较

与距离矢量路由协议不同的是，OSPF的链路状态信息发送至全网，且仅发送与本路由器相邻的路由器的链路状态信息。当某条链路状态发生变化，该路由器就使用链路状态更新分组，用洪泛法向全网更新链路状态。该分组首先发送给相邻路由器，相邻路由器必须将接收到的分组再转发给除分组来源外的所有与自身相邻的路由器，如此反复。若收到相同的LSA的多个实例，将通过比较序列号、校验以及老化时间等参数判断最新的LSA，并更新旧的LSA。

由此可见，OSPF虽然将链路状态信息洪泛至全网，但链路信息首先被发送给相邻的路由器，再通过相邻路由器转发出去。尽管域内每个路由器都有全网的链路状态数据库，并能获知网内任意一条链路的变化，但它们互相之间传递信息却是基于本地的邻接关系。链路的更新信息只传递给邻居，再由邻居继续转发，而不会直接传递给域内的其它路由器。基于OSPF的这一特点，我们可以将路由振荡由目前的基于定时器的全网抑制转化为对本地链路振荡的抑制。对于处于振荡中的链路，相邻路由器将接收到的链路状态信息屏蔽，不再继续转发，该链路状态变化将只局限于与该路由器相邻的路由器范围内，而不会波及全网。即每一个路由器都只处理与自己相邻的路由器的链路变化。

3 基于惩罚机制的路由振荡抑制算法

算法的核心思想是：链路的每一次振荡都会被记录为不良记录，并增加一定的惩罚值，若惩罚值超过某个门限，该链路将会被抑制。被抑制的链路信息不会得到转发，不会参加最短路径重计算。链路稳定下来以后，链路的惩罚值会随时间慢慢减少，当惩罚值减少到重用门限以下时，解除链路抑制。

对振荡链路的抑制可能会影响网络可达性和代价最小原则，因此应设置一个最大链路抑制数。若被抑制的链路数量达到最大链路抑制数，则应提前解除对当前惩罚值最小的链路的抑制。下面描述详细的算法。

算法设置参数如下：

T：链路当前惩罚值的累计总额，初始值为0。

P：链路每振荡一次增加的惩罚值。

H：链路当前的状态，0表示未被抑制，1表示已经被抑制。

Ls：抑制门限，链路惩罚值超过抑制门限时将被抑制。

Lr：重用门限，处于被抑制状态的链路的惩罚值降到重用门限或以下时，将被解除抑制。

Ts：链路处于被抑制状态且已经稳定时，惩罚值的衰减速率。每过一个Ts周期，链路的惩罚值减半。这里的稳定是指一个Ts周期内，链路没有再次振荡。

Tr：链路处于未被抑制状态且已经稳定时，惩罚值的衰减速率。每过一个Tr周期，链路的惩罚值减少P。这里的稳定是指一个Tr周期内，链路没有再次振荡。

Tc：上次惩罚值进行衰减的时间点。惩罚值的衰减并不是连续性的衰减，而是在一个衰减周期后直接减去一定值，因此需要记录上一次衰减时的时间点。初始值为路由器刚启动的时间。

Md：最大抑制门限，每条链路的惩罚值T所能累积到的最大值。这是为了避免链路在短时间内的急剧振荡累积过高的惩罚值，导致链路在很长时间内都无法解除抑制。该值必须大于抑制门限，否则链路将永远不会被惩罚。

Cl：当前被抑制的链路数量，初始为0。

Ml：最大链路抑制数，每个路由器同时可抑制的最大链路数。为了避免链路被抑制过多而影响网络可达性，需限制路由器抑制链路数不大于Ml。

以上参数中除了说明初始值的外，其它都可以自行设置。Ls和P的比值越大，表示可容忍的振荡程度越高。Lr和Ls的比值越大，表示链路被抑制后的恢复时间越短。最大抑制门限Md应该由重用门限Lr、链路在惩罚状态时的衰减周期Ts和链路的最长抑制时间计算出来。假设衰减周期Ts为30分钟，链路的最长抑制时间为1小时，重用门限Lr为1000，则最大抑制门限Md=4000，这样才能保证在一个小时内经过两个半衰期，惩罚值衰减到重用门限Lr以便链路解除抑制。

最重要的两个参数是链路处于抑制状态时的惩罚值衰减周期Ts和链路处于未抑制状态时的惩罚值衰减周期Tr。Ts的值设置过小会导致链路可以迅速从被抑制状态恢复到正常状态，若这个恢复周期比链路振荡周期小，则算法起不到抑制振荡的作用。Ts的值也不能过大，因为过大就意味着链路长时间得不到恢复，即使链路已经稳定。对于Tr，它的值不应该过小，过小就意味着惩罚值衰减得太快，在对链路进行下一次惩罚时，可能前一次的惩罚值已经被清除了，起不到惩罚的作用。

算法的具体实施步骤如下所示：

1）路由器进行初始化，保存所有与自己相邻的路由器的所有链路，并对链路进行参数初始化。T=0，H=0，Cl=0，Tc为当前时间。

2）每当路由器检测到相邻路由器的某条链路产生振荡，就给这条链路增加一个单位惩罚值即T=T+P，若T>Md，则T=Md，同时Tc置为当前时间。若T>Ls，则令链路状态H=1，表示链路已经被抑制，路由器不再对外广播该链路信息，Cl=Cl+1。

3）若Cl>Ml，查找一条当前被抑制链路里最稳定的链路，即T最小的链路，提前解除对这条链路的抑制，Cl=Cl-1，重复执行该步骤直到不满足Cl>Ml。

4）若链路处于未被抑制状态下，检查从Tc到现在是否已经过了Tr时间。若是，惩罚值减去P即T=T-P。

5）若链路处于被抑制状态下，检查从Tc到现在是否已经过了Ts时间。若是，将当前惩罚值减半，即T=T/2。若T

4 仿真与性能分析

为了验证路由振荡抑制算法的可行性和有效性，我们将采用相关的仿真软件进行仿真。仿真包括对原OSPF算法的仿真和改进后算法的仿真，并对两种算法进行比较。路由振荡最显著的危害是频繁的向外更新LSA，占用网络带宽，同时引起路由器的最短路径重计算。因此将每个路由器的LSA更新数量作为本次仿真的对比指标。

我们使用BRite[5]拓扑生成器根据Waxman算法生成一个具有128个节点260条链路的随机网络拓扑，然后利用基于SSFNet[6]仿真实现的OSPF协议进行网络仿真。算法的各参数选取如下：P=1000，Ls=2000，Lr=750，Ts=15分钟，Tr=15分钟，Md=6000，Ml=2。仿真持续时间为120分钟，其中每隔10分钟，随机选取3对链路，在其间产生抖动（通过通断其间的链路来实现）。为避开MinLsInterval定时器，以便模拟OSPF里最坏情况下的路由振荡抑制，通断间隔定为7秒，2秒正常5秒断开，持续35秒。

图1给出了原OSPF路由振荡抑制算法和加入惩罚机制后的路由振荡抑制算法的仿真场景下，LSA的平均更新数量。从图中可以看出，在该参数下的仿真里，改进后的算法比原OSPF算法减少了约34%的LSA更新数量。

5 结语

本文针对OSPF的域内稳定性问题，提出一种基于惩罚机制的路由振荡抑制算法。通过记录历史振荡行为并进行惩罚来抑制不稳定链路，屏蔽振荡源。仿真实验表明，算法简单可行，能大大降低振荡时网络中LSA的洪泛数量，提高网络稳定性。

[1]Ohara Y, Bhatia M, Osamu N, et al. Route flapping effects on OSPF [A]. Proceedings of2003 Symposium on Applications and the Internet Workshops [C]. Orlando,USA: IEEE Computer Society,2003.232～237.

[2]IETF RFC2439. BGP Route Flap Damping [S].

[3]Wang F, Chen S. Z, Li X, et al. A Route Flap Suppression Mechanism Based on Dynamic Timers in OSPF Network.

[4]IETF RFC2328, OSPF version2[S].

[5]Medina A., Lakhina A, Mattal, et al. Brite: boston university representative internet topology generator [EB/OL]. (2004～03)[2008-10-26]. http:∥www.cs.bu.edu/brite.

[6]SSFNet. Scalable simulation framework for networkmodels [EB/OL]. (2003～05) [2008-10-26]. http:∥www.ssfnet.org.

OSPF，BGP OSPF Route Flapping Suppressed Algorithm Based on Punishment Mechanism

Liu Song Ma Lin Liu Fuqiang Naval Academy of Armament, Beijing,100036

Rout Flapping has become more and more serious as a factor on influencing the quality of service in toady’s internet. Aimed at solving the problem, this paper comes up with a Route Flapping Suppression Arithmetic which is fit for the Open Shortest Path First (OSPF). Absorbing the Rout Flapping Suppression mechanism from BGP, introducing the concept of punishment, plus combing the characteristics of the OSPF, the arithmetic method makes the rout flapping suppression shift to link flapping suppression of the neighboring routers. Analogue simulation has demonstrated that the arithmetic helps to improve the stability of the internet by shielding the oscillating link to reduce the number of the LSA appeared in the internet.

10.3969/j.issn.1001-8972.2012.07.019

刘嵩，男，（1974-），辽宁沈阳人，海军装备研究院，高级工程师，硕士，主要研究方向为网络及网络安全。

马琳，女，（1974-），河北唐山人，海军装备研究院，高级工程师，硕士，主要研究方向为网络及网络安全。

刘福强，男，（1976-），辽宁鞍山人，海军装备研究院，工程师，硕士，主要研究方向为网络及网络安全。