SpaceWire 網(wǎng)絡(luò)遍歷及自主路由配置算法研究

王 軍，陳天麗，夏荒生

（1.中國電子科技集團公司第四十一研究所，安徽 蚌埠 233006；2.湖北中煙工業(yè)有限責任公司武漢卷煙廠，湖北 武漢 430040；3.湖北中煙工業(yè)有限責任公司襄陽卷煙廠，湖北 襄陽 441000）

0 引言

時代進步，科技發(fā)展，對衛(wèi)星載荷分辨率要求也與日俱增，同時對于各個星體之間的數(shù)據(jù)交換以及信息共享也要實現(xiàn)高同通速率，非常緊急需求搭建一種高可靠性和全速的網(wǎng)絡(luò)結(jié)構(gòu)，讓許多用戶和數(shù)據(jù)信息能及時共享。本文在研究SpaceWire 協(xié)議標準的基礎(chǔ)上，給出了該網(wǎng)絡(luò)拓撲遍歷算法，進而研究其網(wǎng)絡(luò)自主路由配置算法。

1 SpaceWire 網(wǎng)絡(luò)簡介

SpaceWire 基礎(chǔ)協(xié)議是ESA 在商用標準的基礎(chǔ)上改進而來的，使其可靠性、功耗、速率等性能大大提高以更好地滿足航天應用的要求。我們選擇傳輸速率能夠達到500Mb/s 的串行數(shù)據(jù)總線，因為此總線可實現(xiàn)雙向和全雙工功能。

基礎(chǔ)協(xié)議包含物理層、信號層、字符層、交換層、數(shù)據(jù)包層和網(wǎng)絡(luò)層?；A(chǔ)協(xié)議在硬件接口規(guī)范和網(wǎng)絡(luò)規(guī)范等方面提出要求，給出了數(shù)據(jù)包的流通規(guī)則與容錯要求。每一層僅需完成本層的任務(wù)，而無需關(guān)心其他層的工作內(nèi)容，即層與層之間是相對透明的。一共分為兩種，一種是數(shù)據(jù)包的信源和信宿，另一種是數(shù)據(jù)轉(zhuǎn)發(fā)功能，其中數(shù)據(jù)轉(zhuǎn)發(fā)功能就是我們常說的路由器，而數(shù)據(jù)包的信源和信宿也就是節(jié)點，二者都是多端口設(shè)備。各個設(shè)備通過SpaceWire 鏈路互連便形成了SpaceWire 網(wǎng)絡(luò)。

2 SpaceWire 網(wǎng)絡(luò)拓撲遍歷算法

（Breadth-FirstTranversal，BFT）和深度優(yōu)先遍歷（Depth-FirstTranversal，DFT）是該網(wǎng)絡(luò)常用的兩種遍歷算法。為了便于說明SpaceWire 網(wǎng)絡(luò)是個雙向全雙工網(wǎng)絡(luò)，以圖1中的小型SpaceWire 網(wǎng)絡(luò)示意圖為例，該網(wǎng)絡(luò)經(jīng)常使用的是深度優(yōu)先遍歷和寬度優(yōu)先遍歷兩種算法，對網(wǎng)絡(luò)拓撲遍歷方法進行舉例說明。如圖1所示：

圖1 網(wǎng)絡(luò)模型拓撲示意圖

2.1 采用BFT 網(wǎng)絡(luò)遍歷算法

（1）NM 自檢，發(fā)現(xiàn)自己有1個端口，端口號為1，為自己分配邏輯地址LA1。

（2）零跳設(shè)備查詢：NM 向與自己直接相連的設(shè)備發(fā)送設(shè)備查詢數(shù)據(jù)包，得到查詢應答顯示R1是路由器，其共有8個端口，收到數(shù)據(jù)包的端口為1號端口；NM 向R1寫發(fā)現(xiàn)標識，即將其邏輯地址位寫入0xFE，表征R1已經(jīng)被發(fā)現(xiàn)。

（3）一跳設(shè)備查詢：NM 依次向R1的各個端口發(fā)送設(shè)備查詢包，通過計時等待，發(fā)現(xiàn)其2號、5號、6號、8號端口都沒有連接設(shè)備；3號端口連接有普通節(jié)點SN1，為其分配邏輯地址LA2，并寫入其EDS 中；4號端口連接有路由器R2，向其EDS 中寫入發(fā)現(xiàn)標識，其共有8個端口，其收到查詢包的端口是6號口；7號端口連接有普通節(jié)點SN3，為其分配邏輯地址LA3。

（4）二跳設(shè)備查詢：NM 依次向R2的各端口發(fā)送設(shè)備查詢包，通過計時等待發(fā)現(xiàn)R2的1號、2號、4號、7號、8號端口為空；其3號端口連接有普通節(jié)點SN1，SN1已被發(fā)現(xiàn)，其邏輯地址為LA2；5號端口連接有普通節(jié)點SN2，為其分配邏輯地址LA4。

（5）由于沒有三跳設(shè)備的存在，因此遍歷結(jié)束。

2.2 采用DFT 網(wǎng)絡(luò)遍歷算法

（1）NM 自檢，發(fā)現(xiàn)自己有1個端口，端口號為1，為自己分配邏輯地址LA1。

（2）NM 向與自己直接相連的設(shè)備發(fā)送設(shè)備查詢數(shù)據(jù)包，得到查詢應答顯示R1是路由器，其共有8個端口，收到數(shù)據(jù)包的端口為1號端口；NM 向R1寫發(fā)現(xiàn)標識，即將其邏輯地址位寫入0xFE，表征R1已經(jīng)被發(fā)現(xiàn)。

（3）R1各端口查詢：NM 向R1的2號口發(fā)送設(shè)備查詢包，通過計時等待，發(fā)現(xiàn)其2號口沒有連接設(shè)備；向3號端口發(fā)送查詢包，發(fā)現(xiàn)3號口連接有普通節(jié)點SN1，為其分配邏輯地址LA2；發(fā)現(xiàn)4 號端口連接有路由器R2，其共有6個端口，其收到查詢包的端口是6號口。

（4）R2各端口查詢：NM 依次向R2的各端口發(fā)送設(shè)備查詢包，通過計時等待發(fā)現(xiàn)R2的1號、2號、4號、7號、8號端口為空；其3號端口連接有普通節(jié)點SN1，SN1已被發(fā)現(xiàn)，其邏輯地址為LA2；5號端口連接有普通節(jié)點SN2，為其分配邏輯地址LA3。

（5）R1剩余端口查詢：R2端口查詢結(jié)束后，回到R1 未遍歷的端口上，向R1 的5 號、6 號端口依次發(fā)送查詢包，計時等待后發(fā)現(xiàn)兩個端口上都沒有設(shè)備連接；向R1的7號端口發(fā)送查詢包，發(fā)現(xiàn)其連接有普通節(jié)點SN3，為其分配邏輯地址LA4；向R1的8號端口發(fā)送查詢包，計時等待后發(fā)現(xiàn)該端口上都沒有設(shè)備連接。

（6）由于沒有其他的路由器及剩余端口存在，因此遍歷結(jié)束。

根據(jù)上述可知，寬度優(yōu)先算法BFT 在遍歷過程中比深度優(yōu)先算法DFT 效率更高，更省時。

3 SpaceWire 網(wǎng)絡(luò)路由算法研究

路由算法分為靜態(tài)路由和動態(tài)路由。靜態(tài)路由是手工定義和配置路由的過程，動態(tài)路由是路由器之間相互通信，相互傳遞數(shù)據(jù)信息。靜態(tài)路由適合于組網(wǎng)結(jié)構(gòu)簡單、到達目標只有一條路徑的網(wǎng)絡(luò)，但是對于當網(wǎng)絡(luò)出現(xiàn)問題和其他原因引發(fā)拓撲結(jié)構(gòu)發(fā)生變化時，除非外力干預，否則靜態(tài)路由不會自動發(fā)生變化。

3.1 靜態(tài)路由算法

對于網(wǎng)絡(luò)規(guī)模較小、結(jié)構(gòu)固定、無路由自適應需求的SpaceWire 網(wǎng)絡(luò)，較適合采用靜態(tài)路由。當?shù)谝粋€數(shù)據(jù)包是字符0時，表示是內(nèi)部配置端口，在內(nèi)部用于對路由器進行配置的虛擬端口。

3.2 動態(tài)路由算法

動態(tài)路由有兩種：距離矢量和鏈路狀態(tài)路由選擇算法。

距離矢量路由選擇算法顧名思義就是到達目的地的最短距離和路徑，同時進行實時更新兩個路由器直接的信息分配。鏈路狀態(tài)路由選擇算法是將自己作為中心，同時計算跟別的路由器之間的最短距離，讓數(shù)據(jù)在各個路由器直接傳輸跟及時和高效。

4 組適配路由選擇算法

在SpaceWire 網(wǎng)絡(luò)中，網(wǎng)絡(luò)帶寬至關(guān)重要，一旦出現(xiàn)網(wǎng)絡(luò)故障，導致數(shù)據(jù)的傳輸將受到影響，關(guān)鍵是隨著現(xiàn)代網(wǎng)絡(luò)時代的發(fā)展，對網(wǎng)絡(luò)的及時性和容量要求更加迫切，必須增加網(wǎng)絡(luò)的帶寬。因此，為了提高網(wǎng)絡(luò)容錯能力，增加網(wǎng)絡(luò)帶寬，采用硬容錯思想，以鏈路冗余為代價，提出了組適配路由技術(shù)。

組適配路由的算法，數(shù)據(jù)包轉(zhuǎn)發(fā)過程中，首先要定義端口的優(yōu)先級，按優(yōu)先等級順序排列方式進行數(shù)據(jù)傳送。如圖2所示：

圖2 組適配路由示例

5 結(jié)束語

本文介紹了SpaceWire 網(wǎng)絡(luò)的組成，給出了兩種網(wǎng)絡(luò)拓撲遍歷算法，相比較而言，寬度優(yōu)先算法BFT 遍歷效率更高。本文研究了網(wǎng)絡(luò)路由算法，給出了動態(tài)組適配路由算法。該算法可以有效地進行路由配置，配置結(jié)果可用于邏輯尋址，在后續(xù)高速技術(shù)發(fā)展簡便實用的自適應路由等技術(shù)打下良好的基石，具有很好的科研、生產(chǎn)和民用價值。