[發明專利]一種二維環繞網格片上網絡拓撲結構的路由方法

有效

• 申請號: 201510341674.2
• 申請日: 2015-06-18
• 公開（公告）號: CN105049362B
• 公開（公告）日: 2018-04-17
• 發明（設計）人: 史江義;舒浩;李釗;馬佩軍;王禛;吳冰冰;余文哲;張春焱
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/751
• 分類號: H04L12/751;H04L12/721
• 代理公司: 陜西電子工業專利中心61205
• 代理人: 韋全生,王品華

1.一種二維環繞網格片上網絡拓撲結構的路由方法，其特征在于，所述拓補結構包括由m×n個路由節點組成的m×n矩形網絡，其中m≥2，n≥2，在所述m×n矩形網絡中的任一相鄰行路由節點之間、所有列首尾的路由節點之間、任一相鄰列路由節點之間和所有行首尾的路由節點之間，各連接一個流量控制器，形成二維環繞的拓撲結構；其中路由節點用于接收來自本地端口或路由端口的數據分組，并將數據分組注入流量控制器或轉發至本地端口、目的地址對應的路由節點端口；流量控制器的數量為m+n個，用于接收來自路由節點的數據分組，并將數據分組傳輸至下一個路由節點；

所述m×n的矩形網絡，設定水平向右的方向為x軸的正方向，垂直向下的方向為y軸的正方向；

所述路由節點設有四個路由端口和一個本地端口，其中四個路由端口分別用于連接東、南、西、北四個方向流量控制器，本地端口通過NI模塊與本地IP連接；

所述流量控制器由水平流量控制器和垂直流量控制器組成，其中水平流量控制器用于接收來自任一相鄰列路由節點的端口之間和所有行首尾的路由節點的端口之間的數據分組，垂直流量控制器用于接收來自任一相鄰行路由節點的端口之間和所有列首尾的路由節點的端口之間的數據分組，并按照相應的路由方法將該數據分組傳輸至另一個路由節點；

所述路由方法包含性能優先路由方法和開銷優先路由方法，這兩種路由方法下任何路由路徑跳步數不超過2，若數據分組的目的節點與當前數據分組所在的流量控制器的非接收數據分組端相連，則直接將數據分組通過流量控制器從源節點傳輸到目的節點，若數據分組的目的節點與當前數據分組所在的流量控制器的非接收數據分組端不相連，則先通過水平流量控制器將數據分組從源節點傳輸到偏轉節點然后通過垂直流量控制器將數據分組從偏轉節點傳輸至目的節點，數據分組的路由路徑模式共有十二種；

所述數據分組的路由路徑模式共有十二種，分別為：東方向-南方向、東方向—北方向、西方向-南方向、西方向-北方向、南方向-西方向、南方向-東方向、北方向-西方向、北方向-東方向、南方向、北方向、西方向、東方向；其中東方向-南方向表示的是數據分組由路由節點的東端口方向通過水平流量控制器傳輸到偏轉節點，然后該數據分組再由偏轉節點的南端口方向通過垂直流量控制器傳輸到目的節點，其它模式類似；其中南方向表示的是數據分組由路由節點的南端口方向通過垂直流量控制器傳輸到目的節點，其它模式類似；

所述偏轉節點是指源節點和目的節點沒有通過流量控制器直接相連，數據分組傳輸時先通過水平流量控制器傳輸到一個中轉節點，然后通過垂直流量控制器從中轉節點傳輸到目的節點，該中轉節點即為偏轉節點；

所述性能優先路由方法傳輸數據分組的路由路徑模式限定為六種，分別為東方向-南方向、西方向-北方向、南方向、北方向、西方向、東方向，該路由方法具體步驟如下：

(1)路由節點接收數據分組：

(1a)路由節點接收來自路由端口的數據分組；

(1b)路由節點接收來自本地端口的數據分組；

(2)判斷數據分組的來源：

路由節點判斷接收到的數據分組是否來自本地端口，若是，則執行步驟(3)；否則，執行步驟(6)；

(3)對路由節點的坐標進行分類：

若當前路由節點的橫坐標值與縱坐標值之和為偶數，則執行步驟(4)，否則執行步驟(5)；

(4)本地數據分組西注入：

若當目的節點的縱坐標值比當前節點的縱坐標值大1時，路由節點將本地端口的數據分組傳輸給與路由節點的南端口相連的垂直流量控制器，執行步驟(7)；否則若當目的節點的縱坐標值比當前節點的縱坐標值小1時，路由節點將本地端口的數據分組傳輸給與路由節點的北端口相連的垂直流量控制器，執行步驟(7)；否則若當目的節點的橫坐標值比當前節點的橫坐標值大1時，路由節點將本地端口的數據分組傳輸給與路由節點的東端口相連的水平流量控制器，執行步驟(7)；否則，路由節點將本地端口的數據分組傳輸給與路由節點的西端口相連的水平流量控制器，執行步驟(7)；

(5)本地數據分組東注入：

若當目的節點的縱坐標值比當前節點的縱坐標值大1時，路由節點將本地端口的數據分組傳輸給與路由節點的南端口相連的垂直流量控制器，執行步驟(7)；否則若當目的節點的縱坐標值比當前節點的縱坐標值小1時，路由節點將本地端口的數據分組傳輸給與路由節點的北端口相連的垂直流量控制器，執行步驟(7)；否則若當目的節點的橫坐標值比當前節點的橫坐標值小1時，路由節點將本地端口的數據分組傳輸給與路由節點的西端口相連的水平流量控制器，執行步驟(7)；否則，路由節點將本地端口的數據分組傳輸給與路由節點的東端口相連的水平流量控制器，執行步驟(7)；

(6)分類轉發數據分組：

(6a)若路由節點端口接收的數據分組的目的坐標為當前路由節點坐標，則將數據分組直接傳輸給本地端口，本次路由結束；

(6b)若路由節點端口接收的數據分組的目的坐標不是當前路由節點坐標，則當前節點為偏轉節點，執行步驟(9)；

(7)流量控制器接收來自路由節點的數據分組；

(8)流量控制器端口分配：

(8a)若數據分組的目的節點與當前數據分組所在的流量控制器的非接收數據分組端相連，則流量控制器將接收到的數據分組直接傳輸至與目的節點相連的該流量控制器端口，執行步驟(10)；

(8b)若數據分組的目的節點與當前數據分組所在的流量控制器的非接收數據分組端不相連，則：若路由節點將數據分組注入到其西方向的水平流量控制器，則水平流量控制器將數據分組傳輸至比目的節點縱坐標大1的流量控制器端口，該端口所連接的節點為偏轉節點，執行步驟(9)；若路由節點將數據分組注入到其東方向的水平流量控制器，則水平流量控制器將數據分組傳輸至比目的節點縱坐標小1的流量控制器端口，該端口所連接的節點為偏轉節點，執行步驟(9)；

(9)偏轉節點通過垂直流量控制器將數據分組傳輸至與目的節點相連的流量控制器端口；

(10)目的節點接收來自流量控制器的數據分組，將數據分組傳輸至本地端口，路由結束；

所述開銷優先路由方法傳輸數據分組的路由路徑模式限定為兩種，分別為東方向-南方向、東方向，該路由方法具體步驟如下：

(1)路由節點接收數據分組：

(1a)路由節點接收來自路由端口的數據分組；

(1b)路由節點接收來自本地端口的數據分組；

(2)判斷數據分組的來源：

路由節點判斷接收的數據分組是否來自本地端口，若是，則執行步驟(3)；否則，執行步驟(4)；

(3)本地端口將數據分組傳輸至與當前節點的東端口相連的水平流量控制器，執行步驟(5)；

(4)分類轉發數據分組：

(4a)若路由節點端口接收的數據分組的目的坐標為當前路由節點坐標，則將數據分組直接傳輸給本地端口，本次路由結束；

(4b)若路由節點端口接收的數據分組的目的坐標不是當前路由節點坐標，則將數據分組通過該路由節點的南端口傳輸至與該路由節點相連的垂直流量控制器，執行步驟(7)；

(5)判斷數據分組的目的節點位置：

數據分組的目的節點是否與該水平流量控制器的非接收數據分組端直接相連，若是，則執行步驟(8)；否則，執行步驟(6)；

(6)水平流量控制器將數據分組傳輸至比目的節點縱坐標小1的流量控制器端口，該端口所連接的節點為偏轉節點；

(7)偏轉節點通過垂直流量控制器將數據分組傳輸至與目的節點相連的該垂直流量控制器端口，執行步驟(9)；

(8)水平流量控制器將數據分組傳輸至與該水平流量控制器相連的目的節點端口；

(9)目的節點接收來自流量控制器的數據分組，將數據分組傳輸至本地端口，路由結束。