不規則網絡拓撲結構下的多棵樹路由算法研究

宋冠軍，韓江雪

（1.華北計算技術研究所，北京100083；2.清華大學 軟件學院，北京100084）

0 引 言

對于互聯網絡而言，她主要由下述4個部分組成：路由算法、流控技術、交換技術和拓撲結構。在上述四部分中，核心部分是路由算法。也就是說，影響性能的關鍵的因素在于如何給某一拓撲網絡設計適合的路由算法，讓其在進行消息傳遞時花費相對較少的時間。

當前已經有很多用于構造機群系統的交換式高速互聯網，其中Myinet，Autonet，等都是已經成熟的幾個。這些網絡，一般采用不規則的拓撲結構和蟲孔路由交換技術。然而由于不規則網絡拓撲結構的復雜性和不可控性，網絡中出現環路即通信重疊的可能性大大增加，進而網絡中更加容易出現死鎖現象。

Sancho，等［1］提出了一種基于深度優先搜索的多棵樹路由算法，從而降低了傳統breadthfirst路由算法的路由表數量，它的啟發式up／down生成算法，大大提高了路由的效率。Puente，等［2］提出了一種基于不規則網絡以偽哈密頓周期為基礎的自適應路由機制，明顯削減了傳統的up＊／down＊路由算法的額外開銷，有效地避免死鎖的出現，但也同時造成了路由路徑的增長。A.Jouraku的文章［3］提出的一種自適應路由算法，使數據包分布的盡可能均衡。Levitin，Karpovsky，和 Mustafa［4］中提出的新算法通過保證最小的路由回路被禁止以消除思索和維護圖的連通性。

因此，如何提高系統性能并避免死鎖，是本論文主要討論與解決的問題，也是本研究的核心貢獻所在。up＊／down＊路由現在已被廣泛使用，在包括上文提及的多篇論文［5－11］中分別對NOWs系統路由進行了不同角度的闡述，但是這些路由方法存在很多問題，比如自適應性差，根節點的瓶頸等問題。在此之上，本文將提出一種新的路由機制即多根節點自適應路由，來在一定程度上彌補原始up＊／down＊路由方式的不足。

1 不規則網絡拓撲結構下的算法介紹

1.1 NOWS體系的構成

本文的研究對象是不規則網絡的路由新機制。其基本的體系結構如圖1所示。

圖1 基于開關的不規則互聯網絡

基于開關的不規則互連網絡主要由開關（switch），處理單元（processing elements）和雙向物理鏈路（bidirectional link）組成。

圖1中可以看到，0－8號是開關（Switch），每個開關上有若干個端口（此圖為8個端口）。每個端口可以連接其他開關的端口，也可以連接本地處理單元（processing elements，PE），還可以空閑不接。

本文以不規則開關網絡為研究對象，所提出的算法可以應用到所有不規則網絡。

一個互連網絡可以用網絡拓撲、交換機制、流控機制和路由算法來描述。由于課題本身已經限制了研究的對象是不規則的拓撲網絡結構，因此主要著重于對交換機制、流控機制和路由算法做出更有效率的改進。

1.2 up＊／down＊路由算法

網絡的路由算法也分為直接網絡的路由和間接網絡的路由，規則網絡的路由和不規則網絡的路由。

本文這里濾去與核心問題不相關的部分，集中介紹不規則間接網絡的路由研究情況。

規則網絡中由于拓撲結構的可控制性，使得一些死鎖問題變得簡單。然而，在網絡拓撲不規則的前提下，路由算法的設計就變得十分困難，尤其是如何解決死鎖避免就更困難了。現有的路由算法只是解決了網絡的死鎖問題，然而與此同時在網絡的其他特性上就無法兼得。這里主要介紹經典的up＊／down＊路由算法。

up＊／down＊路由算法是一種禁止拐彎模型，在DEC Autonet網絡的路由算法中首次被提出。簡單來說，up＊／down＊路由算法的目的是給每條鏈路標注上方向（up）或下方向（down），將網絡改造成一個無回路的有向圖，最后禁止消息由下方向拐向上方向，以此避免了路由算法中的死鎖。

下面為up＊／down＊算法的步驟：

在拓撲網絡中選擇一個根節點（通常為節點ID最小的那個節點），以該節點為根，生成整個拓撲網絡的寬度優先搜索樹（BFS樹）；

指定每條物理鏈路的方向。對于鏈路的上方向（up）定義如下：當鏈路連接的兩個節點處在BFS中深度不同的兩層時，從層數較深的節點指向層數較淺的節點的方向為上；當鏈路連接的兩個節點處在BFS中深度相同的兩層時，從ID較大的節點指向ID較小的節點的方向為上。和上述上方向（up）相反的方向即為下方向（down）；

計算路由表。對于每個節點計算它與其他各個節點的最短路徑，但是為了避免死鎖，路徑中只允許出現從上到上（up to up）、從下到下（down to down）和從上到下（up to down）3種拐彎，從下到上（down to up）是非法的。通過屏蔽環路形成條件中的一個，我們能夠確保最后生成的路由路徑不存在回路依賴關系，也就避免了死鎖。

圖2顯示了一個包含9個結點的網絡圖G（V，E），圖3（圖中箭頭方向為up方向）所對應的廣度優先搜索（BFS）生成樹T（G）以及該生成樹各個邊上方向的指定情況。需要注意的一點是對于每條邊的up方向通道，都有一條反向的down方向的通道組成雙向連接，考慮到圖示效果需清晰的原則，該圖中未標出down方向。

圖2 基于開關的不規則拓撲及其通道相關

up＊／down＊算法的優勢在于全部結點的硬件構造與軟件設計簡易，與此同時該算法還提供了一定的網絡自適應性。

但是，up＊／down＊算法也存在許多缺點。比如：

首先，由于路由算法背身的算法原理，導致在很多情況下所選的路徑并不是最短路徑，這樣一來，消息的傳輸延時明顯上升，嚴重影響網絡性能。

第二，由于樹本身的結構使然，網絡擁塞容易趨向于根結點附近，同時較難疏散，這就是的網絡關鍵路徑傳輸效率大幅降低，直接影響了網絡的吞吐率。

最后，由于算法在高層結點處即算法對應生成樹的葉結點處屏蔽的轉彎數較多，使得整個網絡的通道利用率出現了嚴重的不平衡，降低了網絡的性能。并且隨著網絡規模的擴大，上述問題變得尤其凸顯。

2 多棵樹路由算法

在上節中，介紹了不規則網絡拓撲中的一種無死鎖算法up＊／down＊算法。但是該算法有許多顯而易見的問題，主要有以下三點問題最為嚴重：

第一網絡中單根節點的路由會使得網絡的負載分布不平衡，進而使得根節點成為網絡的瓶頸；第二由于拐彎的限制使得高層節點附近通道利用率增加；第三網絡中路由的平均距離明顯增加。這是我們研究多棵樹路由算法的直接動機。

那么我們所提出的新路由算法就應該具有以下長處：新路由算法要做到平衡各個通道之間的負載，不能出現網絡的負載大部分集中在少部分通道的情況；新路由算法要盡量降低網絡中鏈路的長度，同時還要兼顧避免或減少死鎖發生的特性；若新路由算法可能包含死鎖，那么應含有解決死鎖的流控機制。

多棵樹路由算法就是將以上三點作為研發的最終目的而提出的一種新的路由算法。

本文所提出的多棵樹路由算法由三部分組成，第一部分是路由表的生成規則，也就是路徑的生成算法；第二部分是多棵樹路由采用的交換技術；第三部分是多棵樹路由采用的流控機制，其中包括平時的流控方式和產生死鎖后用于死鎖恢復的特殊流控方式。

2.1 路由表的生成算法

我們將圖2所對應的不規則網絡拓撲適當簡化，去掉雙鏈路，將之抽象后得到如圖4所示的模擬拓撲結構。

圖4 原始物理模型抽象簡化后的模擬拓撲結構

根據圖4的模擬拓撲結構，我們分別選擇節點1或者節點8為根節點，按照up＊／down＊規則產生的路由路徑是不同的，在總共的72條路徑中，有17條發生了變化，其中以節點8為根節點產生的新路徑比原路徑短的有四條，新路徑比原路徑長的同樣是四條，而新路徑和原路徑一樣長的有九條。若我們將原來的節點1稱為主根，節點8稱為輔助根，在輔助根生成的新路由表中選擇那些比原有路由表短的路徑代替主根生成的路由表，那么就可以起到縮減路由表中鏈路的平均長度、平衡主根節點附近通道負載的作用。我們將這種在原有主根基礎上增加輔助根的路由算法稱為多棵樹路由算法。

該算法的具體定義如下：

算法1：createMTRRouter（net，n）

功能：多棵樹路由表生成算法

輸入：用無向圖表示的不規則拓撲網絡net，根節點數量n

輸出：路由表routerTable

過程：

1.隨機選定一個節點r作為主根節點；

2.net＝setLevel（net，r）；

3.routerTable＝findRoute（net）；

4.for（k＝1；k＜n；k＋＋ ）

5.隨機選定一個節點r’作為副根節點；

6.net＝setLevel（net，r’）；

7.routerTable’＝findRoute（net）；

8.for（i＝0；i＜net中的節點數 ；i＋＋）

9.for（j＝0；j＜net中的節點數 ；j＋＋）

10.if（routerTable［i］［j］.length＞ router－Table’［i］［j］.length）

11.將routerTable［i］［j］的路徑替換成routerTable’［i］［j］的路徑；

12.end if

13.end for

14.end for

15.end for

16.返回routerTable；

算法2：setLevel（net，root）

功能：對一個不規則拓撲網絡中的鏈路設定方向。

輸入：鏈路未分配方向的拓撲網絡net，根節點的ID root。

輸出：鏈路已分配方向的拓撲網絡net。

過程：

1.根據root節點，用BFS算法計算所有節點的深度；

2.for（net的第一條鏈路k－＞最后一條鏈路）

3.if（k的源節點深度 ＞k的目的節點深度 ）

4.k的方向附為0； ／／up

5.end if

6.if（k的源節點深度 ＜k的目的節點深度 ）

7.k的方向附為1； ／／down

8.end if

9.if（k的源節點深度＝＝k的目的節點深度）

10.if（k的源節點ID＞ k的目的節點ID）

11.k的方向附為0； ／／up

12.end if

13.if（k的源節點ID＜ k的目的節點ID）

14.k的方向附為1； ／／down

15.end if

16.end if

17.end for

18.返回net；

算法3：findRoute（net）

功能：對一個拓撲網絡建立路由表。

輸入：鏈路已分配方向的拓撲網絡net。

輸出：路由表routerTable。

過程：

1.for（i＝0；i＜net的節點數 ；i＋＋ ）

2.for（j＝0；j＜net的節點數 ；j＋＋ ）

3.visit［節點j］＝false； ／／訪問記錄

4.end for

5.for（節點i的第一條鏈路link－＞ 節點i的最后一條鏈路）

6.if（visit［link的目的節點］＝＝false）

7.visit［link的目的節點］＝true；

8.nodeQueue.addLast（link的目的節點）；

9.directionQueue.addLast（link的方向）；

10.linkQueue.addLast（new queue（link））；

11.routerTable［i］［link的目的節點］.add（link）；

12.end if

13.end for

14.while（nodeQueue不為空）

15.node＝nodeQueue.removeFirst；

16.lastDirection＝directionQueue.removeFirst；

17.lastRoute＝linkQueue.removeFirst；

18.for（節點node的第一條鏈路link－＞ 節點i的最后一條鏈路）

19.if（visit［link的目的節點］＝＝false）

20.if（link的方向 ＞＝lastDirection）

21.／／只允許路徑中出現0－＞0，0－＞1，1－＞1的拐彎，屏蔽1－＞0的拐彎

22.visit［link的目的節點］＝true；

23.nodeQueue.addLast（link的目的節點）；

24.directionQueue.addLast（link的方向）；

25.newRoute＝lastRoute.copy；

26.newRoute.addLast（link）；

27.routerTable［i］［link的目的節點］.add（newRoute）；

28.linkQueue.addLast（newRoute）；

29.end if

30.end if

31.end for

32.end while

33.end for

34.返回routerTable；

通過該算法，我們就得到了用多棵樹算法計算得到的路由表。但是由于將輔助根的路由表的一部分替換掉了主根生成的路由表，因此up＊／down＊規則產生的無死鎖特性將不復存在。因此，我們需要在流控方式上采取與up＊／down＊算法不同的，帶有死鎖恢復功能的特殊流控方式。

2.2 多棵樹路由的流控機制

我們知道兩種解決死鎖問題的流控機制，虛通道和冒泡通道。通過研究兩種流控方式我們發現，以一條物理通道劃分為兩條虛通道為例，虛通道流控機制在沒有死鎖發生時，只有一條虛擬通道被利用，物理通道的利用率很低，在死鎖發生后可以通過第二條虛擬通道有效的解決死鎖問題；冒泡通道的流控機制只拿出一個flit的buffer，即冒泡通道，來解決死鎖問題，在死鎖未發生時通道用幾乎全部的buffer來運送消息，但是一旦發生死鎖，系統就會選擇一條消息，用冒泡通道運送該消息，所以當死鎖發生時，每次只能運送一條消息，其他消息都要停滯。因此，虛通道技術在死鎖發生不頻繁時效率較低，而死鎖發生時效率較高；與之相反，冒泡通道在死鎖未發生時效率較高，但死鎖發生頻繁時效率較低。

我們發現，在多棵樹算法選用一個輔助根時，實際上路由表只有四條鏈路選擇了比原來只有主根的時候更短的路由路徑，因此，表中的絕大部分路徑還是滿足原來的up＊／down＊算法提供的無死鎖特征的。那么可以想見，在系統實際運行、系統負載不高的情況下，一定是處于正常狀態的時間更長，而只有少數時間處在死鎖狀態。因此如果我們選擇虛通道的流控方式，等于在絕大部分時間內都處于效率不高的正常狀態。因此，我們在多棵樹路由算法中，選擇冒泡通道作為系統的特殊流控機制。

2.3 多棵樹路由的交換機制

我們知道兩種最為常見的交換方式，虛跨步交換和蟲孔交換。兩種交換方式的主要區別在于，虛跨步交換在消息發生堵塞時依然轉移報文，因此需要每個通道的buffer至少要能夠緩沖整個消息；而蟲孔交換在消息發生堵塞時，就地緩沖報文，不再向前推進，所以對通道的buffer長度沒有要求，在buffer較小的情況下依然適用（理論上只有一個flit就夠）。但是一旦拉得很長的消息被就地緩沖，勢必會引起更多消息的堵塞，造成更多的死鎖。

在蟲孔交換和虛通道流控被廣泛使用的現在，研究人員會在不規則網絡中考慮將這兩種方式聯合使用。然而，西班牙瓦倫西亞大學的J.Duato先生等人在中指出在不規則網絡中蟲孔交換并不是最好的選擇，通過測試比較發現：

（1）對于蟲孔交換緩沖空間的大小限制了線路的長度，然而虛跨步交換就不會出現這樣的問題。

（2）由于在報文阻塞時蟲孔交換就地緩沖報文，而虛跨步轉移報文，所以虛跨步方式使得路由具有了更大的自適應性。

（3）在簡單的開關架構之下，虛跨步交換表現出與蟲孔交換相同的性能，在長報文的情況下，表現更為出色。

網絡的鏈路的不確定性從而使得網絡延時和緩沖及通道等資源難以確定。該論文指出，在不規則拓撲網絡中虛跨步交換技術是最合理的選擇。在通道的buffer不是非常珍惜的情況下，采取虛跨步交換在死鎖發生是也會有更好的表現。

3 算法性能模擬與比較

本實驗是通過模擬器仿真真實的機群環境，并通過調整模擬器的輸入參數來達到模擬不同的硬件條件下，多棵樹路由算法的表現。本文用于對照實驗的是經典的up＊／down＊路由算法，選取該算法作為對照是因為該算法是不規則拓撲網絡常用的路由算法之一，因此對照試驗的結果更有參考價值和意義。

我們進行了多種角度的實驗，因此在每條實驗結果前都會有關于該實驗條件的詳細說明。所有圖表中的數據都是在相同參數下反復試驗20次，以取平均值的方式得出的統計結果，因此結果的偶然性和隨機性很低，參考價值更大。

實驗中輸入參數的詳細說明如下：

·nodeNumber：網絡中的節點數，也就是網絡中的處理單元／開關數量；

·nodeBuffer：網絡中一條通道的緩沖區大小；

·degree：節點的出入度限制；

·totalCycle：系統運行的總周期數；

·messageLength：系統生成消息時的長度；

·messagePerCycle：系統每隔多少周期注入一條消息；

·rootNumber：多棵樹算法中根的總數；

·Continue：系統在執行完totalCycle之后是否繼續執行。

實驗結果反饋的輸出參數如下：

·AverageLength：平均長度，即路由表中所有路徑的平均長度；

·ArrivalPercentage：到達率，即totalCycle執行完畢時送到的消息占發送出的所有消息的百分比；

·Traffic－R：送達的消息總長度（以Flit為單位）／（總周期數＊網絡節點數），衡量網絡能力的重要參數之一；

·AddCycles：附加周期數，即totalCycle執行完后，系統又附加了多少周期才將系統中所有未送達的消息送達。

3.1 路由表平均路徑長度的比較

使用多棵樹算法解決了路由表中路徑過長的問題，我們測試時分別對節點數8、16、32、64，及degree＝2、3、4、5的情況下對兩種算法生成的路由表平均長度進行比較，其中多棵樹算法的rootNumber設為4。結果如圖5及圖6所示。

圖5 up＊／down＊算法平均路徑長度

從兩圖對比我們能夠明顯看出，多棵樹算法的平均路徑長度比相同條件下的up＊／down＊算法減少明顯，特別是在degree＝2的情況下，節點數為64的網絡的平均路徑由6.77827下降到4.69940，下降幅度高達30.6%。這說明多棵樹路由算法對降低路由平均路徑由非常明顯的效果。

圖7是一張逐漸增加輔助根節點，路徑平均長度的變化圖，節點數量固定在64個，從該圖中可以看出，隨著輔助根增加，路徑平均長度不斷減小，但輔助根數量從2增至3后，路徑長度變化已很不明顯，說明3個輔助根（root Number＝4）是一個比較理想的極值。

3.2 在負載變化的網絡中的性能比較

通過修改messagePerCycle參數的大小，我們可以任意修改消息注入的快慢。于是我們選擇nodeNumber＝64、nodeBuffer＝32、degree＝2、totalCycle＝10000、message－Length＝30作為不變量，來檢查messagePerCycle從9（網絡負載低）到3（網絡負載極高）的變化過程中，up＊／down＊算法和多棵樹（MTR）算法（rootNumber＝4）的各項指標差異，實驗結果如圖8～圖10所示。

圖8 AddCycles隨負載變化（節點數64）

我們可以看出，多棵樹算法在負載由低到高的過程中，性能發揮非常穩定。圖8中，當messagePerCycle從6變為5時，up＊／down＊算法的附加周期出現了一個突變，隨后則一路飆升；多棵樹路由算法的附加周期的增長卻十分緩慢，證明多棵樹路由算法依然能在短時間內將系統囤積的消息消耗掉。圖9也很好的證明了這一點，在高負載條件下，多棵樹算法的運載能力開始大幅度領先于up＊／down＊算法。圖10顯示了隨著系統的負載增大，消息在指定的周期內被送達目的節點的概率。多棵樹算法即使在系統負載很大的情況下，仍然能夠保持接近1的送達率；而up＊／down＊算法的送達率卻在高負載條件下出現了明顯的下滑。

為了證明多棵樹算法在不同網絡規模下的表現，我們又對節點數為32的網絡進行了同樣的實驗，實驗結果證明32個節點產生的結果基本與64節點下的實驗結果相類似。

64節點和32節點均屬于大規模網絡，那么為了驗證在小型網絡（8節點、16節點）中兩種算法的效率如何，我們又進行了兩輪實驗，第一輪針對16節點的網絡（nodeNumber＝16、nodeBuffer＝32、degree＝2、totalCycle＝10000、messageLength＝30），二輪針對8節點網絡的實驗（nodeNumber＝8、nodeBuffer＝32、degree＝2、totalCycle＝10000、messageLength＝30），8節點的小規模網絡的實驗結果與16節點時類似，多棵樹的算法在高負載條件下的運載能力沒有明顯高于up＊／down＊算法；多棵樹算法的送達率在高負載情況下也有了明顯的下降。實驗結果顯示出多棵樹算法在網絡規模變小時出現了效率的下滑，究其原因，在于多棵樹算法提高網絡路由性能的主要途徑是降低了路由表路徑的平均長度，但當網絡規模變小時，up＊／down＊規則生成的路徑的平均長度本身就會減小，多棵樹算法的提升空間非常有限，而且由于多棵樹是有死鎖的算法，在平均路徑小的網絡中，死鎖的產生會更加頻繁，因此多棵樹算法在死鎖恢復上的開銷時間將會比網絡規模增大時更多。這兩種因素結合起來就導致了在網絡規模變小時，多棵樹路由算法的效率出現了下降。

通過以上3個參數的驗證，我們證明了多棵樹算法在網絡規模較大時存在很大優勢：對于系統的負載情況的敏感度遠遠低于up＊／down＊算法，在任何種類的負載下都能發揮出穩定的性能和表現。但在網絡規模較小時，多棵樹算法由于自身局限性效率有所下降，但還是略高于up＊／down＊算法。

3.3 實驗總結

多棵樹算法在靜態時的優越性。通過比較所生成路由表中路徑的平均長度，我們發現多棵樹算法在網絡規模較大時能夠有效地降低系統中路徑的平均長度，降幅最大可達30%，避免了up＊／down＊算法中個別路徑長度遠大于最短路徑長度的問題，但在網絡規模較小時，平均路徑長度的縮小量并不明顯；

多棵樹算法在動態時的優越性。通過比較負載增加時消息運送能力的變化，我們可以看出當網絡規模較大時，多棵樹算法對網絡負載的適應能力很強，無論是低負載狀態下還是高負載狀態下，消息送達率都穩定維持在1左右，這是up＊／down＊算法所遠遠達不到的，同時up＊／down＊算法在高負載時消息的消化處理時間陡然增高，但多棵樹算法依然平穩上升，且上升幅度只有up＊／down＊算法的5%，這說明多棵樹算法很好的處理了up＊／down＊算法因為過于強調無死鎖，而忽略了網絡自適應能力的問題。但是當網絡規模縮小時，由于路由表平均距離的縮小量有限，因此多棵樹路由算法出現效率下降的情況，對負載的增大也變的更為敏感，同時在死鎖恢復方面花了更多的時間開銷。但對比發現，多棵樹算法的效率還是要高于up＊／down＊算法。

4 結束語

本研究提出了一個針對不規則網絡拓撲結構的新算法－多棵樹路由算法，該算法大大降低了路由表的平均路徑長度，平衡了網絡中各個通道的利用率，同時能夠及時有效的進行死鎖恢復，解決了先前路由算法中通道負載集中、通道利用率低、路由表平均路徑長度過長的問題。當網絡規模較大時該算法表現了很強的自適應能力，和極高的效率；當網絡規模較小時也能夠有效地防止死鎖的出現。尤其針對不規則網絡該算法有很強的普適性。無論在靜態特性還是動態特性上都確實體現出了其優秀的能力，達到了我們預期的效果。但在小規模網絡時效率還有待進一步提升。

［1］Sancho J C，Robles A，Duato J.An effective methodology to improve the performance of the Up＊／Down＊ routing algorithm［J］.IEEE Trans on Parallel and Distributed Systems，2004，15（8）：740－754.

［2］Puente V，Gregorio J A，Vallejo F，et al.Highperformance adaptive routing for networks with arbitrary topology［J］.Journal of Systems Architecture，2006，52（6）：345－358.

［3］Jouraku A，Koibuchi M，Amano H.An effective design of deadlock－free routing algorithms based 2Dturn model for irregular networks［J］.IEEE Trans on Parallel and Distributed Systems，2007，18（3）：320－333.

［4］Levitin L，Karpovsky K，Mustafa M.Minimal sets of turns for breaking cycles in graphs modeling networks［J］.IEEE Trans Parallel and Distributed Systems，2010，21（9）：1342－1953.

［5］Moraveiji R，Sarbazi－Azad H，Zomaya A Y.A general methodology for routing in irregular networks［C］／／Proc 17th Euromicro Int Conf on Parallel，Distributed and Network－Based Processing，2009：155－160.

［6］Moraveiji R，Sarbazi－Azad H，Zomaya A Y.Multispanning tree zone－ordered label－based routing algorithms for irregular networks［J］.IEEE Trans on Parallel and Distributed Systems，2011，22（5）：817－832.

［7］Lysne O，Skeie T，Reiemo S，et al.Layered routing in irregular networks［J］.IEEE Trans on Parallel and Distributed Systems，2006，17（1）：51－65.

［8］Theiss I，Lysne O.FRoots：A fault－tolerant and topologyflexible routing technique［J］.IEEE Trans on Parallel and Distributed Systems，2006，17（10）：1136－1150.

［9］Akiya Jouraku.An effective design of deadlock－free routing algorithms based on 2Dturn model for irregular network［J］.IEEE Transactions on Parallel and Distributed Systems，2007，18（3）：320－333.

［10］Li Xiaoming，Fu Fangfa，Yang Chao，et al.A solution to irregular 2－D mesh topology network－on－chip［J］.Energy Procedia，2011，13：888－895.

［11］Moraveji R，Sarbazi－Azad H，Zomaya A Y.A general methodology for direction－based irregular routing algorithms［J］.Journal of Parallel and Distributed Computing，2010，70（4）：363－370.