基于逐跳計算的分布式負載均衡算法

耿海軍，劉潔琦

(山西大學 軟件學院，太原 030006)(*通信作者電子郵箱ghj123025449@163.com)

0 引言

隨著互聯(lián)網(wǎng)的普及和快速發(fā)展，部署在互聯(lián)網(wǎng)中的視頻業(yè)務與日俱增[1]。研究表明，隨著網(wǎng)絡中流量的增加，網(wǎng)絡擁塞頻繁發(fā)生。然而目前互聯(lián)網(wǎng)部署的域內(nèi)路由協(xié)議采用最短路徑轉(zhuǎn)發(fā)報文，無法靈活應對網(wǎng)絡擁塞問題[2-3]。因此，因特網(wǎng)服務提供商(Internet Service Provider, ISP)通過配置鏈路權(quán)值來優(yōu)化資源利用，盡量減少由于流量增加而引起的網(wǎng)絡擁塞問題發(fā)生[4]。由于該問題的重要性，在過去的幾十年里大量的研究者致力于對網(wǎng)絡擁塞問題[5]的研究。

文獻[4]中介紹了基于IP的域內(nèi)負載均衡算法——優(yōu)化開放最短路徑優(yōu)先(Open Shortest Path First, OSPF)權(quán)值(Optimizing OSPF Weights, OPW)，該研究的核心思想為給定一個網(wǎng)絡拓撲結(jié)構(gòu)和流量矩陣，通過設置網(wǎng)絡中鏈路代價來優(yōu)化流量的分配。文獻[4]研究將該最優(yōu)化問題表示為一個多商品流問題，然后利用領域搜索算法計算近似最優(yōu)解；但是該算法必須采用集中式解方案，并且算法的代價較大，因此無法直接應用在逐跳計算的鏈路狀態(tài)路由協(xié)議中。鏈路狀態(tài)路由協(xié)議即運行協(xié)議的路由器之間首先建立鄰居關(guān)系，然后鄰居間交換鏈路狀態(tài)信息，如鏈路類型和帶寬等，接著每個路由器根據(jù)交換得到的鏈路狀態(tài)信息建立鏈路狀態(tài)數(shù)據(jù)庫，最后每個路由器根據(jù)該鏈路狀態(tài)數(shù)據(jù)庫計算以自己為根的最短路徑樹，逐跳計算即每個路由器獨立地計算自己的路由表，不需要輔助協(xié)議的支持，如隧道、特殊地址等。多協(xié)議標簽交換(Multi-Protocol Label Switching, MPLS)[6]是一種高效的報文交換協(xié)議，該協(xié)議不受最短路徑路由協(xié)議的約束，可以任意配置路由。MPLS處于開放式系統(tǒng)互聯(lián)(Open System Interconnect, OSI)模型的第二層和第三層中間，當分組達到網(wǎng)絡的時候，為其分配固定長度的標簽，并且將該標簽和分組封裝在一起，利用標簽轉(zhuǎn)發(fā)報文，從而實現(xiàn)報文的高速轉(zhuǎn)發(fā)。文獻[7-8]中將利用MPLS實現(xiàn)負載均衡的問題歸結(jié)為線性整數(shù)規(guī)劃模型，然后利用線性規(guī)劃(Linear Programming, LP)計算器求解。文獻[9]提出了利用基于路徑的路由保護算法，在節(jié)點間通過使用多條路徑并行傳輸數(shù)據(jù)，并且設計了負載均衡算法實現(xiàn)分流，以實現(xiàn)故障恢復期間的負載均衡。文獻[10]提出了利用配置合適的鏈路權(quán)值在基于逐跳計算的鏈路狀態(tài)路由協(xié)議中實現(xiàn)鏈路負載均衡，然而該算法計算開銷極大，并且容易導致網(wǎng)絡不穩(wěn)定。

上述所有的負載均衡算法都需要完整的流量矩陣，并且需要集中式方法求解。研究[11]表明，從網(wǎng)絡中獲取實際流量矩陣是一件相當困難的工作，基本無法實現(xiàn)。因此，本文研究如何在沒有流量矩陣的前提下實現(xiàn)一種基于逐跳計算的分布式負載均衡算法(Distributed Load Balancing algorithm based on Hop-by-hop computing, DLBH)。

1 網(wǎng)絡模型和問題描述

圖G=(V,E)表示一個網(wǎng)絡拓撲結(jié)構(gòu)，在該圖中，V代表該網(wǎng)絡拓撲中節(jié)點的集合，E代表該網(wǎng)絡拓撲中邊的集合。對于?v∈V，N(v)表示該節(jié)點的所有鄰居節(jié)點的集合。對于?(i,j)∈E，w(i,j)為該邊對應的代價，c(i,j)為該邊對應的帶寬。對于網(wǎng)絡中的任意兩個不相同的節(jié)點?x,y∈V(x≠y)，C(x,y)表示這兩個節(jié)點之間的最短路徑對應的代價；B(x,y)表示節(jié)點x到節(jié)點y的最優(yōu)下一跳；H(x,y)表示這兩個節(jié)點之間的最短路徑對應的跳數(shù)，當兩個節(jié)點之間有多條最短路徑時，取具有最小跳數(shù)的路徑作為H(x,y)的數(shù)值。

由于互聯(lián)網(wǎng)中的域內(nèi)路由協(xié)議一般采用分布式方法，因此本文研究如何采用分布式方法進行負載均衡，以降低網(wǎng)絡擁塞。因為本文利用的是分布式解決方法，所以下面僅僅討論節(jié)點c的計算過程。為了防止網(wǎng)絡擁塞，當某條鏈路的鏈路利用率較高時，可以將該條鏈路的權(quán)值設置為較大的數(shù)值，這樣就可以降低該鏈路的鏈路利用率。但是網(wǎng)絡中鏈路利用率隨著時間的變化而變化，如果鏈路的權(quán)值也隨著時間的變化而變化，將會導致網(wǎng)絡不穩(wěn)定，引發(fā)路由震蕩。因此，為了設計一個分布式的負載均衡算法，需要解決下面兩個問題。

1)如何獲得鏈路的鏈路利用率。

因為實際網(wǎng)絡中的流量隨時間的變化而變化，所以網(wǎng)絡中鏈路的鏈路利用率也是時間的函數(shù)。下面將描述如何獲得鏈路的鏈路利用率。

2)如何根據(jù)鏈路利用率設置該鏈路的代價。

對于任意的目的地址，當計算出某條鏈路的鏈路利用率后，如何設置該鏈路的代價是本文需要解決的另外一個關(guān)鍵問題。在設置鏈路代價的時候需要考慮兩個方面的因素:

a)鏈路代價是鏈路利用率的函數(shù)，即w(vi,vj，d)=F(μ(vi,vj,d))=F(T(d)*(H(vj,d)+1)β/c(vi,vj))。鏈路代價和鏈路利用率之間的變化趨勢相同，即鏈路利用率越高，該鏈路的代價越大；反之，鏈路利用率越低，該鏈路的代價越小。

b)為了防止路由環(huán)路，鏈路代價函數(shù)F(T(d)*(H(vj,d)+1)β/c(vi,vj))必須保證左保序性。

下面給出左保序性的定義，對于兩條路徑p和q，如果兩者都表示從節(jié)點s到節(jié)點d的路徑，如果W(p)

圖1 左保序性例子Fig. 1 An example for left isotonicity

從上面的討論可知，對于不同的目的地址，某條鏈路的代價是不相同的。鏈路代價的具體數(shù)值由式(1)表示:

(1)

由式(1)可知，鏈路利用率越高，鏈路的代價越高，該代價函數(shù)滿足了代價函數(shù)必須滿足的第一個要求。下面通過定理1來證明該代價函數(shù)具有左保序性。

定理1 鏈路代價函數(shù)F(T(d)*(H(vj,d)+1)β/c(vi,vj))具有左保序性。

2 本文算法

2.1 算法設計

DLBH是一個分布式的解決算法。運行DLBH的路由器僅僅需要知道自身的局部信息(如網(wǎng)絡拓撲結(jié)構(gòu))即可，而不需要獲取網(wǎng)絡中的實時流量矩陣信息。每個路由器根據(jù)DLBH計算出到達所有目的的最優(yōu)下一跳，從而減低網(wǎng)絡擁塞，達到負載均衡的目的。

下面將詳細描述算法DLBH的執(zhí)行過程。

該算法的輸入為網(wǎng)絡拓撲G(V,E)，計算節(jié)點c和目的地址d，輸出為節(jié)點c到目的地址d的最優(yōu)下一跳。在算法中，每個節(jié)點有一個訪問標記屬性visited，當該屬性的值為true時，表示該節(jié)點已經(jīng)被訪問，反之該節(jié)點未被訪問。算法維護一個優(yōu)先級隊列Q(u,v,p,q)，該隊列中元素包括4個屬性，其中:u表示節(jié)點本身，v表示節(jié)點u的父親節(jié)點，p表示節(jié)點u到目的地址d的代價，q表示節(jié)點u到目的地址d的跳數(shù)。初始化參數(shù)，將所有節(jié)點(除去d)到d的最小代價設置為無窮大，將d到d的最小代價設置為0，將所有節(jié)點(除去d)到d的最小跳數(shù)設置為無窮大，將d到d的最小跳數(shù)設置為0，將所有節(jié)點的訪問屬性標記為未訪問，將節(jié)點d加入到優(yōu)先級隊列(第1)～8)行)。當隊列不為空時，執(zhí)行下面的過程。從隊列中取出第一個元素u(第10)行)，當該元素為計算節(jié)點c時，返回節(jié)點c到目的地址d的最優(yōu)下一跳，程序結(jié)束。當該元素不是計算節(jié)點c時，更新該節(jié)點的屬性(第14)～17)行)。計算該節(jié)點到目的節(jié)點d的最優(yōu)下一跳(第18)～22)行)。訪問節(jié)點u的所有鄰居節(jié)點，對于節(jié)點u的鄰居節(jié)點v，如果節(jié)點v未被訪問，計算鏈路(v,u)的代價，更新節(jié)點v的屬性(第23)～34)行)。

算法DLBH的偽代碼如下。

算法1 DLBH。

輸入G(V,E)，計算節(jié)點c和目的地址d；

輸出 節(jié)點c到目的地址d的最優(yōu)下一跳B(c,d)。

1)

For ?v∈Vdo

2)

C(v)←∞

3)

v.visited←false

4)

H(v)←∞

5)

EndFor

6)

C(d)←0

7)

H(v)←0

8)

Enqueue(Q，(d，0,0,0))

9)

WhileQ不為空 do

10)

(u,p,tc,th)←Extractmin(Q)

11)

Ifu=cthen

12)

returnB(c,d)

13)

else

14)

u.visited←true

15)

P(u)←p

16)

C(u)←tc

17)

H(u)←th

18)

IfP(u)=dthen

19)

B(u,d)=d

20)

else

21)

B(u,d)=B(P(u),d)

22)

EndIf

23)

Forv∈N(u) do

24)

Ifu.visited=false then

25)

t(v,u,d)=T(d)*(H(u)+1)β

26)

μ(v,u,d)=t(v,u,d)/c(v,u)

27)

根據(jù)式(1)計算w(v,u,d)

28)

IfC(u)+w(v,u,d)

w(v,u,d)=C(v) andH(v)

29)

newdist=C(u)+w(v,u,d)

30)

h←H(u)+1

31)

Enqueue(Q，(v,u,newdist,h))

32)

EndIf

33)

EndIf

34)

EndFor

35)

EndIf

36)

EndWhile

2.2 算法復雜度分析

定理2 算法DLBH的時間復雜度為O(VlgV+E)。

證明 算法DLBH在標準的迪杰斯特拉算法的基礎上僅僅增加了第25)～27)行,這幾行語句的時間復雜度為O(1)，不會影響算法的時間復雜度。因此在最壞情況下DLBH的時間復雜度為O(VlgV+E)。DLBH僅僅計算出了節(jié)點c到目的節(jié)點d的最優(yōu)下一跳，為了計算節(jié)點c到所有目的的最優(yōu)下一跳，需要運行V次DLBH。因為對于不同的目的，DLBH可以獨立運行，所以在實際中可以采用并行方法實現(xiàn)。因此，計算節(jié)點c到所有目的的最優(yōu)下一跳的算法復雜度等于標準的迪杰斯特拉算法的算法復雜度。

3 實驗結(jié)果及分析

本章將全面分析DLBH的性能。在實驗中，將DLBH和OPW、OSPF兩種算法進行比較。運行DLBH和OPW、OSPF的網(wǎng)絡拓撲包括ABILENE和GEANT[13]，它們的具體參數(shù)如表1所示。之所以選擇這兩個拓撲作為實驗結(jié)構(gòu)，這是因為這兩個拓撲公布了部分真實流量數(shù)據(jù)。因為已有的研究[14-16]衡量負載均衡能力主要包括兩個方面：1)最大鏈路利用率，該指標用來衡量網(wǎng)絡擁塞程度；2)每條鏈路的鏈路利用率，該指標用來衡量網(wǎng)絡中所有鏈路的整體鏈路利用率。因此，本文實驗的評價指標為最大鏈路利用率和鏈路利用率累計概率分布。在實驗中，取α=0.2，β=0.1。

表1 拓撲參數(shù)Tab. 1 Topology parameters

3.1 最大鏈路利用率

在本節(jié)將利用最大鏈路利用率來衡量不同算法的負載均衡能力。最大鏈路利用率越低，負載均衡能力越強，反之最大鏈路利用率越高，負載均衡能力越弱。不同算法在ABILENE和GEANT的運行結(jié)果分別如圖2(a)和圖2(b)所示,圖2(a)中流量數(shù)據(jù)的采集時間為2004年3月8日，圖2(b)中流量數(shù)據(jù)的采集時間為2005年5月8日。

從圖2(a)和圖2(b)可以看出：在ABILENE中，DLBH的最大鏈路利用率小于OPW和OSPF的最大鏈路利用率，OSPF的最大鏈路利用率是最大的：在GEANT中，DLBH和OPW的最大鏈路利用率基本相同，它們的最大鏈路利用率遠遠小于OSPF的最大鏈路利用率。

不同算法在ABILENE和GEANT的運行結(jié)果分別如圖2(c)和圖2(d)所示,圖2(c)中流量數(shù)據(jù)的采集時間為2018年5月12日，圖2(d)中流量數(shù)據(jù)的采集時間為2018年3月4日。從圖2(c)和圖2(d)中，可以得出如圖2(a)和圖2(b)同樣的結(jié)論。

圖2 最大鏈路利用率隨時間變化規(guī)律Fig. 2 Change of maximum link utilization with time

3.2 鏈路利用率累積概率分布

3.1節(jié)分析了DLBH和OPW對應的最大鏈路利用率。為了進一步細化網(wǎng)絡中所有鏈路的利用率，本節(jié)利用鏈路利用率累計概率分布來評價兩種算法的性能。圖3(a)和圖3(b)分別表示不同算法在ABILENE和GEANT的運行結(jié)果。圖3(a)中流量數(shù)據(jù)的采集時間為2004年3月8日晚上8點;圖3(b)中流量數(shù)據(jù)的采集時間為2005年5月8日晚上8點。

圖3 ABILENE和GEANT中鏈路利用率累計概率分布Fig. 3 Link utilization cumulative probability distribution on ABILENE and GEANT

從圖3(a)可知，DLBH鏈路的利用率均小于12%；OPW鏈路的利用率均小于14%；而OSPF最大鏈路利用率為17%，小于12%的鏈路不到70%。從圖3(b)可知，DLBH和OPW的鏈路利用率累積概率分布基本相同，DLBH和OPW鏈路利用率均小于65%，而OSPF最大鏈路利用率達到了96%。

3.3 最大鏈路利用率和α的關(guān)系

當β=0.1時，DLBH在ABILENE和GEANT中最大鏈路利用率和α的關(guān)系如圖4所示。圖4(a)中流量數(shù)據(jù)的采集時間為2004年3月8日，圖4(b)中流量數(shù)據(jù)的采集時間為2018年4月12日。從圖4可以看出，在ABILENE中，隨著α的增加，最大鏈路利用率略微增加，當α增加到某個值時，最大鏈路利用率基本不再隨α的變化而變化；在GEANT中，隨著α的增加，最大鏈路利用率略微增加。

圖4 DLBH最大鏈路利用率和α的關(guān)系Fig. 4 Relationship between maximum link utilization and α by DLBH

3.4 最大鏈路利用率和β的關(guān)系

當α=0.2時，DLBH在ABILENE和GEANT中最大鏈路利用率和β的關(guān)系如圖5所示。圖5(a)中流量數(shù)據(jù)的采集時間為2004年3月8日，圖5(b)中流量數(shù)據(jù)的采集時間為2018年4月12日。從圖5可以看出，在2004年的ABILENE中，最大鏈路利用率基本不隨β的變化而變化；在GEANT中，當β的值在0.2和0.8之間時，最大鏈路利用率基本不隨β的變化而變化，當β增加到0.8時，最大鏈路利用率隨著β的增加而增加。在2018年的ABILENE和GEANT中，當β的數(shù)值在0.1和0.3之間時，最大連路利用率隨著β的增加而增加，當β大于0.3時，最大鏈路利用率基本不隨β的變化而變化。

圖5 DLBH最大鏈路利用率和β的關(guān)系Fig. 5 Relationship between maximum link utilization and β by DLBH

3.5 總結(jié)分析

從上述的實驗結(jié)果可知，DLBH在實際網(wǎng)絡中的負載均衡能力明顯優(yōu)于OPW的負載均衡能力；并且從實驗中可知，當α=0.2、β=0.1時，DLBH可以得到較優(yōu)的計算結(jié)果。

4 結(jié)語

針對目前已有負載均衡算法需要實際流量矩陣，采用集中式算法，并且算法復雜度較高的問題，本文提出了一種基于逐跳計算的分布式負載均衡算法(DLBH)。該算法不需要實際流量矩陣，并且采用分布式計算方法，算法復雜度和標準迪杰斯特拉算法的復雜度相同，沒有引入過多的額外代價。實驗結(jié)果表明，與OPW相比較，DLBH不僅擁有較小的計算復雜度，并且具有較低的最大鏈路利用率。因此，DLBH可以為互聯(lián)網(wǎng)服務提供商提供一種兼顧執(zhí)行效率和最大鏈路利用率的域內(nèi)負載均衡算法。本文僅僅利用實驗驗證了DLBH的有效性，下一步將從理論方面進行分析。