耿海軍，劉潔琦

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

2 本文算法

2.1 算法設(shè)計(jì)

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

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

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

算法DLBH的偽代碼如下。

算法1 DLBH。

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

輸出 節(jié)點(diǎn)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)計(jì)算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 算法復(fù)雜度分析

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

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

3 實(shí)驗(yàn)結(jié)果及分析

本章將全面分析DLBH的性能。在實(shí)驗(yàn)中，將DLBH和OPW、OSPF兩種算法進(jìn)行比較。運(yùn)行DLBH和OPW、OSPF的網(wǎng)絡(luò)拓?fù)浒ˋBILENE和GEANT[13]，它們的具體參數(shù)如表1所示。之所以選擇這兩個(gè)拓?fù)渥鳛閷?shí)驗(yàn)結(jié)構(gòu)，這是因?yàn)檫@兩個(gè)拓?fù)涔剂瞬糠终鎸?shí)流量數(shù)據(jù)。因?yàn)橐延械难芯縖14-16]衡量負(fù)載均衡能力主要包括兩個(gè)方面：1)最大鏈路利用率，該指標(biāo)用來衡量網(wǎng)絡(luò)擁塞程度；2)每條鏈路的鏈路利用率，該指標(biāo)用來衡量網(wǎng)絡(luò)中所有鏈路的整體鏈路利用率。因此，本文實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)為最大鏈路利用率和鏈路利用率累計(jì)概率分布。在實(shí)驗(yàn)中，取α=0.2，β=0.1。

表1 拓?fù)鋮?shù)Tab. 1 Topology parameters

3.1 最大鏈路利用率

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

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

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

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

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

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

圖3 ABILENE和GEANT中鏈路利用率累計(jì)概率分布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最大鏈路利用率達(dá)到了96%。

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

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

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

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

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

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

3.5 總結(jié)分析

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

4 結(jié)語

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