基于路徑標(biāo)識的多路徑域間路由的開發(fā)與實(shí)現(xiàn)

摘要：針對現(xiàn)有網(wǎng)絡(luò)架構(gòu)中路由擴(kuò)展性方面的問題日益嚴(yán)重，目前提出一種基于路徑標(biāo)識的多路徑域間路由方案，可提高域間路由可擴(kuò)展性和可靠性，但該研究只停留在理論階段。現(xiàn)對基于路徑標(biāo)識的多路徑路由協(xié)議進(jìn)行了開發(fā)與實(shí)現(xiàn)，針對域間路由協(xié)議BGP的控制層和基于Linu x內(nèi)核的轉(zhuǎn)發(fā)層進(jìn)行了具體模塊的結(jié)構(gòu)分析和開發(fā)，并進(jìn)行了功能性測試。結(jié)果顯示，開發(fā)系統(tǒng)可以實(shí)現(xiàn)路徑標(biāo)識路由和多路徑路由的功能。
關(guān)鍵詞：多路徑；路徑標(biāo)識；BGP；內(nèi)核協(xié)議棧

0 引言
    近些年來，互聯(lián)網(wǎng)得到迅猛的發(fā)展，中國網(wǎng)民規(guī)模已經(jīng)突破4．2億，然而，作為其基礎(chǔ)支持的路由系統(tǒng)卻面臨著極大的挑戰(zhàn)。路由條目急劇增加，嚴(yán)重地消耗了路由器的計算資源，同時網(wǎng)絡(luò)阻塞、擁擠、攻擊等也會引起網(wǎng)絡(luò)的失效或不穩(wěn)定，它們都在很大程度上影響互聯(lián)網(wǎng)的性能。
    一體化網(wǎng)絡(luò)網(wǎng)的提出，可以有效地解決上述問題。一體化網(wǎng)絡(luò)是一種新的基于身份位置分離思想的網(wǎng)絡(luò)體系架。一體化網(wǎng)絡(luò)體系模型與理論提出接入標(biāo)識、交換路由標(biāo)識及其映射理論，建立廣義交換路由的概念與機(jī)制，在支持安全和移動的基礎(chǔ)上實(shí)現(xiàn)網(wǎng)絡(luò)一體化。
    延續(xù)一體化網(wǎng)絡(luò)的設(shè)計思想，本文實(shí)現(xiàn)了一種基于路徑標(biāo)識的多路徑域間路由方案。

1 研究背景
    針對核心網(wǎng)域問路由，傳統(tǒng)網(wǎng)絡(luò)主要存在可擴(kuò)展性和可靠性兩方面的問題。路由可擴(kuò)展性主要關(guān)注于轉(zhuǎn)發(fā)表(FIB)的大小和路由更新的頻率。網(wǎng)絡(luò)用戶的劇增、流量工程、策略路由等技術(shù)的應(yīng)用，導(dǎo)致路由前綴不可聚合，使得路由條目呈非線性增長，是限制路由可擴(kuò)展性的主要原因；路由可靠性主要關(guān)注于網(wǎng)絡(luò)拓?fù)涓淖儠r，路由協(xié)議能否快速收斂，提供持續(xù)通信的能力?，F(xiàn)有域間路由協(xié)議BGP只提供一條最佳路由，在路徑失效時，需要等待下次收斂才能繼續(xù)通信，而且域間路由更新的頻率十分高，使得收斂時間長達(dá)幾分鐘至十幾分鐘，是降低路由可靠性的幾點(diǎn)原因。
    針對上述兩個問題，在一體化網(wǎng)絡(luò)中采用了域內(nèi)與域問路由相分離，核心網(wǎng)和接入網(wǎng)路由相分離的多路徑域間路由方案。核心網(wǎng)域內(nèi)采用本地標(biāo)識進(jìn)行路由，域間采用自治域號(AS)進(jìn)行路由，保證路由條目的穩(wěn)定和緩慢增長，提高了路由可擴(kuò)展性。同時域問路由引入路徑標(biāo)識(PID)標(biāo)識多條轉(zhuǎn)發(fā)路徑，在原先的路徑失效時可以快速地切換到其他路徑，保證了路由的可靠性。

2 基于路徑標(biāo)識的多路徑域間路由方案的設(shè)計
    多路徑路域間路由方案主要分為控制層和轉(zhuǎn)發(fā)層兩部分，其中控制層基于目前經(jīng)典的域間路由協(xié)議(BGP)，主要實(shí)現(xiàn)路由的發(fā)現(xiàn)、通告和更新。轉(zhuǎn)發(fā)層基于Linux內(nèi)核協(xié)議棧，主要實(shí)現(xiàn)通告路由的數(shù)據(jù)包封裝解封和轉(zhuǎn)發(fā)以及鏈路失效時的快速收斂。
2．1 控制層的設(shè)計
    邊界網(wǎng)關(guān)路由協(xié)議(BGP)是目前主流的域間路由協(xié)議，它是一種路徑向量協(xié)議，在AS之間傳遞網(wǎng)絡(luò)可達(dá)性，并且可以通過檢查AS_PATH屬性來避免環(huán)路。多路徑路由方案在域間采用AS號路由，為了標(biāo)識多條路徑引入了路徑標(biāo)識(PID)和下一跳路徑標(biāo)識(NEXT_PID)，從而可以在AS之間通告多條路徑。其中PID為從源AS到目的AS之間順次經(jīng)過的所有AS號的哈希值，而N]EXT_PID為此路徑下一跳AS到目的AS之間所有AS號的哈希值。
    基于圖1的拓?fù)鋱D，分析AS 100和AS 200之間傳遞的UPDATE包的NRLI信息，其基本通信流程為：

    (1)首先AS100和AS200分別計算本地的AS號生成本地路由信息，并且在建立鄰居關(guān)系以后直接發(fā)送給對等體路由器。如AS100就將<100，HASH(100)，HASH(100)>發(fā)送給AS 200。
    (2)AS 100和AS 200在收到AS 300通告的路由后，會在鄰居關(guān)系建立后，將收到AS 300的路由的PID替換為NEXT_PID，將本地AS號加入路徑屬性中，重新計算PID，然后傳遞給對等體路由器。如AS 100將<300，HASH(100，300)，HASH(300)>發(fā)送給AS200。
    (3)在下次通告時，AS100和AS200獲得了到達(dá)對端路由器的信息，及時地通告給對等體路由器，如AS100將<200，HASH(100，300，200)>發(fā)送給AS200，這時AS200就知道了兩條可以到達(dá)AS200的路徑，實(shí)現(xiàn)了簡單的多路徑。
2．2 轉(zhuǎn)發(fā)層的設(shè)計
    目前的路由器基本都運(yùn)行在Linux系統(tǒng)中。因為Linux內(nèi)核提供了完善的網(wǎng)絡(luò)功能，本方案也是基于Linux內(nèi)核協(xié)議棧。Linux內(nèi)核協(xié)議棧是指網(wǎng)絡(luò)中各層協(xié)議的總和，從上到下依次為應(yīng)用層、傳輸層、網(wǎng)絡(luò)層和網(wǎng)絡(luò)接口層。其中網(wǎng)絡(luò)層負(fù)責(zé)處理網(wǎng)絡(luò)中的數(shù)據(jù)包，包括數(shù)據(jù)包路徑的查找、轉(zhuǎn)發(fā)、接收等工作。多路徑域問路由方案的數(shù)據(jù)包頭主要由傳統(tǒng)數(shù)據(jù)包頭和PID、AS號和Local Identifier組成。其中PID和AS號字段用于域間路由使用，Local Iclentifier用于域內(nèi)路由使用。
    多路徑域間路由數(shù)據(jù)包轉(zhuǎn)發(fā)的示意圖如圖2所示。

    收到數(shù)據(jù)包需要按如下步驟進(jìn)行轉(zhuǎn)發(fā)：
    (1)檢查PID字段是否為空，如果為空，則匹配AS號，根據(jù)匹配項填充PID字段，根據(jù)查詢到的PID進(jìn)行平面查找內(nèi)核路由表，并將數(shù)據(jù)包轉(zhuǎn)發(fā)到相應(yīng)的端口上。
    (2)如果PID字段不為空，則用平面查找方式匹配PID，如果有匹配項，路由器根據(jù)匹配項轉(zhuǎn)發(fā)到對應(yīng)端口；如果沒有匹配的PID，再根據(jù)標(biāo)志位，置位的路由器可以按匹配目的AS號的方法對數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)，沒有置位的則將數(shù)據(jù)包丟棄。
    (3)當(dāng)數(shù)據(jù)包跨出本AS域轉(zhuǎn)發(fā)到下一個AS域時，PID字段需替換成路由條目中NEXT_PID；當(dāng)PID為本地AS的哈希值時，表明數(shù)據(jù)包此時已經(jīng)到達(dá)目的AS，此時需交由域內(nèi)路由協(xié)議用Destination Local Identier進(jìn)行轉(zhuǎn)發(fā)。

3 基于路徑標(biāo)識的多路徑域間路由方案的實(shí)現(xiàn)
    多路徑域間路由方案實(shí)現(xiàn)模塊圖如圖3所示，其中控制層模塊主要實(shí)現(xiàn)UPDATE消息的產(chǎn)生、交互和處理，并且提供了一些配置和顯示命令。在多路徑域間路由方案中只需要修改NLRI模塊、UPDATE消息處理模塊、平面路由表模塊和配置、顯示命令模塊，其他部分可以沿用BGP的設(shè)計。RTM模塊主要實(shí)現(xiàn)控制層和轉(zhuǎn)發(fā)層之間的交互，原始數(shù)據(jù)包的提交和路由信息的下發(fā)。轉(zhuǎn)發(fā)層模塊實(shí)現(xiàn)平面轉(zhuǎn)發(fā)表的構(gòu)建、數(shù)據(jù)包的封裝和解封，以及具體的數(shù)據(jù)包轉(zhuǎn)發(fā)流程。

3．1 NRLI模塊
   該模塊主要實(shí)現(xiàn)在AS之間傳遞路由可達(dá)消息。在BGP中被設(shè)計成(長度，前綴)二元組，為了兼容多路徑域間路由方案，需要修改成<長度，前綴，PID，AS>四元組，使之既可以滿足多路徑域間路由的需要，也可以兼容現(xiàn)有的路由方式。
3．2 UPDATE消息處理模塊
    該模塊主要實(shí)現(xiàn)UPDATE消息的發(fā)送和接收。在BGP當(dāng)中用來在對等體之問傳遞可用路由前綴、撤銷路由等，在多路徑域間方案中需要修改數(shù)據(jù)包發(fā)送函數(shù)和接收函數(shù)，使之能夠正常地傳遞新的網(wǎng)絡(luò)可達(dá)性信息，同時需要修改包安全性檢查等函數(shù)，使之能夠不被錯誤地丟棄。
3．3 平面路由表模塊
    該模塊主要實(shí)現(xiàn)在控制層維護(hù)核心路由表，并向轉(zhuǎn)發(fā)層下發(fā)最佳轉(zhuǎn)發(fā)信息。BGP的路由表是基于最長前綴匹配的方式查找的，用二又樹具體組織。在多路徑域間路由方案中需要將其平面化，利用PID和AS號來檢索域間路由，利用HASH算法將路由節(jié)點(diǎn)信息存儲在一個雙向鏈表上面，實(shí)行了精確查找。
3．4 配置、顯示和調(diào)試命令模塊
    該模塊主要實(shí)現(xiàn)多路徑域間路由協(xié)議的配置，并且提供了一些顯示核心路由表、對等體狀態(tài)等的顯示命令，還有一些路由器故障時的調(diào)試命令。相對于BGP，在多路徑域間路由方案中添加了以下的命令：
    (1)路由顯示命令
    通過該命令可以遍歷多路徑域間路由協(xié)議的核心路由表，顯示具體路由信息，即到目的AS的具體路由信息，包括PID、NEXT_PID和具體路徑顯示。
    (2)路徑選擇命令
     因為在多路徑路由方案中，在控制層可以發(fā)現(xiàn)多條路徑，通過該命令可以選擇控制層向轉(zhuǎn)發(fā)層通告的最佳路徑，在當(dāng)前鏈路失效時選擇備份路徑下達(dá)到轉(zhuǎn)發(fā)層，實(shí)現(xiàn)鏈路的快速收斂，最終完成了轉(zhuǎn)發(fā)路徑的可控。
3．5 RTM模塊
    該模塊主要實(shí)現(xiàn)轉(zhuǎn)發(fā)層模塊和控制層模塊之間的消息交互。多路徑域間路由協(xié)議在控制層擁有自己的核心路由表，但最終對轉(zhuǎn)發(fā)其作用的是轉(zhuǎn)發(fā)層的內(nèi)核路由表，但是控制層不能對內(nèi)核路由表直接起作用，該模塊實(shí)現(xiàn)了兩者之間的信息交互。它們之間的通信是通過套接字NET LINK起作用的，在公共消息格式中添加標(biāo)識路由所需的PID、AS號和NEXT_PID等信息，滿足標(biāo)識路由在轉(zhuǎn)發(fā)層的需要。
3．6 平面轉(zhuǎn)發(fā)表模塊
    該模塊主要實(shí)現(xiàn)多路徑域問路由在轉(zhuǎn)發(fā)層核心路由表的維護(hù)，當(dāng)需要出路網(wǎng)絡(luò)流量的發(fā)送和接收時查詢該路由表。
    Linux內(nèi)核的轉(zhuǎn)發(fā)表是基于網(wǎng)絡(luò)掩碼的HASH表組織的，根據(jù)不同的網(wǎng)絡(luò)掩碼長度被組織成不同的HASH表。因為IPv4使用32位地址，所以IPv4中有33個不同的網(wǎng)絡(luò)掩碼長度，可對應(yīng)于一個IP地址。fib_table數(shù)據(jù)結(jié)構(gòu)來描述路由表。fib_table結(jié)構(gòu)包含一個由33個指針組成的向量，每個指針對應(yīng)一個網(wǎng)絡(luò)掩碼并指向一個類型為fn_zone的數(shù)據(jù)結(jié)構(gòu)。Fn_zone結(jié)構(gòu)將路由組織成HASH表，因此通向目的網(wǎng)絡(luò)的路由，如果網(wǎng)絡(luò)掩碼長度相同，就被放在同一個HASH表內(nèi)。每個單獨(dú)的子網(wǎng)對應(yīng)一個fib_node實(shí)例，用變量fn_key(網(wǎng)絡(luò)掩碼)識別，它的值就表明該子網(wǎng)。在查找函數(shù)fn_hash_lookup中，也是通過遍歷路由表搜索關(guān)鍵詞fn_key，獲得最終結(jié)果。
    多路徑路由方案中，轉(zhuǎn)發(fā)時需要檢查PID，并根據(jù)PID進(jìn)行檢索和轉(zhuǎn)發(fā)，因此需要修改轉(zhuǎn)發(fā)表，使之可以根據(jù)關(guān)鍵詞PID進(jìn)行查找。在查找時，只需要根據(jù)PID進(jìn)行精確匹配，而不用計算網(wǎng)絡(luò)掩碼。在修改后的路由節(jié)點(diǎn)fib_bgp_node中，添加了PID的信息，使得修改后的路由表fib _bgp_table可以根據(jù)PID為關(guān)鍵詞索引。路由表結(jié)構(gòu)如圖4所示。

3．7 數(shù)據(jù)包封裝解封模塊
    該模塊主要實(shí)現(xiàn)數(shù)據(jù)包中標(biāo)識的轉(zhuǎn)換，Linux內(nèi)核中采用IP地址進(jìn)行路由，而在多路徑域間路由方案中，在域間有需要才用AS號路由，因此需要在發(fā)送數(shù)據(jù)包時，添加PID、目的AS號和源AS號等信息，但為了兼容現(xiàn)有的網(wǎng)絡(luò)架構(gòu)，方便現(xiàn)有網(wǎng)絡(luò)其他服務(wù)的處理，在數(shù)據(jù)包進(jìn)入網(wǎng)絡(luò)層前，去除PID、目的AS號、源AS號等擴(kuò)展選項。只是在數(shù)據(jù)包離開網(wǎng)絡(luò)層后，才增減以上擴(kuò)展選項。修改后的數(shù)據(jù)包頭如圖5所示。
3．8 數(shù)據(jù)包轉(zhuǎn)發(fā)處理模塊
    該模塊主要實(shí)現(xiàn)基于PID的數(shù)據(jù)包轉(zhuǎn)發(fā)，同時維護(hù)一個PID、AS號和NEXT_PID一一對應(yīng)的查詢表，實(shí)現(xiàn)到目的AS路徑標(biāo)識PID的填充。Lin ux內(nèi)核是基于IP地址前綴路由的，而在多路徑域間路由方案中是基于AS號，在查詢平面轉(zhuǎn)發(fā)表要使用PID，如果數(shù)據(jù)包是終端第一次經(jīng)過路由器時，不存在PID等信息，需要根據(jù)目的AS號添加PID等信息，還有域內(nèi)路由時根據(jù)設(shè)計要使用Local Identiner，只有在數(shù)據(jù)包進(jìn)入Linux內(nèi)核網(wǎng)絡(luò)層前，進(jìn)行了該模塊處理，才能完成標(biāo)識路由的功能。

4 基于路徑標(biāo)識的多路徑域間路由方案的功能驗證
    多路徑域間路由方案的功能驗證，主要包括控制層基于路徑標(biāo)識的多路徑路由發(fā)現(xiàn)和轉(zhuǎn)發(fā)層基于路徑標(biāo)識的數(shù)據(jù)包正常轉(zhuǎn)發(fā)。
4．1 測試平臺及拓?fù)?br />     全部系統(tǒng)采用普通的x86系列的PC；測試環(huán)境的核心網(wǎng)路由器配置至少兩個以上的網(wǎng)卡，無線或有線均可；所有充當(dāng)路由器都應(yīng)該安裝Linux操作系統(tǒng)，內(nèi)核版本為2．6．28；測試的拓?fù)淙鐖D6所示，對各個功能實(shí)體進(jìn)行地址和路由配置，在所有路由器都需要安裝文中提到的修改后的BGP路由軟件和相應(yīng)的內(nèi)核軟件。

4．2 控制層基于路徑標(biāo)識的多路徑路由發(fā)現(xiàn)
    AR1為AS號為100的一臺路由器，AR2，AR3分別為AS號為200，300的路由器，其中AR1的BGP配置如圖7所示。
    其他路由器配置與AR1類似，通過配置使得AR1，AR2，AR3之間建立了EBGP關(guān)系對等體關(guān)系，通過show ip bgp命令查看AR1的路由表，內(nèi)容如圖8所示。

    AR1學(xué)習(xí)到了到達(dá)3個AS域的路由信息，學(xué)習(xí)到了到本地AS域100的路由，其中PID和NEXT_PID一致，并且默認(rèn)權(quán)重為32 768；到達(dá)AS域300的路徑則有兩條，分別為“300i”和“200 300i”，表明到達(dá)AS域300的路徑可以是直接到達(dá)AS域300，PID為f78aac78，NEXT_PID為809d3a9 0，也可以是通過AS域200到達(dá)AS域300，PID為7a5flfe8，NEXT_PID為33f960c4，可見PID和NEXT_PID均不一致，可以通過PID和NEXT_PID區(qū)分不同的路徑，通過測試，可以看出本方案在控制層可以正確地發(fā)現(xiàn)基于路徑標(biāo)識的多條路徑。
4．3 轉(zhuǎn)發(fā)層基于路徑標(biāo)識的數(shù)據(jù)包正常轉(zhuǎn)發(fā)
    基于路徑標(biāo)識的數(shù)據(jù)包轉(zhuǎn)發(fā)是多路徑域間路由的重要功能，首先用AR1向AR2發(fā)送ping包，也就是AS域100向AS域200發(fā)送ping包，在AS 200的內(nèi)核編寫打印語句，打印出數(shù)據(jù)包添加的PID，NEXT_PID和AS號，結(jié)果如圖9所示。

    可見，在ping包已經(jīng)正確地添加了域間路由所需的PID，NEXT_PID和AS號等信息。利用wireshark抓包工具進(jìn)行測試，可以成功地獲取icmp包，證明兩個AS域之間可以實(shí)現(xiàn)基于路徑標(biāo)識的數(shù)據(jù)包轉(zhuǎn)發(fā)。

5 結(jié)語
    在實(shí)際搭建的拓?fù)渲校瑢?shí)現(xiàn)了基于路徑標(biāo)識的多路徑路由方案，并且進(jìn)行了功能驗證。結(jié)果表明，可以正確地發(fā)現(xiàn)多路徑路由，并且可以實(shí)現(xiàn)基于路徑標(biāo)識PID的數(shù)據(jù)包轉(zhuǎn)發(fā)。本文實(shí)現(xiàn)了基于路徑標(biāo)識的多路徑域問路由方案，快速實(shí)現(xiàn)鏈路失效時的重新收斂，將成為下一步研究的重點(diǎn)。