域間路由系統(tǒng)級聯(lián)失效分析與建模

陸余良, 楊　斌

(電子工程學(xué)院網(wǎng)絡(luò)系, 安徽 合肥 230037)

?

域間路由系統(tǒng)級聯(lián)失效分析與建模

陸余良, 楊斌

(電子工程學(xué)院網(wǎng)絡(luò)系, 安徽 合肥 230037)

摘要：針對域間路由系統(tǒng)的級聯(lián)失效展開研究,分析了系統(tǒng)級聯(lián)失效的機(jī)制,建立了域間路由系統(tǒng)級聯(lián)失效模型。模型引入了符合節(jié)點真實信息的IRS介數(shù),并基于IRS介數(shù)定義節(jié)點的初始負(fù)載;針對系統(tǒng)中節(jié)點的重啟現(xiàn)象和BGP更新報文的交互現(xiàn)象,引入了節(jié)點重啟時延和更新報文存活時延,使構(gòu)建的級聯(lián)失效模型更加符合系統(tǒng)的真實情況。最后,通過仿真實驗分析了IRS介數(shù)與其他測度的區(qū)別,研究了不同模型參數(shù)對系統(tǒng)級聯(lián)失效的影響。研究結(jié)果為分析和提升域間路由系統(tǒng)的安全性能提供了有效的參考和借鑒。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);域間路由系統(tǒng);級聯(lián)失效;傳播模型;重啟時延

0引言

近年來,關(guān)于域間路由系統(tǒng)的安全性研究主要集中于異常行為檢測和安全性的增強等方面[1-5],但作為一個復(fù)雜網(wǎng)絡(luò)系統(tǒng),針對域間路由系統(tǒng)級聯(lián)失效現(xiàn)象的研究相對較少。級聯(lián)失效(又稱級聯(lián)故障)是指,當(dāng)網(wǎng)絡(luò)中節(jié)點由于過載而效率低下甚至失效后,該節(jié)點所承載的流量負(fù)載繞行其他節(jié)點,增加的流量負(fù)載造成其他節(jié)點的過載或失效,失效過程反復(fù)進(jìn)行,導(dǎo)致網(wǎng)絡(luò)運行被影響的現(xiàn)象[6]。例如,2001年爆發(fā)的Code-RedⅡ和Nimda病毒就曾造成了互聯(lián)網(wǎng)的大面積癱瘓,其中一個重要原因就是域間路由系統(tǒng)的級聯(lián)失效加劇了網(wǎng)絡(luò)的不穩(wěn)定。因此,有必要對域間路由系統(tǒng)的級聯(lián)失效做深入分析研究。

級聯(lián)失效作為復(fù)雜網(wǎng)絡(luò)的一個熱點問題,已吸引較多的學(xué)者展開研究[7-12]。2007年,文獻(xiàn)[13]提出了一種針對級聯(lián)失效的復(fù)雜網(wǎng)絡(luò)模型,認(rèn)為度值大的節(jié)點應(yīng)具有較高的負(fù)載能力,仿真結(jié)果表明,相比于ML模型和WK模型,文獻(xiàn)[13]所提出的節(jié)點容量模型具有更好的穩(wěn)定性,對網(wǎng)絡(luò)系統(tǒng)的構(gòu)建具有指導(dǎo)性作用。文獻(xiàn)[14]提出了一種基于節(jié)點及其鄰居節(jié)點度的負(fù)載衡量方法,并在該規(guī)則上分別對度高和度低的節(jié)點進(jìn)行攻擊,仿真結(jié)果表明,在一定情況下,兩者具有相同的攻擊效果。因此,在提高網(wǎng)絡(luò)的魯棒性時不僅需要考慮核心節(jié)點,也要考慮對邊緣節(jié)點的防護(hù)。文獻(xiàn)[15]利用流量守恒定律來考慮邊的負(fù)載情況,研究了美國電網(wǎng)的級聯(lián)故障行為,考慮了負(fù)載重分布對美國電網(wǎng)級聯(lián)故障的影響。目前,級聯(lián)失效模型的相關(guān)研究中,節(jié)點的初始負(fù)載主要通過節(jié)點的度或介數(shù)來定義。但是,由于域間路由系統(tǒng)主要為互聯(lián)網(wǎng)提供流量轉(zhuǎn)發(fā)服務(wù),域間路由系統(tǒng)節(jié)點的初始負(fù)載應(yīng)為經(jīng)過該節(jié)點的流量信息。因此,節(jié)點的度無法表征域間路由系統(tǒng)節(jié)點的負(fù)載信息;由于節(jié)點的介數(shù)僅考慮節(jié)點的連接關(guān)系,并未考慮域間路由系統(tǒng)節(jié)點間的商業(yè)關(guān)系,因此節(jié)點介數(shù)也無法體現(xiàn)域間路由系統(tǒng)節(jié)點的真實負(fù)載情況。另外,已有的級聯(lián)失效模型認(rèn)為,一旦網(wǎng)絡(luò)中的節(jié)點失效,將不會重新連入網(wǎng)絡(luò)中,這并不符合域間路由系統(tǒng)的實際情況。同時,域間路由系統(tǒng)中的路由器在失效和重啟時,系統(tǒng)中將傳播承載相關(guān)路由信息的BGP更新報文。綜上,現(xiàn)有的級聯(lián)失效模型并未考慮這些問題,因此無法真實地反映域間路由系統(tǒng)的級聯(lián)失效現(xiàn)象。

針對上述問題,本文分析了域間路由系統(tǒng)的級聯(lián)失效機(jī)制,定義了符合域間路由系統(tǒng)節(jié)點信息的IRS介數(shù),并基于IRS介數(shù)定義了系統(tǒng)中各節(jié)點的負(fù)載。同時,通過引入路由器重啟時延、更新報文存活時延來分析系統(tǒng)節(jié)點重啟、失效的真實過程,使得模型對域間路由系統(tǒng)級聯(lián)失效的分析更具實際意義。最后通過實驗分析了IRS介數(shù)與其他節(jié)點測度的區(qū)別,驗證了模型的有效性和真實性,研究了不同模型參數(shù)和不同攻擊策略對域間路由系統(tǒng)級聯(lián)失效的影響。

1域間路由系統(tǒng)級聯(lián)失效機(jī)制分析

域間路由系統(tǒng)是個龐大的復(fù)雜網(wǎng)絡(luò)系統(tǒng),因此一個自治域節(jié)點的失效或者斷開均有可能造成域間路由系統(tǒng)的級聯(lián)失效,從而引發(fā)大規(guī)模的系統(tǒng)故障,影響系統(tǒng)的運行。對域間路由系統(tǒng)的分析顯示,造成域間路由系統(tǒng)級聯(lián)失效的原因主要有以下兩點:①節(jié)點失效引發(fā)的負(fù)載重分配。自治域在域間路由系統(tǒng)中主要負(fù)責(zé)轉(zhuǎn)發(fā)流量負(fù)載,若某個節(jié)點失效,則該節(jié)點所承載的流量負(fù)載將按照一定的規(guī)則向其鄰居節(jié)點進(jìn)行分派。若鄰居節(jié)點所承擔(dān)的負(fù)載超過了它的額定負(fù)載,鄰居節(jié)點就會相繼過載失效,如此反復(fù),進(jìn)而引發(fā)系統(tǒng)的級聯(lián)失效現(xiàn)象;②BGP更新報文導(dǎo)致的節(jié)點失效。域間路由系統(tǒng)節(jié)點間主要通過BGP協(xié)議交互彼此的路由信息。當(dāng)系統(tǒng)中節(jié)點失效或重啟時,將通過BGP協(xié)議的更新報文向全網(wǎng)宣告相關(guān)的路由信息,即該節(jié)點不可達(dá)的信息或該節(jié)點的相關(guān)路由信息。多個節(jié)點的失效或重啟現(xiàn)象有可能導(dǎo)致網(wǎng)絡(luò)中BGP更新報文的爆發(fā),消耗系統(tǒng)中節(jié)點的處理能力,即負(fù)載能力,繼而引發(fā)級聯(lián)失效。

2域間路由系統(tǒng)級聯(lián)模型構(gòu)建

本文將域間路由系統(tǒng)表示成一個具有N個節(jié)點和M條邊的無向圖,并用G=(V,E)表示,其中V表示頂點的集合,E表示邊的集合。

2.1相關(guān)參數(shù)定義

域間路由系統(tǒng)中各個節(jié)點的負(fù)載在每個時間單元內(nèi)均會有所變化,例如節(jié)點失效(重啟)所引發(fā)的更新報文、負(fù)載的重分配等,因此用Li(t)表示節(jié)點i在t時刻的負(fù)載容量。特別地,當(dāng)時刻t取0時,表示域間路由系統(tǒng)級聯(lián)失效初始階段節(jié)點i的初始負(fù)載Li(0)。

域間路由系統(tǒng)主要提供流量轉(zhuǎn)發(fā)的服務(wù),因此節(jié)點的初始負(fù)載與經(jīng)過該節(jié)點的最短路徑數(shù)有關(guān),即與節(jié)點的介數(shù)有關(guān)。同樣地,本文使用節(jié)點的介數(shù)來初始化節(jié)點的初始負(fù)載,但是傳統(tǒng)的節(jié)點介數(shù)僅從網(wǎng)絡(luò)的連接來分析,不符合域間路由系統(tǒng)的真實情況,這是因為自治域間的商業(yè)關(guān)系[16]有可能導(dǎo)致自治域不會為與其直接相連的兩個自治域提供轉(zhuǎn)發(fā)流量的服務(wù),即存在連接的3個自治域并不相互可達(dá)的情況。考察圖1所示的小型網(wǎng)絡(luò)。

圖1　某小型網(wǎng)絡(luò)

如圖1所示,根據(jù)域間路由系統(tǒng)的商業(yè)關(guān)系規(guī)則,節(jié)點X到達(dá)節(jié)點B有且僅有一條路徑XDCB。但是,依據(jù)傳統(tǒng)介數(shù)的定義,節(jié)點X到達(dá)節(jié)點B的路徑有分別為XAB和XDCB的兩條路徑,顯然,傳統(tǒng)介數(shù)的定義方式并不符合域間路由系統(tǒng)的真實情況。針對這一問題,本文定義了域間路由系統(tǒng)節(jié)點的新介數(shù)——域間路由系統(tǒng)介數(shù)(inter-domain routing system betweenness,IRS)。在介紹IRS介數(shù)之前,定義域間路由系統(tǒng)節(jié)點對間的最短路徑集如下。

定義 1域間路由系統(tǒng)節(jié)點間的最短路徑集是指一個自治域節(jié)點到另一個自治域節(jié)點的穩(wěn)定路由路徑中,長度最短路徑所構(gòu)成的集合,用LLPS描述,節(jié)點i、j間的最短路徑集LLPSi,j定義如下:

(1)

式中,RSi,j表示域間路由系統(tǒng)中連接節(jié)點i、j的穩(wěn)定路由路徑;NP為路徑P的長度。

定義 2節(jié)點的IRS介數(shù)是指節(jié)點在系統(tǒng)的所有節(jié)點對最短路徑集中所出現(xiàn)的頻度,用IRS描述,節(jié)點k的IRS介數(shù)記為IRSk:

(2)

式中，LLPSi,j(k)表示節(jié)點k在節(jié)點i、j間最短路由路徑集中出現(xiàn)的路徑數(shù),若節(jié)點k在一條路徑中出現(xiàn)多次,僅記為一次。

根據(jù)IRS介數(shù),本文定義節(jié)點的初始負(fù)載如下:

(3)

式中，IRSi,j(k)指節(jié)點k在節(jié)點i和節(jié)點j的最短路徑中出現(xiàn)的次數(shù);分母表示節(jié)點i和節(jié)點j的最短路徑數(shù)。

在定義了節(jié)點的初始負(fù)載之后,進(jìn)一步定義節(jié)點的額定負(fù)載。本文采用類似于文獻(xiàn)[17]中的額定負(fù)載設(shè)定方法,定義節(jié)點i的額定負(fù)載Ci如下:

(4)

式中,系數(shù)γ稱為容忍系數(shù),表征了系統(tǒng)中節(jié)點對負(fù)載的容忍程度。

以往的級聯(lián)失效模型認(rèn)為,節(jié)點失效后,就徹底地從網(wǎng)絡(luò)中移除了,并未考慮到節(jié)點重啟并再次連入系統(tǒng)的情況,這與域間路由系統(tǒng)的實際情況不符。針對這一問題,本文引入節(jié)點i的重啟時延ΔTi,以衡量節(jié)點重新啟動連入網(wǎng)絡(luò)所需要的時間。節(jié)點重啟時延的大小表征了該節(jié)點的重啟時延與系統(tǒng)級聯(lián)失效傳播時間的比值。當(dāng)重啟時延的取值為0時,表示該節(jié)點在失效的時刻立即重新啟動并連入域間路由系統(tǒng);當(dāng)重啟時延的取值為∞時,即表示節(jié)點在失效后,不再連入域間路由系統(tǒng),等價于該節(jié)點永久失效。

針對域間路由系統(tǒng)失效機(jī)制的分析表明,節(jié)點的失效和重連有可能造成網(wǎng)絡(luò)中BGP更新報文的驟增,增加網(wǎng)絡(luò)中節(jié)點的負(fù)載,然而這類報文并不是網(wǎng)絡(luò)中的主要負(fù)載流量,且具有一定的存活時限。因此,為真實地反映節(jié)點失效和重連時所產(chǎn)生的更新報文對系統(tǒng)的影響,定義更新報文存活時延如下。

定義 3更新報文存活時延描述的是一個更新報文從產(chǎn)生到消亡所需要耗費的時間,即更新報文在系統(tǒng)中存活的時間,記為TAlive。

與重啟時延相似,更新報文存活時延的大小表征了更新報文的存活時延與系統(tǒng)級聯(lián)失效傳播時間的比值。當(dāng)TAlive=0時,則更新報文在系統(tǒng)中存活時間為0,等價于域間路由系統(tǒng)從未產(chǎn)生過更新報文;當(dāng)TAlive=∞時,系統(tǒng)中的更新報文不會隨時間消亡,即更新報文一旦產(chǎn)生就不會消失。

2.2域間路由系統(tǒng)級聯(lián)失效過程解析

根據(jù)復(fù)雜網(wǎng)絡(luò)的級聯(lián)失效演化過程,將域間路由系統(tǒng)的級聯(lián)失效過程劃分為如下幾個階段:故障啟動階段、級聯(lián)故障傳播階段、系統(tǒng)穩(wěn)定階段。

(1)故障啟動階段。域間路由系統(tǒng)穩(wěn)定運行,即尚未有節(jié)點發(fā)生故障時,各個節(jié)點均處于自由流(Free-Flow)狀態(tài)。此時,各節(jié)點的負(fù)載可以用Li(0)表示,且滿足如下關(guān)系式:

(5)

當(dāng)域間路由系統(tǒng)受到干擾時,系統(tǒng)中部分節(jié)點會由于自身故障或者外界攻擊而過載失效,這一階段稱為域間路由系統(tǒng)的故障啟動階段。失效節(jié)點滿足如下關(guān)系:

(6)

式中,F表示由于自身故障或外界攻擊而失效的節(jié)點集合;Ri是節(jié)點i所受到的干擾,即自身的故障或外界的攻擊。

(2) 級聯(lián)故障傳播階段。級聯(lián)故障傳播期間,系統(tǒng)中節(jié)點負(fù)載的變化主要有3種方式。

①根據(jù)BGP的協(xié)議規(guī)則,節(jié)點失效后,其鄰居節(jié)點將會向外發(fā)送更新報文以注銷與該節(jié)點相關(guān)的路由信息,相繼地,該鄰居節(jié)點將會繼續(xù)向外傳播路由更新信息,進(jìn)而造成全網(wǎng)負(fù)載的增加。同樣地,失效節(jié)點重啟后,將與鄰居節(jié)點建立BGP連接,宣告有關(guān)該路由的信息,鄰居節(jié)點將會繼續(xù)向外宣告該節(jié)點加入系統(tǒng)的路由信息,進(jìn)而造成系統(tǒng)負(fù)載的增加。更新報文造成的負(fù)載可表示如下:

(7)

式中，Ψ表示失效、重啟的節(jié)點集;Lupdatek指節(jié)點k重啟(失效)所引發(fā)更新報文的負(fù)載。

為簡化模型,設(shè)定所有節(jié)點的失效(重啟)所造成的更新報文負(fù)載相同,則式(7)可簡化為

(8)

式中,NΨ表示系統(tǒng)中失效、重啟的節(jié)點數(shù);Lupdate是單位更新報文的負(fù)載。

②節(jié)點i失效后,其所承擔(dān)的流量負(fù)載將按照一定的規(guī)則重分配給其鄰居節(jié)點。本文認(rèn)為這種負(fù)載傳播規(guī)則是按照節(jié)點的額定負(fù)載來分配的,即鄰居節(jié)點中額定負(fù)載較大的節(jié)點能夠分配到較多的負(fù)載,這種擇優(yōu)的負(fù)載重分配方式能夠保持網(wǎng)絡(luò)整體通信的通暢,一定程度上抵御了級聯(lián)失效造成的影響,具體負(fù)載重分配方式為

(9)

式中，Cj表示節(jié)點j的額定負(fù)載;Γi表示節(jié)點i的所有鄰居節(jié)點。

根據(jù)額定負(fù)載的定義,可將式(9)簡化如下:

(10)

③節(jié)點的重啟主要包括建立連接和正常運行兩個基本步驟。首先,節(jié)點重啟并與鄰居節(jié)點建立連接,即節(jié)點通過BGP更新報文向周圍節(jié)點宣告路由信息及節(jié)點存活消息,接著,該節(jié)點承擔(dān)原先繞行鄰居節(jié)點的負(fù)載并正常工作。例如,當(dāng)節(jié)點i在t-1時刻重啟時,其并未承擔(dān)網(wǎng)絡(luò)中的任何負(fù)載,這是由于網(wǎng)絡(luò)中并沒有經(jīng)過該節(jié)點的路由信息,此時,節(jié)點i通過更新報文向外宣告自身的存活信息。在t時刻,節(jié)點i開始正常運行并承擔(dān)網(wǎng)絡(luò)中原先繞行鄰居節(jié)點的負(fù)載,此時,節(jié)點i及其鄰居節(jié)點的負(fù)載如式(11)、式(12)所示:

(11)

(12)

綜合上述分析,節(jié)點j在時刻t的負(fù)載可表示為

(13)

式中，Ψt表示在t時刻節(jié)點j鄰居中失效、重啟的節(jié)點集;Rt表示節(jié)點j的鄰居中,在t-1時刻重啟,t時刻正常運行的節(jié)點集。

故障傳播期間,若節(jié)點j的負(fù)載滿足如下關(guān)系:

(14)

即負(fù)載超過節(jié)點的額定負(fù)載時,則節(jié)點j失效并將造成系統(tǒng)故障的進(jìn)一步擴(kuò)散,引發(fā)更深層次的故障。

(3) 系統(tǒng)穩(wěn)定階段。與以往級聯(lián)失效結(jié)束的界定方式不同,由于本文定義了節(jié)點的重啟時延,因此考慮如下的兩種情況:

①當(dāng)ΔTi=∞時,系統(tǒng)的所有存活節(jié)點均正常工作,且不再會由于其他節(jié)點的失效而進(jìn)一步引發(fā)故障,即網(wǎng)絡(luò)中正常工作節(jié)點的負(fù)載均小于其額定負(fù)載;

②當(dāng)ΔTi≠∞時,由于系統(tǒng)中的節(jié)點將會重啟,因此系統(tǒng)中的故障節(jié)點不可能一直處于失效的狀態(tài),即系統(tǒng)各節(jié)點正常運作將是域間路由系統(tǒng)級聯(lián)失效的最終狀態(tài)。

2.3模型假設(shè)和度量指標(biāo)

本文在采用建立的級聯(lián)失效模型分析域間路由系統(tǒng)的級聯(lián)失效現(xiàn)象時,對模型做出如下假設(shè):

(1) 在域間路由系統(tǒng)中,相較于節(jié)點的初始負(fù)載而言,實際協(xié)議更新報文的負(fù)載較小,因此模型設(shè)定BGP協(xié)議更新報文的負(fù)載如下:

(15)

(2) 節(jié)點間的更新報文是驟發(fā)的,即若一個節(jié)點失效(重啟),則關(guān)于節(jié)點路由的更新報文能夠在下一個時刻傳播到網(wǎng)絡(luò)中的各節(jié)點。

(3) 域間路由系統(tǒng)的路由信息在一定時間內(nèi)能夠維持相對穩(wěn)定,即域間路由系統(tǒng)中各節(jié)點的IRS介數(shù)在一定時期內(nèi)穩(wěn)定不變。

為量化分析級聯(lián)失效對域間路由系統(tǒng)的影響程度,定義無效節(jié)點和無效鏈接如下:

定義 4無效節(jié)點指系統(tǒng)中由于級聯(lián)失效而無法正常工作的節(jié)點,主要可分為以下兩類節(jié)點:

(1) 由于過載無法正常轉(zhuǎn)發(fā)流量負(fù)載的節(jié)點,即系統(tǒng)中的失效節(jié)點;

(2) 系統(tǒng)中無法與其他節(jié)點進(jìn)行通信的節(jié)點,即級聯(lián)失效導(dǎo)致的孤立節(jié)點。

定義 5對于系統(tǒng)中的鏈接,若其任意一端節(jié)點無效,則該鏈接無法實現(xiàn)轉(zhuǎn)發(fā)流量的功能,將這類喪失轉(zhuǎn)發(fā)功能的鏈接稱為無效鏈接。

(16)

(17)

式中,F表示失效的節(jié)點集;fi、vi表示節(jié)點i失效時,無效節(jié)點和無效鏈接所占的比例。

3仿真實驗

為了驗證本文域間路由系統(tǒng)級聯(lián)失效模型的有效性,選取CAIDA項目中所提供的2010年01月的BGP AS Relationship數(shù)據(jù)和RouteViews項目采集的路由路徑數(shù)據(jù)作為實驗數(shù)據(jù)[18-19]。數(shù)據(jù)集的分析結(jié)果如表1和表2所示。實驗主要采用蓄意攻擊策略,即攻擊網(wǎng)絡(luò)中的重要節(jié)點,通常指承載負(fù)載較多的節(jié)點。本文中各實驗均以比例p=0.01%選取節(jié)點進(jìn)行攻擊,重復(fù)仿真100次,最后取平均值作為實驗結(jié)果。

表1　BGP AS Relationship的分析結(jié)果

表2　路由路徑集的分析結(jié)果

3.1IRS介數(shù)、度和介數(shù)分析

根據(jù)IRS介數(shù)、節(jié)點度以及介數(shù)的定義,分別計算了各節(jié)點的不同測度值。選取其中IRS介數(shù)、節(jié)點度以及介數(shù)最大的20個節(jié)點作為代表進(jìn)行對比分析,結(jié)果如圖2所示。

圖2　節(jié)點相關(guān)測度對比

由圖2可見,相比于節(jié)點度,域間路由系統(tǒng)節(jié)點的介數(shù)和IRS介數(shù)值較大,可以觀察到,無論是介數(shù)還是IRS介數(shù),節(jié)點之間的差別均比節(jié)點間度的差別顯著。因此,節(jié)點的介數(shù)、IRS介數(shù)能夠更為有效地區(qū)分域間路由系統(tǒng)中的節(jié)點。同時,由節(jié)點的介數(shù)曲線可知,相對于節(jié)點的IRS介數(shù),節(jié)點的介數(shù)值極大,分析其原因,主要是由于節(jié)點的介數(shù)僅考慮了節(jié)點的連接關(guān)系,并未考慮節(jié)點之間的商業(yè)關(guān)系規(guī)則,使得每對節(jié)點之間的最短連接數(shù)較多,造成了節(jié)點介數(shù)值極大的原因。相對地,IRS介數(shù)主要考察了網(wǎng)絡(luò)中的實際路由路徑信息,真實地反映了域間路由系統(tǒng)各個節(jié)點間流量的轉(zhuǎn)發(fā)情況。因此,IRS介數(shù)能夠真實地反映域間路由系統(tǒng)節(jié)點流經(jīng)流量的情況,其值較介數(shù)也相對較低。

3.2不同模型下的級聯(lián)失效分析

圖3　本文模型(α=2,γ=1,TAlive=3,ΔT=4)與傳統(tǒng)模型(α=2,γ=2,β=2)的級聯(lián)失效對比圖

3.3模型參數(shù)對域間路由系統(tǒng)級聯(lián)失效的影響

3.3.1負(fù)載參數(shù)對模型的影響

α取值為0.5,1時,不同容忍系數(shù)γ對本文模型的影響,得到實驗結(jié)果如圖4所示。

圖4　、隨γ的變化情況(TAlive=5,ΔT=∞)

如圖4所示,ΔT=∞,α固定的情況下,隨著γ的增加,域間路由系統(tǒng)發(fā)生級聯(lián)失效所引發(fā)的無效節(jié)點和無效鏈接將逐漸減少。顯然,當(dāng)γ增加時,系統(tǒng)中各節(jié)點的額定負(fù)載也相應(yīng)增加,節(jié)點失效的概率越小,域間路由系統(tǒng)的穩(wěn)定性更高,系統(tǒng)表現(xiàn)出的抵制級聯(lián)失效的能力越強。

考慮ΔT≠∞的情況。根據(jù)級聯(lián)失效過程分析,為了避免級聯(lián)失效的發(fā)生,節(jié)點j需要滿足關(guān)系式Lj(t)≤Cj。根據(jù)式中各個元素的定義,可以將上式表示為

(18)

進(jìn)一步簡化如下:

(19)

(20)

式中,ΔLΓj,tj表示在t時刻節(jié)點j的鄰居節(jié)點中,未正常工作的節(jié)點分配給節(jié)點j的負(fù)載,k表示在t時刻網(wǎng)絡(luò)中所存在的更新報文數(shù)。特別地,取t=1,進(jìn)一步化簡式(20),可知當(dāng)γ滿足式(21)時,即可保證節(jié)點i的失效并不會導(dǎo)致節(jié)點j的失效:

(21)

對于給定的域間路由系統(tǒng),由于更新報文的負(fù)載和存活時延一定,節(jié)點j的鄰居節(jié)點失效所引發(fā)的負(fù)載重分配規(guī)則固定,若容忍系數(shù)γ越大,滿足不等式(20)的可能性越大,節(jié)點失效的概率越小,系統(tǒng)的穩(wěn)定性也就越高。

由圖4可以明顯地看出,無論參數(shù)α如何變化,在其余參數(shù)不變時,系統(tǒng)的級聯(lián)失效效果沒有區(qū)別,這與式(20)相符,即式(20)中的參數(shù)與負(fù)載參數(shù)α無關(guān),因此無論α如何變化,系統(tǒng)的級聯(lián)效果不變。

3.3.2更新報文存活時延對模型的影響

考察不同取值的TAlive對級聯(lián)失效的影響效果并進(jìn)行仿真,得到實驗結(jié)果如圖5所示。

圖5　TAlive對級聯(lián)失效的影響對比圖(α=2,γ=1)

3.3.3重啟時延對模型的影響

考察ΔT對系統(tǒng)級聯(lián)產(chǎn)生的影響,針對不同取值ΔT的系統(tǒng)級聯(lián)失效進(jìn)行仿真,實驗結(jié)果如圖6所示(圖中,不同節(jié)點重啟時延的設(shè)定如下:依據(jù)初始負(fù)載的大小將節(jié)點均勻地分為20類,并分別設(shè)定為從1到20的重啟時延)。

圖6　ΔT對級聯(lián)失效的影響(α=2,γ=1,TAlive=3)

從圖中可以明顯看出,相對于其他情況,ΔT=0時,系統(tǒng)能夠維持較好地穩(wěn)定性。分析原因,主要是由于單節(jié)點故障所能影響的節(jié)點相對較少,節(jié)點失效和重啟所產(chǎn)生的BGP更新報文有限,同時由于失效節(jié)點立即重啟,能夠迅速承擔(dān)繞行其鄰居節(jié)點的流量,使得其鄰居節(jié)點失效的幾率降低,導(dǎo)致無效節(jié)點和無效鏈接相對較少,因此相對其他情況,域間路由系統(tǒng)能夠恢復(fù)到更為穩(wěn)定的狀態(tài)。

對比重啟時延為5,10以及不同重啟時延的級聯(lián)失效實驗結(jié)果,可以發(fā)現(xiàn),節(jié)點重啟時延不同的網(wǎng)絡(luò)相對于所有節(jié)點重啟時延相同的網(wǎng)絡(luò)能較好地抵御級聯(lián)失效,具有更好的魯棒性。造成這一現(xiàn)象的主要原因是各個節(jié)點的重啟時延不同,即同一時刻失效的節(jié)點不會同時重啟,系統(tǒng)中存活的更新報文數(shù)量相對較少,對級聯(lián)失效的影響較小,從而導(dǎo)致相對于所有節(jié)點重啟時延一致的情況,不同重啟時延的系統(tǒng)具有更好的穩(wěn)定性。

4結(jié)論

本文在分析和總結(jié)相關(guān)工作的基礎(chǔ)上,針對域間路由系統(tǒng)與傳統(tǒng)復(fù)雜網(wǎng)絡(luò)系統(tǒng)工作機(jī)制的不同,提出了一種符合真實情況的域間路由系統(tǒng)級聯(lián)失效模型。為了能夠較好地衡量節(jié)點,本文定義了符合域間路由系統(tǒng)節(jié)點的IRS介數(shù)。同時,在模型中引入了節(jié)點重啟時延和更新報文存活時延,使模型能夠更加真實地反映域間路由系統(tǒng)。實驗結(jié)果表明,IRS介數(shù)能夠有效地區(qū)分域間路由系統(tǒng)的節(jié)點并真實反映流經(jīng)節(jié)點的流量情況;更新報文存活時延的增加將更大程度地引發(fā)系統(tǒng)的抖動現(xiàn)象;相對于將系統(tǒng)中各節(jié)點的重啟時延設(shè)置為一致值,節(jié)點重啟時延的多樣性分布將在一定程度上提高系統(tǒng)的魯棒性。

針對域間路由系統(tǒng)的級聯(lián)失效提出理論模型只是研究域間路由系統(tǒng)安全的一個前提,針對系統(tǒng)級聯(lián)失效的預(yù)防和控制也同樣亟需研究。論文下一步的工作將主要針對有限資源下域間路由系統(tǒng)的防護(hù)資源分布策略和級聯(lián)失效的控制機(jī)制展開研究。

參考文獻(xiàn)：

[1] Li S, Zhuge J W, Li X. Study on BGP security[J].JournalofSoftware, 2013,24(1):121-138.(黎松,諸葛建偉,李星.BGP安全研究[J].軟件學(xué)報，2013,24(1):121-138.)

[2] Yang B, Lu Y L, Yang G Z, et al. Path forging detection approach based on aggregation[J].ComputerScience, 2014,41(8):158-163.(楊斌, 陸余良, 楊國正,等.一種基于聚類的路徑偽造檢測方法[J].計算機(jī)科學(xué),2014,41(8):158-163.)

[3] Butler K, Farley T R, McDaniel P, et al.A survey of BGP security issues and solutions[J].ProceedingsoftheIEEE,2010,98(1):100-122.

[4] Hong S C, Hong J W K, Ju H.IP prefix hijacking detection using the collection of AS characteristics[C]∥Proc.ofthe17thNetworkOperationsandManagementSymposium，2011:1-7.

[5] Wang B, An J L,Wu C M,et al. Study of BGP secure scheme based on divide and conquer strategy[J].JournalonCommunications, 2012, 33(5):91-98.(王濱,安金梁,吳春明,等.基于分治策略的BGP安全機(jī)制[J].通信學(xué)報,2012,33(5):91-98.)

[6] Xiao Y D, Lao S Y, Hou L L, et al. Network control ability based on node overloaded failure[J].ActaPhysicaSinica,2013,62(18):180201-180203.(肖延?xùn)|,老松楊,侯綠林,等.基于節(jié)點負(fù)荷失效的網(wǎng)絡(luò)可控性研究[J].物理學(xué)報,2013,62(18):180201-180203.)

[7] Shi M C, Shao P P, Xiao Q Z. An LCOR model for suppressing cascading failure in weighted complex networks[J].ChinesePhysicsB, 2013, 22(5): 058901.

[8] Huang L, Lai Y C, Chen G. Understanding and preventing cascading breakdown in complex clustered networks[J].PhysicalReviewE, 2008, 78(3): 036116.

[9] Sergey V B, Roni P, Gerald P, et al.Catastrophic cascade of failures in interdependent network[J].Nature,2010,464(4):1025-1028.

[10] Huang Y Y,Jin C.Invulnerability analysis of logistics infrastructure network based on cascading failure[J].ControlandDecision,2014,29(9),1711-1714.(黃英藝,金淳.物流基礎(chǔ)設(shè)施網(wǎng)絡(luò)級聯(lián)失效下的抗毀性分析[J].控制與決策,2014,29(9),1711-1714.)

[11] Rosas-Casals M, Solé R. Analysis of major failures in Europe’s power grid[J].InternationalJournalofElectricalPower&EnergySystems, 2011, 33(3): 805-808.

[12] Chang L, Wu Z.Performance and reliability of electrical power grids under cascading failures[J].InternationalJournalofElectricalPower&EnergySystems,2011,33(8):1410-1419.

[13] Li P, Wang B H, Sun H, et al. A limited resource model of fault-tolerant capability against cascading failure of complex network[J].TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems, 2008, 62(1): 101-104.

[14] Jian W W, Li L R. Effect attack on scale-free networks due to cascading failures[J].ChinesePhysicsLetters,2008,25(10):3826.

[15] Simonsen I, Buzna L, Peters K, et al. Transient dynamics increasing network vulnerability to cascading failures[J].PhysicalReviewLetters, 2008, 100(21): 218701.

[16] Gao L. On inferring autonomous system relationships in the Internet[J].IEEE/ACMTrans.onNetworking,2001,9(6):733-745.

[17] Motter A E, Lai Y C. Cascade-based attacks on complex networks[J].PhysicalReviewE, 2002, 66(6): 065102.

[18] CAIDA. BGP AS relationship[EB/OL]. http:∥as-rank.caida.org, 2011-02-01.

[19] Route views project page[OL].http:∥www.routeviews.org.2005.

[20] Guo Y, Wang Z, Luo S, et al. A cascading failure model for interdomain routing system[J].InternationalJournalofCommunicationSystems, 2012, 25(8): 1068-1076.

陸余良(1964-),男,教授,博士研究生導(dǎo)師,主要研究方向為計算機(jī)網(wǎng)絡(luò)安全。

E-mail:Luyuliang@ah165.net

楊斌(1989-),男,博士研究生,主要研究方向為計算機(jī)網(wǎng)絡(luò)安全。

E-mail:810941186@qq.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20150910.1050.008.html

Analysing and modeling cascading failures for inter-domain routing system

LU Yu-liang, YANG Bin

(DepartmentofNetwork,ElectronicEngineeringInstitute,Hefei230037,China)

Abstract:The cascading failures for the inter-domain routing system is researched. Based on the analysis of cascading behaviors for the inter-domain routing system, an cascading failure model for the inter-domain routing system is proposed. By introducing node’s IRS betweenness which is consistent with the inter-domain routing system, node’s initial load is defined. In order to simulate the real situation of the system, node’s restart delay and BGP update alive delay are introduced. Finally, by analyzing the difference between IRS betweenness with other node’s measurements, the impact on cascading failures of different model parameters is investigated. Moreover, research findings will provide useful guidance and reference for analyzing and improving the security of the inter-domain routing system.

Keywords:complex network; inter-domain routing system; cascading failure; propagation model; restart delay

作者簡介：

中圖分類號：TP 393

文獻(xiàn)標(biāo)志碼：A

DOI:10.3969/j.issn.1001-506X.2016.01.27

基金項目：國家自然科學(xué)基金(61171170)；安徽省自然科學(xué)基金(1408085QF115)資助課題

收稿日期：2015-03-25；修回日期：2015-06-27；網(wǎng)絡(luò)優(yōu)先出版日期：2015-09-10。