劉金生，陳石

　?。ㄖ袊?lián)合網(wǎng)絡通信有限公司 網(wǎng)絡運維部綜合監(jiān)控處，北京 100033）

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

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

0引言

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

1等價負載分擔

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

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

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

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

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

2非等價負載分擔的提出

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

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

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

3路由尋址與遞歸過程

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

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

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

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

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

　　int i；

　　/*從后往前查找*/

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

　　return i ;

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

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

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

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

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

　　遞歸過程算法描述如下：

　　CheckNode{

　　int A;

　　int B;

　　Node children［1<<B］;

　　}

　　union Node{

　　Leaf entry;

　　CheckNode node;

　　}

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

4案例實現(xiàn)

　　仍以圖1為例，AS100網(wǎng)內的用戶希望向AS200網(wǎng)內的文件服務器（IP地址200.0.0.1）傳送文件，并且希望在傳送過程中根據(jù)兩條互聯(lián)鏈路帶寬的比例（2.5 Gb/s∶10 Gb/s=1∶4）分配數(shù)據(jù)流量。具體配置如表1所示。表1R1和R2的初始配置設備名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通過雙方的環(huán)回口（loopback0）建立EBGP鄰居關系，因此對R1而言，到達AS200網(wǎng)內的目的IP200.0.0.1的下一跳地址就是R2的loopback0的地址2.2.2.2。

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

　　為了通過遞歸尋址影響B(tài)GP的選路，在R1側，把2.2.2.2/32作為新的目的IP，并分配5個虛擬IP地址作為它的下一跳（之所以選擇5個虛擬IP地址，是因為鏈路帶寬比例為1∶4，可以理解為需要把數(shù)據(jù)流量分成1+4=5份）。

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

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

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

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

　　（3）第三步：尋址過程分析

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

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

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

5結論

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

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

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

參考文獻

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

　?。?］ 薩姆·哈拉比. Internet 路由結構（第2版）［M］.孫劍，孫余強,譯.北京：人民郵電出版社，2015.

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

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

　?。?］ 艾云霄,譚躍生,王靜宇，等.MooseFS中chunkserver負載均衡算法研究［J］.微型機與應用,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.