面向共享風險鏈路組故障恢復的多路徑路由生成算法*

趙甜甜， 孟相如， 趙志遠， 張亞坤

(空軍工程大學 信息與導航學院，陜西 西安 710077)

面向共享風險鏈路組故障恢復的多路徑路由生成算法*

趙甜甜， 孟相如， 趙志遠， 張亞坤

(空軍工程大學 信息與導航學院，陜西 西安 710077)

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

共享風險鏈路組； 多路徑路由； 生成算法； 人工蜂群算法

0 引 言

在基于WDM的光傳輸網絡中，光纖為網絡高速、大量傳輸數據業務提供了便利，但是因為光纖故障可能引發IP層多條相關聯的鏈路同時故障[1]。此外，自然災害和人為攻擊等原因也會引發一片區域內關聯的多條鏈路同時失效的情況。IETF工作組定義這些故障為共享風險鏈路組(shared risk link group,SRLG)故障[2]。

文獻[3～6]提出的網絡可生存性方法大多以解決單、雙鏈路故障或單節點故障為主，且假設鏈路故障是獨立發生的。現實情況卻是基于SRLG的故障頻繁發生，而大多數先應式故障恢復方法在處理此類故障時無能為力。

利用多路徑路由技術解決SRLG故障問題的研究已經起步[7]，文獻[8]基于故障概率和風險將SRLG故障劃分等級提出兩種部分不相交的多路徑路由模型，利用“地震圖”仿真驗證；文獻[9]以多路徑中聯合故障概率最小為目標建模并求解最佳路徑。

本文提出一種面向SRLG故障恢復的多路徑路由生成算法,并通過仿真驗證了本文方法在實際網絡中的性能。

1 相關理論

多路徑路由技術解決網絡故障的基本思路是：在網絡層預先計算工作和備用兩條不同的路徑，當網絡鏈路或節點發生故障時，可以無中斷地切換工作路徑至備用路徑，達到故障快速恢復的目的。

由于共享底層一條物理網絡鏈路斷路而引發上層IP層多條鏈路同時斷路的故障類型稱之為SRLG故障，稱這些同時受到影響的相關聯的IP層鏈路為SRLG。

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

節點B到節點K的原始拓撲路徑,LD—MP,ND—MP和SD—MP示意圖。假設圖中存在一個SRLG包括三條鏈路：C→D,D→H,G→H，從節點B到節點K的原始路徑為B→C→D→E→K，與之鏈路不相交路徑為圖(a)中B→A→D→H→K，與之節點不相交路徑為圖(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。對?s∈N/g0gggggg，?i,j∈N，表達式為

(1)

ND—MP條件：若路徑s→d的工作路徑包含節點i，則s→d的備用路徑不包含節點i。對于?s∈Ng0gggggg，?i∈N{s,d}，表達式為

(2)

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

(3)

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

傳統多路徑生成算法一般基于工作路徑優先考慮，在原始拓撲中找到最優路徑作為工作路徑，然后將工作路徑經過的所有鏈路和這些鏈路所在SRLG包含的所有鏈路刪除，在余下的路徑中找到次優的路徑作為備用路徑。這種生成算法操作簡單，但是易造成“陷阱”，即由于過度刪除使得本身存在的符合條件的路徑未在運行該算法時找到。文獻[10]提出可變鏈路權值SRLG分離的雙路由選擇策略具有一定的實用價值。

本文面向SRLG故障恢復，綜合多路徑建模時路徑不相交、節點不相交、SRLG不相交的約束條件建立多路徑生成模型，并利用改進的人工蜂群算法求解。

2.1 生成模型建立

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

(4)

s.t.

?s∈Ng0ggggggand?i∈N

(5)

?s∈N/g0ggggggand ?i∈N

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

算法變量定義如表1。

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

其中，式(4)為目標函數，通過三個可變參數λ1,λ2,λ3調節鏈路、節點以及SRLG對工作路徑和備用路徑權重的影響；式(5)、式(6)分別限定工作路徑和備用路徑在初始節點、中間節點和目的節點的網絡流量的大小；式(7)、式(8)分別表示工作路徑和備用路徑的鏈路不存在環路；式(9)～式(12)為約定工作路徑和備用路徑鏈路、節點、SRLG不相交條件。

2.2 改進蜂群算法求解

人工蜂群(artificial bee colony,ABC)算法是一種啟發式群智能全局尋優算法，該算法通過模擬蜜蜂覓食等行為求解數值優化問題，具有參數調節少、操作簡單、易于實現、魯棒性強、收斂速度快等特點[11]。

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

1)二進制編碼:為了降低算法搜索的時間復雜度，采用二進制順序字符串網絡編碼方式，即網絡G(N,L,R)共N個節點、L條鏈路，編碼形成2Lbit二進制字符串，分別對應網絡鏈路的正方向和反方向。若某路徑經過某鏈路正方向則前Lbit該位置為1，若經過某鏈路反方向,則后Lbit該位置為1，不經過的位置為0。

2)可變參數調節:當網絡中鏈路與節點比高時，表示網絡中可選路徑數量豐富，可以加大λ1和λ2所占比重；當網絡中SRLG數量較少時，表示SRLG對網絡的影響是很大的，可以加大λ3所占比重。

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

改進人工蜂群算法流程如圖2所示。

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

3 仿真與性能分析

3.1 仿真環境與參數

1)網絡生成：利用網絡生成器BRITE隨機生成包含11個節點，21條鏈路的隨機網絡拓撲。

圖3 隨機網絡拓撲示意圖Fig 3 Diagram of random network topology

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

3.2 仿真結果分析

將本文改進算法、人工蜂群算法、文獻[10]路徑分離方法、工作路徑優先算法四種不同方法作為對比組，從故障恢復能力和平均路徑長度兩方面對比分析。

圖4 故障恢復能力對比圖Fig 4 Contrast figure of failure recovery ability

由圖4可知:本文所提方法故障恢復能力與文獻[10]所提方法均很大，在SRLG數量較少時，可以達到100 %生成，在SRLG數量增多時，恢復能力略有下降，但是較工作路徑優先算法恢復能力強。

圖5 平均路徑長度對比圖Fig 5 Contrast figure of average path length

由圖5可知:相比較文獻[10]和工作路徑優先算法，人工蜂群算法可以縮短恢復路徑長度，原因在群智能生成算法以路徑經過的鏈路長短為適應值函數篩選蜜源位置。與傳統人工蜂群算法相比，本文算法引入可變參數調節使得生成的備用路徑是較優的恢復路徑。

4 結束語

本文提出面向SRLG故障恢復的多路徑路由生成算法，通過分析SRLG故障特點引入可變參數調節多路徑路由生成模型，并利用二進制編碼、設立公告板公示SRLG信息等改進人工蜂群算法對模型求解。通過與其他恢復方

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

[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網絡彈性路由層拓撲生成優化算法[J].電子科技大學學報，2014，43(5)：769-774.

[6] 王明鳴，孟相如，李紀真，等.基于著色樹優化的網絡并發雙鏈路故障恢復方法[J].計算機應用研究,2015,32(6):1822-1825.

[7] 王 濱，楊 強，吳春明.IP網絡可生存性技術[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].計算機技術與發展,2009,19(12):131-134.

[11] 暴 勵.一種思維進化蜂群算法[J].電子學報,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

國家自然科學基金資助項目(61201209)

TP 393

A

1000—9787(2016)07—0129—03

趙甜甜(1990-)，女，山西臨汾人，碩士研究生，主要研究方向為網絡抗毀性。