基于路由狀態因果鏈的域間路由不穩定溯源檢測方法

陳迪，邱菡，張萬里，朱會虎，朱俊虎，王清賢

（1.信息工程大學網絡空間安全學院，河南 鄭州 450002；2.電子信息系統復雜電磁環境效應國家重點實驗室，河南 洛陽 471003）

1 引言

域間路由系統由眾多獨立運營的自治域（AS,autonomous system）組成。作為現行域間路由系統的事實標準協議，邊界網關協議（BGP,border gateway protocol）[1]是策略驅動的路徑矢量協議，支持各自治域自主制定本地選路策略，進而從候選路徑中選擇到達特定目的網絡的路徑。然而，自治域配置路由策略的靈活性是以犧牲路由穩定性為代價的[2]。路由不穩定即在路徑收斂前自治域不斷采用和舍棄路徑的狀態變更過程，例如由拓撲變化導致的短時路由抖動[3]或由多個自治域策略沖突導致的持續路由振蕩[4]。自治域間不必要的路由狀態變更會降低網絡服務質量，增加網絡時延，進而導致服務中斷或數據包丟失[5]。

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

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

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

2 問題描述

2.1 符號與假設

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

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

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

為了表述清晰，本文做出如下假設：1)所有AS節點發出的路由宣告update報文均通往單個目的前綴地址；2)每個AS 節點由單個BGP 路由器代表。

2.2 域間路由穩定收斂條件

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

定義3一致性。對于在t時刻到達目的節點d的路徑分配集合Pt，當所有路徑P∈Pt構成一個以d為根的轉發樹時，則路徑分配Pt是一致的，即對于任意v,u∈V，如果π(v)=vuP，則π(u)=uP。

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

定義 5安全性。對于在t時刻所有節點到達目的節點d的路徑分配集合發生更新時，存在有限時間T，當t'＜T時且路徑可達，當時則路徑分配Pt是安全的。

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

圖1 一個大小為k 的爭議輪

2.3 域間路由不穩定類型

域間路由不穩定主要包括2 種類型：持續路由振蕩及短時路由抖動。圖2 分別給出了持續路由振蕩與短時路由抖動的示例。

持續路由振蕩指一些AS 節點在選路過程中始終無法穩定，使路由更新持續在這些AS 節點中交換傳遞的現象。導致持續路由振蕩的原因通常是各AS 自主配置的本地優先屬性配置不合理，路由策略產生了沖突。圖2(a)為策略沖突導致持續路由振蕩的例子，AS0為其他AS 節點的目的節點，每個節點旁邊標注的是本地路徑偏好列表，最上面的路徑為根據本地偏好的最優路徑。例如AS1相較于路徑10，更希望選擇路徑1430 到達AS0。當AS2選擇210 時，AS3由于最優路由320 不可達變更路徑為30，繼而AS4更改路徑為430，AS1更改路徑為1430，導致AS2由于120 路徑不可達重新更改路徑為20，使AS3重新選擇320……AS0～AS4構成了一個爭議輪，路由狀態會因策略沖突周而復始地切換。

圖2 持續路由振蕩與短時路由抖動示例

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

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

綜上，本文要解決的問題是針對當前路由不穩定溯源檢測方法中檢測時間受限于路由更新時延、溯源信息可能被篡改的問題，在不改變現行BGP 的前提下，檢測BGP 不穩定現象并判斷其類型（拓撲變化導致的短時路由抖動/策略沖突導致的持續路由振蕩），追溯導致BGP 不穩定的具體失效鏈路/策略沖突AS 序列，同時保證檢測過程可追溯、防篡改。

3 RSCTchain

3.1 RSCTchain 概述

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

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

圖3 RSCTchain 的整體架構與工作流程

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

為了優化路由不穩定檢測與溯源時間，RSCTchain 在實現中可將每個RSCT 節點運行在與BGP 路由器物理上獨立的專用服務器中，并對應一個運行在BGP 路由器中的本地驗證節點。路由狀態標識發布時，RSCT 節點負責在區塊鏈網絡中完成同步與存儲。本地驗證節點不參與區塊鏈中的共識同步過程，只負責定期接收RSCT 節點下發的區塊并在緩存中存儲本地相關的路由狀態變更標識以供查詢，即對于任意的AS，可將通往同一目的網絡且具有連鎖因果關系的路由狀態變更標識按序存儲于本地路由驗證緩存中。

3.2 路由狀態變更標識

在RSCTchain 中，使用路由狀態變更標識記錄各自治域路由狀態變更信息與轉移過程。本節給出路由狀態變更標識的定義及其生成算法。

文獻[18-19]給出了由拓撲與策略變化觸發的可能影響收斂過程的四類路由狀態變更事件（Tup,Tdown,Tshort,Tlong），統稱為T 事件，并在此基礎上給出路由狀態變更類別的定義。

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

為敘述方便，下文使用新路徑rn和舊路徑ro分別代表t+1時刻的更新路徑和t時刻的當前路徑。下面，給出路由狀態變更標識RSCT 的定義。

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

路由狀態變更標識的生成算法如算法1 所示。

算法1路由狀態變更標識生成RSCTgeneration

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

輸出路由狀態變更標識RSCT

生成路由狀態變更標識分為4 種情況。

1) 當ASu與路徑ro的下一跳AS 之間的鏈路失效，ASu將ro撤回（即rn=〈?〉）或將其替換為一條次優路徑rn時，生成(hash(u,rn,t),null,0?,u,null,ro,rn,t,Sigu,Pku)作為該路由狀態變更的標識RSCT（第1)～2)行）。

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

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

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

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

圖4 RSCTchain 路由狀態變更標識生成示例

3.3 路由不穩定溯源檢測

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

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

算法2路由不穩定溯源檢測RITdetection

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

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

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

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

4 正確性證明

本節給出RSCTchain 的正確性證明。基于第2節中描述的域間路由模型及路由收斂的充分條件，針對RSCTchain 在鏈路失效導致的短時路由抖動及策略沖突導致的持續路由振蕩2 種情況下的溯源檢測方法，相應地給出定理1 和定理2，并進行證明。

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

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

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

圖5 鏈路失效導致的短時路由抖動

當G=(V,E)中所有自治域節點v∈V均為RSCTchain 的參與節點時，根據RSCTgeneration 算法，v0在對P0進行撤回通告的同時會生成類型為“0-”的路由狀態變更標識，同步至RSCTchain區塊鏈網絡，并由其他各RSCT 節點存至本地RSCTchain 存儲模塊。根據路由不穩定溯源檢測RITdetection 算法，對于任意節點vi∈V，不管是否收到鄰接節點發送的路由更新報文，均可檢測導致短時路由抖動的失效鏈路P0，并在本地路由表中過濾包含P0的路由，避免無效路由的冗余傳播。證畢。

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

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

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

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

當G=(V,E)中所有自治域節點均為RSCTchain的參與節點時，根據RSCTgeneration 算法，自治域節點對應的RSCT 節點會生成描述本地路由狀態變更的標識，同步至RSCTchain 區塊鏈網絡，并由各RSCT 節點存至本地RSCTchain 存儲模塊。根據上述分析，當在v0節點開始發生路由持續振蕩后，v0可使用RITdetection 算法基于RSCTchain 本地存儲模塊追溯路由狀態變更標識，從而檢測出在本地節點發生的路由持續振蕩并追溯出相應的策略沖突自治域序列S={v0,v1,v2,…,vk}。證畢。

綜上，RSCTchain 可以對短時路由抖動（收斂時延）及持續路由振蕩2 種類型的BGP 不穩定情況進行檢測，且可以追溯導致路由不穩定的故障源（失效鏈路或策略沖突AS 序列）。

5 仿真分析

為了對RSCTchain 的有效性和可擴展性進行驗證，本文基于Quagga 軟件路由器和BigchainDB實現了RSCTchain 的功能，在經典拓撲中開展仿真實驗驗證其有效性，并基于 BGP 現網數據對RSCTchain 的可擴展性進行分析。

5.1 仿真實驗設計

本文實現了RSCTchain 原型系統。區塊鏈存儲基于BigchainDB 實現。BigchainDB 廣泛用于開發并部署區塊鏈概念驗證平臺和應用程序，可視為一個具備區塊鏈特征的開源分布式存儲系統，同時具備區塊鏈塊鏈屬性和數據庫屬性，其數據存儲基于MangoDB 實現，其聯網與共識基于拜占庭容錯的Tendermint 實現；域間路由網絡拓撲基于軟件路由器Quagga 的BGPd 模塊（即BGP 守護進程）實現；每個網絡節點運行在Docker 虛擬容器（20.10.5 版本）上，運行在一臺64 GB 內存，Intel? Xeon? Gold 6230 CPU@2.10 GHz 的服務器中的Ubuntu 16.04 虛擬機（內存8 GB，硬盤40 GB，處理器8）上。

本文選取Quagga BGPd 模塊（等同于使用BGP）及stableBGP[15]作為比較對象，分別在策略沖突和鏈路失效的情況下開展RSCTchain 的有效性實驗。在策略沖突實驗情景中，采用文獻[6]中給出的策略沖突導致持續路由振蕩的Bad Garget 經典拓撲（如圖2(a)所示），選用更新報文數量用于評估有效性[14-15]。在鏈路失效實驗情景中，采用經常用于路由失效穩定性研究的 Clique 拓撲及Backup-Clique 拓撲[18,21-22]，如圖6 所示。圖6(a)為Clique 拓撲，圖6(b)為8 節點的Backup-Clique拓撲。Backup-Clique 拓撲可模擬一個邊緣網絡通過一條直接路徑和一個較長的備選路徑連接到核心網絡的情景。在鏈路失效情況下，選用路由收斂時間和更新報文數量評估有效性。

圖6 鏈路失效實驗網絡拓撲

5.2 有效性分析

RSCTchain 能夠針對非單一類型的路由不穩定進行檢測溯源，區分路由不穩定類型并追溯其源頭。因此分別在策略沖突和鏈路失效的情況下開展有效性實驗。

1) 策略沖突實驗

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

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

2) 鏈路失效實驗

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

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

由上述實驗結果可知，相較于stableBGP，RSCTchain 能夠更及時地檢測策略與拓撲動態變化導致的路由不穩定現象并確定其源頭，且能抑制更多的冗余更新報文傳播，其原因在于：RSCTchain使用了BGP 帶外路由狀態變更同步機制（區塊鏈節點數據同步），而stableBGP 使用BGP 帶內路由狀態變更同步機制（攜帶于BGP 更新報文中逐跳傳遞，其效率取決于MRAI 設置）。本實驗中MRAI 設置為默認值30 s，BigchainDB 中采用Tendermint 的區塊時間實測為3 s 左右，因此RSCTchain 能夠更及時地對路由不穩定現象做出反應。

5.3 可擴展性分析

為了分析RSCTchain 在實際域間路由部署的可擴展性，基于Routeviews 項目提供的BGP 現網數據在BigchainDB 中模擬路由變更標識的發布與存儲過程，統計時間開銷和空間開銷隨著處理更新報文數量的變化，進而根據當前域間路由系統實際需求分析RSCTchain 的可擴展性。

RSCTchain 原型系統中每個區塊最多能包含400 個路由狀態變更標識交易，平均區塊時間為3 s，確認并同步一個路由狀態變更標識的時間為7.5 ms。在處理不同數量BGP 更新報文的情況下分別生成對應的RSCTchain 區塊鏈數據庫，其所需空間大小及相應路由不穩定溯源的平均時間如圖9 所示。從圖9 可以看出，隨著處理BGP 更新報文數量的增多，RSCTchain 所需存儲大小及路由不穩定溯源檢測平均時間均呈線性增長趨勢。

圖9 RSCTchain 可擴展性分析

根據上述實驗結果，結合域間路由實際需求對RSCTchain 的可擴展性進行分析。當前域間路由系統中平均每日的更新報文約為400 000 個。在時間開銷方面，RSCTchain 不穩定溯源檢測時間在毫秒級別，對處理400 000 個更新報文產生的RSCT 溯源檢測檢測時間為193.23 ms，當以天為單位進行溯源檢測時可以滿足域間路由系統控制平面實際需求；在空間開銷方面，RSCTchain 的路由狀態變更鏈大小將以每日約0.7 GB 的速度增長，一年的路由狀態變更鏈約需255.5 GB 的存儲空間，可以適應當前通用商用硬盤。因此RSCTchain 應用于實際域間路由系統是可行的。此外，現有的區塊鏈歷史交易數據壓縮、擴容技術等研究[23]也可進一步提高RSCTchain 的可行性。

6 結束語

本文提出一種基于路由狀態因果鏈的域間路由不穩定溯源檢測方法RSCTchain，通過將路由狀態變更信息與轉移過程發布到區塊鏈，構建可反映路由狀態變更因果關系的路由狀態因果鏈，使自治域通過追溯本地區塊鏈存儲以檢測和定位失效鏈路或策略沖突自治域序列。理論證明與仿真實驗結果表明，RSCTchain 能夠以合理開銷及時檢測非單一類型的路由不穩定現象，并定位導致路由不穩定的失效鏈路或策略沖突自治域序列，可有效抑制冗余路由更新報文、減少路由收斂時間。下一步工作將基于實際域間路由拓撲開展更大規模的仿真實驗與性能測試。