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

耿海軍，劉潔琦

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

0 引言

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

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

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

1 網絡模型和問題描述

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

2 本文算法

2.1 算法設計

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

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

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

算法DLBH的偽代碼如下。

算法1 DLBH。

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

輸出 節點c到目的地址d的最優下一跳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)

根據式(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僅僅計算出了節點c到目的節點d的最優下一跳，為了計算節點c到所有目的的最優下一跳，需要運行V次DLBH。因為對于不同的目的，DLBH可以獨立運行，所以在實際中可以采用并行方法實現。因此，計算節點c到所有目的的最優下一跳的算法復雜度等于標準的迪杰斯特拉算法的算法復雜度。

3 實驗結果及分析

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

表1 拓撲參數Tab. 1 Topology parameters

3.1 最大鏈路利用率

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

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

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

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

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

3.1節分析了DLBH和OPW對應的最大鏈路利用率。為了進一步細化網絡中所有鏈路的利用率，本節利用鏈路利用率累計概率分布來評價兩種算法的性能。圖3(a)和圖3(b)分別表示不同算法在ABILENE和GEANT的運行結果。圖3(a)中流量數據的采集時間為2004年3月8日晚上8點;圖3(b)中流量數據的采集時間為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 最大鏈路利用率和α的關系

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

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

3.4 最大鏈路利用率和β的關系

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

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

3.5 總結分析

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

4 結語

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