BGP Add-path的研究与实现

王 婷，程友清，邓冬平

（1.武汉邮电科学研究院　湖北 武汉430000；2.武汉烽火网络责任有限公司　湖北　武汉 430000）

BGP Add-path的研究与实现

王 婷1，2，程友清2，邓冬平2

（1.武汉邮电科学研究院湖北 武汉430000；2.武汉烽火网络责任有限公司湖北武汉 430000）

现有的BGP标准实现中，BGP只向邻居通告一条最优路径，从而隐藏了其他路径信息，且最佳路径失效时重新收敛较缓慢。本文针对路径信息隐藏问题，提出一种新的机制，对于同一NLRI，允许BGP通告和接收多路径。实验结论证明，此方案完全可以基于现有的软件平台，由管理员或者运营商自行选择是否配置Add-path。在典型的路由反射器拓扑中，配置邻居间通告和接收Add-path，客户端能够从反射器学习多条路由而不是只有一条反射器选择的最优路径，从而自身能够选择更好的路由。此外，增加路径多样性还能够帮助实现负载分担，通过对多路径精心的选择，还能够预防路由震荡。

多路径；选择算法；收敛；路由震荡

BGP是一种外部网关协议（EGP），在许多网络中得到广泛的应用，与OSPF、RIP等内部网关协议不同，它自身不计算和发现路由，而是控制路由的传播和根据选路算法计算最佳路由，基本功能是在自制系统间自动交换无环路的路由信息［1］。

BGP为路由信息携带丰富的属性，标准的BGP实现中，根据这些属性信息以及选路规则选择一条最佳路由，通告给BGP对等体。因此对于同一NLRI，实际网络拓扑中可能存在多条路径，但BGP只选择一条最佳路径，其他的路径信息则被隐藏，当这条最优路径失效时，BGP需要重新选择新的最佳路径，这一系列收敛过程比较缓慢。其次，在配置了路由反射器（RR）的拓扑中，RR选择并向客户端通告的路径，对于客户端来说可能并不是最优路径［2］。文中提出一种新的机制，对于同一NLRI，允许BGP通告多条路径。

1　Add-path能力的提出

Add-path即允许BGP对等体间交换NLRI信息时，对同一NLRI可通告多条路径的能力。

配置了反射器的基本拓扑如图1所示。

图1　配置了RR的基本拓扑

未配置Add-path时，D路由器只能学习到一条最优路径A。

假定A在通告路由时将下一跳设为自己，则当A到E的链路失效时，恢复D到目的地XYZ间的连通性会经历以下几个步骤：

A发送UPDATE更新撤销路径A；

RR1收到撤销通告，并向所有的客户端发送撤销消息；

B收到撤销路径A的通告，将重新选择B作为新的最佳路径，并向RR1发送UPDATE更新 （RR1配置了bestexternal，链路未失效时，RR1上只有路径A）；

RR1选择B作为新的最佳路径，并向客户端A、C、D通告路径B；

D重新选择路径B作为新的最佳路径，并更新转发表。自此，D到目的XYZ的流量恢复。

而使用Add-path，在上文描述的链路失效场景中，收敛时间将相应的减少。主要原因是Add-path能力使得D能够学习到XYZ的多条路径，当A到E之间的链路失效时，重新收敛所需的步骤为1、2、5。

可见，通告多路径后，当主链路故障时可以快速收敛，EBGP间的UPDATE更新信息也减少了。通过对路径精心的选择，Add-path还能预防路由震荡。其次，如果在转发表中下发多条路径，还有助于实现负载分担。

2　Add-path的实现分析

为了能够从邻居学习特定地址族 （AFI=x,SAFI=y）同一NLRI的多条路径，BGP会话建立阶段的能力通告应该指出，对端想要发送AFI=x，SAFI=y地址族的多路径，本端要接收相应地址族AFI=x，SAFI=y的多路径。反之。

本地路由器的Add-path能力必须是针对每邻居和每地址族配置，且应该支持send-only或者receive-only操作。默认的模式是同时发送和接收，IANA已经为能力通告分配了编码69［3］。

为允许通告多路径，需要为路径增加一个新的标识符。为携带路径标识符，对现有NLRI格式进行修改，在NLRI之前增加4字节路径标识符字段。如图2所示。

图2　NLRI扩展格式

path identifier只具有本地意义，实现中应由多路径发送端选择分配算法和对应的序列空间，接收端根据区分同一从add-path peer接收的多路径。接收端不应假定path identifier有任何其他意义。其次应格外小心邻居重启后path identifier的处理［4］。

当前BGP的标准实现中，对于特定邻居通告的NLRI，如果该邻居再次通告此NLRI，但对应的路径不同，则新的路径覆盖旧的路径。

当Add-path Speaker协商后对某邻居某地址族 （AFI= X,SAFI=Y）支持多路径能力，那么该邻居发送的地址族（AFI =X,SAFI=Y）所有的通告和撤销应包含path id。如果接收端从邻居接收的NLRI和path id是唯一的，则将该路由添加到RIB-IN，否则，新的路由替代旧的路由。

多路径会相应的增加控制平面以及内存的压力，首先接收端需要存储多条路径，发送端需要计算需要通告给邻居的路径，其次当这些多路径发生改变时，还应处理产生的路由变动。特别提出的是，由于唯一标识一条路径，因此，BGP发言者在通告一条路径的更新消息时，如果此前已经通告过这条路径，则重新通告路径时，应该携带旧的path-id。类似的，邻居在执行优雅重启的过程中，为了保证业务不中断，不会删除旧的路由，而是将路由设置为stale状态，此时重新通告路由消息时，也应该保证path-id值的一致。

首先分析4种基本的路径选择模式，有些模式的实现只能停留在理论分析上，给实际开发提供一些参考［5-6］。

1）通告N条路径，N的默认值为2，命令行可配置

这种模式下向邻居最多通告N条路径，为了保证路径选择的一直想，需要路径选择算法，选择N条路径，且这N条路径是严格排序的。

选择的过程是进行N次迭代，每次迭代的候选路径应满足以下条件：

①在之前的迭代中没有被选择；

②跟前面的迭代过程中选择的的路径不同；

③没有被策略过滤。

2）通告所有的路径

这种模式可以使邻居学习到全部的路径信息，但由于要交换更多的路径信息，BGP初始化收敛时需要通告的消息量将十分庞大，收敛速度也会变慢，且实际应用时路径的数量不可预估。

3）通告AS范围的最优多路径

前面我们分析了在配置了路由反射器的网络中存在的问题，即RR通告给client的最佳路由是基于反射器自身的选择，但这条路由往往对client来说可能并不是最佳的。由此联想到，我们在选择路径时，不计算IGP开销，计算开销减小了，但这种模式很难预测会有多少条路径被选择，若采用此种选择路径的思路，则应限定选择多路径的数目上限。

4）通告AS范围最优多路径 和AS范围次优多路径

这是对前面一种选择模式的衍生，首先选择AS范围的最佳路径，然后剩余的路径在再执行一次选择过程。

通告所有的路径是不可取的，因为接收端需要存储的路径数目不可预估，可以选择通告N条路径，N值根据实际应用的需求命令行可配置。例如，为了实现快速链路恢复，N值可以取2，而如果是负载分担，N可以再取稍大一点的值。

设想向两个邻居peer_m和peer_n通告多路径的情形，配置的多路径数目相应的为M和N（M

N条路径的选择过程为N次迭代，假设一共有M条路径：

第一次选择优先级最高的最佳路径；

第二次从剩余的M-1条路径中选择优先级最高的路径；

…

依次迭代,直到N次迭代完毕（N>=M），或者没有剩下的路径可选择（M

3　仿真结果分析

测试拓扑如图3。

图3　仿真拓扑

其中RR为反射器，R1、R2、R3配置为RR的客户端。

R1和R2均向RR通告一条到CE的路由，RR能够学习到两条到CE的路由，下一跳分别是R1和R2，在未进行任何add-path能力配置时，RR只向R3通告一条路由，查看R3上的BGP路由表只有一条到CE的路由；

RR上配置add-path send，R3上配置add-path recv后，RR和R3间邻居会重启，双方进行能力通告后，RR向R3通告2条到CE的路由 （这里，我们默认的add-path路由的N值为2，命令行可配置N值），在R3上查看BGP路由表我们能够看到两条到CE的路由。根据BGP的最佳路由选路原则，R1的router-id值较小，因此R3选择下一跳为R1的路由转发流量。

两种场景下，断开R1和RR间链路，R3到CE的路由将重新收敛，但配置了add-path的场景中，由于R3学习到两条路由，收敛期间需要交互的信息减少，RR只需向R3通告失效链路的撤销。

表1　仿真结果对比

可见使能了add-path能力，R3能够学习多条路由，且最佳链路失效时，收敛时间稍有改善。

自此基本实现了add-path路由的通告和接收处理，后期还需要完善，如果条件允许能够搭建图一所示的拓扑，收敛时间改善应该更显著。而R3由于增加路径多样性带来的好处，前文已经介绍，这里也不再赘述。

应注意到，对每一前缀通告多条路径，需要更多的内存和状态信息。没有实现Add-path的BGP发言者为每前缀每邻居维护发送状态信息，用来表示该前缀已经通告给该邻居。在Add-path实现中，这些状态信息应该是每路径每邻居的，因此，如果到达某一前缀的路径有n条，那么维护发送信息所需的内存相应的为之前的n倍。实现中可以进行优化，比如共享某些路径属性，这样可以减少一些内存压力。接收多条路径也需要更多内存和状态信息，因为在Adj-RIB-Ins中每条路径是分离的实体。

如前文所述，Add-paths能够帮助路由器选择更多的最佳路径，并能够改善由于路径信息学习不全从而引起的路由震荡。如果AS内的路由器对某一目的地的路由不能够做出一致的选择，可能发生路由震荡，甚至造成流量丢失。

优化Add-path的扩展性与路由稳定性目标可能互相矛盾，因此运营商应该根据自己的配置需求做出一定的折中。

BGP有丰富的策略，可以对通告的路径属性进行修改，但这样可能导致邻居路由选择的不一致。类似的，IBGP中路由过滤策略的使用不当，也可能导致路由选择的不一致，从而产生环路。Add-path特性对于路由过滤应做额外考虑，因为接收端无法对收到NLRI对应的多路径判断哪一个是发送端的主路径。发送端应当发送最佳路径，接收端在选择路径时应格外小心，不要丢弃了最佳路径，而选择了备份路径。无论是发送端还是接收端，发送或者接收最佳路由时的错误操作都可能导致路由选择的不一致。

4　结束语

本文提出的Add-path旨在增加路径多样性，能够加快BGP在最佳路径失效时的收敛过程，减少收敛期间的需要交互的UPDATE更新信息。此外，在配置了反射器的拓扑中，多路径可能帮助客户端选择更优的路径，还能够在一定程度上预防路由震荡。实现方面，笔者根据代码编写和调试过程，提出了Add-path实现过程相关的一些建议，多路径无疑会增加内存的压力，对于多路径中共同的路径属性，存储上可以进行优化。

［1］IETF.RFC4271,A Border Gateway Protocol 4［S］.New York:The Internet Engineering Task Force,2006.

［2］RaszukR,CassarC,Aman E,DecraeneB,LitkowskiS.BGP Optimal Route Reflection［EB/OL］.［2015-07-02］.https://datatracker.ietf.org/doc/draft-ietf-idr-bgp-optimal-route-reflection/.

［3］WaltonD,RetanaA,Chen E,Scudder J.Advertisement of Multiple Paths in BGP［EB/OL］.［2014-10-24］.https://datatracker.ietf.org/doc/draft-ietf-idr-add-paths/.

［4］IETF.RFC 4724,Graceful Restart Mechanism for BGP［S］.New York:The Internet Engineering Task Force,2007.

［5］UttaroJ,FrancoisP,PatelK.Best Practices for Advertisementof Multiple Paths inIBGP［EB/OL］.［2014-12-04］.https://datatracker.ietf.org/doc/draft-ietf-idr-add-paths-guidelines/.

［6］A Retana,Advertisement of Multiple Paths in BGP:Implementation Report［EB/OL］.［2015-04-10］.https://datatracker.ietf.org/doc/draft-ietf-idr-add-paths-implementation/.

Research and design of BGP Add-path capability

WANG Ting1，2,CHENG You-qing2,DENG Dong-ping2
（1.Wuhan Research Institute of Posts and Telecommunications，Wuhan 430000,China；2.FiberHome Networks Co.，Ltd.，Wuhan 430000,China）

In this paper,we propose a BGP extension that allows the advertisement of multiple paths for the same address prefix without the new paths implicitly replacing any previous ones,which would help to reduce the convergence time in cases of failure and offer the potential for loading-balancing.Multiple paths can also help to improve path visibility in IBGP system where route reflector is employed,cause the route reflector always choose the best path based on it's own decision process, with more paths accepted from RR,the client will choose a more efficient path.Besides,with the appropriate path selection algorithm,Add-path can also prevent routing oscillations.

multiple paths；path selection algorithm；convergence

TN91

A

1674－6236（2016）13-0123-03

2015-07-15稿件编号：201507114

王 婷（1989—），女，湖北武汉人，硕士。研究方向：通信与信息系统。