基于路徑標識的多路徑域間路由的開發與實現

摘 要：針對現有網絡架構中路由擴展性方面的問題日益嚴重，目前提出一種基于路徑標識的多路徑域間路由方案，可提高域間路由可擴展性和可靠性，但該研究只停留在理論階段?，F對基于路徑標識的多路徑路由協議進行了開發與實現，針對域間路由協議BGP的控制層和基于Linux內核的轉發層進行了具體模塊的結構分析和開發，并進行了功能性測試。結果顯示，開發系統可以實現路徑標識路由和多路徑路由的功能。



關鍵詞：多路徑； 路徑標識； BGP； 內核協議棧

中圖分類號：TN711-34

文獻標識碼：A

文章編號：1004-373X(2012)01-0040-05

Research and implementation of multi-path inter-domain routing based on path identifiers



DUAN Can-ran， SU Wei， CHEN Jia

(National Engineering Laboratory for Next Generation Internet Interconnection Devices， School of Electronic and Information Engineering， 

Beijing Jiaotong University， Beijing 100044， China)



Abstract：

A multi-path inter-domain scheme based on path identifiers is proposed for solving the obvious scalability problem of routing existed in network architechture， which can improve the scalability and the reliability. This scheme is researched and realized， including the control plane for inter-domain routing protocol BGP and the forwarding plane based on the Linux kernel，and the functional test is performed. The results show that the developed system can achieve the path identifiers routing and the multi-path routing.



Keywords： multiple path； path identifiers； BGP； kernel protocol stack



收稿日期：2011-09-09

基金項目：國家973項目(2007CB307101)；北京交通大學基本科研業務經費 (W11JB00150)；北京交通大學人才基金(W10RC00050)

0 引 言

近些年來，互聯網得到迅猛的發展，中國網民規模已經突破4.2億[1]，然而，作為其基礎支持的路由系統卻面臨著極大的挑戰。路由條目急劇增加，嚴重地消耗了路由器的計算資源，同時網絡阻塞、擁擠、攻擊等也會引起網絡的失效或不穩定， 它們都在很大程度上影響互聯網的性能。

一體化網絡網[2]的提出，可以有效地解決上述問題。一體化網絡是一種新的基于身份位置分離思想的網絡體系架。一體化網絡體系模型與理論提出接入標識、交換路由標識及其映射理論，建立廣義交換路由的概念與機制，在支持安全和移動的基礎上實現網絡一體化。

延續一體化網絡的設計思想，本文實現了一種基于路徑標識的多路徑域間路由方案。

1 研究背景

針對核心網域間路由，傳統網絡主要存在可擴展性和可靠性兩方面的問題。路由可擴展性[3]主要關注于轉發表(FIB)的大小和路由更新的頻率。網絡用戶的劇增、流量工程、策略路由等技術的應用，導致路由前綴不可聚合，使得路由條目呈非線性增長，是限制路由可擴展性的主要原因;路由可靠性[4]主要關注于網絡拓撲改變時，路由協議能否快速收斂，提供持續通信的能力。現有域間路由協議BGP只提供一條最佳路由，在路徑失效時，需要等待下次收斂才能繼續通信，而且域間路由更新的頻率十分高，使得收斂時間長達幾分鐘至十幾分鐘，是降低路由可靠性的幾點原因。

針對上述兩個問題，在一體化網絡中采用了域內與域間路由相分離，核心網和接入網路由相分離的多路徑域間路由方案。核心網域內采用本地標識進行路由，域間采用自治域號(AS)進行路由，保證路由條目的穩定和緩慢增長，提高了路由可擴展性。同時域間路由引入路徑標識(PID)標識多條轉發路徑，在原先的路徑失效時可以快速地切換到其他路徑，保證了路由的可靠性。

2 基于路徑標識的多路徑域間路由方案的設計

多路徑路域間路由方案主要分為控制層和轉發層兩部分，其中控制層基于目前經典的域間路由協議(BGP)，主要實現路由的發現、通告和更新。轉發層基于Linux內核協議棧，主要實現通告路由的數據包封裝解封和轉發以及鏈路失效時的快速收斂。

2.1 控制層的設計

邊界網關路由協議(BGP)[5]是目前主流的域間路由協議，它是一種路徑向量協議，在AS之間傳遞網絡可達性，并且可以通過檢查AS_PATH屬性來避免環路。多路徑路由方案在域間采用AS號路由，為了標識多條路徑引入了路徑標識(PID)和下一跳路徑標識(NEXT_PID)，從而可以在AS之間通告多條路徑。其中PID為從源AS到目的AS之間順次經過的所有AS號的哈希值，而NEXT_PID為此路徑下一跳AS到目的AS之間所有AS號的哈希值。 

基于圖1的拓撲圖，分析AS 100和AS 200之間傳遞的UPDATE包的NRLI信息，其基本通信流程為:

圖1 控制層通信流程圖

(1) 首先AS 100和AS 200分別計算本地的AS號生成本地路由信息，并且在建立鄰居關系以后直接發送給對等體路由器。如AS 100就將〈100，HASH(100)，HASH(100)〉發送給AS 200。

(2) AS 100和AS 200在收到AS 300通告的路由后，會在鄰居關系建立后，將收到AS 300的路由的PID替換為NEXT_PID，將本地AS號加入路徑屬性中，重新計算PID，然后傳遞給對等體路由器。如AS 100將〈300，HASH(100，300)，HASH(300)〉發送給AS 200。

(3) 在下次通告時，AS 100和AS 200獲得了到達對端路由器的信息，及時地通告給對等體路由器，如AS 100將〈200，HASH(100，300，200)〉發送給AS 200，這時AS 200就知道了兩條可以到達AS 200的路徑，實現了簡單的多路徑。

2.2 轉發層的設計

目前的路由器基本都運行在Linux系統中。因為Linux內核[6]提供了完善的網絡功能，本方案也是基于Linux內核協議棧。Linux內核協議棧是指網絡中各層協議的總和，從上到下依次為應用層、傳輸層、網絡層和網絡接口層。其中網絡層負責處理網絡中的數據包，包括數據包路徑的查找、轉發、接收等工作。多路徑域間路由方案的數據包頭主要由傳統數據包頭和PID、AS號和Local Identifier組成。其中PID和AS號字段用于域間路由使用，Local Identifier用于域內路由使用。

多路徑域間路由數據包轉發的示意圖如圖2所示。

圖2 轉發層數據包轉發流程圖

收到數據包需要按如下步驟進行轉發：

(1) 檢查PID字段是否為空，如果為空，則匹配AS號，根據匹配項填充PID字段，根據查詢到的PID進行平面查找內核路由表，并將數據包轉發到相應的端口上。

(2) 如果PID字段不為空，則用平面查找方式匹配PID，如果有匹配項，路由器根據匹配項轉發到對應端口；如果沒有匹配的PID，再根據標志位，置位的路由器可以按匹配目的AS號的方法對數據包進行轉發，沒有置位的則將數據包丟棄。

(3) 當數據包跨出本AS域轉發到下一個AS域時，PID字段需替換成路由條目中NEXT_PID；當PID為本地AS的哈希值時，表明數據包此時已經到達目的AS，此時需交由域內路由協議用Destination Local Identier進行轉發。

3 基于路徑標識的多路徑域間路由方案的實現

多路徑域間路由方案實現模塊圖如圖3所示，其中控制層模塊主要實現UPDATE消息的產生、交互和處理，并且提供了一些配置和顯示命令。在多路徑域間路由方案中只需要修改NLRI模塊、UPDATE消息處理模塊、平面路由表模塊和配置、顯示命令模塊，其他部分可以沿用BGP的設計。RTM模塊主要實現控制層和轉發層之間的交互，原始數據包的提交和路由信息的下發。轉發層模塊實現平面轉發表的構建、數據包的封裝和解封，以及具體的數據包轉發流程。

圖3 多路徑域間路由方案實現模塊圖

3.1 NRLI模塊

該模塊主要實現在AS之間傳遞路由可達消息。在BGP中被設計成〈長度，前綴〉二元組，為了兼容多路徑域間路由方案，需要修改成〈長度，前綴，PID，AS〉四元組，使之既可以滿足多路徑域間路由的需要，也可以兼容現有的路由方式。

3.2 UPDATE消息處理模塊

該模塊主要實現UPDATE消息的發送和接收。在BGP當中用來在對等體之間傳遞可用路由前綴、撤銷路由等，在多路徑域間方案中需要修改數據包發送函數和接收函數，使之能夠正常地傳遞新的網絡可達性信息，同時需要修改包安全性檢查等函數，使之能夠不被錯誤地丟棄。

3.3 平面路由表模塊

該模塊主要實現在控制層維護核心路由表，并向轉發層下發最佳轉發信息。BGP的路由表是基于最長前綴匹配的方式查找的，用二叉樹具體組織。在多路徑域間路由方案中需要將其平面化，利用PID和AS號來檢索域間路由，利用HASH算法將路由節點信息存儲在一個雙向鏈表上面，實行了精確查找。

3.4 配置、顯示和調試命令模塊

該模塊主要實現多路徑域間路由協議的配置，并且提供了一些顯示核心路由表、對等體狀態等的顯示命令，還有一些路由器故障時的調試命令。相對于BGP，在多路徑域間路由方案中添加了以下的命令：

(1) 路由顯示命令

通過該命令可以遍歷多路徑域間路由協議的核心路由表，顯示具體路由信息，即到目的AS的具體路由信息，包括PID、NEXT_PID和具體路徑顯示。

(2) 路徑選擇命令

因為在多路徑路由方案中，在控制層可以發現多條路徑，通過該命令可以選擇控制層向轉發層通告的最佳路徑，在當前鏈路失效時選擇備份路徑下達到轉發層，實現鏈路的快速收斂，最終完成了轉發路徑的可控。

3.5 RTM模塊

該模塊主要實現轉發層模塊和控制層模塊之間的消息交互。多路徑域間路由協議在控制層擁有自己的核心路由表，但最終對轉發其作用的是轉發層的內核路由表，但是控制層不能對內核路由表直接起作用，該模塊實現了兩者之間的信息交互。它們之間的通信是通過套接字NETLINK起作用的，在公共消息格式中添加標識路由所需的PID、AS號和NEXT_PID等信息，滿足標識路由在轉發層的需要。 

3.6 平面轉發表模塊

該模塊主要實現多路徑域間路由在轉發層核心路由表的維護，當需要出路網絡流量的發送和接收時查詢該路由表。

Linux內核的轉發表是基于網絡掩碼的HASH表組織的，根據不同的網絡掩碼長度被組織成不同的HASH表。因為IPv4使用32位地址，所以IPv4中有33個不同的網絡掩碼長度，可對應于一個IP地址。fib_table數據結構來描述路由表。fib_table結構包含一個由33個指針組成的向量，每個指針對應一個網絡掩碼并指向一個類型為fn_zone的數據結構。Fn_zone結構將路由組織成HASH表，因此通向目的網絡的路由，如果網絡掩碼長度相同，就被放在同一個HASH表內。每個單獨的子網對應一個fib_node實例，用變量fn_key(網絡掩碼)識別，它的值就表明該子網。在查找函數fn_hash_lookup中，也是通過遍歷路由表搜索關鍵詞fn_key，獲得最終結果。

多路徑路由方案中，轉發時需要檢查PID，并根據PID進行檢索和轉發，因此需要修改轉發表，使之可以根據關鍵詞PID進行查找。在查找時，只需要根據PID進行精確匹配，而不用計算網絡掩碼。在修改后的路由節點fib_bgp_node中，添加了PID的信息，使得修改后的路由表fib_bgp_table可以根據PID為關鍵詞索引。路由表結構如圖4所示。

3.7 數據包封裝解封模塊

該模塊主要實現數據包中標識的轉換，Linux內核中采用IP地址進行路由，而在多路徑域間路由方案中，在域間有需要才用AS號路由，因此需要在發送數據包時，添加PID、目的AS號和源AS號等信息，但為了兼容現有的網絡架構，方便現有網絡其他服務的處理，在數據包進入網絡層前，去除PID、目的AS號、源AS號等擴展選項。只是在數據包離開網絡層后，才增減以上擴展選項。修改后的數據包頭如圖5所示。

圖4 多路徑域間路由方案轉發表示意圖

圖5 多路徑域間路由方案數據包頭圖

3.8 數據包轉發處理模塊

該模塊主要實現基于PID的數據包轉發，同時維護一個PID、AS號和NEXT_PID一一對應的查詢表，實現到目的AS路徑標識PID的填充。Linux內核是基于IP地址前綴路由的，而在多路徑域間路由方案中是基于AS號，在查詢平面轉發表要使用PID，如果數據包是終端第一次經過路由器時，不存在PID等信息，需要根據目的AS號添加PID等信息，還有域內路由時根據設計要使用Local Identifier，只有在數據包進入Linux內核網絡層前，進行了該模塊處理，才能完成標識路由的功能。

4 基于路徑標識的多路徑域間路由方案的功能驗證

多路徑域間路由方案的功能驗證，主要包括控制層基于路徑標識的多路徑路由發現和轉發層基于路徑標識的數據包正常轉發。

4.1 測試平臺及拓撲

全部系統采用普通的x86系列的PC；測試環境的核心網路由器配置至少兩個以上的網卡，無線或有線均可；所有充當路由器都應該安裝Linux操作系統，內核版本為2.6.28；測試的拓撲如圖6所示，對各個功能實體進行地址和路由配置，在所有路由器都需要安裝文中提到的修改后的BGP路由軟件和相應的內核軟件。

4.2 控制層基于路徑標識的多路徑路由發現

AR1為AS號為100的一臺路由器，AR2，AR3分別為AS號為200，300的路由器，其中AR1的BGP配置如圖7所示。

圖6 測試拓撲圖

圖7 AR1路由器BGP配置圖

其他路由器配置與AR1類似，通過配置使得AR1，AR2，AR3之間建立了EBGP關系對等體關系，通過show ip bgp命令查看AR1的路由表，內容如圖8所示。

圖8 AR1路由器路由表示意圖

AR1學習到了到達3個AS域的路由信息，學習到了到本地AS域100的路由，其中PID和NEXT_PID一致，并且默認權重為32 768；到達AS域300的路徑則有兩條，分別為“300 i”和“200 300 i”，表明到達AS域300的路徑可以是直接到達AS域300，PID為f78aac78，NEXT_PID為809d3a90，也可以是通過AS域200到達AS域300，PID為7a5f1fe8，NEXT_PID為33f960c4，可見PID和NEXT_PID均不一致，可以通過PID和NEXT_PID區分不同的路徑，通過測試，可以看出本方案在控制層可以正確地發現基于路徑標識的多條路徑。

4.3 轉發層基于路徑標識的數據包正常轉發

基于路徑標識的數據包轉發是多路徑域間路由的重要功能，首先用AR1向AR2發送ping包，也就是AS域100向AS域200發送ping包，在AS 200的內核編寫打印語句，打印出數據包添加的PID，NEXT_PID和AS號，結果如圖9所示。



圖9 AR1路由器內核打印結果示意圖

可見，在ping包已經正確地添加了域間路由所需的PID，NEXT_PID和AS號等信息。利用wireshark抓包工具進行測試，可以成功地獲取icmp包，證明兩個AS域之間可以實現基于路徑標識的數據包轉發。

5 結 語

在實際搭建的拓撲中，實現了基于路徑標識的多路徑路由方案，并且進行了功能驗證。結果表明，可以正確地發現多路徑路由，并且可以實現基于路徑標識PID的數據包轉發。本文實現了基于路徑標識的多路徑域間路由方案，快速實現鏈路失效時的重新收斂，將成為下一步研究的重點。

參 考 文 獻

［1］FULLER V. Scaling issues with routing + multihoming［C］.［S.l.］: Plenary session at APRICOT， the AsiaPacifc Regional Internet Conference on Operational Technologies， 2007.



［2］張宏科，蘇偉.新網絡體系基礎研究:一體化網絡與普適服務[J].電子學報，2007，35(4):593-598.



［3］MEYER D， ZHANG L， FALL K. Report from the IAB workshop on routing and addressing. IETF RFC 4984 [EB/OL].［2007-09-21］. http://www.ietf.org/rfc/rfc4984.txt.



［4］CAESAR M， SUBRAMANIAN L， KATZ R H. Root cause analysis of internet routing dynamics. Technical Report UCB/CSD-04-1302 [R]. U.C.Berkeley： Department of Computer Science， 2003.



［5］REKHTER Y， LI T， HARES S. A border gateway protocol 4 (BGP-4). IETF RFC4271［EB/OL］.［2006-01-16］. http://www.ietf.org/rfc/rfc4271.txt.



［6］BENVENUTI Christian.深入理解Linux網絡技術內幕[M].夏安，譯.北京:中國電力出版社，2009.



［7］郭華明.標識路由關鍵技術研究[D].北京:北京交通大學，2010.



［8］王立平，崔智林，馬力.基于OPNET仿真平臺的MANET路由協議性能分析[J].現代電子技術，2011，34(14):71-74.



［9］夏素菁，程明定，范柳青.無線Mesh網中基于信道感知的多徑路由判據[J].現代電子技術，2011，34(4):53-55.



作者簡介： 段璨然 男，1986年出生，山西陽泉人，碩士生。主要研究方向為下一代互聯網。