陸余良, 楊　斌

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

?

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

陸余良, 楊斌

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

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

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

0引言

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

(4)

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

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

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

定義 3更新報(bào)文存活時(shí)延描述的是一個(gè)更新報(bào)文從產(chǎn)生到消亡所需要耗費(fèi)的時(shí)間,即更新報(bào)文在系統(tǒng)中存活的時(shí)間,記為T(mén)Alive。

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

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

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

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

(5)

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

(6)

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

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

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

(7)

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

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

(8)

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

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

(9)

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

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

(10)

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

(11)

(12)

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

(13)

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

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

(14)

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

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

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

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

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

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

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

(15)

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

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

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

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

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

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

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

(16)

(17)

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

3仿真實(shí)驗(yàn)

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

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

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

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

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

圖2　節(jié)點(diǎn)相關(guān)測(cè)度對(duì)比

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

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

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

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

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

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

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

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

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

(18)

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

(19)

(20)

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

(21)

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

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

3.3.2更新報(bào)文存活時(shí)延對(duì)模型的影響

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

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

3.3.3重啟時(shí)延對(duì)模型的影響

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

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

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

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

4結(jié)論

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

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

參考文獻(xiàn)：

[1] Li S, Zhuge J W, Li X. Study on BGP security[J].JournalofSoftware, 2013,24(1):121-138.(黎松,諸葛建偉,李星.BGP安全研究[J].軟件學(xué)報(bào)，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.(楊斌, 陸余良, 楊國(guó)正,等.一種基于聚類的路徑偽造檢測(cè)方法[J].計(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é)報(bào),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é)點(diǎn)負(fù)荷失效的網(wǎng)絡(luò)可控性研究[J].物理學(xué)報(bào),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ò)級(jí)聯(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)師,主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全。

E-mail:Luyuliang@ah165.net

楊斌(1989-),男,博士研究生,主要研究方向?yàn)橛?jì)算機(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

作者簡(jiǎn)介：

中圖分類號(hào)：TP 393

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

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

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

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