基于SSFnet环境的BGP快速收敛方法研究

吴学会　祁建松　郑超　吕思思

摘要：BGP协议是网络中最流行的域间路由协议之一，其具有路由控制机制丰富、稳定、安全的特点。BGP协议中路由选择受从相邻路由发出的UPDATE消息影响，由于AS选择各自的路由策略，这可能会导致收敛时间过长，丢失AS的数据包。采用调整MRAI定时器值的方式能实现减少收敛时间的效果，但也会带来如广播风暴这样的危害。该文提出了一种基于坏消息传的缓慢而好消息传播快的BGP快速收敛机制，通过修改不同类别消息的定时器值实现快速收敛。通过SSFnt工具仿真验证了该机制可以大幅减少收敛时间并在一定程度上减少冗余数据包的结论。

关 键 词：BGP；路由协议；快速收敛；SSFnet工具

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）14-0047-03

Abstract： The BGP protocol is the most popular protocol in the inter-domain routing， it has plenty of routing control mechanisms， to provide a stable and secure scheme. The attribute information of BGP routing depends on UPDATE messages received from the adjacent routing contained in the AS. It allows each AS routing strategy， which may lead to the convergence time is too long， the loss of AS packets. By modifying the MRAI timer value can reduce the convergence time in a certain extent， but also may have a negative impact on the broadcast storm. In this paper， we proposed a BGP fast convergence mechanism by modifying the timer depending on the message type based on the concept that the bad news travels slowly while the good news travels quickly in the Internet. By simulating our mechanism on the SSFnt， it draw the conclusion that it can greatly reduce the convergence time， as well as reducing the redundant packets to some extent.

Key words： BGP； routing protocol； fast convergence； SSFnet

1 引言

目前BGP协议是互联网上标准的域间路由协议，它在网络性能上扮演着重要的角色。该协议是路径向量协议，该协议中各个节点向它的相邻节点广播到目标地址的最佳路由信息。因此路由器在网络上通过该协议发送的UPDATE消息带有目标路径信息。一个BGP节点存储了发送到邻居中节点的所有路径，但仅使用和广播那些对于某些标准来讲最好的消息。如果这个首选的路径失败，那么BGP选择下一个后备的最优路由，这个路由会被广播到它的邻居节点，但不能保证这个后备的路由是有效的。为了防止这个后备的路由也是失败的，它将在发送一个撤销消息到它的邻居后替换这个路由消息，然后其它的备份路由将被选择。路由消息有效信息的缺乏导致 BGP在正确选择前可能已经选择了大量的后备路由。BGP是网间路由协议的标准，使用的最普遍，因此在撤销和公告周期中，所有BGP节点形成有效、稳定的目标路径之前，这里可能有相当大的延迟。最近的研究表明，节点发生故障后可能花费3到15分钟建立稳定的路由。

2基于消息分类的BGP收敛方法

本文提出一个简单的机制：通过对BGP的UPDATE消息分类和修改相应的定时器值来实现缓解路由器的负担和减少BGP收敛的时间。

2.1消息优先级分类

在方案中设置MARI定时器值的前提是对BGP的UPDATE消息进行优先级划分。从BGP消息接收器角度来看，如果BGP消息的目的地址是一个新地址，那么它对应较高的优先级。反之，它的优先级由UPDATE消息的状态是“on-tree”还是“off-tree”来决定。如果接收到的UPDATE消息是沿转发树的树干发送的那么它是“on-tree”状态，否则是在“off-tree”状态。在BGP路由协议中，子树节点知道它的父节点数据，但它的父节点不保存子节点的数据。因为处于“on-tree”状态的UPDATE消息可以立刻做出路由决策，因此它具有更高的优先级。

若UPDATE消息是撤回消息且为“on-tree”的状态，这说明前期删除的路径被使用，也表明这个路径是非常重要，应该具有更高的优先级。相反，表明删除的路径是一个可替代的路径，先前没有被使用过，所以应该对应到一个较低的优先级。如果UPDATE消息是一个“on-tree”状态的消息，这意味着有一个新的路径，可以替代先前通告的路径，这是一个好消息，它应该具有更高的优先级。如果UPDATE消息是一个“off-tree”状态，但比路径通告路径更好，即它是一个更短的路径，应该有更高的优先权，否则，它应该有低优先级。

对于通告消息的特别处理：对于相同目标，如果通告路径比前一个长，那么它是在收敛时间内产生的无效信息。为了删除网络中的该信息从而实现加快BGP收敛的目的，需要通知其它BGP路由先前通告的路径不再有效。即对于通告的消息，不管是 “on-tree”或“off-tree”状态，只要存在同一目的地址的路径较长的情况，就说明在网络中存在无效信息。在这种情况下，消息应该具有更高的优先级，节点需要向目标地址发送撤销消息，声明到达目标的先前路径是有效的。消息分类后，还需要通过以下两种方法进一步处理：

1）从接收端设置队列优先级：实现接收端对UPDATE消息的分类，最简单的方法是对消息设置不同的优先级。优点在于是通过转发表的检查容易判断消息的优先级。然而，接收机需要事先做大量的处理工作，从而提高接收机的负担。

2）从发送端设置队列优先级：发送端为带有不同优先级的消息设置不同的延时时间。使用BGP协议作为默认定时器值的消息设置较低优先级。定时器值较小的消息，则为它设置较高的优先级。该方式的优势在于可以减少BGP的收敛时间，只需要修改MRAL值就可以实现UPDATE消息在每一跳的时间较短。同时，利用该方法可以在相同时间内加快BGP收敛。

2.2 BGP 快速收敛算法

通过BGP的 UPDATE消息分类而进一步设置消息的优先级，实现快速收敛。如图2所示，该算法在BGP消息的发送端实现，高优先级的消息被直接发送，而低优先级的消息将被延迟发送。为加快使BGP收敛，低优先级消息的MRAI值设置为BGP协议的默认值，高优先级的MRAI设置为标准值的一半。

一个UPDATE消息发送时，需要检查消息类型，若是一个处于“on-tree”状态的撤回消息，则表明被删除的路径是转发树的一个分支，为达到加快BGP收敛目的，因此使用较小的MRAI定时器值发送；若是“off-tree”的状态，说明该路径从没有被使用过，推迟它不会影响目前路径的使用，因此这个撤销消息会被更晚发送从而实现降低BGP收敛处理过程中产生的消耗。

当一个通告消息发送，需要对通告的目标地址的新旧进行检验：若是新的地址，说明存在一个新的路径消息，这是好消息，需要设置较高的优先级；若是旧目标地址，并通告的路径比前一个更好，也就是说比前一个更短，那么这个通告消息应该具有更高的优先级。但若通告的路径比以前的更长，说明有无效路径信息存在，为了快速删除这些消息，无论定时器是否超时该消息都需要立即发送，并且发送者需要将目的地的路径设置为空。当接收到一个新的目标路径，因为不存在比空路径更短的路径，所以可以立即发布通告。该方式降低了网络中无效的消息和BGP收敛时间。

3仿真验证实验

通过SSFnet工具完成仿真，对生成一个新的路由和链路失效的路由两种情况进行测试。在每一个场景中，对ENCT、AENCT和 NEUM三个参数进行分析。

仿真结果：

（1）产生新路由的场景

在这种场景下测试了ENCT， AENCT， NEUM三个参数。测试节点的各个参数如表1所示。

（2） 链路故障的场景

在这种情况下，除了比较默认BGP和默认BGP MRAI 15算法的三参数，也与目前的BGP路由收敛算法ghost flushing和Root-Cause进行了比较。在比较中将默认BGP的MRAI定时器分别为30和15，Root-Cause的MRAI定时器为15。在每种拓扑结构，选择一个随机的节点与邻居节点的路由，并且这个节点广播到达邻居的目标地址，该地址带有网络前缀信息。实验将测试网络收敛达到稳定状态时切断与某个相邻节点间链路，观察该算法与其他算法的性能变化情况。

4 结论

本文研究了一个基于消息分类BGP快速收敛机制，实验将消息在转发过程中被按照状态进行分类，将处于“on-tree”状态的消息设置较高优先级和较小MRAI值；处于“off-tree”状态的消息设置较低优先级和较大的MRAI值。采用SSFNet仿真工具进行了模拟实验，结果表明该机制与默认BGP协议、Ghost flushing机制相比具有更小的BGP收敛时间。它具有与RNC机制类似的性能，且与其它机制相比较产生较少的UPDATE消息。

参考文献：

[1] 汪小滟.刍议BGP/VPN快速收敛技术[J]. 中国新技术新产品，2011（2）：40.

[2] 胡字滢，张涛. 基于路由更新链的BGP收敛性改进机制[J]. 计算机应用研究，2011（9）：3481-3484.

[3] 赵金晶，朱培栋，卢锡城. BGP收敛性及其对网络性能影响的定量分析[J]. 通信学报，2007（8）：24-33.

[4] 赵金晶，朱培栋，周丽涛. 域间路由协议BGP收敛时间的定量分析及预测[J]. 计算机工程与科学，2007（9）：56-57+63.

[5] 郭辉，常晋义.边界网关协议收敛问题研究综述[J]. 计算机应用，2010（10）：2628-2631.

[6] Dan Pei， Zhang B.An analysis of convergence delay in path vector routing protocols[J]. Computer Networks， 2006，30（3）：398–421.

[7] Villamizar C， Chandra R， Govindan R. BGP route flap damping[S].RFC 2439，November 1998.

[8] Griffin T G， Premore B J.An experimental analysis of BGP convergence time[J]. Proc. ICNP 2001， Riverside， California， 2001，11–14：53–61.

[9] Gao L. and Rexford J. Stable Internet routing without global coordination[J].IEE E /A CM Transactions on Networking，2001，9（6）：681-692.