王 婷，程友清，鄧冬平

（1.武漢郵電科學(xué)研究院　湖北 武漢430000；2.武漢烽火網(wǎng)絡(luò)責(zé)任有限公司　湖北　武漢 430000）

BGP Add-path的研究與實現(xiàn)

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

（1.武漢郵電科學(xué)研究院湖北 武漢430000；2.武漢烽火網(wǎng)絡(luò)責(zé)任有限公司湖北武漢 430000）

現(xiàn)有的BGP標(biāo)準(zhǔn)實現(xiàn)中，BGP只向鄰居通告一條最優(yōu)路徑，從而隱藏了其他路徑信息，且最佳路徑失效時重新收斂較緩慢。本文針對路徑信息隱藏問題，提出一種新的機制，對于同一NLRI，允許BGP通告和接收多路徑。實驗結(jié)論證明，此方案完全可以基于現(xiàn)有的軟件平臺，由管理員或者運營商自行選擇是否配置Add-path。在典型的路由反射器拓?fù)渲?，配置鄰居間通告和接收Add-path，客戶端能夠從反射器學(xué)習(xí)多條路由而不是只有一條反射器選擇的最優(yōu)路徑，從而自身能夠選擇更好的路由。此外，增加路徑多樣性還能夠幫助實現(xiàn)負(fù)載分擔(dān)，通過對多路徑精心的選擇，還能夠預(yù)防路由震蕩。

多路徑；選擇算法；收斂；路由震蕩

BGP是一種外部網(wǎng)關(guān)協(xié)議（EGP），在許多網(wǎng)絡(luò)中得到廣泛的應(yīng)用，與OSPF、RIP等內(nèi)部網(wǎng)關(guān)協(xié)議不同，它自身不計算和發(fā)現(xiàn)路由，而是控制路由的傳播和根據(jù)選路算法計算最佳路由，基本功能是在自制系統(tǒng)間自動交換無環(huán)路的路由信息［1］。

BGP為路由信息攜帶豐富的屬性，標(biāo)準(zhǔn)的BGP實現(xiàn)中，根據(jù)這些屬性信息以及選路規(guī)則選擇一條最佳路由，通告給BGP對等體。因此對于同一NLRI，實際網(wǎng)絡(luò)拓?fù)渲锌赡艽嬖诙鄺l路徑，但BGP只選擇一條最佳路徑，其他的路徑信息則被隱藏，當(dāng)這條最優(yōu)路徑失效時，BGP需要重新選擇新的最佳路徑，這一系列收斂過程比較緩慢。其次，在配置了路由反射器（RR）的拓?fù)渲?，RR選擇并向客戶端通告的路徑，對于客戶端來說可能并不是最優(yōu)路徑［2］。文中提出一種新的機制，對于同一NLRI，允許BGP通告多條路徑。

1　Add-path能力的提出

Add-path即允許BGP對等體間交換NLRI信息時，對同一NLRI可通告多條路徑的能力。

配置了反射器的基本拓?fù)淙鐖D1所示。

圖1　配置了RR的基本拓?fù)?/p>

未配置Add-path時，D路由器只能學(xué)習(xí)到一條最優(yōu)路徑A。

假定A在通告路由時將下一跳設(shè)為自己，則當(dāng)A到E的鏈路失效時，恢復(fù)D到目的地XYZ間的連通性會經(jīng)歷以下幾個步驟：

A發(fā)送UPDATE更新撤銷路徑A；

RR1收到撤銷通告，并向所有的客戶端發(fā)送撤銷消息；

B收到撤銷路徑A的通告，將重新選擇B作為新的最佳路徑，并向RR1發(fā)送UPDATE更新 （RR1配置了bestexternal，鏈路未失效時，RR1上只有路徑A）；

RR1選擇B作為新的最佳路徑，并向客戶端A、C、D通告路徑B；

D重新選擇路徑B作為新的最佳路徑，并更新轉(zhuǎn)發(fā)表。自此，D到目的XYZ的流量恢復(fù)。

而使用Add-path，在上文描述的鏈路失效場景中，收斂時間將相應(yīng)的減少。主要原因是Add-path能力使得D能夠?qū)W習(xí)到XYZ的多條路徑，當(dāng)A到E之間的鏈路失效時，重新收斂所需的步驟為1、2、5。

可見，通告多路徑后，當(dāng)主鏈路故障時可以快速收斂，EBGP間的UPDATE更新信息也減少了。通過對路徑精心的選擇，Add-path還能預(yù)防路由震蕩。其次，如果在轉(zhuǎn)發(fā)表中下發(fā)多條路徑，還有助于實現(xiàn)負(fù)載分擔(dān)。

2　Add-path的實現(xiàn)分析

為了能夠從鄰居學(xué)習(xí)特定地址族 （AFI=x,SAFI=y）同一NLRI的多條路徑，BGP會話建立階段的能力通告應(yīng)該指出，對端想要發(fā)送AFI=x，SAFI=y地址族的多路徑，本端要接收相應(yīng)地址族AFI=x，SAFI=y的多路徑。反之。

本地路由器的Add-path能力必須是針對每鄰居和每地址族配置，且應(yīng)該支持send-only或者receive-only操作。默認(rèn)的模式是同時發(fā)送和接收，IANA已經(jīng)為能力通告分配了編碼69［3］。

為允許通告多路徑，需要為路徑增加一個新的標(biāo)識符。為攜帶路徑標(biāo)識符，對現(xiàn)有NLRI格式進行修改，在NLRI之前增加4字節(jié)路徑標(biāo)識符字段。如圖2所示。

圖2　NLRI擴展格式

path identifier只具有本地意義，實現(xiàn)中應(yīng)由多路徑發(fā)送端選擇分配算法和對應(yīng)的序列空間，接收端根據(jù)區(qū)分同一從add-path peer接收的多路徑。接收端不應(yīng)假定path identifier有任何其他意義。其次應(yīng)格外小心鄰居重啟后path identifier的處理［4］。

當(dāng)前BGP的標(biāo)準(zhǔn)實現(xiàn)中，對于特定鄰居通告的NLRI，如果該鄰居再次通告此NLRI，但對應(yīng)的路徑不同，則新的路徑覆蓋舊的路徑。

當(dāng)Add-path Speaker協(xié)商后對某鄰居某地址族 （AFI= X,SAFI=Y）支持多路徑能力，那么該鄰居發(fā)送的地址族（AFI =X,SAFI=Y）所有的通告和撤銷應(yīng)包含path id。如果接收端從鄰居接收的NLRI和path id是唯一的，則將該路由添加到RIB-IN，否則，新的路由替代舊的路由。

多路徑會相應(yīng)的增加控制平面以及內(nèi)存的壓力，首先接收端需要存儲多條路徑，發(fā)送端需要計算需要通告給鄰居的路徑，其次當(dāng)這些多路徑發(fā)生改變時，還應(yīng)處理產(chǎn)生的路由變動。特別提出的是，由于唯一標(biāo)識一條路徑，因此，BGP發(fā)言者在通告一條路徑的更新消息時，如果此前已經(jīng)通告過這條路徑，則重新通告路徑時，應(yīng)該攜帶舊的path-id。類似的，鄰居在執(zhí)行優(yōu)雅重啟的過程中，為了保證業(yè)務(wù)不中斷，不會刪除舊的路由，而是將路由設(shè)置為stale狀態(tài)，此時重新通告路由消息時，也應(yīng)該保證path-id值的一致。

首先分析4種基本的路徑選擇模式，有些模式的實現(xiàn)只能停留在理論分析上，給實際開發(fā)提供一些參考［5-6］。

1）通告N條路徑，N的默認(rèn)值為2，命令行可配置

這種模式下向鄰居最多通告N條路徑，為了保證路徑選擇的一直想，需要路徑選擇算法，選擇N條路徑，且這N條路徑是嚴(yán)格排序的。

選擇的過程是進行N次迭代，每次迭代的候選路徑應(yīng)滿足以下條件：

①在之前的迭代中沒有被選擇；

②跟前面的迭代過程中選擇的的路徑不同；

③沒有被策略過濾。

2）通告所有的路徑

這種模式可以使鄰居學(xué)習(xí)到全部的路徑信息，但由于要交換更多的路徑信息，BGP初始化收斂時需要通告的消息量將十分龐大，收斂速度也會變慢，且實際應(yīng)用時路徑的數(shù)量不可預(yù)估。

3）通告AS范圍的最優(yōu)多路徑

前面我們分析了在配置了路由反射器的網(wǎng)絡(luò)中存在的問題，即RR通告給client的最佳路由是基于反射器自身的選擇，但這條路由往往對client來說可能并不是最佳的。由此聯(lián)想到，我們在選擇路徑時，不計算IGP開銷，計算開銷減小了，但這種模式很難預(yù)測會有多少條路徑被選擇，若采用此種選擇路徑的思路，則應(yīng)限定選擇多路徑的數(shù)目上限。

4）通告AS范圍最優(yōu)多路徑 和AS范圍次優(yōu)多路徑

這是對前面一種選擇模式的衍生，首先選擇AS范圍的最佳路徑，然后剩余的路徑在再執(zhí)行一次選擇過程。

通告所有的路徑是不可取的，因為接收端需要存儲的路徑數(shù)目不可預(yù)估，可以選擇通告N條路徑，N值根據(jù)實際應(yīng)用的需求命令行可配置。例如，為了實現(xiàn)快速鏈路恢復(fù)，N值可以取2，而如果是負(fù)載分擔(dān)，N可以再取稍大一點的值。

設(shè)想向兩個鄰居peer_m和peer_n通告多路徑的情形，配置的多路徑數(shù)目相應(yīng)的為M和N（M

N條路徑的選擇過程為N次迭代，假設(shè)一共有M條路徑：

第一次選擇優(yōu)先級最高的最佳路徑；

第二次從剩余的M-1條路徑中選擇優(yōu)先級最高的路徑；

…

依次迭代,直到N次迭代完畢（N>=M），或者沒有剩下的路徑可選擇（M

3　仿真結(jié)果分析

測試拓?fù)淙鐖D3。

圖3　仿真拓?fù)?/p>

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

R1和R2均向RR通告一條到CE的路由，RR能夠?qū)W習(xí)到兩條到CE的路由，下一跳分別是R1和R2，在未進行任何add-path能力配置時，RR只向R3通告一條路由，查看R3上的BGP路由表只有一條到CE的路由；

RR上配置add-path send，R3上配置add-path recv后，RR和R3間鄰居會重啟，雙方進行能力通告后，RR向R3通告2條到CE的路由 （這里，我們默認(rèn)的add-path路由的N值為2，命令行可配置N值），在R3上查看BGP路由表我們能夠看到兩條到CE的路由。根據(jù)BGP的最佳路由選路原則，R1的router-id值較小，因此R3選擇下一跳為R1的路由轉(zhuǎn)發(fā)流量。

兩種場景下，斷開R1和RR間鏈路，R3到CE的路由將重新收斂，但配置了add-path的場景中，由于R3學(xué)習(xí)到兩條路由，收斂期間需要交互的信息減少，RR只需向R3通告失效鏈路的撤銷。

表1　仿真結(jié)果對比

可見使能了add-path能力，R3能夠?qū)W習(xí)多條路由，且最佳鏈路失效時，收斂時間稍有改善。

自此基本實現(xiàn)了add-path路由的通告和接收處理，后期還需要完善，如果條件允許能夠搭建圖一所示的拓?fù)?，收斂時間改善應(yīng)該更顯著。而R3由于增加路徑多樣性帶來的好處，前文已經(jīng)介紹，這里也不再贅述。

應(yīng)注意到，對每一前綴通告多條路徑，需要更多的內(nèi)存和狀態(tài)信息。沒有實現(xiàn)Add-path的BGP發(fā)言者為每前綴每鄰居維護發(fā)送狀態(tài)信息，用來表示該前綴已經(jīng)通告給該鄰居。在Add-path實現(xiàn)中，這些狀態(tài)信息應(yīng)該是每路徑每鄰居的，因此，如果到達某一前綴的路徑有n條，那么維護發(fā)送信息所需的內(nèi)存相應(yīng)的為之前的n倍。實現(xiàn)中可以進行優(yōu)化，比如共享某些路徑屬性，這樣可以減少一些內(nèi)存壓力。接收多條路徑也需要更多內(nèi)存和狀態(tài)信息，因為在Adj-RIB-Ins中每條路徑是分離的實體。

如前文所述，Add-paths能夠幫助路由器選擇更多的最佳路徑，并能夠改善由于路徑信息學(xué)習(xí)不全從而引起的路由震蕩。如果AS內(nèi)的路由器對某一目的地的路由不能夠做出一致的選擇，可能發(fā)生路由震蕩，甚至造成流量丟失。

優(yōu)化Add-path的擴展性與路由穩(wěn)定性目標(biāo)可能互相矛盾，因此運營商應(yīng)該根據(jù)自己的配置需求做出一定的折中。

BGP有豐富的策略，可以對通告的路徑屬性進行修改，但這樣可能導(dǎo)致鄰居路由選擇的不一致。類似的，IBGP中路由過濾策略的使用不當(dāng)，也可能導(dǎo)致路由選擇的不一致，從而產(chǎn)生環(huán)路。Add-path特性對于路由過濾應(yīng)做額外考慮，因為接收端無法對收到NLRI對應(yīng)的多路徑判斷哪一個是發(fā)送端的主路徑。發(fā)送端應(yīng)當(dāng)發(fā)送最佳路徑，接收端在選擇路徑時應(yīng)格外小心，不要丟棄了最佳路徑，而選擇了備份路徑。無論是發(fā)送端還是接收端，發(fā)送或者接收最佳路由時的錯誤操作都可能導(dǎo)致路由選擇的不一致。

4　結(jié)束語

本文提出的Add-path旨在增加路徑多樣性，能夠加快BGP在最佳路徑失效時的收斂過程，減少收斂期間的需要交互的UPDATE更新信息。此外，在配置了反射器的拓?fù)渲校嗦窂娇赡軒椭蛻舳诉x擇更優(yōu)的路徑，還能夠在一定程度上預(yù)防路由震蕩。實現(xiàn)方面，筆者根據(jù)代碼編寫和調(diào)試過程，提出了Add-path實現(xiàn)過程相關(guān)的一些建議，多路徑無疑會增加內(nèi)存的壓力，對于多路徑中共同的路徑屬性，存儲上可以進行優(yōu)化。

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