在BGP鄰居之間實現(xiàn)流量非等價負載分擔

劉金生，陳 石

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

在BGP鄰居之間實現(xiàn)流量非等價負載分擔

劉金生，陳 石

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

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

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

0 引言

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

1 等價負載分擔

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

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

基于網絡可靠性的考慮，很多企業(yè)網在與電信運營商互聯(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ù)流量的傳遞。

圖1 BGP鄰居的多鏈路互聯(lián)拓撲

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

2 非等價負載分擔的提出

仍以圖1為例，R1和R2之間的兩條物理鏈路，第一條是點到點的串行鏈路，假設帶寬為2.5 Gb/s；第二條是廣播型的以太網鏈路，假設為帶寬為10 Gb/s。如果在R1和R2上開啟ECMP功能，則每條鏈路最大流量不能超過2.5 Gb/s，否則串行鏈路就會因流量超過帶寬值而丟包，此時的以太網鏈路尚有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ù)包被送入默認網關(若未設默認網關，則該數(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所經的出接口。從控制層面(RIB：路由信息庫)看，就是在路由表中進行最長掩碼匹配的哈希算法查找的結果，是一個IP地址，如果這個IP地址對應一個直連出接口，它就是一個有效的下一跳，可以被直接映射到轉發(fā)表中，參與指導數(shù)據(jù)包的轉發(fā)[5]；如果這個IP地址沒有對應的直連出接口，則不能稱之為有效的下一跳，需要進行遞歸查找，最終找到對應的直連出接口為止。

如圖3所示，在BGP路由表中，R0到達Server的下一跳是R3，到達R3的下一跳是R2，到達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表示)，并且經過本次遞歸查找后下一跳是否有對應的直連接口也不確定(用B表示)，因此每一輪遞歸查找就是一個CheckNode過程。

4 案例實現(xiàn)

仍以圖1為例，AS100網內的用戶希望向AS200網內的文件服務器(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鄰居關系，因此對R1而言，到達AS200網內的目的IP200.0.0.1的下一跳地址就是R2的loopback0的地址2.2.2.2。

(1)第一步：指定新的目的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)網中，因此建議使用私網地址，本例中使用的是192.168.1.1～192.168.1.5。

圖4 到達2.2.2.2/32的下一跳地址

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

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

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

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

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

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

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

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

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

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

5 結論

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

這里需要強調的是，本例中的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的下一跳地址，再經過路由遞歸查找，也能實現(xiàn)非等價負載均衡的效果，具體配置方法本文不再贅述。

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

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

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

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

[5] 艾云霄,譚躍生,王靜宇，等.MooseFS中chunkserver負載均衡算法研究[J].微型機與應用,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鄰居之間實現(xiàn)流量非等價負載分擔[J] .微型機與應用，2016，35(4)：72-75.

2015-10-16)

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

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