朱會虎，邱菡，朱俊虎，曾子懿

基于傳播動力學的域間路由系統(tǒng)關鍵節(jié)點識別方法

朱會虎1,2，邱菡1,2，朱俊虎1,2，曾子懿1,2

（1. 數學工程與先進計算國家重點實驗室，河南 鄭州 450001；2. 國家數字交換系統(tǒng)工程技術研究中心，河南 鄭州 450001）

域間路由系統(tǒng)是互聯(lián)網的關鍵基礎設施，對域間路由系統(tǒng)中的關鍵節(jié)點實施保護具有重要意義。針對現(xiàn)有關鍵節(jié)點識別方法識別出的關鍵節(jié)點不能反映節(jié)點在失效傳播過程中起到關鍵作用的問題，提出了基于傳播動力學的關鍵節(jié)點識別方法。該方法通過綜合考慮節(jié)點失效后引發(fā)的負載重分配和UPDATE報文傳播對周圍節(jié)點和邊產生的影響，提出了基于DDF-CFM模型的節(jié)點重要性評估模型。實驗結果表明，該方法相比已有方法識別關鍵節(jié)點的準確程度至少提高7.3%。同時，在10 000個網絡的規(guī)模下，僅5個關鍵節(jié)點失效就將導致大規(guī)模的域間路由系統(tǒng)級聯(lián)失效。

域間路由系統(tǒng)；關鍵節(jié)點；評估；傳播動力學

1 引言

域間路由系統(tǒng)是互聯(lián)網的關鍵基礎設施，一旦遭受攻擊將對互聯(lián)網造成巨大損失。近年來，研究者提出了一系列針對域間路由系統(tǒng)的攻擊方法，典型的包括CXPST（coordinated cross plane session termination）攻擊[1]、壓力測試攻擊[2]、DNP（distributed network paralyzing）攻擊[3]以及LFA(link-flooding attacks)[4]等，該類攻擊一旦達成將對互聯(lián)網造成不可估量的損傷。此外，報告顯示該類攻擊已經逐步出現(xiàn)在現(xiàn)實生活中[5]，因此對該類攻擊的防御迫在眉睫。該類攻擊主要是通過攻擊部分關鍵節(jié)點，造成域間路由系統(tǒng)級聯(lián)失效，并產生較大范圍的影響。其原因在于域間路由系統(tǒng)中節(jié)點間存在耦合關系，部分關鍵節(jié)點的失效會引發(fā)域間路由系統(tǒng)級聯(lián)失效。為了防御該類攻擊，需要找到在域間路由系統(tǒng)發(fā)生級聯(lián)失效時起關鍵作用的節(jié)點，并對其實施有針對性的保護，從而加大攻擊者攻擊的難度，降低攻擊的損害程度。

2 相關研究

在復雜網絡領域，依據研究的角度不同，識別關鍵節(jié)點的方法分為兩類：基于網絡結構的關鍵節(jié)點識別方法和基于傳播動力學的關鍵節(jié)點識別方法[6]?；诰W絡結構的關鍵節(jié)點識別方法主要將結構屬性作為評價節(jié)點重要程度的指標，通過節(jié)點的重要程度來識別關鍵節(jié)點[7-9]；基于傳播動力學的關鍵節(jié)點識別方法主要研究節(jié)點在傳播動力學過程中產生的影響大小[10]。由于域間路由網絡的拓撲結構和網絡流量路徑選擇的方式與一般的復雜網絡存在較大差異，導致一般復雜網絡中，基于靜態(tài)結構屬性的關鍵節(jié)點識別方法不能很好地解決域間路由系統(tǒng)關鍵節(jié)點識別的問題。而且域間路由系統(tǒng)中節(jié)點和邊的失效條件不同，導致節(jié)點失效后產生影響的傳播動力學機制與一般復雜網絡有較大差別，因此復雜網絡中基于傳播動力學的關鍵節(jié)點識別方法不能直接應用在域間路由系統(tǒng)中進行關鍵節(jié)點識別。現(xiàn)有針對域間路由系統(tǒng)的關鍵節(jié)點識別方法研究主要是從網絡結構的角度出發(fā)，分為兩種思路：一是認為節(jié)點的度越大節(jié)點越重要[11]；二是認為節(jié)點的介數越大節(jié)點越重要[1]。將度作為評價節(jié)點重要性的指標，認為度越大的節(jié)點其鄰居節(jié)點越多，從而導致經過其上的流量越多，因此認為摘除度大的節(jié)點影響更大。度作為網絡節(jié)點一個比較重要的屬性，能夠在一定程度上反映出節(jié)點的重要性，但用來評估域間路由系統(tǒng)節(jié)點重要性仍然存在較大局限性。域間路由系統(tǒng)中的節(jié)點按照所處的位置不同，可以分為核心節(jié)點和邊緣節(jié)點。核心區(qū)域的節(jié)點與邊緣區(qū)域的節(jié)點在度相同的情況下，重要程度有較大差別。將單一的度作為評價節(jié)點重要性的標準，會造成較大的誤差。將介數作為節(jié)點選擇的依據，也很難真實地反映出節(jié)點在域間路由系統(tǒng)中的重要程度。節(jié)點介數是指網絡中所有經過該節(jié)點的最短路徑占所有最短路徑的比，因此介數的大小主要與最短路徑相關。但域間路由系統(tǒng)中路由路徑的選擇并不僅與最短路徑相關，還與AS（autonomous system）域之間的商業(yè)關系以及局部優(yōu)先級等因素相關，因此介數大的節(jié)點，經過其上的流量并不一定多，重要程度也并不一定高。文獻[12]提出了一種基于首選路由的關鍵AS識別方法（PR-TEAO，technique of evaluating AS importance based on preferred route），其主要思想是認為經過最優(yōu)路徑越多的節(jié)點越重要。其本質是對介數中心性的改進，克服了介數不能表示實際流量的問題，能反映節(jié)點失效后對周圍節(jié)點負載的影響。但節(jié)點失效后不但對負載產生影響，其失效后產生的UPDATE報文對其他節(jié)點在資源消耗上也會產生較大影響。因此，不能完全反映節(jié)點在失效傳播過程中的作用。

本文研究目標是找出在級聯(lián)失效過程中起關鍵作用的節(jié)點，評價節(jié)點是否關鍵，需要評估節(jié)點失效后產生的影響大??；產生的影響越大，其在級聯(lián)失效過程中的作用越關鍵，這樣的節(jié)點就是關鍵節(jié)點。域間路由系統(tǒng)單個節(jié)點的失效會造成UPDATE報文傳播和負載重分配兩方面影響，UPDATE報文傳播導致新的節(jié)點失效，負載重分配又導致邊失效，如此反復造成整個域間路由系統(tǒng)級聯(lián)失效。因此，評估節(jié)點的重要性首先需要對節(jié)點失效后產生的兩方面影響進行量化分析，進而提出評估節(jié)點重要性的綜合指標。對節(jié)點失效后產生的影響進行量化分析，首先需要對節(jié)點失效后造成的傳播動力學過程進行建模分析，之后通過運用該模型進行節(jié)點摘除實驗，采集實驗過程數據，基于該數據利用綜合評估方法評估節(jié)點重要度，進而依據重要度的大小識別出關鍵節(jié)點。

3 域間路由系統(tǒng)級聯(lián)失效傳播動力學分析

本節(jié)主要分析域間路由系統(tǒng)級聯(lián)失效的傳播動力學過程，研究影響級聯(lián)失效傳播的關鍵因素，找出適合描述域間路由系統(tǒng)傳播動力學過程的傳播模型。

3.1 級聯(lián)失效傳播動力學過程分析

域間路由系統(tǒng)級聯(lián)失效傳播過程主要包括兩階段[13]，分別是級聯(lián)失效觸發(fā)階段和失效傳播階段。觸發(fā)階段是指節(jié)點（或邊）發(fā)生故障或遭受攻擊，使節(jié)點（或邊）失效；基于節(jié)點間的耦合關系，部分節(jié)點（或邊）的失效可以觸發(fā)級聯(lián)失效。失效傳播階段是指當節(jié)點（或邊）失效時，導致經過該節(jié)點（或邊）的負載重新選路，引發(fā)負載重分配；同時，相鄰的節(jié)點向周圍節(jié)點傳播UPDATE報文，通報節(jié)點失效情況，大量節(jié)點（或邊）失效可以導致域間路由系統(tǒng)中產生過量的UPDATE報文。研究表明，負載重分配后，一些新的邊由于業(yè)務流量急劇增加，導致過載失效[14]；而且，當過量的UPDATE報文同時到達某一個節(jié)點時，導致該節(jié)點CPU、內存等資源耗盡，引發(fā)節(jié)點失效。新的節(jié)點和邊的失效又導致新一輪的負載重分配和UPDATE報文傳播，從而促進域間路由系統(tǒng)級聯(lián)失效傳播，具體過程如圖1所示。

圖1 級聯(lián)失效過程分析

因此，負載重分配和UPDATE報文是導致域間路由系統(tǒng)級聯(lián)失效傳播的兩個關鍵因素。為了刻畫域間路由系統(tǒng)級聯(lián)失效傳播動力學過程，需要對其過程進行建模。文獻[11]給出了CFM（cascading failure model）模型，該模型認為節(jié)點和邊失效是等價的，都是由過載引發(fā)的。文獻[15]和文獻[16]繼承了文獻[11]的思想，認為導致級聯(lián)失效傳播的主要因素是負載重分配。三者均沒有考慮UPDATE報文級聯(lián)失效的促進作用，與事實不相符。文獻[17]同時考慮了負載重分配和UPDATE報文級聯(lián)失效的影響，提出DDF-CFM（double damage factor based inter-domain routing system cascading failure model）模型，與本文分析相同，因此，本文在DDF-CFM模型的基礎上，進一步分析節(jié)點失效后對周圍節(jié)點產生的影響。

3.2 DDF-CFM模型的運行過程

DDF-CFM模型主要模擬了負載重分配和UPDATE報文在域間路由系統(tǒng)的傳播過程，刻畫了節(jié)點和邊的失效過程，還原了級聯(lián)失效在域間路由系統(tǒng)中的傳播過程。利用該模型，可以采集單節(jié)點失效后造成的UPDATE報文傳播和負載重分配對周圍節(jié)點和邊產生影響大小的基礎評估數據，基于該數據結合節(jié)點重要性評估模型，可以對節(jié)點的重要性進行量化評估。DDF-CFM模型主要工作流程如下。

步驟1 摘除部分節(jié)點（或邊），觸發(fā)級聯(lián)失效過程。

步驟2 判斷是否存在失效節(jié)點（或邊），若不存在，結束；若存在，則進行下一步。

步驟3 找出與失效節(jié)點（或邊）相鄰的所有節(jié)點，作為UPDATE報文傳播的初始節(jié)點，將這些初始節(jié)點加入路由轉發(fā)集

步驟4 判斷路由轉發(fā)集中的節(jié)點是否存在節(jié)點需要向外發(fā)送或轉發(fā)UPDATE報文信息，需要則進行下一步，不需要則進行步驟7。

步驟5 將接收到UPDATE報文信息的節(jié)點加入新的路由轉發(fā)集1，周圍節(jié)點接收到UPDATE報文信息后，對其進行解析處理，更新自己的路由信息表和路由轉發(fā)表。

步驟6 判斷是否有新的節(jié)點因UPDATE報文過量，導致CPU、內存等資源耗盡失效，如果有，將與之相鄰的節(jié)點加入新的路由轉發(fā)集1，重復步驟4~步驟6；若沒有，則進行下一步。

步驟7 找出最優(yōu)路徑受到影響的節(jié)點和邊，依據最優(yōu)路徑選擇方法找出新的最優(yōu)路徑，將原有負載加到新的最優(yōu)路徑上。

步驟8 判斷負載重分配后，各條邊是否過載，過載則失效，將失效邊加入失效集中，回到步驟2。

DDF-CFM模型具體運行過程如圖2所示。

圖2 DDF-CFM模型運行過程

4 基于失效影響的節(jié)點重要性評估模型

域間路由系統(tǒng)中節(jié)點重要性是由該節(jié)點失效后對周圍節(jié)點產生的影響大小來決定的。由3.1節(jié)的分析可知，節(jié)點的失效主要對周圍節(jié)點產生如下兩方面影響：1) 導致負載重分配，使其他邊負載增加；2) 導致相鄰的節(jié)點向其周圍的節(jié)點發(fā)送UPDATE報文信息，消耗周圍節(jié)點的CPU和內存等資源。因此，分別從這兩個方面對單個節(jié)點失效后對網絡的影響程度進行評估。

4.1 負載重分配對邊的影響

4.2 UPDATE報文對節(jié)點的影響

當節(jié)點失效時，與該節(jié)點相鄰的節(jié)點向其周圍的節(jié)點發(fā)送UPDATE報文信息，通報節(jié)點失效情況。其他節(jié)點接收到報文信息后，對報文信息進行解析，修改自己的路由信息表和路由轉發(fā)表。之后，判斷是否轉發(fā)該報文。需要，則轉發(fā)；不需要，則不轉發(fā)。一個UPDATE報文由節(jié)點檢測到會話斷開而產生，到不再有節(jié)點轉發(fā)而停止。報文的傳播過程可以看作節(jié)點失效后整個影響過程。主要和兩個因素相關，分別是相鄰節(jié)點的數目以及每個相鄰節(jié)點產生的UPDATE報文的影響范圍。

圖3 域間路由系統(tǒng)局部結構示意

4.3 單節(jié)點失效對域間路由系統(tǒng)整體影響評估

4.4 關鍵節(jié)點識別方法的評價標準

評價關鍵節(jié)點識別方法好壞的主要思路是將這些方法識別出的關鍵節(jié)點集作為研究對象，通過考察這些節(jié)點摘除后對網絡結構和功能的影響大小[19]。當基于網絡結構屬性識別關鍵節(jié)點時，主要通過考察摘除部分節(jié)點對整體網絡結構的影響，用網絡的頑健性和脆弱性來評價方法的好壞。當基于網絡的傳播動力學過程研究節(jié)點的重要度時，主要通過考察部分節(jié)點摘除后對失效傳播過程的影響來評估方法的好壞，造成節(jié)點和邊的失效比例越高，說明方法越好。

5 基于傳播動力學的域間路由系統(tǒng)關鍵節(jié)點識別過程

5.1 關鍵節(jié)點識別過程

通過前文的分析可知，域間路由系統(tǒng)關鍵節(jié)點識別主要包含兩個階段。首先建立域間路由系統(tǒng)級聯(lián)失效傳播動力學模型，在這個模型的基礎上，采集相關的網絡數據，利用基于失效影響的節(jié)點重要性評估模型，評價各個節(jié)點的重要程度。之后，綜合比較各個節(jié)點的重要程度選出較為關鍵的節(jié)點，具體過程如下。

步驟1 利用真實的網絡數據建立基礎的網絡環(huán)境，作為運行DDF-CFM模型的基礎。

步驟2 從域間路由系統(tǒng)節(jié)點集中選擇一個節(jié)點，作為摘除節(jié)點，輸入DDF-CFM模型中。

步驟3 在模型運行過程中，通過記錄每一次循環(huán)受影響的邊和加入路由轉發(fā)集中的節(jié)點以及UPDATE報文，采集負載變化信息和UPDATE報文傳播信息。

步驟5 如果域間路由系統(tǒng)節(jié)點集中仍有節(jié)點沒有被選中，重復步驟2~步驟4，直到所有節(jié)點都被選中一次。

步驟6 比較各個節(jié)點重要性的大小，輸出較為重要的節(jié)點。

具體過程如圖4所示。

5.2 確定最優(yōu)a值

圖4 域間路由系統(tǒng)關鍵節(jié)點識別過程

圖5 確定最優(yōu)a值

圖6 節(jié)點影響大小分布情況

6 實驗驗證

為了驗證本文方法的有效性和準確性，將本文方法與現(xiàn)有方法和隨機選擇的方法識別出的關鍵節(jié)點進行對比分析。

6.1 與現(xiàn)有關鍵節(jié)點識別方法對比分析

本節(jié)分別選擇2001年、2004年、2007年、2010年、2013年、2016年7月的數據集用作對比實驗的基礎網絡環(huán)境，驗證本文方法與傳統(tǒng)方法的優(yōu)劣。對各年份的數據集進行節(jié)點數目的統(tǒng)計分析，不同時期網絡中節(jié)點的個數隨時間的變化關系如圖7所示。由圖可知，隨著時間的推移，域間路由節(jié)點的數目不斷增加。

圖7 節(jié)點個數隨時間的變化情況

用本文SD-KNI（spreading dynamics based key nodes identification in inter-domain routing system）方法與現(xiàn)有方法和隨機選擇的方法作對比，現(xiàn)有較好的方法主要包括度中心性法、基于文獻[16]提出的IRS-CFM模型的方法和PR-TEAI方法。通過大量的實驗發(fā)現(xiàn)，僅需要較少關鍵的節(jié)點即可造成較大規(guī)模的級聯(lián)失效，因此用以上方法從不同年份的數據中分別找出域間路由系統(tǒng)中最關鍵的20個節(jié)點。為了排除節(jié)點間的組合關系以及特殊節(jié)點對實驗結果的影響，從選出的不同關鍵節(jié)點集中，分別進行摘除前5、前10、前15和前20個關鍵節(jié)點的域間路由系統(tǒng)級聯(lián)失效實驗，實驗結果如圖8~圖11所示。

由圖可知，無論摘除多少個節(jié)點，在不同的年份下，本文方法識別出的關鍵節(jié)點，造成的節(jié)點和邊失效比例比其他方法造成的失效比例高，驗證了本文方法的有效性。由圖8和圖9可知如下結果。1) 在節(jié)點集規(guī)模不斷增大的情況下，摘除節(jié)點個數為5和10時，關鍵節(jié)點失效造成的節(jié)點和邊的失效比隨著年份的增加而降低。主要原因是隨著時間的推移，域間路由系統(tǒng)節(jié)點規(guī)模不斷增加，每個節(jié)點單獨的影響范圍不斷降低。同時，以度中心性作為判斷節(jié)點重要性的依據相對于其他方法更好，主要原因是度較大的節(jié)點，相對于其他方法，其失效后直接影響的節(jié)點和路徑較多，造成的影響范圍較大。2) 通過摘除隨機選擇的節(jié)點造成的節(jié)點和邊的失效比變化較大，且整體造成的失效比例較低，說明一般的節(jié)點能夠產生的影響較小，更加凸顯關鍵節(jié)點的重要性。

圖8 摘除5個節(jié)點條件下各方法失效比例分布

圖9 摘除10個節(jié)點條件下各方法失效比例分布

圖11 摘除20個節(jié)點條件下各方法失效比例分布

對比本文方法與度中心性的方法實驗結果，在摘除20個節(jié)點的條件下，本文方法造成的節(jié)點和邊的失效比例平均高出16.7%，最多高出21.9%。

6.2 摘除節(jié)點個數對實驗結果的影響

通過對第6.1節(jié)的數據分析發(fā)現(xiàn)，以2001年7月數據集為環(huán)境基礎，當選擇5個比較關鍵的節(jié)點時，對域間路由系統(tǒng)進行節(jié)點摘除實驗，可以造成較大范圍的級聯(lián)失效過程。增加失效節(jié)點的個數不但沒有增加失效節(jié)點和失效邊的比例，反而降低了，實驗數據如圖12所示。

圖12 失效比例隨節(jié)點數目變化情況

通過分析比較這些關鍵節(jié)點的網絡基礎結構發(fā)現(xiàn)，當摘除重要度靠前的5個節(jié)點時，其分布在域間路由系統(tǒng)的不同區(qū)域，節(jié)點間不存在緊密的連接關系，造成的級聯(lián)失效過程具有較大的毀傷效果。當摘除前10、前15、前20和前25個節(jié)點時，隨著摘除的重要節(jié)點的數目增加，部分情況下造成的失效比例不但沒有增加，反而有所降低。通過研究后續(xù)增加節(jié)點的位置以及連接關系發(fā)現(xiàn)，后續(xù)的部分節(jié)點與最初的5個節(jié)點存在直接的連通關系，連接關系如圖13所示。

圖13 域間路由節(jié)點連接關系

通過本次實驗可以發(fā)現(xiàn)，使整個網絡達到比較嚴重的級聯(lián)失效過程，并不需要大量的節(jié)點失效，極少量的關鍵節(jié)點同時失效可以造成較嚴重的網絡癱瘓。因此，找出關鍵節(jié)點，對其進行有針對性的保護具有重要意義。

7 結束語

針對傳統(tǒng)關鍵節(jié)點識別方法的不足，本文提出了基于傳播動力學的關鍵節(jié)點識別方法，該方法能夠更加準確地識別出域間路由系統(tǒng)中的關鍵節(jié)點，為進一步對關鍵節(jié)點實施有針對性的保護提供了重要理論支撐。通過與現(xiàn)有關鍵節(jié)點識別方法對比分析，驗證了本文方法的有效性和準確性。實驗結果表明，僅需要較少的關鍵節(jié)點就可以造成整個域間路由系統(tǒng)癱瘓。失效節(jié)點間的連接關系以及組合關系對級聯(lián)失效產生的影響，是后續(xù)研究工作的重點。

[1] SCHUCHARD M, MOHAISEN A, FOO K D, et al. Losing control of the internet: using the data plane to attack the control plane[C]//The 17th ACM Conference on Computer and Communications Security. ACM, 2010: 726-728.

[2] DENG W, ZHU P, LU X, et al. On evaluating BGP routing stress attack[J]. JCM, 2010, 5(1): 13-22.

[3] LI H S, ZHU J H, QIU H, et al. The new threat to internet: DNP attack with the attacking flows strategizing technology[J]. International Journal of Communication Systems, 2015, 28(6): 1126-1139.

[4] KANG M S, GLIGOR V D, SEKAR V. SPIFFY: inducing cost-detectability tradeoffs for persistent link-flooding attacks[C]//NDSS. 2016.

[5] Zheng J, Li Q, Gu G, et al. Realtime DDoS defense using COTS SDN switches via adaptive correlation analysis[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(7): 1838-1853.

[6] 劉建國, 任卓明, 郭強, 等. 復雜網絡中節(jié)點重要性排序的研究進展[J]. 物理學報, 2013, 62(17): 178901. LIU J G, REN Z M, GUO Q, et al. Node importance ranking of complex networks [J]. Acta Physica Sinica 2013, 62(17): 178901.

[7] ROSSI R A, AHMED N K. Role discovery in networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(4): 1112-1131.

[8] TENG D, CHU D. A fast frequent directions algorithm for low rank approximation:(previous title: sparse frequent directions algorithm for low rank approximation)[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018.

[9] WANG W, TANG M, STANLEY H E, et al. Unification of theoretical approaches for epidemic spreading on complex networks[J]. Reports on Progress in Physics, 2017, 80(3): 036603.

[10] BORGE-HOLTHOEFER J, MORENO Y. Absence of influential spreaders in rumor dynamics[J]. Physical Review E, 2012, 85(2): 026116.

[11] GUO Y, WANG Z, LUO S, et al. A cascading failure model for interdomain routing system[J]. International Journal of Communication Systems, 2012, 25(8): 1068-1076.

[12] 劉紅軍, 胡曉峰, 鄧文平, 等. 基于首選路由的 AS 重要性評估方法[J]. 軟件學報, 2012, 23(9): 2388-2400. LIU H J, HU XF, DENG W P, et al. Technique of evaluating AS importance based on preferred route[J]. Journal of Software, 2012,23(9):2388-2400.

[13] 邱菡, 李玉峰, 蘭巨龍, 等. 域間路由系統(tǒng)的級聯(lián)失效攻擊及檢測研究[J]. 中國科學: 信息科學, 2017, 47: 1715-1729. QIU H, LI Y F, LAN J L, et al. Research on cascading failure attack and detection of inner-domain routing system[J]. Scientia Sinica Informations, 2017, 47: 1715-1729.

[14] ZHANG Y, MAO Z M, WANG J. Low-rate TCP-targeted DoS attack disrupts internet routing[C]//NDSS. 2007.

[15] LIU Y, PENG W, SU J, et al. Assessing the impact of cascading failures on the inter-domain routing system of the internet[J]. New Generation Computing, 2014, 32(3-4): 237-2552.

[16] YANG B, ZHANG Y, LU Y. A new methods for cascading failures analysis in inter-domain routing system[C]//2015 Fifth International Conference IEEE on Instrumentation and Measurement, Computer, Communication and Control (IMCCC). 2015: 382-385.

[17] 朱會虎, 邱菡, 王清賢, 等. 基于雙毀傷因素的域間路由系統(tǒng)級聯(lián)失效模型[J].計算機工程與應用, 2019, 55(2): 92-99.ZHU H H, QIU H, WANG Q X, et al. Double damage factor based inter-domain routing system cascading failure model[J]. Computer Engineering and Applications, 2019, 55(2): 92-99.

[18] MOTTER A E, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102.

[19] 任曉龍, 呂琳媛. 網絡重要節(jié)點排序方法綜述[J]. 科學通報, 2014, 59: 1175-1197.REN X L, Lü L Y. Review of ranking nodes in complex networks [J]. Chinese Science Bulletin, 2014, 59: 1175-1197.

Spreading dynamics based key nodes identification in inter-domain routing system

ZHU Huihu1,2, QIU Han1,2, ZHU Junhu1,2, ZENG Ziyi1,2

1. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China 2. National Engineering Technology Research Center of the National Digital Switching System, Zhengzhou 450001, China

The inter-domain routing system is a critical infrastructure of the Internet and it is of great significance to protect the key nodes of inter-domain routing system. The key nodes identified by the existing methods can not reflect the importance of the nodes on the cascading failure process. The method of key nodes identification is proposed basing on spreading dynamics. A node importance evaluation model based on DDF-CFM model is proposed., which could takes the failure effect caused by load redistribution and UPDATE messages propagation into account after node fails. The experiments turn out that the accuracy of this method is at least 7.3% higher than that of existing methods. And the experimental results show that in the scale of 10000 nodes, the failure of only 5 key nodes will lead to large-scale cascade failure of inter-domain routing systems.

inter-domain routing system, key nodes, evaluation, spreading dynamics

朱會虎（1992? ），男，河南商丘人，數學工程與先進計算國家重點實驗室博士生，主要研究方向為域間路由系統(tǒng)安全。

邱菡（1981? ），女，湖北隨州人，數學工程與先進計算國家重點實驗室副教授，主要研究方向為網絡空間安全、域間路由系統(tǒng)安全。

朱俊虎（1974? ），男，江蘇鎮(zhèn)江人，數學工程與先進計算國家重點實驗室教授，主要研究方向為網絡空間安全。

曾子懿（1989? ），男，湖南祁東人，數學工程與先進計算國家重點實驗室博士生，主要研究方向為域間路由系統(tǒng)安全。

TP393.4

A

10.11959/j.issn.2096?109x.2019046

2018?12?11；

2019?02?13

邱菡，qiuhan410@aliyun.com

國家自然科學基金資助項目（No. 61502528,No. 61402525）

The National Natural Science Foundation of China (No.61502528, No.61402525)

朱會虎, 邱菡, 朱俊虎, 等. 基于傳播動力學的域間路由系統(tǒng)關鍵節(jié)點識別方法[J]. 網絡與信息安全學報, 2019, 5(5): 9-20.

ZHU H H, QIU H, ZHU J H, et al. Spreading dynamics based key nodes identification in inter-domain routing system[J]. Chinese Journal of Network and Information Security, 2019, 5(5): 9-20.