衛(wèi)星網(wǎng)絡(luò)路由器高速數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)計(jì)

，， ， ，

(北京空間飛行器總體設(shè)計(jì)部，北京 100094)

0 引言

衛(wèi)星網(wǎng)絡(luò)包括衛(wèi)星系統(tǒng)、地面站等多種網(wǎng)絡(luò)節(jié)點(diǎn)，構(gòu)成一個(gè)典型的多層、天地一體的空間信息網(wǎng)絡(luò)，具備全球數(shù)據(jù)接入服務(wù)能力。星間通過(guò)高速激光鏈路通信。衛(wèi)星網(wǎng)絡(luò)的核心之一就是路由器。衛(wèi)星系統(tǒng)搭載激光終端和高速路由器進(jìn)行在軌驗(yàn)證，同時(shí)也為我國(guó)天地一體化網(wǎng)絡(luò)的建設(shè)提供支撐。

在討論了路由器發(fā)展歷程之后，對(duì)高性能路由器典型結(jié)構(gòu)、路由查找關(guān)鍵技術(shù)、內(nèi)部交換關(guān)鍵技術(shù)進(jìn)行了調(diào)研，結(jié)合衛(wèi)星網(wǎng)絡(luò)的路由需求、軟硬件環(huán)境的設(shè)計(jì)約束條件，開展了衛(wèi)星網(wǎng)絡(luò)路由器數(shù)據(jù)轉(zhuǎn)發(fā)的設(shè)計(jì)。所實(shí)現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)設(shè)計(jì)具有路由效率高、交換效率高的特點(diǎn)，并具備一定的可擴(kuò)展性，經(jīng)簡(jiǎn)單擴(kuò)展后，還可滿足后續(xù)更高性能空間路由器的設(shè)計(jì)需求。

1 路由技術(shù)調(diào)研

路由器出現(xiàn)在20世紀(jì)80年代末，用于互聯(lián)不同類型網(wǎng)絡(luò)的通用組網(wǎng)設(shè)備，工作在OSI參考模型的第三層，適應(yīng)于大型組網(wǎng)對(duì)性能、容量和安全性的要求。

高性能路由器結(jié)構(gòu)的一個(gè)典型特點(diǎn)是數(shù)據(jù)路徑和控制路徑的分離。輸入接口接收來(lái)自外部高速網(wǎng)絡(luò)接口的數(shù)據(jù)包，根據(jù)轉(zhuǎn)發(fā)表信息，通過(guò)交換網(wǎng)絡(luò)將數(shù)據(jù)包傳輸?shù)侥康妮敵鼋涌冢l(fā)送到外部網(wǎng)絡(luò)。轉(zhuǎn)發(fā)表由路由引擎下載到各個(gè)接口板上，一般的數(shù)據(jù)包轉(zhuǎn)發(fā)不再通過(guò)路由引擎，實(shí)現(xiàn)了數(shù)據(jù)路徑與控制路徑的獨(dú)立，不同接口的數(shù)據(jù)轉(zhuǎn)發(fā)也是獨(dú)立進(jìn)行的。既提高了系統(tǒng)的轉(zhuǎn)發(fā)性能，又增加了數(shù)據(jù)路徑的可靠性。數(shù)據(jù)路徑處理需要轉(zhuǎn)發(fā)的數(shù)據(jù)包，是整個(gè)路由器的關(guān)鍵路徑，它的實(shí)現(xiàn)好壞直接影響著路由器的整體性能[1-2]。數(shù)據(jù)路徑設(shè)計(jì)中的2個(gè)關(guān)鍵問(wèn)題是路由查找和內(nèi)部交換。高性能路由器典型結(jié)構(gòu)如圖1所示。

圖1 高性能路由器典型結(jié)構(gòu)

1.1 路由查找

路由查找的主要功能：基于IP數(shù)據(jù)包的目的地址，使用最長(zhǎng)前綴匹配規(guī)則，對(duì)IP路由表進(jìn)行查詢，獲知對(duì)應(yīng)的輸出端口。路由查找的主要方法有以下3種[3-4]：

(1)基于軟件的查找方法：軟件實(shí)現(xiàn)一般采用基于Trie的二叉樹結(jié)構(gòu)或基于鍵樹(Key Tree)的算法。在鍵樹中，從搜索鍵中順序抽取相應(yīng)數(shù)位或字母字符決定分支去向。該方法實(shí)現(xiàn)簡(jiǎn)單，適用性好，可以用于任何長(zhǎng)度關(guān)鍵字的查找。但查找效率低，存儲(chǔ)效率較低，Trie樹查找過(guò)程實(shí)際上就是在長(zhǎng)度空間內(nèi)的順序查找操作[5]。

(2)基于大容量RAM的快速路由查找方法：隨著網(wǎng)絡(luò)傳輸速度大規(guī)模提升，基于CPU的純軟件處理滿足不了要求。引出了基于大容量RAM的快速路由查找方法。將路由查找表項(xiàng)存儲(chǔ)到大容量SRAM中。以“多分支Trie樹查找算法”為例，在RAM中存儲(chǔ)兩種查找表結(jié)構(gòu)，分別為Table16和TableNext。Table16表保存路由地址前綴小于等于16的表項(xiàng)；TableNext表保存路由地址前綴大于16的表項(xiàng)。對(duì)于任何一個(gè)IP地址，查找過(guò)程最多只需要訪問(wèn)兩次查表(Table16和TableNext)即可獲得轉(zhuǎn)發(fā)信息，大大加快了路由查找的速度[6]。

(3)基于TCAM路由查找方法：TCAM(Ternary Content Addressable Memory)三元內(nèi)容可尋址存儲(chǔ)器，是近年來(lái)在各種高端設(shè)備上逐漸廣泛使用的一種技術(shù)。TCAM采用并行查找技術(shù)，與查找速度和表項(xiàng)的條目數(shù)量無(wú)關(guān)。采用TCAM可以實(shí)現(xiàn)每秒上億次的查找。TCAM器件在速度和容量上都有很大提高，能夠滿足大規(guī)模高速路由查找的需求?；赥CAM 的查找速度快，但是實(shí)現(xiàn)代價(jià)較高，功耗較大，表項(xiàng)的更新復(fù)雜[7]。

1.2 交換結(jié)構(gòu)

交換結(jié)構(gòu)是高性能路由器的核心，完成輸入端口和輸出端口的連接，是影響路由器速度和容量的關(guān)鍵因素。根據(jù)路由器中使用的交換結(jié)構(gòu)不同，路由器可分為共享總線、共享存儲(chǔ)器、交叉開關(guān)陣列等類型[8-9]，交換結(jié)構(gòu)分類如圖2所示。

圖2 交換結(jié)構(gòu)分類

(1)共享總線結(jié)構(gòu)：數(shù)據(jù)包在路由器中通過(guò)共享總線傳輸。共享總線采用時(shí)分復(fù)用方式，連接在共享介質(zhì)上的某一輸入、輸出端口只在指定的時(shí)間片進(jìn)行數(shù)據(jù)傳輸。這種方式交換速率受限于總線的帶寬。

(2)共享存儲(chǔ)器結(jié)構(gòu)：使用了大量的高速RAM來(lái)存儲(chǔ)輸入數(shù)據(jù)，由于數(shù)據(jù)首先由輸入端口存入共享存儲(chǔ)器，再?gòu)墓蚕泶鎯?chǔ)器傳輸?shù)捷敵龆丝冢浣粨Q速率受限于存儲(chǔ)器的訪問(wèn)速度。包頭信息傳輸?shù)睫D(zhuǎn)發(fā)控制器，由轉(zhuǎn)發(fā)控制器來(lái)決定讀取哪個(gè)數(shù)據(jù)包傳送到輸出端口。如果要實(shí)現(xiàn)輸出排隊(duì)，存儲(chǔ)器的操作速度必須多倍于端口速度，這將受限于存儲(chǔ)器性能而難以擴(kuò)展。

(3)交叉開關(guān)陣列結(jié)構(gòu)：交叉開關(guān)陣列結(jié)構(gòu)的路由器中，多個(gè)數(shù)據(jù)分組可以同時(shí)通過(guò)不同的線路進(jìn)行交換，從而極大地提高系統(tǒng)吞吐量，使系統(tǒng)性能得到顯著提高。系統(tǒng)的最終交換帶寬取決于交叉開關(guān)陣列和調(diào)度器的能力，而不是取決于互連介質(zhì)。可實(shí)現(xiàn)吞吐量和交換延遲的最優(yōu)化，滿足高速路由器對(duì)容量和性能的要求。

2 總體方案

在調(diào)研高性能路由器技術(shù)發(fā)展歷程、典型結(jié)構(gòu)及相關(guān)關(guān)鍵技術(shù)的基礎(chǔ)上，考慮目前衛(wèi)星網(wǎng)絡(luò)系統(tǒng)需求、軟硬件環(huán)境約束條件，對(duì)現(xiàn)有技術(shù)進(jìn)行了優(yōu)化和適應(yīng)性修改，確定衛(wèi)星網(wǎng)絡(luò)路由器數(shù)據(jù)轉(zhuǎn)發(fā)實(shí)現(xiàn)方案如下：

(1)路由器結(jié)構(gòu)：選用第三代高性能路由器作為衛(wèi)星網(wǎng)絡(luò)路由器的設(shè)計(jì)結(jié)構(gòu)，控制路徑和數(shù)據(jù)路徑分離。控制路徑根據(jù)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)生成路由表，將路由表項(xiàng)注入到數(shù)據(jù)路徑的轉(zhuǎn)發(fā)表中；數(shù)據(jù)路徑從IP數(shù)據(jù)包中提取包頭信息，查詢轉(zhuǎn)發(fā)表獲得下一跳端口，將數(shù)據(jù)交換到輸出線路上。數(shù)據(jù)路徑實(shí)現(xiàn)最長(zhǎng)前綴匹配、數(shù)據(jù)緩存、內(nèi)部交換等功能。路由器采用CPU+FPGA的實(shí)現(xiàn)方案，其中路由管理CPU完成控制路徑的功能，路由處理FPGA完成數(shù)據(jù)路徑的功能；

(2)路由查找：基于軟件的查找方法效率較低，而基于TCAM的路由查找方法需要專用器件，目前尚無(wú)宇航產(chǎn)品。因此使用RAM存儲(chǔ)轉(zhuǎn)發(fā)表項(xiàng)，并實(shí)現(xiàn)最長(zhǎng)前綴匹配的功能。并借鑒IP網(wǎng)三層交換中“流式IP交換”策略，經(jīng)適應(yīng)性改進(jìn)后，采取了“基于標(biāo)記的快速轉(zhuǎn)發(fā)策略”，提高數(shù)據(jù)包路由查詢效率；

(3)交換結(jié)構(gòu)：選用交叉開關(guān)陣列的交換結(jié)構(gòu)。輸入輸出接口之間設(shè)置多對(duì)多交換網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)包傳輸。并實(shí)現(xiàn)數(shù)據(jù)緩存、內(nèi)部傳輸?shù)裙δ?。并采取“?dòng)態(tài)優(yōu)先首1查詢策略”，提高數(shù)據(jù)包交換效率。

3 路由查找

路由策略由路由管理CPU和路由處理FPGA的配合完成，其中路由管理CPU負(fù)責(zé)根據(jù)鏈路狀態(tài)以及地面注入的路由信息維護(hù)接入節(jié)點(diǎn)表和骨干路由表。并生成硬件轉(zhuǎn)發(fā)表，注入到路由處理FPGA中。路由處理FPGA依據(jù)轉(zhuǎn)發(fā)表完成數(shù)據(jù)的轉(zhuǎn)發(fā)[8]。

3.1 最長(zhǎng)前綴匹配

路由處理FPGA上設(shè)置轉(zhuǎn)發(fā)表緩沖區(qū)，用于存儲(chǔ)轉(zhuǎn)發(fā)表項(xiàng)。轉(zhuǎn)發(fā)表項(xiàng)包括目的IP前綴、前綴長(zhǎng)度、端口號(hào)等信息，僅需匹配前綴長(zhǎng)度字段規(guī)定的數(shù)據(jù)位。前綴長(zhǎng)度較長(zhǎng)的轉(zhuǎn)發(fā)表項(xiàng)需放置到轉(zhuǎn)發(fā)表中靠前位置，路由查表時(shí)從轉(zhuǎn)發(fā)表第一項(xiàng)開始查找，如此前綴較長(zhǎng)的表項(xiàng)首先被查詢到。

默認(rèn)路由表項(xiàng)：路由管理CPU填充完有效IP轉(zhuǎn)發(fā)表項(xiàng)后，在轉(zhuǎn)發(fā)表末尾再填入一項(xiàng)默認(rèn)轉(zhuǎn)發(fā)表項(xiàng)，前綴長(zhǎng)度為0。所有與表中前部表項(xiàng)不匹配的IP數(shù)據(jù)包，均能與之匹配，并從所設(shè)置的默認(rèn)通道輸出。轉(zhuǎn)發(fā)表格式如表1所示。

表2 實(shí)驗(yàn)設(shè)備主要參數(shù)

3.2 轉(zhuǎn)發(fā)表項(xiàng)管理

路由處理FPGA中采用“乒乓”緩存方式解決路由更新和路由查詢的沖突。雙口RAM一端接收路由管理CPU寫入的轉(zhuǎn)發(fā)表項(xiàng)，另一端供路由查找模塊使用。如圖3所示，路由管理CPU向DRAM1注入轉(zhuǎn)發(fā)表項(xiàng)時(shí)，路由查找模塊使用DRAM2。表項(xiàng)注入完成后，路由管理CPU發(fā)送“注入完成”標(biāo)識(shí)，切換DRAM對(duì)應(yīng)關(guān)系。DRAM2供路由管理CPU注入，DRAM1供路由查詢模塊使用。

圖3 轉(zhuǎn)發(fā)表注入和輸出示意圖

轉(zhuǎn)發(fā)表中的表項(xiàng)通過(guò)“循環(huán)發(fā)布”的方式送給各通道。每個(gè)時(shí)鐘周期從轉(zhuǎn)發(fā)表中提取一個(gè)表項(xiàng)，發(fā)布到各接收通道。每個(gè)周期開始階段需發(fā)出“循環(huán)開始標(biāo)記”，各通道接收到數(shù)據(jù)包后，等待“循環(huán)開始標(biāo)記”后，依次匹配轉(zhuǎn)發(fā)表發(fā)布的各個(gè)表項(xiàng)。如有匹配則退出路由查詢，并進(jìn)行數(shù)據(jù)包傳輸；如匹配超時(shí)，則丟棄當(dāng)前數(shù)據(jù)包。各接收通道獨(dú)立進(jìn)行路由匹配，某一接收通道故障不影響其他接收通道。轉(zhuǎn)發(fā)表循環(huán)發(fā)布方式如圖4所示。

圖4 轉(zhuǎn)發(fā)表循環(huán)發(fā)布

3.3 路由查表的優(yōu)化

為提高路由查表效率，路由處理FPGA借鑒了IP網(wǎng)三層交換中“流式IP交換”策略(利用IP包頭信息來(lái)對(duì)后續(xù)數(shù)據(jù)業(yè)務(wù)流進(jìn)行標(biāo)記，記錄IP地址、端口號(hào)、應(yīng)用層協(xié)議類型、服務(wù)質(zhì)量要求等信息，建立從發(fā)端到收端的轉(zhuǎn)發(fā)路徑。具有同一特征標(biāo)記的業(yè)務(wù)流的后續(xù)分組直接傳送到已記錄的端口，不必對(duì)所有數(shù)據(jù)包進(jìn)行路由查找[8])。經(jīng)適應(yīng)性改進(jìn)后，采取了“基于標(biāo)記的快速轉(zhuǎn)發(fā)策略”。接收到數(shù)據(jù)包后，記錄數(shù)據(jù)包的“特征標(biāo)記”。當(dāng)有新的數(shù)據(jù)包送入時(shí)，將目的IP與所記錄的“標(biāo)記”進(jìn)行匹配，同時(shí)與轉(zhuǎn)發(fā)總表發(fā)布的表項(xiàng)進(jìn)行匹配。如果與“標(biāo)記”匹配，則直接進(jìn)入傳輸環(huán)節(jié)，否則需要對(duì)轉(zhuǎn)發(fā)總表進(jìn)行查詢，匹配后進(jìn)入傳輸環(huán)節(jié)。當(dāng)連續(xù)接收的數(shù)據(jù)包為同一目的IP時(shí)，路由查詢周期僅為1個(gè)時(shí)鐘周期。還可根據(jù)需要設(shè)置多個(gè)“特征標(biāo)記”，數(shù)據(jù)包與最近的多個(gè)“標(biāo)記”之一相匹配時(shí)，查詢周期也僅為1個(gè)時(shí)鐘周期。路由查表流程圖如圖5所示。

圖5 路由查表流程圖

為保證“最長(zhǎng)前綴匹配”的策略的實(shí)現(xiàn)，“標(biāo)記”的格式為目的IP地址全部字段和輸出通道號(hào)，需匹配目的IP的全部字段，且當(dāng)轉(zhuǎn)發(fā)總表發(fā)生更新時(shí)，需將所記錄的“標(biāo)記”清除。

4 內(nèi)部交換

4.1 交換單元

路由處理FPGA內(nèi)部采用多對(duì)多交換網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)包交互。圖6為MxN交換單元示意圖，傳輸控制模塊數(shù)量為M，接收控制模塊為N。每個(gè)傳輸控制模塊均能對(duì)任一接收控制模塊提出申請(qǐng)。每個(gè)接收控制模塊均能響應(yīng)任一傳輸控制模塊發(fā)出的數(shù)據(jù)傳輸請(qǐng)求。傳輸控制模塊、接收控制模塊均獨(dú)立運(yùn)行。

圖6 M x N交換單元

傳輸控制模塊實(shí)現(xiàn)的功能：當(dāng)輸入緩沖非空時(shí)，向?qū)?yīng)接收控制模塊發(fā)出傳輸申請(qǐng)F(tuán)rame_Req；等待應(yīng)答Frame_Ack；通過(guò)寫信號(hào)Frame_Wr、數(shù)據(jù)信號(hào)Frame_data將數(shù)據(jù)包傳輸?shù)浇邮湛刂颇K。

接收控制模塊實(shí)現(xiàn)的功能：當(dāng)輸出緩沖非滿時(shí)，檢查M個(gè)傳輸控制模塊送出的申請(qǐng)信號(hào)；根據(jù)有效傳輸申請(qǐng)F(tuán)rame_Req的序號(hào)，向?qū)?yīng)傳輸控制模塊的發(fā)出應(yīng)答信號(hào)Frame_Ack；等待傳輸控制模塊發(fā)出數(shù)據(jù)包，在Frame_wr信號(hào)有效時(shí)，將Frame_Ack信號(hào)撤銷，并將Frame_data存入輸出緩沖中。

傳輸控制模塊和接收控制模塊均設(shè)置“超時(shí)退出”機(jī)制，避免突發(fā)異常影響后續(xù)數(shù)據(jù)傳輸。

4.2 動(dòng)態(tài)優(yōu)先首1查詢策略

表2 動(dòng)態(tài)優(yōu)先排序

在查詢周期0，申請(qǐng)信號(hào)按照0～m-1順序排列；在查詢周期1，申請(qǐng)信號(hào)1排在第一個(gè)位置，申請(qǐng)信號(hào)0排在末尾；以此類推，在查詢周期m-1，申請(qǐng)信號(hào)m-1排在第一個(gè)位置，申請(qǐng)信號(hào)0～(m-2)按序排列。

首1查詢策略的實(shí)現(xiàn)方法如表3所示(以八位申請(qǐng)信號(hào)為例)，計(jì)算出申請(qǐng)信號(hào)reqtemp中第一個(gè)為1的排列序號(hào)index。

表3 首1查詢策略示例

flag為1時(shí)，表示申請(qǐng)信號(hào)組合中存在有效申請(qǐng)信號(hào)。將首1查詢所得“首1序號(hào)”index與動(dòng)態(tài)優(yōu)先策略中查詢周期序號(hào)clknum相加，并對(duì)申請(qǐng)通道總數(shù)M取模，可得動(dòng)態(tài)優(yōu)先排序后的第一個(gè)有效申請(qǐng)通道序號(hào)reqnum，計(jì)算公式如下所示。

reqnum=(clknum+index)%M

(1)

5 實(shí)驗(yàn)結(jié)果與分析

某空間骨干網(wǎng)絡(luò)采用了該方案的衛(wèi)星網(wǎng)絡(luò)路由器，已成功地實(shí)現(xiàn)了星間網(wǎng)絡(luò)數(shù)據(jù)幀的高速轉(zhuǎn)發(fā)功能，同時(shí)支持星內(nèi)遙控?cái)?shù)據(jù)上行及遙測(cè)數(shù)據(jù)下行等傳輸業(yè)務(wù)。根據(jù)測(cè)試結(jié)果，每路接口工作速率最高可達(dá)1.6 Gb/s，能夠滿足大部分衛(wèi)星網(wǎng)絡(luò)的需求。測(cè)試結(jié)果如表4所示，經(jīng)擴(kuò)展后還可以滿足未來(lái)衛(wèi)星網(wǎng)絡(luò)高速數(shù)據(jù)轉(zhuǎn)發(fā)需求。

表4 高速數(shù)據(jù)轉(zhuǎn)發(fā)性能表

6 結(jié)束語(yǔ)

在討論了路由器發(fā)展歷程之后，對(duì)高性能路由器典型結(jié)構(gòu)、路由查找、內(nèi)部交換關(guān)鍵技術(shù)進(jìn)行了充分調(diào)研，結(jié)合衛(wèi)星網(wǎng)絡(luò)的路由需求、硬件電路設(shè)計(jì)約束條件，開展了衛(wèi)星網(wǎng)絡(luò)路由器數(shù)據(jù)路徑的設(shè)計(jì)。采取了基于RAM的路由查找策略、“循環(huán)發(fā)布”的方式，各接收模塊獨(dú)立進(jìn)行路由匹配；采取了“基于標(biāo)記的快速轉(zhuǎn)發(fā)策略”，實(shí)現(xiàn)“一次路由，多次交換”，提高數(shù)據(jù)包轉(zhuǎn)發(fā)效率；數(shù)據(jù)傳輸路徑采用多對(duì)多交換網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)包交互，各通道獨(dú)立運(yùn)行；采取“動(dòng)態(tài)優(yōu)先首1查詢策略”，在一個(gè)時(shí)鐘周期內(nèi)受理所有申請(qǐng)信號(hào)中第一個(gè)有效信號(hào)，并可動(dòng)態(tài)改變各路通道申請(qǐng)信號(hào)的排列順序，以均衡各申請(qǐng)信號(hào)的被受理的概率。所實(shí)現(xiàn)的路由查找功能、內(nèi)部交換結(jié)構(gòu)，經(jīng)擴(kuò)展后還可滿足后續(xù)更高性能衛(wèi)星路由器的設(shè)計(jì)需求。