一種新型安全路由協議:勢能導向多下一跳路由協議*

蘭巨龍，張建輝，王艷紅，馬海龍，卜佑軍

（1.國家數字交換系統工程技術研究中心 鄭州450002；2.大連環宇移動科技有限公司 大連116600）

1 引言

隨著信息技術對人類生產、生活影響力的不斷增強，各種網絡基礎設施逐漸成為關系到國計民生的重要戰略資源，網絡的安全性和生存性日益凸顯。在新的歷史條件下，網絡安全性和生存性面臨兩大挑戰：一是平時環境下針對網絡設備的惡意攻擊和侵害造成的網絡失效；二是軍事打擊、恐怖襲擊及自然災害等極端環境下，網絡局部或全局失效。傳統商用路由器已有的網絡生存性和快速自愈技術都不足以應對上述挑戰，當前結合網絡路由技術進行網絡可生存性的研究集中體現在3個方面：基于MPLS協議的路徑快速保護切換技術、基于傳統成熟IP路由協議的參數調整機制和基于傳統IP路由技術的擴展方法。

基于MPLS協議的路徑快速保護切換技術是一種基于預先確定故障恢復的生存性技術，針對網絡中特定鏈路或路徑進行資源預留，即在傳輸路徑建立的同時就建立起備份路徑。當在數據傳輸過程中檢測到鏈路故障發生時，傳輸的業務就自動切換到備份鏈路或路徑。根據受保護的LSP和備份LSP之間的比例，保護技術通常采用4種結構來實現：1+1 LSP保護、1∶1 LSP保護、1∶n LSP保 護 和n∶m LSP保護。由于此技術依賴人工配置，雖然可以實現路徑的快速切換，但其靈活性和擴展性具有很大的局限，一般只用來保護關鍵的節點和鏈路。

基于IP路由協議的參數調整機制是通過調整路由協議中計數器的參數值加快協議收斂的。傳統的OSPF（open shortest path first）路由協議和IS-IS（intermediate system to intermediate system）路由協議周期性地發送網絡路由協議報文探測各鄰居節點，當檢測到網絡發生故障時，會觸發路由協議的收斂過程，此時路由協議產生并洪泛網絡鏈路狀態信息，接收到鏈路狀態信息的路由器依據最短路徑樹計算結果更新網絡路由和路由器其轉發表。為了加快網絡故障發生時路由協議的收斂過程，可以通過調整路由協議中采用的計數器的值，將較大規模網絡的路由收斂過程控制在100 ms內完成。但傳統路由協議本身不具備根據網絡環境變化自適應調整路由配置參數的能力，協議參數的調整需要人工干預方能完成，使得該技術的應用僅能局限在單一網絡故障場景，無法適應多種網絡故障并發的情況。

基于傳統IP路由技術的擴展方法主要包括了基于備份路徑技術的故障恢復技術、基于多拓撲的故障恢復機制和多路徑路由機制。基于備份路徑技術的故障恢復技術無需為保護路徑預留網絡資源，故障恢復能夠在毫秒數量級的時間內完成，這類方法特別適合解決頻繁發作的故障，保障了路由收斂期間的通信暢通，這類恢復方案主要有：快速重路由[1]、故障抑制路由[2]、基于偏轉的備份路由。基于多拓撲的故障恢復機制是IP網絡所獨有的提高生存性技術，其主要思想就是路由器在原有拓撲的基礎上建立多個備份拓撲，每個備份拓撲保護部分鏈路或節點，所有備份拓撲保護全部鏈路和節點。這類技術不僅可以處理單鏈路、單節點故障，也可以解決多故障問題，目前的相關研究工作主要有：多拓撲路由機制[3]、多配置路由機制[4]、基于故障推理的快速重路由[1]、彈性路由層機制[5,6]。多路徑路由方法中，典型的研究成果是Vutukury和Garcia-Luna-Aceves等提出的多路距離矢量算法（MDVA）[7]、多路徑局部分發算法與結合服務質量的局部分發算法[7]等改進的MDVA算法以及在時延容遲網絡等場景下的多徑路由機制[8,9]。這些方法可為每個目的IP地址提供多個可用下一跳鏈路，在算法設計時采用一組無環不等式條件來避免瞬時的環路和計數無窮大等問題；但算法的計算開銷過大，其可用下一跳節點數量較少，網絡資源利用率不高。

另外在路由安全性方面，IETF成立了路由協議安全工作組，研究路由協議的安全威脅，有研究人員提出的建立主路由信息庫方法[10]，如采用密碼技術的安全RIP（routing information protocol,路由信息協議）（SRIP）[11]、三角理論安全距離矢量協議（SDV協議）[13]，但這些方案路由負載和計算開銷過大，只針對特定攻擊手段設計，抵御攻擊類型有限。

2 基于勢能的網絡多下一跳路由思想

自然界中的水流具有從高處向低處流動的特性，因為水在所流經地點的相對海拔高度不同而具有不同的勢能，任何存在海拔差的相通的地方，水流均能由高勢能點流向低勢能點。由此現象啟發，在IP網絡中引入勢能的思想，規定數據報文可以由高勢能節點向低勢能節點轉發，從而形成了由源節點到目的節點的多個可用下一跳路徑，在這些可用下一跳路徑中進行數據報文轉發時不會形成環路。

以圖1（a）的網絡拓撲為例，經過網絡勢能通告過程后得到圖1（b）所示的相對于目的節點i的網絡層次圖，勢能的計算過程如圖1（a）中實線箭頭所示。在勢能計算過程，所有節點均知道自己鄰居節點的勢能值，然后各個節點依據勢能計算式算出自己節點的勢能值，進行報文轉發時各節點選擇低勢能節點進行數據的轉發，如圖1（a）中虛線箭頭所示。

圖1 節點勢能的報文轉發方法

3 協議設計

協議的設計思路是在不改變現有網絡基本路由架構的情況下，提出“節點勢能”路由機制，設計基于尋路勢能和安全可信勢能的勢能導向多下一跳路由協議（multi-next hop routing protocol based on node potential,NP-MNRP），通過對節點可信度的有效評估實現了不可信節點的檢測和避繞；通過局部的流量感知和自適應的多下一跳并行轉發解決了異常流量導致的網絡不可用，保證了網絡級的自主可控和應用級的持續可用。

3.1 勢能計算方法

3.1.1 尋路勢能計算方法

步驟1計算節點在所處網絡中的勢能層值。對于網絡中指定的目的節點，定義其勢能層值為0；而對于網絡中其他節點，勢能層值為其鄰居節點勢能層值中的最小值加1，具體的計算式為：

其中，L(i,j)表示節點i相對于目的節點j的勢能層值，N為網絡中的節點集合，K為節點i的鄰居節點集合。

步驟2計算節點勢能值。如果待計算節點的勢能層值為0，則其勢能值為0；如果待計算節點的勢能層值非零，則在其同層或低一層鄰居節點中選出性能最高且勢能值未確定的節點，將該鄰居節點的勢能層值加1作為待計算節點的勢能值。

步驟3生成多下一跳集合。勢能值為0的節點的多下一跳集合為空；對于其他節點，其多下一跳集合由勢能值小于本節點的所有鄰居節點組成。

規定數據傳送時，選擇本節點的多下一跳集合進行數據轉發，即多下一跳路由。

3.1.2 可信勢能計算方法

協議首次將節點可信程度作為路由度量考慮因素之一，引入路由計算過程，從根本上解決了路由協議面臨的路由安全問題。設計的可信勢能計算方法如下：依據路由通告的真實性鑒別結果，在一定時間周期T和網絡路由空間范圍R內，統計每一個節點的路由通告真偽頻次D，結合節點重要度K和拓撲結構熵E等要素，計算節點的可信勢能值Pj。

將低于可信勢能閾值的節點判定為可疑節點，同時將網絡中承載的用戶業務進行安全屬性分級，高安全級的業務映射到可信勢能值高的節點組成的路徑上。

而在時間周期T內路由前綴在路由空間R內的所有用戶業務流不經過被判為可疑的節點，只選擇可信勢能滿足業務安全要求的路徑進行數據轉發。

3.2 協議設計

3.2.1 協議的網絡視圖

考慮到網絡拓撲信息和網絡可達性信息的來源、動態性、信息變化對路由轉發的影響等因素，協議的網絡視圖將網絡劃分為終端用戶網絡和業務承載網絡，如圖2所示。終端用戶網絡的節點運行傳統單下一跳路由協議，把目的IP地址不是本網的數據報文轉發給業務承載網絡，完成本地通信；業務承載網絡中的節點運行節點勢能導向多下一跳路由協議，節點勢能導向路由協議在業務承載網絡內計算并選擇到達終端用戶網絡的路徑，并負責將用戶網絡前綴信息通告給網絡中其他節點。通過將終端用戶網絡和業務承載網絡分離，用戶網絡前綴等網絡可達性信息通過網絡層可達信息洪泛通告報文、網絡層可達信息特定請求報文和網絡層可達信息特定應答報文按照協議流程進行通告；不同類型信息選擇適合自身的通告更新流程。

3.2.2 協議主要流程

3.2.2.1 協議報文與前綴通告過程

節點勢能導向多下一跳由協議設計了3類9種協議報文，其中鏈路狀態探測類報文實現鄰居節點發現和鏈路質量動態檢測，勢能層級圖建立類報文實現網絡尋路勢能的分布式計算，可達性信息通告類報文完成承載網絡勢能層級圖與用戶網絡路由前綴的映射。

終端用戶網絡前綴的維護和通告功能由業務承載網絡的邊界節點完成。當業務承載網絡中的某個節點（包括出口節點或中間節點）不知道某個用戶網絡前綴綁定的出口節點時，該節點洪泛發送報文進行查詢，直到得到對應前綴的出口節點信息。

3.2.2.2 節點勢能的計算

（1）節點勢能的分布式計算

協議通過勢能層級圖建立類報文完成節點勢能的分布式計算，首先每個出口節點按照廣度優先算法將自己的勢能層值發送給鄰居節點，每個未計算出勢能值的鄰居節點按照第3.1節的勢能計算方法得到自身勢能后，再從本節點發起一個類似的過程，通過廣度優先遍歷過程完成相對給定出口節點的勢能值的全網計算，通過這一過程，將可發現從每個節點到達出口節點的多個可行下一跳。勢能計算過程在網絡中沒有終止條件，通過特定出口節點勢能值的不同計算版本，確定當前節點勢能值的時效性。

（2）節點勢能的動態更新當發生以下兩種情形時，需要進行節點勢能值的更新。

·某個節點發現自己相對于某個出口節點無勢能更低的鄰居節點（某些鏈路或者節點發生故障時會發生），需要查詢自己鄰居節點的勢能值，觸發勢能躍遷過程，需要提升本節點的勢能值或認定某個出口節點不可達，確保數據轉發過程適應網絡動態變化。

·某個節點新添加到網絡中時，主動向鄰居節點發起勢能查詢過程，并根據查詢結果按照第3.1節方法計算勢能。

3.2.2.3 基于信息真實性檢測的可信勢能計算

網絡數據傳送路徑上不可信節點的存在會導致信息泄漏，必須對之進行有效甄別和避繞。節點勢能導向多下一跳路由協議，在傳統路由報文認證、傳輸加密等保證信息源真實可信、傳輸過程完整性保證的基礎上，引入的路由信息真實性檢測方法。該方法借鑒現實生活中常用的評斷謊言和個人信譽的方法，即大多數人都說實話，只有極個別人說假話，而少數人所說的假話的內容一定和其他多數人說的不同，依此鑒別謊言；而一個人說謊的次數和頻率決定了其信譽度。

利用該方法，將節點通告的路由度量信息比作人說的話，通過鑒別比對不同節點的路由度量信息評判其可信度；綜合考慮節點在一定時間空間內通告路由度量信息真偽的頻度、節點的網絡拓撲位置信息等，按照第3.1節可信勢能計算式，計算節點的“可信勢能”；在數據傳送時依據節點可信勢能進行避繞，保障數據傳送的安全可控。

3.3 逐跳流量分派的路由策略實現機制

依據勢能導向路由協議計算出的多個路由下一跳信息，使得節點可采用靈活多變的路由策略來保證網絡安全性和高生存性。每個節點可并發使用多個低勢能下一跳節點進行數據轉發，提高了網絡利用率和運載能力；在網絡出現局部擁塞、故障或安全隱患高時，憑借尋路勢能的感知和自適應機制，可實現傳送路徑的迅速調整，保證數據傳送的持續暢通。本文提出了一種區分流量的動態負載均衡（traffic-distinguished dynamic load balancing，TDLB）算法，按照勢能計算結果，通過流量分配過程選擇下一跳進行路由轉發，實現用戶路由策略。

TDLB算法的流程如圖3所示。當接收到數據分組時，其五元組信息經散列計算后，得到數據流標識，由散列分配單元確定輸出端口。選擇器給動態調整單元和散列分配單元的輸出結果賦予不同的優先級；為實現流量精確分配，該算法把數據流區分為極大流和普通流，在負載分配不均衡時，通過負載調整單元對過載輸出端口上的極大流進行重映射，實現負載的動態均衡分配；強調均衡時可設定動態調整單元的優先級高于散列分配單元，反之亦然。依據選擇器選擇的結果，報文送往相應的輸出端口。

4 實驗測試

4.1 實驗測試方法

在針對節點勢能導向的多下一跳路由協議仿真測試中，使用拓撲生成軟件BRITE，基于WAXMAN模型生成測試網絡的拓撲，該測試網絡拓撲包含15個網絡節點，共60條鏈路，如圖4所示。分析時，將距離矢量類協議單下一跳RIP、NP-MDVA協議（多路徑協議）和本文提出的NP-MNRP進行對比。

圖3 區分流量的動態負載均衡算法結構

采用UDP（user datagram protocol，用戶數據報協議）進行數據分組傳輸試驗，檢測仿真拓撲中各節點和鏈路中傳輸的UDP數據分組數作為分析MNRP性能的依據。每個UDP數據分組的大小設定為1 000 byte，在仿真拓撲中傳輸的UDP數據分組總量為20 MB，數據分組發送的時間間隔為1 ms。在仿真拓撲中設定了3個基于UDP進行數據傳輸的節點對：節點2→節點3、節點4→節點11、節點9→節點10。

4.2 多下一跳資源發現與利用能力

分析表1中的仿真結果：采用MDVA協議和采用單下一跳RIP的仿真實驗中數據分組完成接收的時間基本一致，而采用NP-MNRP的數據分組完成接收時間提前了約30%。

統計分析傳輸實驗中網絡的負載均衡度，如圖5所示，采用NP-MNRP和MDVA協議進行數據傳輸時的負載均衡度優于采用單下一跳RIP傳輸，其均衡度相差多個數量級；而采用NP-MNRP進行數據傳輸時的負載均衡度相比采用MDVA協議提高了20%。

4.3 節點故障、不可信時快速避繞的性能

在圖6中對比分析了鏈路4～19和8～19發生故障時，分別采用MDVA協議和NP-MNRP時，網絡反應時間的差異。其中，反應時間定義為網絡檢測到故障的時間與路由表重新計算并穩定的時間的差值，MDVA協議和NP-MNRP都是可實現局部自愈的路由算法，但NP-MNRP的平均反應時間比MDVA協議減少了20%。

表1 傳輸完成時間

5 結束語

本文受自然界水順勢而流特性啟發，將勢能引入路由機制中，通過路由機制創新增強網絡的安全可控能力。在網絡路由機制中定義了節點的“尋路勢能和可信勢能”，以尋路和可信勢能為核心設計了節點勢能導向路由協議，并基于距離矢量路由算法實現，按照將網絡劃分為用戶網絡和承載網絡的視圖，設計協議報文和處理流程，完成了基于勢能的多下一跳路由的分布式計算。

本協議將網絡尋路與安全一體化設計，實驗測試表明了該協議在均衡利用網絡資源、快速避繞故障節點或安全隱患節點方面的有效性；協議從路由機制角度提高了網絡的安全可控性方面，具有重要的應用價值。

1 Iyer S,Bhattacharyya S,Taft N,et al.An approach toalleviate link overload as observed on an IP backbone.Proceedings of INFOCOM’03,San Franciso,CA,USA,2003:406～416

2 Zhong Z,Nelakuditi S,Yu Y,et al.Failure inferencing based fast rerouting for handling transient link and node failures.Proceedings of IEEE Global Internet,Miami,FL,USA,2005

3 Menth M,Martin R.Network Resilience through Multi-Topology Routing.Technical Report No.353,University of Wuerzburg,Institute of Computer Science,May 2004

4 Kvalbein A,Cicic T,Gjessing S.Post-failure routing performance with multiple routing configurations.Proceedings of IEEE 26th Annual Conference on Computer Communications（INFOCOM 2007）,Anchorage,Alaska,USA,2007

5 Kvalbein A,Hansen A F,Cicic T,et al.Fast recovery from link failures using resilient routing layers.Proceedings of 10th IEEE Symposium on Computers and Communications(ISCC),Cartagena,Spain,June 2005

6 Kvalbein A,Hansen A F,Cicic T,et al.Fast IP network recovery using multiple routing configurations.Proceedings of INFOCOM 2006,Spain,April 2006

7 Vutukury S,Garcia-Luna-Aceves J J.MDVA:a distance-vector multipath routing protocol.Proceedings of the INFOCOM,Anchorage,AK,USA,2001

8 Huo H,Shen W.Virtual hypercube routing in wireless sensor networks for health care systems.Proceedings of ICFIN,Beijing,China,2009

9 Wu J,Wang Y S.Social feature-based multi-path routing in delay tolerant networks.Proceedings of INFOCOM 2012,Orlando,FL,USA,2012

10 Mittal V,Vigna G.Sensor-based intrusion detection for intra-domain distance-vector routing.Proceedings of CCS’02,Washington,D C,USA,Nov 2002

11 Wan T,Kranakis E,Oorschot P C.S-RIP:a secure distance vector routing protocol.Proceedings of ACNS,Yellow Mountain,China,2004:103～119

12 Babakhouya A,Challal Y,Bouabdallah M,et al.SDV:a new approach to secure distance vector routing protocols.Proceedings of IEEE SecureCom,Baltimore,Maryland,USA,2006