劉金生，陳石

　　（中國(guó)聯(lián)合網(wǎng)絡(luò)通信有限公司 網(wǎng)絡(luò)運(yùn)維部綜合監(jiān)控處，北京 100033）

      摘要：在多鏈路互聯(lián)的BGP鄰居之間實(shí)現(xiàn)流量按需負(fù)載分擔(dān)，可以有效提高鏈路利用率，降低組網(wǎng)成本，但目前常見(jiàn)的實(shí)現(xiàn)方法要么對(duì)硬件性能要求較高，要么配置復(fù)雜，不易在較大網(wǎng)絡(luò)特別是電信運(yùn)營(yíng)商網(wǎng)內(nèi)靈活部署。利用BGP路由尋址的特點(diǎn)，采用多重遞歸的方式，實(shí)現(xiàn)了按鏈路帶寬的比例分配流量的非等價(jià)負(fù)載分擔(dān)。這種方法原理簡(jiǎn)單，易于操作，具備較好的擴(kuò)展性。

　　關(guān)鍵詞：邊界網(wǎng)關(guān)協(xié)議；等價(jià)多路徑；非等價(jià)負(fù)載分擔(dān)；遞歸尋址；選路原則

0引言

　　數(shù)據(jù)流量的多鏈路負(fù)載分擔(dān)技術(shù)在互聯(lián)網(wǎng)界應(yīng)用廣泛，對(duì)應(yīng)不同的網(wǎng)絡(luò)結(jié)構(gòu)和需求，解決方案不盡相同。本文提供的非等價(jià)負(fù)載分擔(dān)方案基于路由尋址算法和BGP“下一跳”的遞歸屬性，與常見(jiàn)的策略路由方式相比，該方案配置更簡(jiǎn)單，部署更加靈活。

1等價(jià)負(fù)載分擔(dān)

　　Internet是由眾多相互聯(lián)在一起的自治系統(tǒng)（Autonomous System）組成的，為這些自治系統(tǒng)提供路由交換功能的協(xié)議就是邊界網(wǎng)關(guān)協(xié)議（BGP）［1］。為了保障BGP協(xié)議自身的健壯性和穩(wěn)定性，BGP協(xié)議規(guī)定了13條選路原則，所有開(kāi)啟BGP功能的路由器都嚴(yán)格遵守這些選路原則。

　　根據(jù)這13條選路原則，BGP協(xié)議默認(rèn)不支持等價(jià)路徑，也就是說(shuō)BGP數(shù)據(jù)庫(kù)中到達(dá)同一個(gè)目的IP只有一條最優(yōu)的路由會(huì)被放入路由表。

　　基于網(wǎng)絡(luò)可靠性的考慮，很多企業(yè)網(wǎng)在與電信運(yùn)營(yíng)商互聯(lián)時(shí)采用了雙歸、甚至多上聯(lián)的拓?fù)浣Y(jié)構(gòu)。為了提高數(shù)據(jù)傳送的效率和可靠性，對(duì)于這種多鏈路互聯(lián)的BGP鄰居，BGP協(xié)議在設(shè)計(jì)之初也保留了一個(gè)后門(mén)，即“等價(jià)多路徑”（Equal Cost MultiPath，ECMP）功能，一旦啟用了這一功能，對(duì)于同一目的IP，BGP協(xié)議允許最多可以有6條等價(jià)路徑被放入路由表中。

　　如圖1所示，自治系統(tǒng)AS100和AS200通過(guò)邊界路由器R1和R2建立了BGP鄰居關(guān)系。R1和R2之間有兩條直連的物理鏈路。當(dāng)AS100內(nèi)的用戶訪問(wèn)AS200內(nèi)的服務(wù)器時(shí)，在R1和R2上開(kāi)啟ECMP功能，兩個(gè)自治系統(tǒng)之間的流量就會(huì)按照1∶1的比例加載到兩條直連鏈路上，而不是只選擇其中一條鏈路進(jìn)行數(shù)據(jù)流量的傳遞。

　　這樣看，ECMP解決了多鏈路流量負(fù)載均擔(dān)問(wèn)題，在一定程度上提高了網(wǎng)絡(luò)的可靠性。目前，國(guó)內(nèi)主要電信運(yùn)營(yíng)商已把ECMP功能作為BGP接入的備選方案向用戶推薦，各主流電信設(shè)備供應(yīng)商如思科、華為、Junior、中興等也紛紛宣布支持這一功能。

2非等價(jià)負(fù)載分擔(dān)的提出

　　仍以圖1為例，R1和R2之間的兩條物理鏈路，第一條是點(diǎn)到點(diǎn)的串行鏈路，假設(shè)帶寬為2.5 Gb/s；第二條是廣播型的以太網(wǎng)鏈路，假設(shè)為帶寬為10 Gb/s。如果在R1和R2上開(kāi)啟ECMP功能，則每條鏈路最大流量不能超過(guò)2.5 Gb/s，否則串行鏈路就會(huì)因流量超過(guò)帶寬值而丟包，此時(shí)的以太網(wǎng)鏈路尚有10 Gb/s-2.5 Gb/s=7.5 Gb/s的帶寬處于閑置狀態(tài)。

　　如何既能夠讓去往同一目的IP的流量承載在不同的鏈路上，又能夠讓帶寬高的鏈路能者多勞？就此提出了非等價(jià)負(fù)載分擔(dān)的需求。

　　目前實(shí)現(xiàn)非等價(jià)負(fù)載分擔(dān)常見(jiàn)方法包括：策略路由、流量工程、MPLSVPN等。這些方法要么對(duì)設(shè)備的性能要求較高，要么需要BGP鄰居之間密切配合，對(duì)各種數(shù)據(jù)流進(jìn)行分類(lèi)和打標(biāo)記，并在路由進(jìn)行收發(fā)雙向控制，配置過(guò)程復(fù)雜，無(wú)法根據(jù)業(yè)務(wù)流量和中繼鏈路的變化靈活地部署，擴(kuò)展性差［2］。

3路由尋址與遞歸過(guò)程

　　路由尋址算法的本質(zhì)就是在路由表中實(shí)現(xiàn)對(duì)目的IP地址前綴的最長(zhǎng)匹配［3］。

　　圖2路由尋址的哈希過(guò)程如圖2所示，目的IP一旦被放入路由表，它的前綴同時(shí)就被哈希到特定的桶中，尋址的過(guò)程就是從哈希表中的第一個(gè)記錄開(kāi)始，對(duì)被哈希的關(guān)鍵字與給定值（即掩碼值，從32到0）逐個(gè)進(jìn)行比較，當(dāng)某個(gè)哈希的關(guān)鍵字與給定值完全相等時(shí)，則查找成功，路由協(xié)議會(huì)根據(jù)所查的記錄將包含目的IP數(shù)據(jù)包送入對(duì)應(yīng)的出接口；否則，若直到最后一個(gè)記錄，其關(guān)鍵字和給定值比較都不相等，則查找失敗，包含目的IP的數(shù)據(jù)包被送入默認(rèn)網(wǎng)關(guān)（若未設(shè)默認(rèn)網(wǎng)關(guān)，則該數(shù)據(jù)包被丟棄）。

　　路由尋址哈希算法描述［4］如下：

　　int Search(int d,int a［］,int n)

　　/*在數(shù)組a［］中查找等于D元素，若找到，則函數(shù)返回d在數(shù)組中的位置，否則為0。其中n為數(shù)組長(zhǎng)度*/

　　int i；

　　/*從后往前查找*/

　　for(i=n-1;a!=d;--i)

　　return i ;

　　/*如果找不到，則i為0*/

　　事實(shí)上，路由尋址算法還包含了遞歸的過(guò)程，即尋找數(shù)據(jù)包下一跳的過(guò)程路由的三元素包括：目標(biāo)地址、掩碼、下一跳。只有計(jì)算出有效的下一跳，IP協(xié)議才能逐跳地將數(shù)據(jù)包送往目的地。

　　所謂有效的下一跳，對(duì)于路由器而言分為兩個(gè)層面。從轉(zhuǎn)發(fā)層面（FIB：轉(zhuǎn)發(fā)信息庫(kù)）看，就是本路由器到達(dá)目的IP所經(jīng)的出接口。從控制層面（RIB：路由信息庫(kù)）看，就是在路由表中進(jìn)行最長(zhǎng)掩碼匹配的哈希算法查找的結(jié)果，是一個(gè)IP地址，如果這個(gè)IP地址對(duì)應(yīng)一個(gè)直連出接口，它就是一個(gè)有效的下一跳，可以被直接映射到轉(zhuǎn)發(fā)表中，參與指導(dǎo)數(shù)據(jù)包的轉(zhuǎn)發(fā)［5］；如果這個(gè)IP地址沒(méi)有對(duì)應(yīng)的直連出接口，則不能稱(chēng)之為有效的下一跳，需要進(jìn)行遞歸查找，最終找到對(duì)應(yīng)的直連出接口為止。

　　如圖3所示，在BGP路由表中，R0到達(dá)Server的下一跳是R3，到達(dá)R3的下一跳是R2，到達(dá)R2的下一跳是R1，以此類(lèi)推。IP協(xié)議在查找路由時(shí)，如果發(fā)現(xiàn)下一跳不是與自己直連的，那么就會(huì)將此下一跳地址作為目的IP再次按照上述邏輯查找路由表，直到查到與自己直連的下

　　一跳或者完全失敗為止，這就是路由的遞歸查找。

　　遞歸過(guò)程算法描述如下：

　　CheckNode{

　　int A;

　　int B;

　　Node children［1<<B］;

　　}

　　union Node{

　　Leaf entry;

　　CheckNode node;

　　}

　　由于查找下一跳的次數(shù)不是固定的（用A表示），并且經(jīng)過(guò)本次遞歸查找后下一跳是否有對(duì)應(yīng)的直連接口也不確定（用B表示），因此每一輪遞歸查找就是一個(gè)CheckNode過(guò)程。

4案例實(shí)現(xiàn)

　　仍以圖1為例，AS100網(wǎng)內(nèi)的用戶希望向AS200網(wǎng)內(nèi)的文件服務(wù)器（IP地址200.0.0.1）傳送文件，并且希望在傳送過(guò)程中根據(jù)兩條互聯(lián)鏈路帶寬的比例（2.5 Gb/s∶10 Gb/s=1∶4）分配數(shù)據(jù)流量。具體配置如表1所示。表1R1和R2的初始配置設(shè)備名R1R2Loopback0接口IP地址1.1.1.1/322.2.2.2/32鏈路帶寬鏈路流量占比

　　需求（共5份）R1R2Serial5/112.0.0.1/2412.0.0.2/242.5 Gb/s1份R1R2GigabitEthernet1/021.0.0.1/2421.0.0.2/2410 Gb/s4份

　　本例中R1與R2通過(guò)雙方的環(huán)回口（loopback0）建立EBGP鄰居關(guān)系，因此對(duì)R1而言，到達(dá)AS200網(wǎng)內(nèi)的目的IP200.0.0.1的下一跳地址就是R2的loopback0的地址2.2.2.2。

　?。?）第一步：指定新的目的IP和下一跳地址

　　為了通過(guò)遞歸尋址影響B(tài)GP的選路，在R1側(cè)，把2.2.2.2/32作為新的目的IP，并分配5個(gè)虛擬IP地址作為它的下一跳（之所以選擇5個(gè)虛擬IP地址，是因?yàn)殒溌穾挶壤秊?∶4，可以理解為需要把數(shù)據(jù)流量分成1+4=5份）。

　　完成配置后，檢查到達(dá)2.2.2.2/32的路由。如圖4所示，每個(gè)下一跳均為“traffic share count is 1”，代表這5個(gè)下一跳之間是等價(jià)的。注意：由于這些虛擬IP地址僅用于本地路由表的遞歸尋址，并不需要廣播到互聯(lián)網(wǎng)中，因此建議使用私網(wǎng)地址，本例中使用的是192.168.1.1~192.168.1.5。

　?。?）第二步：將虛擬下一跳引入路由表

　　根據(jù)實(shí)際鏈路的帶寬比例（1∶4）為這些下一跳地址分配出接口（本例中串口被分配1次，以太口被分配4次），如圖5所示。

　　虛擬下一跳地址一旦關(guān)聯(lián)了出接口，指向虛擬IP地址的靜態(tài)路由就變了合法的路由，將被放入路由表中，參與對(duì)目的IP的遞歸尋址過(guò)程（查找有效的下一跳）。

　?。?）第三步：尋址過(guò)程分析

　　從控制層面看（如圖6所示），在R1的路由表（RIB）中查找到達(dá)目的IP200.0.0.1的路由，首先會(huì)查到它的下一跳地址2.2.2.2，但由于沒(méi)有對(duì)應(yīng)的出接口，需要進(jìn)行一次遞歸查找；以2.2.2.2作為目的IP，經(jīng)過(guò)第一次遞歸查找，發(fā)現(xiàn)到達(dá)2.2.2.2有5個(gè)等價(jià)的下一跳地址，分別是192.168.1.1~192.168.1.5，由于這5個(gè)下一跳依然沒(méi)有對(duì)應(yīng)的出接口，因此需要再進(jìn)行一次遞歸查找；經(jīng)過(guò)第二次遞歸查找，5個(gè)下一跳都找到了對(duì)應(yīng)的出接口，路由尋址過(guò)程結(jié)束［6］。

　　從轉(zhuǎn)發(fā)層面看（如圖7所示），轉(zhuǎn)發(fā)表（FIB）中去往目的IP 200.0.0.1的數(shù)據(jù)包被等價(jià)地分配到5個(gè)出口：1份流量由點(diǎn)到點(diǎn)的串口鏈路（Serial5/1）承載，剩下的4份流量由廣播型的以太口鏈路（Gigabit1/0）承載?！　?/p>

　　這樣就實(shí)現(xiàn)了預(yù)先設(shè)定的需求：在兩條鏈路上實(shí)現(xiàn)按1∶4的流量進(jìn)行轉(zhuǎn)發(fā)，即非等價(jià)負(fù)載分擔(dān)。

5結(jié)論

　　實(shí)際案例證明：在路由尋址中增加一次遞歸過(guò)程，可以比較靈活地實(shí)現(xiàn)等價(jià)或非等價(jià)負(fù)載分擔(dān)。相比常用的策略路由，這種方法不需要對(duì)特定的數(shù)據(jù)流量進(jìn)行分類(lèi)標(biāo)記，在配置上更簡(jiǎn)單，另外用于遞歸算法的下一跳使用的是私網(wǎng)地址，不消耗公網(wǎng)資源，部署起來(lái)也比較方便。

　　這里需要強(qiáng)調(diào)的是，本例中的EBGP鄰居R1和R2并未打開(kāi)等價(jià)多路徑（ECMP）功能，對(duì)于目的IP200.0.0.1，在R1的BGP數(shù)據(jù)庫(kù)中只有2.2.2.2/32這一個(gè)下一跳，而不是多個(gè)下一跳。也就是說(shuō)本方法并不是在BGP協(xié)議內(nèi)實(shí)現(xiàn)非等價(jià)負(fù)載分擔(dān)，而是借用BGP協(xié)議中“下一跳”的概念，通過(guò)路由表中的多重遞歸實(shí)現(xiàn)流量非等價(jià)分擔(dān)的效果，因此這與BGP的等價(jià)多路徑選路原則并不矛盾。

　　另外，本例中介紹的非等價(jià)負(fù)載分擔(dān)方法適用于通過(guò)環(huán)回口建立的EBGP鄰居。對(duì)于通過(guò)直連接口建立的EBGP鄰居，可以在雙方的直連接口上配置若干個(gè)second IP作為到目的IP的下一跳地址，再經(jīng)過(guò)路由遞歸查找，也能實(shí)現(xiàn)非等價(jià)負(fù)載均衡的效果，具體配置方法本文不再贅述。

參考文獻(xiàn)

　?。?］ STEWART J.BGP4: interdomain routing in the Internet［M］．USA Addison Wesley，1998.

　?。?］ 薩姆·哈拉比. Internet 路由結(jié)構(gòu)（第2版）［M］.孫劍，孫余強(qiáng),譯.北京：人民郵電出版社，2015.

　　［3］ 布萊恩特，奧哈拉倫.深入理解計(jì)算機(jī)系統(tǒng)（第2版）［M］.北京：機(jī)械工業(yè)出版社，2011.

　　［4］ 維斯.數(shù)據(jù)結(jié)構(gòu)與算法分析：C語(yǔ)言描述［M］.馮舜璽，譯.北京：機(jī)械工業(yè)出版社，2004.

　?。?］ 艾云霄,譚躍生,王靜宇，等.MooseFS中chunkserver負(fù)載均衡算法研究［J］.微型機(jī)與應(yīng)用,2013,32(5):13.

　?。?］ SCUDDER J， CHANDRA R.RFC 5492： capabilities advertisement with BGP4［EB/OL］.（200902xx）.http://tools.ietf.org/html/rfc5492.