劉金生，陳 石

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

在BGP鄰居之間實(shí)現(xiàn)流量非等價負(fù)載分擔(dān)

劉金生，陳 石

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

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

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

0 引言

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

1 等價負(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條選路原則，所有開啟BGP功能的路由器都嚴(yán)格遵守這些選路原則。

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

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

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

圖1 BGP鄰居的多鏈路互聯(lián)拓?fù)?/p>

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

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

仍以圖1為例，R1和R2之間的兩條物理鏈路，第一條是點(diǎn)到點(diǎn)的串行鏈路，假設(shè)帶寬為2.5 Gb/s；第二條是廣播型的以太網(wǎng)鏈路，假設(shè)為帶寬為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的流量承載在不同的鏈路上，又能夠讓帶寬高的鏈路能者多勞？就此提出了非等價負(fù)載分擔(dān)的需求。

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

3 路由尋址與遞歸過程

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

圖2 路由尋址的哈希過程

如圖2所示，目的IP一旦被放入路由表，它的前綴同時就被哈希到特定的桶中，尋址的過程就是從哈希表中的第一個記錄開始，對被哈希的關(guān)鍵字與給定值(即掩碼值，從32到0)逐個進(jìn)行比較，當(dāng)某個哈希的關(guān)鍵字與給定值完全相等時，則查找成功，路由協(xié)議會根據(jù)所查的記錄將包含目的IP數(shù)據(jù)包送入對應(yīng)的出接口；否則，若直到最后一個記錄，其關(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ù)組長度*/

int i；

/*從后往前查找*/

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

return i ;

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

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

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

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

圖3 遞歸查找過程

遞歸過程算法描述如下：

CheckNode{

int A;

int B;

Node children[1<

}

union Node{

Leaf entry;

CheckNode node;

}

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

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

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

表1 R1和R2的初始配置

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

(1)第一步：指定新的目的IP和下一跳地址

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

完成配置后，檢查到達(dá)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。

圖4 到達(dá)2.2.2.2/32的下一跳地址

(2)第二步：將虛擬下一跳引入路由表

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

圖5 為5個虛擬下一跳指定出接口

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

(3)第三步：尋址過程分析

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

圖6 在路由表中分析兩次遞歸過程

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

圖7 轉(zhuǎn)發(fā)表中到達(dá)目的IP的5個出接口

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

5 結(jié)論

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

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

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

[1] STEWART J.BGP4: inter-domain routing in the Internet[M]．USA Addison Wesley，1998.

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

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

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

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

[6] SCUDDER J， CHANDRA R.RFC 5492： capabilities advertisement with BGP-4[EB/OL].(2009-02-xx).http://tools.ietf.org/html/rfc5492.

A method to achieve unbalanced-traffic-load-sharing between BGP neighbors

Liu Jinsheng，Chen Shi

(Network Operation and Maintenance Department Comprehensive Monitoring Office, China United Telecommunication Company, Beijing 100033, China)

The unbalanced-traffic-load-sharing between BGP neighbors which is connected by multi-links can effectively improve the link utilization, and reduce the cost on network construction as well. However, using normal methods to achieve this goal either requires higher performance hardware, or needs complex configuration, which is hard to deploy in larger network, especially in those telecommunication backbone networks. In this paper, the author follows the characteristics of BGP routing, and uses multiple recursive way to fulfill the unbalanced-traffic-load-sharing according to the bandwidth of each link between BGP neighbors. The principle is simple and easy to operate, and has deployment.

BGP; ECMP(Equal-Cost Multi-Path); unbalanced-traffic-load-sharing; recursive addressing; routing principle

TP393

A

1674-7720(2016)04-0072-04

劉金生，陳石．在BGP鄰居之間實(shí)現(xiàn)流量非等價負(fù)載分擔(dān)[J] .微型機(jī)與應(yīng)用，2016，35(4)：72-75.

2015-10-16)

劉金生(1973-)，男，本科，工程師，主要研究方向：互聯(lián)網(wǎng)管理和維護(hù)。

陳石(1974-)，通信作者，男，碩士，高級工程師，主要研究方向：互聯(lián)網(wǎng)管理和維護(hù)。E-mail:chenshi5@chinaunicom.cn。