基于路由狀態(tài)因果鏈的域間路由不穩(wěn)定溯源檢測(cè)方法

陳迪，邱菡，張萬里，朱會(huì)虎，朱俊虎，王清賢

（1.信息工程大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，河南 鄭州 450002；2.電子信息系統(tǒng)復(fù)雜電磁環(huán)境效應(yīng)國家重點(diǎn)實(shí)驗(yàn)室，河南 洛陽 471003）

1 引言

域間路由系統(tǒng)由眾多獨(dú)立運(yùn)營(yíng)的自治域（AS,autonomous system）組成。作為現(xiàn)行域間路由系統(tǒng)的事實(shí)標(biāo)準(zhǔn)協(xié)議，邊界網(wǎng)關(guān)協(xié)議（BGP,border gateway protocol）[1]是策略驅(qū)動(dòng)的路徑矢量協(xié)議，支持各自治域自主制定本地選路策略，進(jìn)而從候選路徑中選擇到達(dá)特定目的網(wǎng)絡(luò)的路徑。然而，自治域配置路由策略的靈活性是以犧牲路由穩(wěn)定性為代價(jià)的[2]。路由不穩(wěn)定即在路徑收斂前自治域不斷采用和舍棄路徑的狀態(tài)變更過程，例如由拓?fù)渥兓瘜?dǎo)致的短時(shí)路由抖動(dòng)[3]或由多個(gè)自治域策略沖突導(dǎo)致的持續(xù)路由振蕩[4]。自治域間不必要的路由狀態(tài)變更會(huì)降低網(wǎng)絡(luò)服務(wù)質(zhì)量，增加網(wǎng)絡(luò)時(shí)延，進(jìn)而導(dǎo)致服務(wù)中斷或數(shù)據(jù)包丟失[5]。

解決域間路由穩(wěn)定收斂問題的難點(diǎn)在于BGP在路由策略配置上分布自治的特性。Griffin 等[6]提出了穩(wěn)定路徑問題（SPP,stable paths problem）作為BGP 穩(wěn)定問題的形式化模型，給出了反映自治域間選路策略循環(huán)依賴關(guān)系的爭(zhēng)議輪，證明了域間路由系統(tǒng)收斂的充分條件即不存在爭(zhēng)議輪，但同時(shí)指出即使在已知所有策略信息的前提下檢查系統(tǒng)是否存在穩(wěn)定路徑是NP 完全問題。Gao 等[7]根據(jù)AS 間的商業(yè)層級(jí)關(guān)系提出了域間路由策略配置的無谷底原則，并表明自治域通過犧牲一定的策略自治性，在均遵守?zé)o谷底原則的情況下可保證路由穩(wěn)定性。然而實(shí)際中由于復(fù)雜的自治域商業(yè)關(guān)系，并非所有自治域都會(huì)遵守建議的路由策略原則[8]。路由抖動(dòng)抑制（RFD,route flap damping）機(jī)制[9]早期曾作為緩解措施，但研究表明RFD 對(duì)網(wǎng)絡(luò)可達(dá)性存在負(fù)面影響[10]。因此，如何提高BGP 路由的穩(wěn)定性仍是實(shí)際域間路由系統(tǒng)中尚未解決的關(guān)鍵問題。

針對(duì)BGP 路由不穩(wěn)定問題的研究工作主要有路由不穩(wěn)定預(yù)測(cè)與路由不穩(wěn)定溯源2 種思路[11]。路由不穩(wěn)定預(yù)測(cè)通常采用動(dòng)態(tài)調(diào)整或統(tǒng)一約束各節(jié)點(diǎn)的出入站選路策略的方式以減小BGP 的收斂時(shí)延，并不關(guān)注導(dǎo)致路由不穩(wěn)定的源頭[12-13]，不僅無法判斷與追溯BGP 不穩(wěn)定的類型及其源頭，且犧牲了一定的策略自治性。路由不穩(wěn)定溯源主要通過增加BGP 傳遞屬性追溯導(dǎo)致路由不穩(wěn)定的源頭，從而限制冗余路徑探索和消除不一致狀態(tài)。Zhang等[14]針對(duì)持續(xù)路由振蕩提出update chain，通過構(gòu)造路由更新鏈標(biāo)識(shí)以檢測(cè)路由振蕩，但其判斷發(fā)生路由振蕩的充分條件只是導(dǎo)致路由振蕩的特殊情況，有失一般性。Li 等[15]針對(duì)非單一類型的路由不穩(wěn)定溯源問題提出stable BGP，通過增加路由變更原因root cause 傳遞屬性過濾相關(guān)路由，提高BGP的收斂速度，但持續(xù)增加root cause 信息會(huì)為BGP通信帶來額外開銷，且溯源檢測(cè)時(shí)間受限于BGP更新報(bào)文傳播時(shí)延。此外，用于路由不穩(wěn)定溯源的傳遞屬性中攜帶的信息在BGP 更新報(bào)文傳遞過程中可被任意篡改，無法保證溯源信息的安全性與一致性。

針對(duì)上述問題，本文提出一種基于路由狀態(tài)因果鏈的域間路由不穩(wěn)定溯源檢測(cè)方法RSCTchain。RSCTchain 的主要思想是將自治域狀態(tài)變更信息與轉(zhuǎn)移過程以交易的模式發(fā)布并存儲(chǔ)于區(qū)塊鏈，構(gòu)建能夠反映自治域間路由狀態(tài)變更因果關(guān)系的路由狀態(tài)因果鏈，從而通過追溯RSCTchain 檢測(cè)是否存在導(dǎo)致路由不穩(wěn)定的失效鏈路或策略沖突AS 序列。本文的研究工作主要包括：1)基于拓?fù)渑c策略變化等觸發(fā)路由狀態(tài)變更的不同類型及因果關(guān)系，設(shè)計(jì)RSCTchain 路由狀態(tài)變更標(biāo)識(shí)生成算法，生成能夠反映路由狀態(tài)變更的唯一標(biāo)識(shí)并在區(qū)塊鏈上進(jìn)行同步；2)通過分析短時(shí)路由抖動(dòng)及持續(xù)路由振蕩的機(jī)理，設(shè)計(jì)RSCTchain 路由不穩(wěn)定溯源檢測(cè)算法，判斷路由不穩(wěn)定的類型，并定位失效鏈路或策略沖突AS 序列；3)從理論上證明了RSCTchain 用于BGP 不穩(wěn)定溯源檢測(cè)的正確性，并基于Quagga軟件路由器及區(qū)塊鏈數(shù)據(jù)庫 BigchainDB 對(duì)RSCTchain 的有效性及可擴(kuò)展性進(jìn)行驗(yàn)證。

2 問題描述

2.1 符號(hào)與假設(shè)

本文將AS 組成的域間路由系統(tǒng)表示為一個(gè)時(shí)間相關(guān)的無向圖G=(V,E)，其中時(shí)間由非負(fù)的離散序列t=[0,∞)表示，每個(gè)節(jié)點(diǎn)v∈V對(duì)應(yīng)一個(gè)AS，邊(u,v)t∈E代表t時(shí)刻ASv與ASu之間的BGP鏈路可達(dá)，(u,v)t?E代表t時(shí)刻ASu與ASv之間的BGP 鏈路失效。選路過程中，每個(gè)節(jié)點(diǎn)根據(jù)本地路徑偏好排序從到達(dá)特定目的節(jié)點(diǎn)的路徑候選集中選擇最優(yōu)路徑。下面給出路徑偏好排序與路徑的形式化描述。

定義1路徑偏好排序?。對(duì)于任意AS 節(jié)點(diǎn)u∈V，其路徑偏好排序指u對(duì)本地路徑集合的全序關(guān)系，表示為?u，若節(jié)點(diǎn)u在路徑P和路徑Q中更偏向于選擇路徑P，則P?uQ。

定義2路徑P。在任意時(shí)刻t，AS 節(jié)點(diǎn)u0∈V到達(dá)目的節(jié)點(diǎn)d的路徑P用路徑分配函數(shù)π表示為P=π(u,t)，路徑P途經(jīng)的節(jié)點(diǎn)可使用序列形式表示為的鄰居節(jié)點(diǎn)u通過路徑P到達(dá)目的節(jié)點(diǎn)d可用節(jié)點(diǎn)與路徑連接表示為 〈u,P〉，空路徑表示為〈?〉，如果路徑P是被禁止的，則

為了表述清晰，本文做出如下假設(shè)：1)所有AS節(jié)點(diǎn)發(fā)出的路由宣告update報(bào)文均通往單個(gè)目的前綴地址；2)每個(gè)AS 節(jié)點(diǎn)由單個(gè)BGP 路由器代表。

2.2 域間路由穩(wěn)定收斂條件

當(dāng)域間路由在t時(shí)刻穩(wěn)定收斂時(shí)，其中每一個(gè)v∈V都被分配了通往目的節(jié)點(diǎn)d的路徑π(v,t)，所有節(jié)點(diǎn)到達(dá)d的路徑構(gòu)成路徑分配集合Pt，且Pt需是一致、穩(wěn)定、安全的[16]。下面，給出路徑分配集合一致性、穩(wěn)定性與安全性的形式化描述。

定義3一致性。對(duì)于在t時(shí)刻到達(dá)目的節(jié)點(diǎn)d的路徑分配集合Pt，當(dāng)所有路徑P∈Pt構(gòu)成一個(gè)以d為根的轉(zhuǎn)發(fā)樹時(shí)，則路徑分配Pt是一致的，即對(duì)于任意v,u∈V，如果π(v)=vuP，則π(u)=uP。

定義4穩(wěn)定性。對(duì)于在t時(shí)刻到達(dá)目的節(jié)點(diǎn)d的路徑分配集合Pt，其中任意AS 節(jié)點(diǎn)v∈V的路徑π(v,t)是其根據(jù)本地路由策略的優(yōu)選路徑，則路徑分配Pt是穩(wěn)定的，即對(duì)于任意v,u,w∈V，如果π(v)=vπ(u)，不存在其他節(jié)點(diǎn)w使vπ(w)?vπ(v)。

定義 5安全性。對(duì)于在t時(shí)刻所有節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)d的路徑分配集合發(fā)生更新時(shí)，存在有限時(shí)間T，當(dāng)t'＜T時(shí)且路徑可達(dá)，當(dāng)時(shí)則路徑分配Pt是安全的。

域間路由系統(tǒng)中各自治域均根據(jù)本地自主策略進(jìn)行選路，在所有時(shí)刻保證路徑分配的一致性、穩(wěn)定性和安全性十分困難。Griffin 等[6]證明了判斷域間路由系統(tǒng)穩(wěn)定收斂的充分條件為在系統(tǒng)中不存在爭(zhēng)議輪。一個(gè)大小為k的爭(zhēng)議輪W=(V,Q,R)如圖1 所示，由節(jié)點(diǎn)集合、輻邊路徑集合及弧邊路徑集合組成，其中對(duì)于每個(gè)為連接vi與vi-1的邊；Qi∈Q為從vi到d的邊；且對(duì)于任意節(jié)點(diǎn)

圖1 一個(gè)大小為k 的爭(zhēng)議輪

2.3 域間路由不穩(wěn)定類型

域間路由不穩(wěn)定主要包括2 種類型：持續(xù)路由振蕩及短時(shí)路由抖動(dòng)。圖2 分別給出了持續(xù)路由振蕩與短時(shí)路由抖動(dòng)的示例。

持續(xù)路由振蕩指一些AS 節(jié)點(diǎn)在選路過程中始終無法穩(wěn)定，使路由更新持續(xù)在這些AS 節(jié)點(diǎn)中交換傳遞的現(xiàn)象。導(dǎo)致持續(xù)路由振蕩的原因通常是各AS 自主配置的本地優(yōu)先屬性配置不合理，路由策略產(chǎn)生了沖突。圖2(a)為策略沖突導(dǎo)致持續(xù)路由振蕩的例子，AS0為其他AS 節(jié)點(diǎn)的目的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)旁邊標(biāo)注的是本地路徑偏好列表，最上面的路徑為根據(jù)本地偏好的最優(yōu)路徑。例如AS1相較于路徑10，更希望選擇路徑1430 到達(dá)AS0。當(dāng)AS2選擇210 時(shí)，AS3由于最優(yōu)路由320 不可達(dá)變更路徑為30，繼而AS4更改路徑為430，AS1更改路徑為1430，導(dǎo)致AS2由于120 路徑不可達(dá)重新更改路徑為20，使AS3重新選擇320……AS0～AS4構(gòu)成了一個(gè)爭(zhēng)議輪，路由狀態(tài)會(huì)因策略沖突周而復(fù)始地切換。

圖2 持續(xù)路由振蕩與短時(shí)路由抖動(dòng)示例

短時(shí)路由抖動(dòng)指AS 節(jié)點(diǎn)錯(cuò)誤選取并通告含有失效鏈路的不可達(dá)路徑，導(dǎo)致路徑冗余探索及收斂時(shí)延的現(xiàn)象。圖2(b)為鏈路失效導(dǎo)致短時(shí)路由抖動(dòng)的例子，當(dāng)鏈路AS4與AS0之間的鏈路失效時(shí)，AS4會(huì)向AS2與AS3發(fā)送撤回消息。然而由于AS2與AS3分別有備選路徑340 與230，導(dǎo)致沿備選路徑互相發(fā)送數(shù)據(jù)包。由于最小路由宣告間隔（MRAI,minimum route advertisement interval）計(jì)時(shí)器的限制，即使AS2和AS3已經(jīng)開始互相轉(zhuǎn)發(fā)流量，但還無法發(fā)出新路徑的更新報(bào)文（MRAI 計(jì)時(shí)器建議取值為30 s[11]）。最終當(dāng)MRAI 計(jì)時(shí)器到期，AS2與AS3才會(huì)發(fā)現(xiàn)通過AS1到達(dá)AS0的備選路徑。

因此，需要一種路由不穩(wěn)定溯源檢測(cè)方法，能夠在圖2(a)中的路由狀態(tài)開始反復(fù)變更時(shí)檢測(cè)出策略沖突的AS 序列2→3→4→1→2，使相關(guān)AS 可調(diào)整本地策略消除沖突；且能夠在圖2(b)中的鏈路失效后使相關(guān)AS 獲知AS0與AS4間的鏈路已失效，不再向包含鏈路40 的路徑發(fā)送數(shù)據(jù)包或通告該路徑，避免路徑的冗余探索。

綜上，本文要解決的問題是針對(duì)當(dāng)前路由不穩(wěn)定溯源檢測(cè)方法中檢測(cè)時(shí)間受限于路由更新時(shí)延、溯源信息可能被篡改的問題，在不改變現(xiàn)行BGP 的前提下，檢測(cè)BGP 不穩(wěn)定現(xiàn)象并判斷其類型（拓?fù)渥兓瘜?dǎo)致的短時(shí)路由抖動(dòng)/策略沖突導(dǎo)致的持續(xù)路由振蕩），追溯導(dǎo)致BGP 不穩(wěn)定的具體失效鏈路/策略沖突AS 序列，同時(shí)保證檢測(cè)過程可追溯、防篡改。

3 RSCTchain

3.1 RSCTchain 概述

針對(duì)上述問題，本文提出一種基于路由狀態(tài)因果鏈的域間路由不穩(wěn)定溯源檢測(cè)方法RSCTchain。為了能夠以可追溯、防篡改的方式對(duì)非單一類型的BGP 路由不穩(wěn)定現(xiàn)象進(jìn)行溯源檢測(cè)，采用區(qū)塊鏈對(duì)反映路由狀態(tài)變更因果關(guān)系的信息進(jìn)行分布式存儲(chǔ)；通過檢索本地區(qū)塊鏈數(shù)據(jù)庫，從而與BGP 并行工作完成BGP 不穩(wěn)定溯源檢測(cè)；基于區(qū)塊鏈共識(shí)機(jī)制保證數(shù)據(jù)存儲(chǔ)的安全性與一致性。

圖3 展示了RSCTchain 的整體架構(gòu)與工作流程。在RSCTchain 中，每個(gè)參與自治域需要運(yùn)行一個(gè)代表本自治域的RSCTchain 區(qū)塊鏈節(jié)點(diǎn)，在不引起混淆的情況下，下文簡(jiǎn)稱其為RSCT 節(jié)點(diǎn)。每個(gè)RSCT節(jié)點(diǎn)都持有一個(gè)公鑰?私鑰對(duì)，其公鑰的哈希值作為該節(jié)點(diǎn)的唯一身份標(biāo)識(shí)。所有參與RSCTchain 的AS 節(jié)點(diǎn)共同構(gòu)成邏輯上的信任覆蓋網(wǎng)絡(luò)，基于RSCTchain 采用的共識(shí)算法發(fā)布并一致地存儲(chǔ)路由狀態(tài)變更標(biāo)識(shí)，協(xié)同檢測(cè)路由不穩(wěn)定并追溯其源頭。RSCTchain 的工作流主要由記錄與檢索兩類組成。記錄工作流指當(dāng)AS 更新本地路由狀態(tài)時(shí)，其RSCT 節(jié)點(diǎn)生成相應(yīng)的路由狀態(tài)變更標(biāo)識(shí)RSCT，將RSCT 以交易的形式經(jīng)簽名后發(fā)布于區(qū)塊鏈網(wǎng)絡(luò)，在完成共識(shí)確認(rèn)后存儲(chǔ)于每個(gè)RSCT 節(jié)點(diǎn)。RSCT 記錄對(duì)應(yīng)狀態(tài)更新的類型、變更路徑、觸發(fā)節(jié)點(diǎn)等信息，在邏輯上按照AS 間導(dǎo)致路由狀態(tài)變更的因果關(guān)系依次相連，構(gòu)成路由狀態(tài)因果鏈。檢索工作流指RSCT節(jié)點(diǎn)在對(duì)應(yīng)AS做出路由決策前，通過追溯路由狀態(tài)因果鏈檢測(cè)是否存在導(dǎo)致路由不穩(wěn)定的失效鏈路或策略沖突AS 序列，并將檢測(cè)結(jié)果返回對(duì)應(yīng)AS 以為其路由決策提供參考。

圖3 RSCTchain 的整體架構(gòu)與工作流程

RSCTchain 中分布式存儲(chǔ)的路由狀態(tài)因果鏈的安全性與一致性取決于RSCTchain 采用的共識(shí)算法。RSCTchain 中的自治域參與節(jié)點(diǎn)不同于公鏈參與節(jié)點(diǎn)的完全競(jìng)爭(zhēng)狀態(tài)，各RSCT 節(jié)點(diǎn)間是在有限競(jìng)爭(zhēng)的基礎(chǔ)上共同尋求整體利益的最大化（如路由的穩(wěn)定一致）。因此聯(lián)盟鏈共識(shí)機(jī)制更適用于RSCTchain 的實(shí)際需求。以Tendermint[17]共識(shí)算法為例，由于Tendermint 是拜占庭容錯(cuò)的，當(dāng)RSCT節(jié)點(diǎn)中惡意節(jié)點(diǎn)比例不超過1/3 時(shí)，能夠避免路由狀態(tài)因果鏈被篡改，誠實(shí)節(jié)點(diǎn)仍達(dá)成一致的路由狀態(tài)因果鏈最終狀態(tài)，從而正常完成BGP 不穩(wěn)定溯源檢測(cè)。因此RSCTchain 可以使參與自治域在去中心化信任的基礎(chǔ)上，實(shí)現(xiàn)可追溯、防篡改的路由不穩(wěn)定檢測(cè)，提供可靠溯源證據(jù)。

為了優(yōu)化路由不穩(wěn)定檢測(cè)與溯源時(shí)間，RSCTchain 在實(shí)現(xiàn)中可將每個(gè)RSCT 節(jié)點(diǎn)運(yùn)行在與BGP 路由器物理上獨(dú)立的專用服務(wù)器中，并對(duì)應(yīng)一個(gè)運(yùn)行在BGP 路由器中的本地驗(yàn)證節(jié)點(diǎn)。路由狀態(tài)標(biāo)識(shí)發(fā)布時(shí)，RSCT 節(jié)點(diǎn)負(fù)責(zé)在區(qū)塊鏈網(wǎng)絡(luò)中完成同步與存儲(chǔ)。本地驗(yàn)證節(jié)點(diǎn)不參與區(qū)塊鏈中的共識(shí)同步過程，只負(fù)責(zé)定期接收RSCT 節(jié)點(diǎn)下發(fā)的區(qū)塊并在緩存中存儲(chǔ)本地相關(guān)的路由狀態(tài)變更標(biāo)識(shí)以供查詢，即對(duì)于任意的AS，可將通往同一目的網(wǎng)絡(luò)且具有連鎖因果關(guān)系的路由狀態(tài)變更標(biāo)識(shí)按序存儲(chǔ)于本地路由驗(yàn)證緩存中。

3.2 路由狀態(tài)變更標(biāo)識(shí)

在RSCTchain 中，使用路由狀態(tài)變更標(biāo)識(shí)記錄各自治域路由狀態(tài)變更信息與轉(zhuǎn)移過程。本節(jié)給出路由狀態(tài)變更標(biāo)識(shí)的定義及其生成算法。

文獻(xiàn)[18-19]給出了由拓?fù)渑c策略變化觸發(fā)的可能影響收斂過程的四類路由狀態(tài)變更事件（Tup,Tdown,Tshort,Tlong），統(tǒng)稱為T 事件，并在此基礎(chǔ)上給出路由狀態(tài)變更類別的定義。

定義6路由狀態(tài)變更類別。對(duì)于任意的自治域節(jié)點(diǎn)在t+1時(shí)刻將t時(shí)刻的路徑ro=π(u,t)更改為rn=π(u,t+1)的路由狀態(tài)變更事件e，其對(duì)應(yīng)的路由狀態(tài)變更類別指導(dǎo)致該事件的原因類別，具體可表示 為 RSCT.type(e)，RSCT.type(e)∈{0+,0 -,1+,1-}，其中，“0+”代表由ASu與某鄰接AS 間的鏈路在t+1時(shí)刻恢復(fù)導(dǎo)致，且ASu在t+1時(shí)刻變更的新路徑rn的本地優(yōu)先級(jí)高于t時(shí)刻的當(dāng)前路徑ro，即rn?ro的路由狀態(tài)變更事件；“0-”代表由ASu與某鄰接AS間的鏈路在t+1時(shí)刻失效導(dǎo)致，且ASu在t+1時(shí)刻變更的新路徑rn的本地優(yōu)先級(jí)低于t時(shí)刻的當(dāng)前路徑ro，即rn?ro的路由狀態(tài)變更事件（當(dāng)rn=〈?〉時(shí)即對(duì)ro進(jìn)行撤回操作）；“1+”代表由ASu本地路由策略變更或收到某鄰接AS 的路徑更新通告導(dǎo)致，且ASu在t+1時(shí)刻變更的新路徑rn的本地優(yōu)先級(jí)高于t時(shí)刻的當(dāng)前路徑ro，即rn?ro的路由狀態(tài)變更事件；“1-”代表由ASu收到某鄰接AS 的路徑更新通告導(dǎo)致，且ASu在t+1時(shí)刻變更的新路徑rn的本地優(yōu)先級(jí)低于t時(shí)刻的當(dāng)前路徑ro，即rn?ro的路由狀態(tài)變更事件。

為敘述方便，下文使用新路徑rn和舊路徑ro分別代表t+1時(shí)刻的更新路徑和t時(shí)刻的當(dāng)前路徑。下面，給出路由狀態(tài)變更標(biāo)識(shí)RSCT 的定義。

定義7路由狀態(tài)變更標(biāo)識(shí)。對(duì)于任意一個(gè)路由狀態(tài)變更事件，路由狀態(tài)變更標(biāo)識(shí)RSCT 指唯一對(duì)應(yīng)該事件的一個(gè)十元組，RSCT=(Key,PT,SC,UN,CN,OP,NP,TS,Sig,Pk)，其中，“Key”代表該路由狀態(tài)變更標(biāo)識(shí)的索引，這里Key=hash(UN,NP,TS)；“PT(previous token)”代表該路由狀態(tài)變更標(biāo)識(shí)的上一個(gè)標(biāo)識(shí)的索引，即導(dǎo)致當(dāng)前AS 路由狀態(tài)變更的路由狀態(tài)變更標(biāo)識(shí)，在當(dāng)前AS 路由狀態(tài)變更是由于本地原因（如鏈路失效、策略更改）的情況下，PT=null；“SC(state change type) ” 代表路由狀態(tài)變更的類別，SC ∈{0 +,0 -,1+,1-} ；“UN(update node)”代表當(dāng)前路由狀態(tài)變更的AS 對(duì)應(yīng)節(jié)點(diǎn)，即發(fā)布該路由狀態(tài)變更標(biāo)識(shí)的節(jié)點(diǎn)；“CN(cause node)”代表導(dǎo)致當(dāng)前AS 路由狀態(tài)變更的觸發(fā)AS，在當(dāng)前AS 僅根據(jù)本地因素變更路由狀態(tài)時(shí)，CN=null；“OP(old path)”代表變更節(jié)點(diǎn)的當(dāng)前待更改的路徑；“NP(new path)”代表變更節(jié)點(diǎn)要采用的新路徑，當(dāng)沒有可達(dá)路徑時(shí)，NP=null；“TS(time stamp)”代表當(dāng)前路由狀態(tài)變更的時(shí)間戳；“Sig(signature)”代表當(dāng)前路由狀態(tài)變更節(jié)點(diǎn)使用本地私鑰對(duì)發(fā)布RSCT 內(nèi)容摘要進(jìn)行的數(shù)字簽名DSKUN(hash(Key,PT,SC,UN,CN,OP,NP,TS))，用于驗(yàn)證RSCT 中的信息未被篡改過；“Pk(public key)”代表當(dāng)前路由狀態(tài)變更節(jié)點(diǎn)的公鑰，用于檢查數(shù)字簽名的真實(shí)性。

路由狀態(tài)變更標(biāo)識(shí)的生成算法如算法1 所示。

算法1路由狀態(tài)變更標(biāo)識(shí)生成RSCTgeneration

輸入在t時(shí)刻ASu的路徑ro被撤回或被替換為rn（因鏈路失效/恢復(fù)、本地策略更改或收到鄰接ASv在t'時(shí)刻通告路徑rv的路由更新Uv）

輸出路由狀態(tài)變更標(biāo)識(shí)RSCT

生成路由狀態(tài)變更標(biāo)識(shí)分為4 種情況。

1) 當(dāng)ASu與路徑ro的下一跳AS 之間的鏈路失效，ASu將ro撤回（即rn=〈?〉）或?qū)⑵涮鎿Q為一條次優(yōu)路徑rn時(shí)，生成(hash(u,rn,t),null,0?,u,null,ro,rn,t,Sigu,Pku)作為該路由狀態(tài)變更的標(biāo)識(shí)RSCT（第1)～2)行）。

2) 當(dāng)ASu與路徑rn的下一跳AS 之間的鏈路在失效后恢復(fù)，ASu將當(dāng)前次優(yōu)路徑ro替換為本地偏好值更高的rn路徑時(shí)，生成(hash(u,rn,t),null,0+,u,null,ro,rn,t,Sigu,Pku)作為該路由狀態(tài)變更的標(biāo)識(shí)RSCT（第3)～4)行）。

3) 當(dāng)ASu的本地優(yōu)先級(jí)策略發(fā)生更改，選取更改后優(yōu)先級(jí)更高的rn替換當(dāng)前路徑ro時(shí)，生成(hash(u,rn,t),null,1+,u,null,ro,rn,t,Sigu,Pku)作為該路由狀態(tài)變更的標(biāo)識(shí)RSCT（第5)～6)行）。

4) 當(dāng)ASu由于接收到鄰接ASv在t'時(shí)刻通告路徑rv的路由更新Uv要將當(dāng)前路徑ro替換為rn時(shí)（第7)行）時(shí)，需再分為2 種情況考慮，第一種情況是ASu將ASv作為下一跳并通過rv的路徑本地優(yōu)先級(jí)高于當(dāng)前路徑ro(即rn=〈uv,rv〉)，此時(shí)ASu將(hash(u,rn,t),hash(v,rv,t’),1+,u,v,ro,rn,t,Sigu,Pku) 作為其路由狀態(tài)變更的標(biāo)識(shí)RSCT（第8)～9)行）；第二種情況是ASu不選擇ASv作為其下一跳AS，且因?yàn)槭盏経v不得不將當(dāng)前路徑ro替換為優(yōu)先級(jí)更低的新路徑rn時(shí)，將(hash(u,rn,t),hash(v,rv,t’),1?,u,v,ro,rn,t,Sigu,Pku)作為其路由狀態(tài)變更標(biāo)識(shí)RSCT（第10)～11)行）；最后返回生成的路由狀態(tài)變更標(biāo)識(shí)RSCT（第12)行）。

圖4 給出了RSCTchain 中一個(gè)路由狀態(tài)變更標(biāo)識(shí)生成的例子，在圖4(a)的初始穩(wěn)定狀態(tài)t0時(shí)刻，節(jié)點(diǎn)a,b,c到達(dá)d的路徑形成一個(gè)穩(wěn)定的轉(zhuǎn)發(fā)樹P0={ad,bd,cad}；在t1時(shí)刻，節(jié)點(diǎn)a變更了本地策略，如圖4(b)，將路徑abd的優(yōu)先級(jí)調(diào)整為高于路徑ad的優(yōu)先級(jí)，進(jìn)而將到達(dá)d的路徑由ad變更為abd并向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)路由更新報(bào)文，同時(shí)生成對(duì)應(yīng)該狀態(tài)變更的RSCT，即圖4 右側(cè)的RSCT（Key①）；在t2時(shí)刻，節(jié)點(diǎn)c由于收到節(jié)點(diǎn)a的路由更新，不得不將當(dāng)前路徑cad更改為cd并向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)路由更新報(bào)文，同時(shí)生成RSCT（Key②）；在t3時(shí)刻，節(jié)點(diǎn)b由于收到節(jié)點(diǎn)a的路由更新，在獲取路徑cd可達(dá)后將本地路徑更新為優(yōu)先級(jí)更高的bcd并向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)路由更新報(bào)文，同時(shí)生成對(duì)應(yīng)該狀態(tài)變更的RSCT（Key③）；在t4時(shí)刻，節(jié)點(diǎn)a又因?yàn)槭盏絙的路由更新，獲知路徑bd不可達(dá)后重新將路徑變更為ad，生成RSCT（Key④）。在沒有檢測(cè)機(jī)制的干預(yù)下，節(jié)點(diǎn)a,b,c的路由狀態(tài)會(huì)循環(huán)往復(fù)地變更，RSCTchain 也會(huì)不斷增長(zhǎng)。在每個(gè)RSCT 中都包含了對(duì)應(yīng)狀態(tài)變更的必要信息，且能夠通過RSCT 中的PT 值獲取引發(fā)當(dāng)前路由狀態(tài)變更的變更事件及節(jié)點(diǎn)信息，從而支持對(duì)整個(gè)路由狀態(tài)變更過程的追溯。

圖4 RSCTchain 路由狀態(tài)變更標(biāo)識(shí)生成示例

3.3 路由不穩(wěn)定溯源檢測(cè)

RSCTchain 中的路由不穩(wěn)定溯源檢測(cè)算法不僅需要判斷路由不穩(wěn)定類型，還需要定位失效鏈路或策略沖突AS 序列。本節(jié)給出RSCTchain 的路由不穩(wěn)定溯源檢測(cè)算法。

路由不穩(wěn)定溯源檢測(cè)算法如算法2 所示。首先對(duì)參數(shù)進(jìn)行初始化（第1)～6)行）。然后在指定檢測(cè)時(shí)間范圍內(nèi)，從當(dāng)前RSCT 開始向前追溯（第7)～27)行），檢查RSCT 中數(shù)字簽名的正確性，若數(shù)字簽名有誤，報(bào)告對(duì)應(yīng)路由狀態(tài)變更標(biāo)識(shí)的索引值并返回（第8)～9)行）。當(dāng)檢測(cè)到“0-”類型路由狀態(tài)變更事件時(shí)，則返回失效鏈路（第10)～11)行），當(dāng)前AS 可對(duì)路由表中包含失效鏈路的路徑進(jìn)行過濾；當(dāng)追溯的RSCT 中的UN 節(jié)點(diǎn)與當(dāng)前AS 節(jié)點(diǎn)相同時(shí)，即發(fā)生了路由狀態(tài)因果環(huán)路。在此情況下，第一步根據(jù)curRSCT 的前一個(gè)標(biāo)識(shí)nxtRSCT 的事件類型SC 來決定Pathin的取值，當(dāng)nxtRSCT.SC 為“1+”或“0+”時(shí)，Pathin為curRSCT 中的新路徑，當(dāng)nxtRSCT.SC 為“1-”時(shí)則為curRSCT 中的舊路徑（第13)～16)行）；第二步根據(jù)ASu根據(jù)Uv要在本地變更的新路徑rn與要替換的舊路徑ro來決定Pathout取值，當(dāng)ro?rn且rn的下一跳為v時(shí)，Pathout為ASu選取的新路徑rn，當(dāng)ro?rn且rn的下一跳不是v時(shí)，Pathout為ASu當(dāng)前的舊路徑ro（第17)～20)行）；第三步通過比較Pathin與Pathout在ASu的優(yōu)先級(jí)，判斷是否發(fā)生了策略沖突，若存在策略沖突，將檢測(cè)起始時(shí)間T作為當(dāng)前發(fā)生沖突的時(shí)間t并返回策略沖突AS 序列causeChain，報(bào)告策略沖突爭(zhēng)議輪（第21)～23)行）。若不存在策略沖突，則將nxtRSCT 賦為curRSCT 的索引，curRSCT 賦為其上一個(gè)索引標(biāo)識(shí)curRSCT.PT，并將當(dāng)前路由狀態(tài)更新自治域節(jié)點(diǎn)追加至causeChain，繼續(xù)向前回溯（第24)～26)行）。最后若在指定檢測(cè)時(shí)間范圍內(nèi)未發(fā)現(xiàn)異常情況，返回True（第27)行）。

算法2路由不穩(wěn)定溯源檢測(cè)RITdetection

輸入ASu收到ASv在t時(shí)刻通告路徑rv的路由更新Uv；ASu根據(jù)Uv要在本地變更的新路徑rn與要替換的舊路徑ro；檢測(cè)起始時(shí)間T，路由狀態(tài)變更鏈RSCTchain

輸出檢測(cè)正常/異常（異常時(shí)返回故障源：失效故障鏈路或策略沖突AS 序列）

以圖4 為例，在t4時(shí)刻，當(dāng)a收到來自b宣告路徑bcd時(shí)，需把當(dāng)前路徑abd更新為ad，此時(shí)為了檢測(cè)是否存在失效鏈路或策略沖突，a在RSCTchain 中向前追溯，直到發(fā)現(xiàn)在t1時(shí)刻的RSCT（Key①）中的UN 為a，構(gòu)成因果環(huán)路。首先根據(jù)RSCT（Key②）中的SC 類型，確定Pathin=ad；然后根據(jù)路徑abd與ad的優(yōu)先級(jí)順序，確定Pathout=abd；最后通過比較Pathin與Pathout的優(yōu)先級(jí)，發(fā)現(xiàn)存在策略沖突，并報(bào)告構(gòu)成策略沖突的AS 序列{a,b,c,a} 與沖突路徑{abd,ad}。

基于RSCTchain 進(jìn)行路由不穩(wěn)定溯源檢測(cè)的時(shí)間復(fù)雜度主要體現(xiàn)在該更新報(bào)文在每一次被自治域節(jié)點(diǎn)接收和轉(zhuǎn)發(fā)時(shí)在路由狀態(tài)標(biāo)識(shí)鏈中根據(jù)導(dǎo)致路由狀態(tài)變更的因果關(guān)系向前回溯的過程。假設(shè)鏈上存儲(chǔ)的到達(dá)不同目的前綴的數(shù)量為c，待驗(yàn)證的更新報(bào)文U中的AS-path 長(zhǎng)度為n，RSCTchain路由不穩(wěn)定溯源檢測(cè)在最壞情況下的時(shí)間復(fù)雜度為O(cn2)。根據(jù)2021 年1 月發(fā)布的BGP 測(cè)量報(bào)告，從2012 年到2021 年，BGP 更新報(bào)文中的平均路徑長(zhǎng)度一直穩(wěn)定在5.7，在2021 年還呈下降趨勢(shì)。截至2021 年1 月，路由表中宣告的目的IP 網(wǎng)絡(luò)前綴數(shù)量為860 000，且數(shù)量近年來均保持較穩(wěn)定，沒有出現(xiàn)大規(guī)模增長(zhǎng)。

4 正確性證明

本節(jié)給出RSCTchain 的正確性證明?；诘?節(jié)中描述的域間路由模型及路由收斂的充分條件，針對(duì)RSCTchain 在鏈路失效導(dǎo)致的短時(shí)路由抖動(dòng)及策略沖突導(dǎo)致的持續(xù)路由振蕩2 種情況下的溯源檢測(cè)方法，相應(yīng)地給出定理1 和定理2，并進(jìn)行證明。

定理1給定由去往同一目的節(jié)點(diǎn)d的自治域節(jié)點(diǎn)組成的無向圖G=(V,E)，若所有自治域節(jié)點(diǎn)v∈V均為RSCTchain 的參與節(jié)點(diǎn)，則在鏈路失效時(shí)，對(duì)于任意自治域節(jié)點(diǎn)v∈V，v能夠檢測(cè)出可導(dǎo)致短時(shí)路由抖動(dòng)的失效鏈路。

證明無效路由的冗余傳播是導(dǎo)致短時(shí)路由抖動(dòng)的必要條件[20]。假設(shè)在無向圖G=(V,E)中存在失效鏈路P，定理1 的證明等同于證明RSCTchain的參與節(jié)點(diǎn)使用RITdetection 算法可避免繼續(xù)選擇或傳播包含失效鏈路P的無效路由。

不失一般性地，假設(shè)有無向圖G。鏈路失效導(dǎo)致的短時(shí)路由抖動(dòng)如圖5 所示，節(jié)點(diǎn)v0通往目的節(jié)點(diǎn)d的優(yōu)選路由為P0=〈v0d〉；節(jié)點(diǎn)vk通往目的節(jié)點(diǎn)d的優(yōu)選路由為；節(jié)點(diǎn)vi(0＜i＜k)通往目的節(jié)點(diǎn)d的優(yōu)選路由均包含鏈路P0。若不使用RSCTchain 進(jìn)行溯源檢測(cè)，當(dāng)鏈路P0失效后，vk在收到v0對(duì)P0的撤回通告后會(huì)選用路由表中的備選路徑；在收到v1對(duì)P1的撤回通告后會(huì)選用備選路徑，不斷重復(fù)此過程，直到收到vk-1對(duì)Pk-1的撤回通告后才發(fā)現(xiàn)去往目的節(jié)點(diǎn)d不可達(dá)。由于鏈路P0的失效導(dǎo)致冗余更新報(bào)文的傳播，造成短時(shí)路由抖動(dòng)。

圖5 鏈路失效導(dǎo)致的短時(shí)路由抖動(dòng)

當(dāng)G=(V,E)中所有自治域節(jié)點(diǎn)v∈V均為RSCTchain 的參與節(jié)點(diǎn)時(shí)，根據(jù)RSCTgeneration 算法，v0在對(duì)P0進(jìn)行撤回通告的同時(shí)會(huì)生成類型為“0-”的路由狀態(tài)變更標(biāo)識(shí)，同步至RSCTchain區(qū)塊鏈網(wǎng)絡(luò)，并由其他各RSCT 節(jié)點(diǎn)存至本地RSCTchain 存儲(chǔ)模塊。根據(jù)路由不穩(wěn)定溯源檢測(cè)RITdetection 算法，對(duì)于任意節(jié)點(diǎn)vi∈V，不管是否收到鄰接節(jié)點(diǎn)發(fā)送的路由更新報(bào)文，均可檢測(cè)導(dǎo)致短時(shí)路由抖動(dòng)的失效鏈路P0，并在本地路由表中過濾包含P0的路由，避免無效路由的冗余傳播。證畢。

定理2給定由去往同一目的節(jié)點(diǎn)d的自治域節(jié)點(diǎn)組成的無向圖G=(V,E)，若所有自治域節(jié)點(diǎn)v∈V均為RSCTchain 的參與節(jié)點(diǎn)，則對(duì)于任意自治域節(jié)點(diǎn)v0∈V，v0能夠檢測(cè)出是否在本地節(jié)點(diǎn)發(fā)生路由持續(xù)振蕩并追溯相應(yīng)的策略沖突自治域序列。

證明假設(shè)在G=(V,E)中存在引起路由持續(xù)振蕩的策略沖突相鄰自治域序列，則S中對(duì)于任意整數(shù)i∈[0,k]，節(jié)點(diǎn)vi-1的路由狀態(tài)變更引發(fā)節(jié)點(diǎn)vi的路由狀態(tài)變更且v0=vk。對(duì)定理2的證明即等同于證明v0使用RITdetection 算法可檢測(cè)出G中存在爭(zhēng)議輪。

不失一般性地，假設(shè)無向圖G為如第2 節(jié)中圖1所示的爭(zhēng)議輪。當(dāng)相鄰自治域序列中對(duì)于任意整數(shù)i∈[0,k]，節(jié)點(diǎn)vi-1的路由狀態(tài)變更引發(fā)節(jié)點(diǎn)vi的路由狀態(tài)變更時(shí)，對(duì)于任意整數(shù)i∈[0,k]，節(jié)點(diǎn)vi-1的路由狀態(tài)變更引發(fā)節(jié)點(diǎn)vi的路由狀態(tài)變更可分為2 種情況：第一種情況為vi的路由狀態(tài)變更類型為“0+”或“1+”，即由于vi-1的路由狀態(tài)變更使vi選擇vi-1作為新路徑的下一跳且新路徑的優(yōu)先級(jí)高于舊路徑，這代表vi更愿意選擇通過弧邊的路徑；第二種情況為vi的路由狀態(tài)變更類型為“1-”，即由于vi-1的路由狀態(tài)變更使vi不得不放棄當(dāng)前偏好值更高的路徑，該被替換的舊路徑下一跳為vi-1，即優(yōu)先級(jí)高于舊路徑，這也代表vi更愿意選擇通過弧邊的路徑。因此S中自治域節(jié)點(diǎn)依次相連可構(gòu)成爭(zhēng)議輪中的弧邊。

當(dāng)v0=vk時(shí)，S中的自治域節(jié)點(diǎn)依次相連構(gòu)成一個(gè)環(huán)，這里將v0首次狀態(tài)變更的時(shí)刻記為tin，v0由vk-1狀態(tài)變更導(dǎo)致的狀態(tài)變更時(shí)刻記為tout，下面分別通過分析tin和tout時(shí)刻的路由狀態(tài)變化，確定v0節(jié)點(diǎn)的輻邊與弧邊：在tin時(shí)刻，若v0導(dǎo)致v1的狀態(tài)變更類型為“0+”或“1+”時(shí)，代表v1選取了一條經(jīng)過v0的新路徑這說明v0在tin時(shí)刻的新路徑Q0=π(v0,tin)是可達(dá)的。因?yàn)関0的輻邊是唯一的，且在v1節(jié)點(diǎn)處的優(yōu)先級(jí)更高，所以v0的輻邊為v0在tin時(shí)刻的新路徑Q0；若v0導(dǎo)致v1的狀態(tài)變更類型為“1-”時(shí)，代表v1被迫放棄了經(jīng)過v0的舊路徑，這說明v0在tin時(shí)刻狀態(tài)變更前的舊路徑在tin時(shí)刻前是可達(dá)的，則v0的輻邊為v0在tin時(shí)刻狀態(tài)變更時(shí)被替換的舊路徑Q0；同樣地，在tout時(shí)刻，若vk-1導(dǎo)致v0狀態(tài)變更時(shí)的新路徑優(yōu)先級(jí)高于舊路徑，且v0擬選取的新路徑下一跳為vk-1，即代表v0在狀態(tài)變更后包含弧邊Rk的新路徑可達(dá)，因此v0包含弧邊的路徑為在tout時(shí)刻的新路徑；若vk-1導(dǎo)致v0狀態(tài)變更時(shí)的新路徑優(yōu)先級(jí)低于舊路徑，且v0擬選取的新路徑下一跳不是vk-1時(shí)，代表v0狀態(tài)變更前包含弧邊Rk的舊路徑可達(dá)，因此v0包含弧邊的路徑為在tout時(shí)刻的舊路徑在確定本地輻邊與弧邊后，v0可在本地比較路徑與路徑Q0的優(yōu)先級(jí)，當(dāng)時(shí)，v0即可判斷G中存在爭(zhēng)議輪。

當(dāng)G=(V,E)中所有自治域節(jié)點(diǎn)均為RSCTchain的參與節(jié)點(diǎn)時(shí)，根據(jù)RSCTgeneration 算法，自治域節(jié)點(diǎn)對(duì)應(yīng)的RSCT 節(jié)點(diǎn)會(huì)生成描述本地路由狀態(tài)變更的標(biāo)識(shí)，同步至RSCTchain 區(qū)塊鏈網(wǎng)絡(luò)，并由各RSCT 節(jié)點(diǎn)存至本地RSCTchain 存儲(chǔ)模塊。根據(jù)上述分析，當(dāng)在v0節(jié)點(diǎn)開始發(fā)生路由持續(xù)振蕩后，v0可使用RITdetection 算法基于RSCTchain 本地存儲(chǔ)模塊追溯路由狀態(tài)變更標(biāo)識(shí)，從而檢測(cè)出在本地節(jié)點(diǎn)發(fā)生的路由持續(xù)振蕩并追溯出相應(yīng)的策略沖突自治域序列S={v0,v1,v2,…,vk}。證畢。

綜上，RSCTchain 可以對(duì)短時(shí)路由抖動(dòng)（收斂時(shí)延）及持續(xù)路由振蕩2 種類型的BGP 不穩(wěn)定情況進(jìn)行檢測(cè)，且可以追溯導(dǎo)致路由不穩(wěn)定的故障源（失效鏈路或策略沖突AS 序列）。

5 仿真分析

為了對(duì)RSCTchain 的有效性和可擴(kuò)展性進(jìn)行驗(yàn)證，本文基于Quagga 軟件路由器和BigchainDB實(shí)現(xiàn)了RSCTchain 的功能，在經(jīng)典拓?fù)渲虚_展仿真實(shí)驗(yàn)驗(yàn)證其有效性，并基于 BGP 現(xiàn)網(wǎng)數(shù)據(jù)對(duì)RSCTchain 的可擴(kuò)展性進(jìn)行分析。

5.1 仿真實(shí)驗(yàn)設(shè)計(jì)

本文實(shí)現(xiàn)了RSCTchain 原型系統(tǒng)。區(qū)塊鏈存儲(chǔ)基于BigchainDB 實(shí)現(xiàn)。BigchainDB 廣泛用于開發(fā)并部署區(qū)塊鏈概念驗(yàn)證平臺(tái)和應(yīng)用程序，可視為一個(gè)具備區(qū)塊鏈特征的開源分布式存儲(chǔ)系統(tǒng)，同時(shí)具備區(qū)塊鏈塊鏈屬性和數(shù)據(jù)庫屬性，其數(shù)據(jù)存儲(chǔ)基于MangoDB 實(shí)現(xiàn)，其聯(lián)網(wǎng)與共識(shí)基于拜占庭容錯(cuò)的Tendermint 實(shí)現(xiàn)；域間路由網(wǎng)絡(luò)拓?fù)浠谲浖酚善鱍uagga 的BGPd 模塊（即BGP 守護(hù)進(jìn)程）實(shí)現(xiàn)；每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)運(yùn)行在Docker 虛擬容器（20.10.5 版本）上，運(yùn)行在一臺(tái)64 GB 內(nèi)存，Intel? Xeon? Gold 6230 CPU@2.10 GHz 的服務(wù)器中的Ubuntu 16.04 虛擬機(jī)（內(nèi)存8 GB，硬盤40 GB，處理器8）上。

本文選取Quagga BGPd 模塊（等同于使用BGP）及stableBGP[15]作為比較對(duì)象，分別在策略沖突和鏈路失效的情況下開展RSCTchain 的有效性實(shí)驗(yàn)。在策略沖突實(shí)驗(yàn)情景中，采用文獻(xiàn)[6]中給出的策略沖突導(dǎo)致持續(xù)路由振蕩的Bad Garget 經(jīng)典拓?fù)洌ㄈ鐖D2(a)所示），選用更新報(bào)文數(shù)量用于評(píng)估有效性[14-15]。在鏈路失效實(shí)驗(yàn)情景中，采用經(jīng)常用于路由失效穩(wěn)定性研究的 Clique 拓?fù)浼癇ackup-Clique 拓?fù)鋄18,21-22]，如圖6 所示。圖6(a)為Clique 拓?fù)?，圖6(b)為8 節(jié)點(diǎn)的Backup-Clique拓?fù)?。Backup-Clique 拓?fù)淇赡M一個(gè)邊緣網(wǎng)絡(luò)通過一條直接路徑和一個(gè)較長(zhǎng)的備選路徑連接到核心網(wǎng)絡(luò)的情景。在鏈路失效情況下，選用路由收斂時(shí)間和更新報(bào)文數(shù)量評(píng)估有效性。

圖6 鏈路失效實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)?/p>

5.2 有效性分析

RSCTchain 能夠針對(duì)非單一類型的路由不穩(wěn)定進(jìn)行檢測(cè)溯源，區(qū)分路由不穩(wěn)定類型并追溯其源頭。因此分別在策略沖突和鏈路失效的情況下開展有效性實(shí)驗(yàn)。

1) 策略沖突實(shí)驗(yàn)

圖7 展示了在策略沖突實(shí)驗(yàn)情景中，使用BGP、RSCTchain 及stableBGP 時(shí)，網(wǎng)絡(luò)中的更新報(bào)文總量隨MRAI 時(shí)間間隔的變化，這里MRAI 取值為30 s。從圖7 中可觀察到，在使用BGP 的情況下，整個(gè)網(wǎng)絡(luò)中的累計(jì)更新報(bào)文數(shù)量隨著MRAI 時(shí)間間隔的增多而不斷增長(zhǎng)，這說明發(fā)生了由策略沖突引起的路由振蕩，導(dǎo)致路由不收斂；在使用stableBGP的情況下，在第三個(gè)MRAI 時(shí)間間隔前后檢測(cè)出策略沖突，在調(diào)整策略后的3 個(gè)MRAI 時(shí)間間隔內(nèi)路由收斂，之后網(wǎng)絡(luò)中的更新報(bào)文數(shù)量不再繼續(xù)增長(zhǎng)，其總量保持為51 個(gè)，說明stableBGP 能夠檢測(cè)出可能導(dǎo)致路由振蕩的路由策略沖突，并在及時(shí)干預(yù)后能夠使路由收斂；在使用RSCTchain 的情況下，也是在第三個(gè)MRAI 時(shí)間間隔前后檢測(cè)出策略沖突，但調(diào)整策略后的2 個(gè)MRAI 時(shí)間間隔內(nèi)路由即收斂，后續(xù)網(wǎng)絡(luò)中的更新報(bào)文數(shù)量不再繼續(xù)增長(zhǎng)，其總量保持為45 個(gè)。

圖7 路由策略沖突情景中BGP、stableBGP 和RSCTchain 有效性對(duì)比

2) 鏈路失效實(shí)驗(yàn)

圖8 展示了鏈路失效實(shí)驗(yàn)情景中，使用BGP、RSCTchain 及stableBGP 時(shí)，在不同規(guī)模的網(wǎng)絡(luò)中的收斂時(shí)間和更新報(bào)文數(shù)量。從圖8(a)可以看出，使用 BGP 的網(wǎng)絡(luò)收斂時(shí)間最長(zhǎng)；使用stableBGP 的網(wǎng)絡(luò)收斂時(shí)間次之，比使用BGP 平均減少了39.75%；使用RSCTchain 的網(wǎng)絡(luò)收斂時(shí)間最短，比使用BGP 平均減少了50%。相較于使用BGP，RSCTchain 能夠比stableBGP 平均多縮短10.25%的網(wǎng)絡(luò)收斂時(shí)間。從圖8(b)可觀察到，使用BGP 情況下路由收斂時(shí)網(wǎng)絡(luò)中總共交換的更新報(bào)文數(shù)量最多；使用stabelBGP 的更新報(bào)文數(shù)量次之，比使用BGP 平均減少了16.75%；使用RSCTchain 的更新報(bào)文數(shù)量最少，比使用BGP平均減少了27.06%。相較于使用BGP，RSCTchain能夠比stableBGP 平均多減少10.31%的冗余更新報(bào)文傳播。

圖8 鏈路失效情景中BGP、stableBGP 和RSCTchain 的有效性對(duì)比

由上述實(shí)驗(yàn)結(jié)果可知，相較于stableBGP，RSCTchain 能夠更及時(shí)地檢測(cè)策略與拓?fù)鋭?dòng)態(tài)變化導(dǎo)致的路由不穩(wěn)定現(xiàn)象并確定其源頭，且能抑制更多的冗余更新報(bào)文傳播，其原因在于：RSCTchain使用了BGP 帶外路由狀態(tài)變更同步機(jī)制（區(qū)塊鏈節(jié)點(diǎn)數(shù)據(jù)同步），而stableBGP 使用BGP 帶內(nèi)路由狀態(tài)變更同步機(jī)制（攜帶于BGP 更新報(bào)文中逐跳傳遞，其效率取決于MRAI 設(shè)置）。本實(shí)驗(yàn)中MRAI 設(shè)置為默認(rèn)值30 s，BigchainDB 中采用Tendermint 的區(qū)塊時(shí)間實(shí)測(cè)為3 s 左右，因此RSCTchain 能夠更及時(shí)地對(duì)路由不穩(wěn)定現(xiàn)象做出反應(yīng)。

5.3 可擴(kuò)展性分析

為了分析RSCTchain 在實(shí)際域間路由部署的可擴(kuò)展性，基于Routeviews 項(xiàng)目提供的BGP 現(xiàn)網(wǎng)數(shù)據(jù)在BigchainDB 中模擬路由變更標(biāo)識(shí)的發(fā)布與存儲(chǔ)過程，統(tǒng)計(jì)時(shí)間開銷和空間開銷隨著處理更新報(bào)文數(shù)量的變化，進(jìn)而根據(jù)當(dāng)前域間路由系統(tǒng)實(shí)際需求分析RSCTchain 的可擴(kuò)展性。

RSCTchain 原型系統(tǒng)中每個(gè)區(qū)塊最多能包含400 個(gè)路由狀態(tài)變更標(biāo)識(shí)交易，平均區(qū)塊時(shí)間為3 s，確認(rèn)并同步一個(gè)路由狀態(tài)變更標(biāo)識(shí)的時(shí)間為7.5 ms。在處理不同數(shù)量BGP 更新報(bào)文的情況下分別生成對(duì)應(yīng)的RSCTchain 區(qū)塊鏈數(shù)據(jù)庫，其所需空間大小及相應(yīng)路由不穩(wěn)定溯源的平均時(shí)間如圖9 所示。從圖9 可以看出，隨著處理BGP 更新報(bào)文數(shù)量的增多，RSCTchain 所需存儲(chǔ)大小及路由不穩(wěn)定溯源檢測(cè)平均時(shí)間均呈線性增長(zhǎng)趨勢(shì)。

圖9 RSCTchain 可擴(kuò)展性分析

根據(jù)上述實(shí)驗(yàn)結(jié)果，結(jié)合域間路由實(shí)際需求對(duì)RSCTchain 的可擴(kuò)展性進(jìn)行分析。當(dāng)前域間路由系統(tǒng)中平均每日的更新報(bào)文約為400 000 個(gè)。在時(shí)間開銷方面，RSCTchain 不穩(wěn)定溯源檢測(cè)時(shí)間在毫秒級(jí)別，對(duì)處理400 000 個(gè)更新報(bào)文產(chǎn)生的RSCT 溯源檢測(cè)檢測(cè)時(shí)間為193.23 ms，當(dāng)以天為單位進(jìn)行溯源檢測(cè)時(shí)可以滿足域間路由系統(tǒng)控制平面實(shí)際需求；在空間開銷方面，RSCTchain 的路由狀態(tài)變更鏈大小將以每日約0.7 GB 的速度增長(zhǎng)，一年的路由狀態(tài)變更鏈約需255.5 GB 的存儲(chǔ)空間，可以適應(yīng)當(dāng)前通用商用硬盤。因此RSCTchain 應(yīng)用于實(shí)際域間路由系統(tǒng)是可行的。此外，現(xiàn)有的區(qū)塊鏈歷史交易數(shù)據(jù)壓縮、擴(kuò)容技術(shù)等研究[23]也可進(jìn)一步提高RSCTchain 的可行性。

6 結(jié)束語

本文提出一種基于路由狀態(tài)因果鏈的域間路由不穩(wěn)定溯源檢測(cè)方法RSCTchain，通過將路由狀態(tài)變更信息與轉(zhuǎn)移過程發(fā)布到區(qū)塊鏈，構(gòu)建可反映路由狀態(tài)變更因果關(guān)系的路由狀態(tài)因果鏈，使自治域通過追溯本地區(qū)塊鏈存儲(chǔ)以檢測(cè)和定位失效鏈路或策略沖突自治域序列。理論證明與仿真實(shí)驗(yàn)結(jié)果表明，RSCTchain 能夠以合理開銷及時(shí)檢測(cè)非單一類型的路由不穩(wěn)定現(xiàn)象，并定位導(dǎo)致路由不穩(wěn)定的失效鏈路或策略沖突自治域序列，可有效抑制冗余路由更新報(bào)文、減少路由收斂時(shí)間。下一步工作將基于實(shí)際域間路由拓?fù)溟_展更大規(guī)模的仿真實(shí)驗(yàn)與性能測(cè)試。