[發明專利]2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法

在審

• 申請號: 201410384174.2
• 申請日: 2014-08-06
• 公開（公告）號: CN104202241A
• 公開（公告）日: 2014-12-10
• 發明（設計）人: 楊勇;才華;吳劍飛;陳玉群;谷欣超;韓太林;劉俊杰
• 申請（專利權）人: 長春理工大學
• 主分類號: H04L12/703
• 分類號: H04L12/703;H04L12/771;H04L12/757
• 代理公司: 長春市吉利專利事務所 22206
• 代理人: 李曉莉

1.2D-Mesh拓補結構下的片上網絡偏轉容錯路由算法，其特征在于：該方法包括如下步驟：

步驟一：給m×n的2D-mesh拓撲片上網絡定義變量、全局路由器、基礎的X-Y傳輸規則、邊緣路由表和容錯偏轉決策模型，其具體包括如下子步驟：

步驟1.1：分別定義變量，包括：內部路由節點、邊緣路由節點和ping命令的測試超時時間；

內部路由節點：在m×n的2D-mesh拓撲片上網絡上的一個當前路由節點，若與該當前路由節點直接相連的其它路由節點共有四個，則將這類有四個鄰近路由節點的當前路由節點稱為內部路由節點；

邊緣路由節點：在m×n的2D-mesh拓撲片上網絡上的一個當前路由節點，若與該當前路由節點直接相連的其它路由節點的總數不大于三個，則將這類至多有三個鄰近路由節點的當前路由節點稱為邊緣路由節點；

ping命令的測試超時時間：定義一個確定的時間常數T，當前路由節點對其它鄰近路由節點進行ping測試命令時，若被測試的路由節點在時長為T的時間段內一直沒有反饋，則將該被測試路由節點所在的路徑判定為非通路；

步驟1.2：定義基礎的X-Y傳輸規則為：

2Dmesh拓撲的片上網絡上，由m×n個路由節點組成的矩形陣列上的每一個路由節點都具有自己的唯一坐標，設任意一個路由節點A的坐標值(x,y)，另外一個任意路由節點B的坐標值(p,q)，則從路由節點A(x,y)始發并去往路由節點B(p,q)時，其遵循如下的基礎規則：

當路由節點A(x,y)與B(p,q)的橫坐標和縱坐標均不相同時，A(x,y)總是忽略縱坐標上的差值，并優先選擇能使橫坐標差值的絕對值縮小的那一個橫軸上的鄰近路由節點作為下一跳時的交付地址；

當路由節點A(x,y)與B(p,q)的橫坐標相同但縱坐標不相同時，A(x,y)總是優先選擇能使縱坐標差值的絕對值縮小的那一個縱軸上的鄰近路由節點作為下一跳時的交付地址；

從路由節點A(x,y)始發并去往路由節點B(p,q)時，按上述基礎X-Y傳輸規則所確定的總跳步數初始值T_初的表達式為：

T_初＝|x-p|+|y-q|……(1)

步驟1.3：定義全局路由器：隨機指定一個路由節點作為m×n的2D-mesh拓撲片上網絡的全局路由器，并將該全局路由器在片上網絡中的坐標分配給所有其他路由節點；

步驟1.4：定義任意確定路由節點與其他全部路由節點相對坐標位置關系的全局相對坐標關系路由表；該全局相對坐標關系路由表由步驟1.3所述的全局路由器按照步驟1.2所述基礎的X-Y傳輸規則求解生成并存儲；

所述全局相對坐標關系路由表中的每一行條目均與由步驟1.2所述的基礎X-Y傳輸規則所確定的一條基礎X-Y路徑對應，該行條目順次記載了以任意一個路由節點A為起點并以另外一個任意路由節點B為終點所形成的一條基礎X-Y路徑上的全部路由節點的坐標信息，并且也記載了沿該條基礎X-Y路徑的總跳步數初始值T_初；

在當前傳送任務中，當前的路由節點A禁止向剛剛給路由節點A傳送數據的鄰近節點反向回傳數據，該限制一直持續到當前源節點順利將信息傳送到目的節點之后才予以解除；

步驟1.5：定義容錯偏轉決策模型，其具體包括如下子步驟：

步驟1.5.1：分別定義任意一個當前路由節點A向其自身的上、下、左、右四個臨近路由節點：路由節點U、路由節點D、路由節點L或路由節點R交付任務數據包時的優先級順序為：

從當前路由節點A出發，選擇向路由節點U傳送的優先級為最低；

從當前路由節點A出發，選擇向路由節點D傳送的優先級為最高；

從當前路由節點A出發，選擇向路由節點R傳送優先級為較高，而選擇向路由節點L傳送的優先級為較低；

步驟1.5.2：由當前路由節點A分別向與其如步驟1.5.1所述的四個臨近路由節點分別發送如步驟1.1所述的ping命令測試以判斷當前路徑是否通路；

步驟1.5.3：由當前路由節點A將ping命令測試結果為非通路的各個臨近路由節點的優先級在當前傳送任務完成之前均暫時被降低為限制級；

步驟1.5.4：由當前路由節點A將當前優先級相對最高的臨近路由節點作為下一跳的交付路由節點，并向該下一跳的交付路由節點傳送全部任務數據；

步驟二：2D-mesh拓撲片上網絡的初始化

步驟2.1：為2D-mesh拓撲片上網絡指定一個具體的路由節點作為全局路由器；

步驟2.2：對全部路由節點進行初始化，為每一個路由節點都設定統一的如步驟1.1所述的時間常數T；

步驟2.3：將步驟2.1所述的全局路由器在片上網絡中的坐標地址分配給其余全部路由節點；

步驟2.4：由全局路由器按照步驟1.4所述方法分別求得任意確定路由節點與其他全部路由節點相對坐標位置關系的全局相對坐標關系路由表；

步驟2.5：除全局路由器以外的每一個路由節點分別從步驟2.4所述全局相對坐標關系路由表中調取包含自身坐標的全部條目片段，并將這些片段合并成為本節點自身與其它節點的相對位置關系路由表，保存在該節點自身的緩存中；

步驟2.6：除全局路由器以外每一個路由節點對其自身所存儲的本節點自身與其它節點的相對位置關系路由表進行運算，根據式(1)分別求解出本節點自身與其它節點的相對位置關系路由表中每一行條目對應下的由基于基礎X-Y傳輸規則所確定的總跳步數的初始值T_初；

步驟三：當m×n的2D-mesh拓撲片上網絡開始一個以任意一個路由節點A為起點并以另外一個任意路由節點B為終點的數據傳送任務時，將路由節點A稱為數據源節點，并將目標路由節點B稱為目標節點；

由當前的數據源節點根據其自身在片上網絡內的坐標值進行判斷，若其自身屬于步驟1.1所述內部路由節點則將路由節點A重新計作由當前的內部數據源節點M并繼續執行步驟四，若其自身屬于步驟1.1所述邊緣路由節點則將路由節點A重新計作當前的邊緣數據源節點N并繼續執行步驟五；

步驟四：內部路由節點的數據傳輸過程，其具體包括如下子步驟：

步驟4.1：由當前的內部數據源節點M從如步驟2.5所述的本節點自身與其它節點的相對位置關系路由表中查找包含有當前目標節點B的一行條目，從而獲得由步驟1.2所述基于基礎X-Y傳輸規則所確定的一條由當前的內部數據源節點M始發去往目標節點B的基礎X-Y傳輸路徑；

步驟4.2：由當前的內部數據源節點M向沿著步驟4.1所述基礎X-Y傳輸路徑上的下一個臨近節點C發送ping命令測試包，以判斷內部數據源節點M到下一個臨近節點C的鄰近路徑是否通路；若該鄰近路徑為通路則執行步驟4.3，若該鄰近路徑為非通路則執行步驟4.4；

步驟4.3：由當前的內部數據源節點M將待傳送的數據全部傳送給步驟4.2所述的臨近節點C，并在當前傳送的最后一個數據包內做出當前數據全部傳送完成的標志；

步驟4.4：由步驟4.2所述的臨近節點C判斷，其自身是否已經收到攜帶有如步驟4.3所述當前數據全部傳送完成的標志的數據包，若已收到則執行步驟4.5，否則，重新執行步驟4.3；

步驟4.5：由步驟4.2所述的當前臨近節點C判斷，其自身如步驟2.6所述到目標節點B的總跳步數的初始值T_初是否等于1，若T_初等于1則當前臨近節點C將自身待傳送數據全部傳給目標節點B并在完成全部數據的傳送后終止當前的傳送任務；若前述T_初不等于1則所述的臨近節點C將其自身視作如步驟三所述的一個全新的數據源節點，并重新執行步驟三；

步驟4.6：由當前的內部數據源節點M判斷，其自身的橫坐標值與目標節點B的橫坐標值是否相同，若其二者的橫坐標值不同則執行步驟4.7，否則執行步驟4.8；

步驟4.7：按照步驟1.5所述容錯偏轉決策模型將全部數據傳送至當前的數據源節點的下一鄰近節點D，然后，該鄰近節點D將其自身視作步驟4.3所述的臨近節點C，并繼續執行步驟4.4至步驟4.5所述過程；

步驟4.8：由當前的內部數據源節點M優先向沿著步驟4.1所述基礎X-Y傳輸路徑的X軸方向上的下一個臨近節點E發送ping命令測試包，以判斷內部數據源節點M到其在X軸方向上的下一個臨近節點E的鄰近路徑是否通路；若該鄰近路徑為通路則執行步驟4.9，若該鄰近路徑為非通路則執行步驟4.7；

步驟4.9：由當前的內部數據源節點M將待傳送的數據全部傳送給步驟4.8所述的其在X軸方向上的下一個臨近節點E，并在當前傳送的最后一個數據包內做出當前數據全部傳送完成的標志；

步驟4.10：步驟4.9所述的當前節點E在收到由內部數據源節點M傳來的全部數據后，當前節點E判斷其自身的縱坐標值與目標節點B的縱坐標值是否相同，若其二者的縱坐標值相同，則執行步驟4.11，否則執行步驟4.12；

步驟4.11：步驟4.9所述的當前節點E判斷，其自身如步驟2.6所述到目標節點B的總跳步數的初始值T_初是否等于1，若T_初等于1則當前臨近節點E將自身待傳送數據全部傳給目標節點B并在完成全部數據的傳送后終止當前的傳送任務；若前述T_初不等于1則所述的臨近節點E將其自身視作如步驟三所述的一個全新的數據源節點，并重新執行步驟三；

步驟4.12：由步驟4.9所述的當前節點E將數據包沿著能使當前節點E與目標節點B之間的縱坐標差值的絕對值進一步縮小的方向，將待傳輸的數據包全部傳給該方向上的下一個臨近節點F，并在當前傳送的最后一個數據包內做出當前數據全部傳送完成的標志；

步驟4.13：由步驟4.12所述的當前臨近節點F判斷，其自身是否已經收到攜帶有如步驟4.12所述當前數據全部傳送完成的標志的數據包，若已收到則執行步驟4.14，否則，重新執行步驟4.12；

步驟4.14：由步驟4.12所述的當前臨近節點F判斷，其自身如步驟2.6所述到目標節點B的總跳步數的初始值T_初是否等于1，若T_初等于1則由步驟4.12所述的當前臨近節點F將自身待傳送數據全部傳給目標節點B并在完成全部數據的傳送后終止當前的傳送任務；若前述T_初不等于1則由步驟4.12所述的當前臨近節點F將其自身視作如步驟三所述的一個全新的數據源節點，并重新執行步驟三；

步驟五：內部路由節點的數據傳輸過程，其具體包括如下子步驟：

步驟5.1：由當前的邊緣數據源節點N向其自身的各個鄰近節點分別發送ping命令測試包，以判斷當前的邊緣數據源節點N到其下一個臨近節點S_(n)(n≤3，n取自然數)的鄰近路徑是否通路；若該鄰近路徑為通路則執行步驟5.2，若該鄰近路徑為非通路則在當前的傳送任務全部完成之前，暫時禁止向該非通路的下一個臨近節點S_(n)傳送數據；

步驟5.2：由當前的邊緣數據源節點N分別從其如步驟5.1所述剩余的臨近節點S_(n剩)的路由表中調取如步驟2.5所述的該臨近節點S_(n剩)與其它節點的相對位置關系路由表，并分別獲得以該臨近節點S_(n剩)為起點并去往目標節點B時，如步驟2.6所述的總跳步數的初始值T_初S_(n剩)(n≤3，n取自然數)；

步驟5.3：由當前的邊緣數據源節點N對步驟5.2所述的多個總跳步數的初始值T_初S_(n剩)(n≤3，n取自然數)進行比較和排序，并從中隨機選擇一個總跳步數初始值T_初S_(n剩)最小的臨近節點S_(n剩)作為邊緣數據源節點N的數據交付節點K；

步驟5.4：由當前的邊緣數據源節點N將待傳輸的數據包全部傳給由步驟5.3所確定的數據交付節點K，并在當前傳送的最后一個數據包內做出當前數據全部傳送完成的標志；

步驟5.5：由步驟5.4所述的當前數據交付節點K，其自身是否已經收到攜帶有如步驟5.3所述當前數據全部傳送完成的標志的數據包，若已收到則執行步驟5.6，否則，重新執行步驟5.4；

步驟5.6：由步驟5.4所述的當前數據交付節點K判斷，其自身如步驟2.6所述到目標節點B的總跳步數的初始值T_初是否等于1，若T_初等于1則所述當前數據交付節點K將自身待傳送數據全部傳給目標節點B并在完成全部數據的傳送后終止當前的傳送任務；若前述T_初不等于1則所述當前數據交付節點K將其自身視作如步驟三所述的一個全新的數據源節點，并重新執行步驟三。