，， ， ，

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

0 引言

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

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

1 路由技術調研

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

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

圖1 高性能路由器典型結構

1.1 路由查找

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

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

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

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

1.2 交換結構

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

圖2 交換結構分類

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

(2)共享存儲器結構：使用了大量的高速RAM來存儲輸入數(shù)據(jù)，由于數(shù)據(jù)首先由輸入端口存入共享存儲器，再從共享存儲器傳輸?shù)捷敵龆丝?，其交換速率受限于存儲器的訪問速度。包頭信息傳輸?shù)睫D發(fā)控制器，由轉發(fā)控制器來決定讀取哪個數(shù)據(jù)包傳送到輸出端口。如果要實現(xiàn)輸出排隊，存儲器的操作速度必須多倍于端口速度，這將受限于存儲器性能而難以擴展。

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

2 總體方案

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

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

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

(3)交換結構：選用交叉開關陣列的交換結構。輸入輸出接口之間設置多對多交換網(wǎng)絡進行數(shù)據(jù)包傳輸。并實現(xiàn)數(shù)據(jù)緩存、內部傳輸?shù)裙δ堋２⒉扇　皠討B(tài)優(yōu)先首1查詢策略”，提高數(shù)據(jù)包交換效率。

3 路由查找

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

3.1 最長前綴匹配

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

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

表2 實驗設備主要參數(shù)

3.2 轉發(fā)表項管理

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

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

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

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

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

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

圖5 路由查表流程圖

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

4 內部交換

4.1 交換單元

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

圖6 M x N交換單元

傳輸控制模塊實現(xiàn)的功能：當輸入緩沖非空時，向對應接收控制模塊發(fā)出傳輸申請Frame_Req；等待應答Frame_Ack；通過寫信號Frame_Wr、數(shù)據(jù)信號Frame_data將數(shù)據(jù)包傳輸?shù)浇邮湛刂颇K。

接收控制模塊實現(xiàn)的功能：當輸出緩沖非滿時，檢查M個傳輸控制模塊送出的申請信號；根據(jù)有效傳輸申請Frame_Req的序號，向對應傳輸控制模塊的發(fā)出應答信號Frame_Ack；等待傳輸控制模塊發(fā)出數(shù)據(jù)包，在Frame_wr信號有效時，將Frame_Ack信號撤銷，并將Frame_data存入輸出緩沖中。

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

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

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

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

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

表3 首1查詢策略示例

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

reqnum=(clknum+index)%M

(1)

5 實驗結果與分析

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

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

6 結束語

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