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—），女，湖北武漢人，碩士。研究方向：通信與信息系統。