基于不相交路徑的域內(nèi)路由保護(hù)方案

耿海軍,劉潔琦,張 舉

(山西大學(xué) 軟件學(xué)院,太原 030006)

0 概述

互聯(lián)網(wǎng)在設(shè)計之初主要用于部署一些非實時應(yīng)用[1],但是目前許多實時應(yīng)用[2-4]也部署在互聯(lián)網(wǎng)中,實時應(yīng)用對網(wǎng)絡(luò)的性能提出更加嚴(yán)格的要求[5-7]。很多研究已經(jīng)表明,網(wǎng)絡(luò)經(jīng)常會出現(xiàn)故障[8-10],但目前的路由協(xié)議很難應(yīng)對頻繁發(fā)生的突發(fā)故障。為了解決上述出現(xiàn)的問題,業(yè)界提出了路由保護(hù)方案[11-12],該方案利用預(yù)先計算出的備份路徑來應(yīng)對主路徑出現(xiàn)斷路的情況。

下文主要介紹一些常見的路由保護(hù)方案。多配置路由(Multiple Routing Configurations,MRC)[13]利用多拓?fù)浣Y(jié)構(gòu)的思想為每條鏈路存儲備份路徑,但是該方案的計算開銷過大,消耗了大量的計算資源。FCP(Failure Carrying Packet)[14]將故障信息存儲在報文的頭部,然后利用給出信息預(yù)先計算相應(yīng)的備份路由表,但是該方案對路由協(xié)議的改變較大,無法在互聯(lián)網(wǎng)中部署。IP快速重路由(IP Fast Re-Route,IPFRR)[15]是一種較為簡單的路由保護(hù)方案,該方案利用無環(huán)路規(guī)則預(yù)先計算備份路由表,但故障覆蓋率較低。為進(jìn)一步提升LFA(Loop Free Alternate)的故障保護(hù)率,文獻(xiàn)[16]提出U-turn方案,該方案可以在鄰居節(jié)點中計算LFA下一跳。U-turn雖然明顯提高了故障保護(hù)率,但是仍然達(dá)不到預(yù)期目標(biāo)。文獻(xiàn)[17]利用紅綠樹來構(gòu)造2條不相交路徑,但是該方案限制了默認(rèn)路由,即默認(rèn)路由可能不采用最短路徑。文獻(xiàn)[18]提出在SDN網(wǎng)絡(luò)中如何應(yīng)對網(wǎng)絡(luò)故障的框架和算法,但是該方法只能部署在SDN網(wǎng)絡(luò)中。針對上述問題,本文提出一種基于不相交路徑的域內(nèi)路由保護(hù)方案。

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

為了清晰地描述本文要解決的問題,需要在基本網(wǎng)絡(luò)模型的基礎(chǔ)上進(jìn)行擴(kuò)充。

下面首先描述網(wǎng)絡(luò)的基本模型,該模型和目前學(xué)術(shù)界普遍采用的模型一致。網(wǎng)絡(luò)可以表示為一個無向圖G=(V,E,C),其中,V代表網(wǎng)絡(luò)中的所有路由器,E代表網(wǎng)絡(luò)中的所有鏈路,C代表網(wǎng)絡(luò)中鏈路權(quán)值的集合。對于該網(wǎng)絡(luò)中的每一條邊?e=(i,j)∈E,w(e)、w(i,j)代表該邊對應(yīng)的權(quán)值。在實際網(wǎng)絡(luò)中邊的權(quán)值一般具有對稱性,即w(i,j)=w(j,i) 。P(o,d,G)代表網(wǎng)絡(luò)中節(jié)點對(o,d)的最短路徑,D(o,d,G)代表節(jié)點對(o,d)的最小代價。

然后對上述基本模型進(jìn)行擴(kuò)展。在網(wǎng)絡(luò)基本模型G=(V,E,C)的基礎(chǔ)上,生成其對應(yīng)的擴(kuò)展模型G′=(V,E,C′)。在擴(kuò)展模型中,P(o,d,G′)代表網(wǎng)絡(luò)中節(jié)點對(o,d)的備份路徑,D(o,d,G′)代表節(jié)點對(o,d)的最小代價,P(o,d,G′)代表該節(jié)點對之間的備份路徑,K(o,d,e)代表鏈路e是否同時在節(jié)點對(o,d)的最短路徑和備份路徑上,可以用下面的數(shù)學(xué)公式來表示:

從該定義可知,如果鏈路e同時在節(jié)點對(o,d)的最短路徑和備份路徑上,則K(o,d,e)的數(shù)值為1;否則為0。L(o,d)定量地描述了節(jié)點對(o,d)的最短路徑和備份路徑,同時包括邊的總數(shù)量。

網(wǎng)絡(luò)交叉度為網(wǎng)絡(luò)中全部節(jié)點對之間的最短路徑和備份路徑包括的邊的總的數(shù)量,用R(G,G′)來表示,即:

最后在網(wǎng)絡(luò)模型和擴(kuò)展網(wǎng)絡(luò)模型的基礎(chǔ)上描述本文解決的關(guān)鍵問題。

已知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G(V,E,C),在該拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上生成其對應(yīng)的擴(kuò)展拓?fù)浣Y(jié)構(gòu)G′=(V,E,C′),使得網(wǎng)絡(luò)交叉度R(G,G′)的數(shù)值最小。

本文貢獻(xiàn)主要包含3個方面:

1)將本文需要解決的科學(xué)問題轉(zhuǎn)化為求解整數(shù)線性規(guī)劃(Integer Linear Programming,ILP)的問題。

2)利用遺傳算法求解上述ILP問題。

3)在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中對算法進(jìn)行模擬。

2 本文算法

從第1節(jié)描述的關(guān)鍵科學(xué)問題可知,本文需要在已知拓?fù)浣Y(jié)構(gòu)G=(V,E,C)上生成其對應(yīng)的擴(kuò)展結(jié)構(gòu)G′=(V,E,C′),從而使得網(wǎng)絡(luò)交叉度的數(shù)值最小。G=(V,E,C)和G′=(V,E,C′)的唯一區(qū)別是鏈路的權(quán)值集合不同,即本文需要解決如何在G=(V,E,C)的基礎(chǔ)上調(diào)整網(wǎng)絡(luò)中鏈路的權(quán)值,從而使得R(G,G′)的數(shù)值最小。

下面定性地描述本文需要解決的問題:已知網(wǎng)絡(luò)拓?fù)銰=(V,E,C),C={w(e),e∈E},如何調(diào)整網(wǎng)絡(luò)中所有邊的權(quán)值C′={w′(e),e∈E},使得R(G,G′)最小,其中G′=(V,E,C′)。這個問題可用ILP來表示,即:

minR(G,G′)

(1)

s.t.

D(u,u,G)=0,u∈V

(2)

D(u,u,G′)=0,u∈V

(3)

w(i,j)+D(i,d,G)-D(j,d,G)≥0,i,j,d∈V

(4)

w′(i,j)+D(i,d,G′)-D(j,d,G′)≥0,i,j,d∈V

(5)

x(i,j,d)∈{0,1},i,j,d∈V

(6)

y(i,j,d)∈{0,1},i,j,d∈V

(7)

x(i,j,d)+w(i,j)+D(i,d,G)-D(j,d,G)≥1,i,j,d∈V

(8)

i,j,d∈V

(9)

y(i,j,d)+w′(i,j)+D(i,d,G′)-

D(j,d,G′)≥1,i,j,d∈V

(10)

i,j,d∈V

(11)

w(i,j)=w(j,i),w(i,j)∈{1,2,…,max},i,j∈V

(12)

w′(i,j)=w′(j,i),w′(i,j)∈{1,2,…,max},i,j∈V

(13)

在上面描述的問題中,式(1)即是本文需要解決的問題的最終目標(biāo)。式(2)、式(3)表示網(wǎng)絡(luò)中節(jié)點到自身的最短距離為0。式(4)、式(5)代表最短路徑規(guī)則。在式(6)中,x(i,j,d)代表在網(wǎng)絡(luò)G中,節(jié)點(i,d)之間的最短路徑是否包含鏈路(i,j),如果包含則x(i,j,d)=1,否則x(i,j,d)=0。在式(7)中,y(i,j,d)代表在網(wǎng)絡(luò)G′中,節(jié)點(i,d)之間的最短路徑是否包含鏈路(i,j),如果包含則y(i,j,d)=1,否則y(i,j,d)=0。在式(8)中,假如x(i,j,d)=1,則式(8)、式(4)的表達(dá)式是一樣的,相反假如x(i,j,d)=0,式(8)的表達(dá)式將轉(zhuǎn)化為w(i,j)+D(i,d,G)-D(j,d,G)≥1。在式(9)中,假如x(i,j,d)=1,則式(9)將被轉(zhuǎn)化為w(i,j)+D(i,d,G)-D(j,d,G)≤0,合并式(8)、式(9),當(dāng)x(i,j,d)=0時w(i,j)+D(i,d,G)-D(j,d,G)=0。假如x(i,j,d)=0,則式(9)將被轉(zhuǎn)變?yōu)閣(i,j)+D(i,d,G)-D(j,d,G)≤M,M=2×max。在式(10)中,假如y(i,j,d)=1,則式(10)、式(5)的表達(dá)式是一樣的,相反假如y(i,j,d)=0,式(10)的表達(dá)式將轉(zhuǎn)化為w′(i,j)+D(i,d,G′)-D(j,d,G′)≥1。在式(11)中,假如y(i,j,d)=1,則式(11)將被轉(zhuǎn)化為w(i,j)+D(i,d,G′)-D(j,d,G′)≤0,合并式(10)、式(11),當(dāng)y(i,j,d)=0時,w′(i,j)+D(i,d,G′)-D(j,d,G′)=0假如y(i,j,d)=0,式(11)將被轉(zhuǎn)變?yōu)閣′(i,j)+D(i,d,G′)-D(j,d,G′)=0,M=2×max。式(12)、式(13)代表鏈路具有對稱性。

本文解決的問題可以轉(zhuǎn)化為解決ILP的問題。在小拓?fù)渚W(wǎng)絡(luò)中,可以使用cplex計算器計算出最優(yōu)結(jié)果,但是在大拓?fù)渚W(wǎng)絡(luò)中,cplex計算器的執(zhí)行時間較長,無法滿足應(yīng)用的需求。因此,本文提出利用啟發(fā)式方法,即快速計算近似最優(yōu)解。

在啟發(fā)式算法中,如果采用貪心算法來解決上述問題,則算法收斂時間較長,并且容易陷入局部最優(yōu)解。而遺傳算法[19]擁有較強的全局搜索能力,可以快速計算出近似最優(yōu)解從而加快求解速度。同時,為了防止遺傳算法陷入局部最優(yōu)解,本文采用了自適應(yīng)的交叉概率和變異概率。遺傳算法中的操作主要包括遺傳編碼、選擇、交叉算子和變異算子,下面詳細(xì)介紹本文針對每種操作采用的方法。

1)遺傳編碼

本文采用一種最簡單也是比較常見的編碼方式,即二進(jìn)制編碼。在該編碼中,如果某位為0則表示相應(yīng)的鏈路的權(quán)值未發(fā)生變化,為1則表示相應(yīng)的鏈路的權(quán)值發(fā)生變化。對于本文研究的問題,需要|E|位來表示一種解決方案,如(01001010)就表示將鏈路集合E中編號為2、5和7的鏈路的權(quán)值改變,而其他鏈路的權(quán)值沒有變化。本文將遺傳編碼形式化描述為:

2)初始種群的生成

本文采用隨機方式生成初始種群。如果一個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中有k條鏈路,隨機產(chǎn)生k個二進(jìn)制數(shù),則該k個二進(jìn)制數(shù)就是一個種群。假設(shè)初始種群的規(guī)模為n,則將上述的過程執(zhí)行n次就產(chǎn)生出了初始種群。

3)適應(yīng)度

適應(yīng)度函數(shù)也被稱為評價函數(shù),是評價種群中個體性能優(yōu)劣的標(biāo)準(zhǔn),其對應(yīng)的數(shù)值一定是正數(shù),并且數(shù)值越大其對應(yīng)個體的性能越優(yōu)。本文采用網(wǎng)絡(luò)交叉度的倒數(shù)作為適應(yīng)度函數(shù),即:

4)選擇算子

通過該操作來選出種群中個體適應(yīng)度高的個體來進(jìn)化,適應(yīng)度低的個體參與進(jìn)化的機會比較少,后代就會越來越少,從而保證優(yōu)勢群體在后代中占據(jù)的數(shù)量較多。本文采用輪盤賭選擇策略作為選擇算子,其具體方法如下:

(1)根據(jù)適應(yīng)度函數(shù)計算種群中所有個體i={1,2,…,M}對應(yīng)的適應(yīng)度數(shù)值,其中M表示初始種群中個體的數(shù)量;

(2)計算出每個個體被遺傳到下一代的概率;

(3)確定種群中所有個體的累積概率q(i);

(4)產(chǎn)生一個隨機數(shù)r∈[0,1];

(5)如果r

(6)執(zhí)行步驟(4)和步驟(5)M次。

5)交叉算子

對選擇后的種群隨機兩兩匹配,以一定的概率進(jìn)行交叉,產(chǎn)生子代種群。為了防止算法收斂速度較慢或者算法的搜索空間較小,采用一種自適應(yīng)的交叉概率,它根據(jù)適應(yīng)度的變化而變化,可保護(hù)最優(yōu)解并加快劣質(zhì)解的淘汰速度。自適應(yīng)交叉概率的計算公式為:

其中,fmax是種群最大適應(yīng)度,favg是種群平均適應(yīng)度,f′是參與交叉操作的2個個體中適應(yīng)度較大的個體對應(yīng)的適應(yīng)度,k1和k2均為小于等于1的常數(shù)。

6)變異算子

為了增加種群的多樣性,擴(kuò)大遺傳算法的搜索空間,本文采用自適應(yīng)變異概率,計算公式為:

其中,fmax是種群最大適應(yīng)度,favg是種群平均適應(yīng)度,k3和k4均為小于等于1的常數(shù)。

本文提出利用遺傳算法計算近似最優(yōu)解,并描述遺傳算法的具體實施過程。首先初始化算法中的一些參數(shù),如最大遺傳代數(shù)、交叉算子和變異算子中參數(shù)的具體數(shù)值,并利用隨機方法構(gòu)造初始種群(算法第1行、第2行)。然后根據(jù)適應(yīng)度函數(shù)計算初始種群中所有個體對應(yīng)的適應(yīng)度(算法第3行)。下面是迭代過程,每次迭代過程均執(zhí)行選擇、交叉和變異操作(算法第6行～第8行)。在此基礎(chǔ)上修改個體中相應(yīng)的鏈路的權(quán)值,修改方法如下:對于網(wǎng)絡(luò)中的一條鏈路(m,n),將該鏈路對應(yīng)的權(quán)值修改為w′(m,n)=w(m,n)+a(deg(m)+deg(n)),其中,a為變量,用來控制鏈路權(quán)值的變化量,deg(m)表示節(jié)點m的度數(shù)(算法第9行),最后重新評估新個體的適應(yīng)度(算法第10行)。

算法1遺傳算法

輸入G=(V,E,C),C={w(e),e∈E}

輸出G′=(V,E,C′),C′={w′(e),e∈E}

1.初始化算法的參數(shù)

2.產(chǎn)生初始種群

3.計算種群中所有個體的適應(yīng)度

4.gen=0

5.While gen

6.選擇

7.交叉

8.變異

9.修改相應(yīng)個體中鏈路的權(quán)值

10.計算新產(chǎn)生個體的適應(yīng)度

11.End While

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

本節(jié)介紹實驗方法,并且對不同算法的實驗結(jié)果進(jìn)行對比。比較算法GA、LFA和U-turn在網(wǎng)絡(luò)交叉度比率和網(wǎng)絡(luò)可用性2個方面的性能。在實驗中,a為[1,2 500]之間的隨機數(shù),種群規(guī)模的范圍為[200,1 000],k1、k2、k3和k4的取值范圍為[0,1],所有的實驗結(jié)果為運行1 000次算法計算的平均值。

3.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

本文使用了3種典型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu):

1)Abilene[20],該結(jié)構(gòu)由11個路由器和28條鏈路組成,可以訪問美國教育網(wǎng)查詢到該網(wǎng)絡(luò)的具體連接方式。

2)Rocketfuel[21]項目公開了很多測量拓?fù)浣Y(jié)構(gòu),本文選取的結(jié)構(gòu)如表1所示。

表1 Rocketfuel拓?fù)浣Y(jié)構(gòu)

3)波士頓大學(xué)開發(fā)的Brite[22]可以生成類似真實的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),該軟件的參數(shù)如下:模型為Waxman;節(jié)點數(shù)量為50～400;鏈路節(jié)點比值為2～10;節(jié)點位置為隨機;增長方式為增量式;α為0.15;β為0.2;鏈路代價為固定值;最小帶寬為10 Mb/s;最大帶寬為1 024 Mb/s;模式為路由器。

3.2 網(wǎng)絡(luò)交叉度比率

本節(jié)采用網(wǎng)絡(luò)交叉度比率來衡量網(wǎng)絡(luò)中所有節(jié)點對的最短路徑和備份路徑包括的公共邊的數(shù)量總和。本文將該度量定義為:網(wǎng)絡(luò)交叉度(算法執(zhí)行后)/網(wǎng)絡(luò)交叉度(算法執(zhí)行前)。實驗的結(jié)果如圖1～圖3所示,其中,圖1為Abilene和Rocketfuel的結(jié)果,圖2、圖3為Brite的結(jié)果。在Brite結(jié)構(gòu)中得到了兩組實驗結(jié)果。圖2表示固定網(wǎng)絡(luò)平均度為5時改變網(wǎng)絡(luò)拓?fù)浯笮〉慕Y(jié)果。圖3表示固定網(wǎng)絡(luò)拓?fù)浯笮?00時改變網(wǎng)絡(luò)平均度的結(jié)果。從實驗運行的結(jié)果可以看出,GA的結(jié)果明顯優(yōu)于LFA和U-turn的結(jié)果。

圖1 不同算法在Abilene和Rocketfuel上的運行結(jié)果

圖2 3種算法網(wǎng)絡(luò)拓?fù)浯笮〉淖兓闆r

圖3 3種算法網(wǎng)絡(luò)平均度的變化情況

3.3 網(wǎng)絡(luò)可用性

本節(jié)采用網(wǎng)絡(luò)斷開概率來度量網(wǎng)絡(luò)的可用性。網(wǎng)絡(luò)斷開概率定義為:如果網(wǎng)絡(luò)中的所有鏈路根據(jù)一定的概率發(fā)生故障時,網(wǎng)絡(luò)中所有受這些故障影響的節(jié)點對的數(shù)量和網(wǎng)絡(luò)中所有節(jié)點對的數(shù)量之間的比值。

實驗均運行在實際網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中,運行的結(jié)果如圖4～圖6所示。

圖4 不同算法在Abilene上的運行情況

圖5 不同算法在Ebone上的運行情況

圖6 不同算法在Sprint上的運行情況

其中,圖4為Abilene的結(jié)果,圖5為Ebone的結(jié)果,圖6表示Sprint的結(jié)果。在這些實驗結(jié)果中,可以得到如下結(jié)論:當(dāng)網(wǎng)絡(luò)中鏈路的失效概率變大時,網(wǎng)絡(luò)斷開概率的數(shù)值也變大。但是GA的網(wǎng)絡(luò)斷開概率明顯低于其余2種算法對應(yīng)的網(wǎng)絡(luò)斷開概率。例如,如果鏈路失效概率都為0.1時,那么在Sprint中,GA、LFA和U-turn的網(wǎng)絡(luò)斷開概率分別為 12%、16% 和15%。

4 結(jié)束語

本文通過調(diào)整網(wǎng)絡(luò)中鏈路的權(quán)值來計算網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對應(yīng)的擴(kuò)展拓?fù)浣Y(jié)構(gòu),進(jìn)而求得所有目的對對應(yīng)的路徑,使得網(wǎng)絡(luò)交叉度最小。將該問題轉(zhuǎn)化為一個ILP問題,利用遺傳算法計算近似解,并且在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中對算法進(jìn)行模擬。實驗結(jié)果表明,本文方案可以增加網(wǎng)絡(luò)的可用性,降低因故障造成的報文丟失率。