趙甜甜， 孟相如， 趙志遠(yuǎn)， 張亞坤

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077)

面向共享風(fēng)險(xiǎn)鏈路組故障恢復(fù)的多路徑路由生成算法*

趙甜甜， 孟相如， 趙志遠(yuǎn)， 張亞坤

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，陜西 西安 710077)

為了在IP層恢復(fù)網(wǎng)絡(luò)共享風(fēng)險(xiǎn)鏈路組(SRLG)故障，提出一種基于改進(jìn)人工蜂群算法的網(wǎng)絡(luò)多路徑路由生成算法。針對(duì)SRLG故障特點(diǎn)建立多路徑路由生成模型，最后通過(guò)改進(jìn)人工蜂群算法求解。仿真驗(yàn)證該方法不僅可以生成滿足SRLG約束的備用路徑，還可以增強(qiáng)故障恢復(fù)能力、降低算法復(fù)雜度、縮短重路由的平均路徑長(zhǎng)度。

共享風(fēng)險(xiǎn)鏈路組； 多路徑路由； 生成算法； 人工蜂群算法

0 引 言

在基于WDM的光傳輸網(wǎng)絡(luò)中，光纖為網(wǎng)絡(luò)高速、大量傳輸數(shù)據(jù)業(yè)務(wù)提供了便利，但是因?yàn)楣饫w故障可能引發(fā)IP層多條相關(guān)聯(lián)的鏈路同時(shí)故障[1]。此外，自然災(zāi)害和人為攻擊等原因也會(huì)引發(fā)一片區(qū)域內(nèi)關(guān)聯(lián)的多條鏈路同時(shí)失效的情況。IETF工作組定義這些故障為共享風(fēng)險(xiǎn)鏈路組(shared risk link group,SRLG)故障[2]。

文獻(xiàn)[3～6]提出的網(wǎng)絡(luò)可生存性方法大多以解決單、雙鏈路故障或單節(jié)點(diǎn)故障為主，且假設(shè)鏈路故障是獨(dú)立發(fā)生的?，F(xiàn)實(shí)情況卻是基于SRLG的故障頻繁發(fā)生，而大多數(shù)先應(yīng)式故障恢復(fù)方法在處理此類故障時(shí)無(wú)能為力。

利用多路徑路由技術(shù)解決SRLG故障問(wèn)題的研究已經(jīng)起步[7]，文獻(xiàn)[8]基于故障概率和風(fēng)險(xiǎn)將SRLG故障劃分等級(jí)提出兩種部分不相交的多路徑路由模型，利用“地震圖”仿真驗(yàn)證；文獻(xiàn)[9]以多路徑中聯(lián)合故障概率最小為目標(biāo)建模并求解最佳路徑。

本文提出一種面向SRLG故障恢復(fù)的多路徑路由生成算法,并通過(guò)仿真驗(yàn)證了本文方法在實(shí)際網(wǎng)絡(luò)中的性能。

1 相關(guān)理論

多路徑路由技術(shù)解決網(wǎng)絡(luò)故障的基本思路是：在網(wǎng)絡(luò)層預(yù)先計(jì)算工作和備用兩條不同的路徑，當(dāng)網(wǎng)絡(luò)鏈路或節(jié)點(diǎn)發(fā)生故障時(shí)，可以無(wú)中斷地切換工作路徑至備用路徑，達(dá)到故障快速恢復(fù)的目的。

由于共享底層一條物理網(wǎng)絡(luò)鏈路斷路而引發(fā)上層IP層多條鏈路同時(shí)斷路的故障類型稱之為SRLG故障，稱這些同時(shí)受到影響的相關(guān)聯(lián)的IP層鏈路為SRLG。

多路徑路由依據(jù)保護(hù)元素不同，可分為鏈路不相交多路徑(link disjoint multi path,LD—MP)、節(jié)點(diǎn)不相交多路徑(node disjoint multi path,ND—MP)和SRLG不相交多路徑(SRLG disjoint multi path,SD—MP)。圖1(a)～(d)分別為從

節(jié)點(diǎn)B到節(jié)點(diǎn)K的原始拓?fù)渎窂?LD—MP,ND—MP和SD—MP示意圖。假設(shè)圖中存在一個(gè)SRLG包括三條鏈路：C→D,D→H,G→H，從節(jié)點(diǎn)B到節(jié)點(diǎn)K的原始路徑為B→C→D→E→K，與之鏈路不相交路徑為圖(a)中B→A→D→H→K，與之節(jié)點(diǎn)不相交路徑為圖(b)中B→F→G→H→K，與之SRLG不相交路徑為圖(c)中B→A→K。

圖1 不相交多路徑示意圖Fig 1 Disjoint multi path schematic diagram

LD—MP條件：若路徑s→d的工作路徑包含鏈路i→j，則s→d的備用路徑不包含i→j，也不包含j→i。對(duì)?s∈N/9zlp55p，?i,j∈N，表達(dá)式為

(1)

ND—MP條件：若路徑s→d的工作路徑包含節(jié)點(diǎn)i，則s→d的備用路徑不包含節(jié)點(diǎn)i。對(duì)于?s∈Njrtvtjn，?i∈N{s,d}，表達(dá)式為

(2)

SD—MP條件：若路徑s→d的工作路徑包含r中任何一條鏈路，則s→d的備用路徑不包含r中所有鏈路。對(duì)于?s∈Ndzj5xph，?r∈R，表達(dá)式為

(3)

2 面向SRLG故障恢復(fù)的多路徑路由生成算法

傳統(tǒng)多路徑生成算法一般基于工作路徑優(yōu)先考慮，在原始拓?fù)渲姓业阶顑?yōu)路徑作為工作路徑，然后將工作路徑經(jīng)過(guò)的所有鏈路和這些鏈路所在SRLG包含的所有鏈路刪除，在余下的路徑中找到次優(yōu)的路徑作為備用路徑。這種生成算法操作簡(jiǎn)單，但是易造成“陷阱”，即由于過(guò)度刪除使得本身存在的符合條件的路徑未在運(yùn)行該算法時(shí)找到。文獻(xiàn)[10]提出可變鏈路權(quán)值SRLG分離的雙路由選擇策略具有一定的實(shí)用價(jià)值。

本文面向SRLG故障恢復(fù)，綜合多路徑建模時(shí)路徑不相交、節(jié)點(diǎn)不相交、SRLG不相交的約束條件建立多路徑生成模型，并利用改進(jìn)的人工蜂群算法求解。

2.1 生成模型建立

面向SRLG故障恢復(fù)的多路徑路由生成模型

(4)

s.t.

?s∈Nzjxzhvxand?i∈N

(5)

?s∈N/5htrpv5and ?i∈N

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

算法變量定義如表1。

表1 算法變量定義 Tab 1 Algorithm variables defined

其中，式(4)為目標(biāo)函數(shù)，通過(guò)三個(gè)可變參數(shù)λ1,λ2,λ3調(diào)節(jié)鏈路、節(jié)點(diǎn)以及SRLG對(duì)工作路徑和備用路徑權(quán)重的影響；式(5)、式(6)分別限定工作路徑和備用路徑在初始節(jié)點(diǎn)、中間節(jié)點(diǎn)和目的節(jié)點(diǎn)的網(wǎng)絡(luò)流量的大??；式(7)、式(8)分別表示工作路徑和備用路徑的鏈路不存在環(huán)路；式(9)～式(12)為約定工作路徑和備用路徑鏈路、節(jié)點(diǎn)、SRLG不相交條件。

2.2 改進(jìn)蜂群算法求解

人工蜂群(artificial bee colony,ABC)算法是一種啟發(fā)式群智能全局尋優(yōu)算法，該算法通過(guò)模擬蜜蜂覓食等行為求解數(shù)值優(yōu)化問(wèn)題，具有參數(shù)調(diào)節(jié)少、操作簡(jiǎn)單、易于實(shí)現(xiàn)、魯棒性強(qiáng)、收斂速度快等特點(diǎn)[11]。

利用人工蜂群算法求解面向SRLG故障恢復(fù)的多路徑路由生成問(wèn)題時(shí)，結(jié)合可變參數(shù)調(diào)節(jié)并設(shè)立公告板公式SRLG信息，提出基于改進(jìn)的人工蜂群(modified ABC,MABC)算法。

1)二進(jìn)制編碼:為了降低算法搜索的時(shí)間復(fù)雜度，采用二進(jìn)制順序字符串網(wǎng)絡(luò)編碼方式，即網(wǎng)絡(luò)G(N,L,R)共N個(gè)節(jié)點(diǎn)、L條鏈路，編碼形成2Lbit二進(jìn)制字符串，分別對(duì)應(yīng)網(wǎng)絡(luò)鏈路的正方向和反方向。若某路徑經(jīng)過(guò)某鏈路正方向則前Lbit該位置為1，若經(jīng)過(guò)某鏈路反方向,則后Lbit該位置為1，不經(jīng)過(guò)的位置為0。

2)可變參數(shù)調(diào)節(jié):當(dāng)網(wǎng)絡(luò)中鏈路與節(jié)點(diǎn)比高時(shí)，表示網(wǎng)絡(luò)中可選路徑數(shù)量豐富，可以加大λ1和λ2所占比重；當(dāng)網(wǎng)絡(luò)中SRLG數(shù)量較少時(shí)，表示SRLG對(duì)網(wǎng)絡(luò)的影響是很大的，可以加大λ3所占比重。

3)增加公告板:公示每個(gè)SRLG包含的鏈路信息，跟隨蜂獲得引領(lǐng)蜂分享的蜜源信息后和進(jìn)行鄰域搜索后都會(huì)對(duì)比查找公告板SRLG信息以便剔除有共同信息的蜜源，保持不跟隨狀態(tài)。

改進(jìn)人工蜂群算法流程如圖2所示。

圖2 MABC算法流程圖Fig 2 Flow chart of MABC algorithm

3 仿真與性能分析

3.1 仿真環(huán)境與參數(shù)

1)網(wǎng)絡(luò)生成：利用網(wǎng)絡(luò)生成器BRITE隨機(jī)生成包含11個(gè)節(jié)點(diǎn)，21條鏈路的隨機(jī)網(wǎng)絡(luò)拓?fù)洹?/p>

圖3 隨機(jī)網(wǎng)絡(luò)拓?fù)涫疽鈭DFig 3 Diagram of random network topology

2)故障設(shè)置：設(shè)置兩個(gè)SRLG，r1={1-7.4-11,6-8}，r2={1-4,3-5,7-8}。

3.2 仿真結(jié)果分析

將本文改進(jìn)算法、人工蜂群算法、文獻(xiàn)[10]路徑分離方法、工作路徑優(yōu)先算法四種不同方法作為對(duì)比組，從故障恢復(fù)能力和平均路徑長(zhǎng)度兩方面對(duì)比分析。

圖4 故障恢復(fù)能力對(duì)比圖Fig 4 Contrast figure of failure recovery ability

由圖4可知:本文所提方法故障恢復(fù)能力與文獻(xiàn)[10]所提方法均很大，在SRLG數(shù)量較少時(shí)，可以達(dá)到100 %生成，在SRLG數(shù)量增多時(shí)，恢復(fù)能力略有下降，但是較工作路徑優(yōu)先算法恢復(fù)能力強(qiáng)。

圖5 平均路徑長(zhǎng)度對(duì)比圖Fig 5 Contrast figure of average path length

由圖5可知:相比較文獻(xiàn)[10]和工作路徑優(yōu)先算法，人工蜂群算法可以縮短恢復(fù)路徑長(zhǎng)度，原因在群智能生成算法以路徑經(jīng)過(guò)的鏈路長(zhǎng)短為適應(yīng)值函數(shù)篩選蜜源位置。與傳統(tǒng)人工蜂群算法相比，本文算法引入可變參數(shù)調(diào)節(jié)使得生成的備用路徑是較優(yōu)的恢復(fù)路徑。

4 結(jié)束語(yǔ)

本文提出面向SRLG故障恢復(fù)的多路徑路由生成算法，通過(guò)分析SRLG故障特點(diǎn)引入可變參數(shù)調(diào)節(jié)多路徑路由生成模型，并利用二進(jìn)制編碼、設(shè)立公告板公示SRLG信息等改進(jìn)人工蜂群算法對(duì)模型求解。通過(guò)與其他恢復(fù)方

法對(duì)比可知本文方法可以提高多路徑路由的恢復(fù)效果，有一定的理論意義。

[1] Chen Zhen,Han Fuye,Cao Junwei,et al.Cloud computing-based forensic analysis for collaborative network security management system[J].Tsinghua Science and Technology,2013,18(1):40-50.

[2] Papadimitriou D,Poppe F,Jones J.Inference of shared risk link groups[EB/OL].2001—11—14.http:∥www.watersprings.org/pub/id/draft-many-inference-srlg-02.txt.

[3] Jayavelu G,Ramasubramanian S,Younis O.Maintaining colored trees for disjoint multipath routing under node failures[J].IEEE/ACM Transactions on Networking,2009,17(1):346-359.

[4] Zhang Mingui,Liu Bin.Traffic engineering for proactive failure recovery of IP networks[J].Tsinghua Science and Technology,2011,16(1):55-61.

[5] 伍 文，孟相如，劉蕓江，等.IP網(wǎng)絡(luò)彈性路由層拓?fù)渖蓛?yōu)化算法[J].電子科技大學(xué)學(xué)報(bào)，2014，43(5)：769-774.

[6] 王明鳴，孟相如，李紀(jì)真，等.基于著色樹優(yōu)化的網(wǎng)絡(luò)并發(fā)雙鏈路故障恢復(fù)方法[J].計(jì)算機(jī)應(yīng)用研究,2015,32(6):1822-1825.

[7] 王 濱，楊 強(qiáng)，吳春明.IP網(wǎng)絡(luò)可生存性技術(shù)[M].北京：人民郵電出版社，2013.

[8] Moritz Kiese,Velislava Marcheva,Jorg Eberspacher,et al.Diverse routing based on shared risk link group[C]∥7th International Workshop on the Design of Reliable Communication Networks,IEEE,2009:153-159.

[9] Lee Hyang-Won,Modiano Eytan,Lee Kayi.Diverse routing in networks with probabilistic failures[J].IEEE/ACM Transactions on Networking,2010,18(6):1895-1907.

[10] 孫 晨，白顯毅.一種基于SRLG分離的雙路由選擇策略[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(12):131-134.

[11] 暴 勵(lì).一種思維進(jìn)化蜂群算法[J].電子學(xué)報(bào),2015,43(5):948-954.

Generation algorithm of multi-path routing for recovery from shared risk link group failures*

ZHAO Tian-tian， MENG Xiang-ru， ZHAO Zhi-yuan， ZHANG Ya-kun

(School of Information and Navigation,Air Force Engineering University,Xi’an 710077,China)

Aiming at recovering from network shared risk link group(SRLG)failures in IP layer,a generation algorithm of network multi-path routing is proposed based on modified artificial bee colony algorithm.A multi-path routing generation model focusing on SRLG failure characteristic is created and modified artificial bee colony algorithm is used to solve it.Simulation results show that this method can not only generate backup path satisfied to SRLG constraints, but also can strengthen failure recovery ability,reduce algorithm complexity and shorten average length of rerouting path.

shared risk link group(SRLG); multi-path routing; generation algorithm; artificial bee colony algorithm

10.13873/J.1000—9787(2016)07—0129—03

2015—10—09

國(guó)家自然科學(xué)基金資助項(xiàng)目(61201209)

TP 393

A

1000—9787(2016)07—0129—03

趙甜甜(1990-)，女，山西臨汾人，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)抗毀性。