一種基于Torus網絡的高效隨機Oblivious路由算法
2017-03-22 12:41:33任一曼
軟件工程 2017年1期
任一曼
摘 要：一個好的路由算法應同時滿足：最小的路由跳數以減小傳輸延時，保持通訊的局域性；最大的平均情況和最壞情況吞吐率；簡單的路由器結構。隨機Oblivious路由算法在低功耗并行計算機互聯網絡以及片上網絡中得到廣泛應用。針對Torus網絡下已提出的Oblivious路由算法所需虛通道數目多的缺點，提出了隨機Oblivious路由算法WRD，該算法僅使用兩條虛擬通道即可實現算法的無死鎖性。通過仿真對所提算法的性能進行了驗證，結果表明，該算法與使用兩條虛擬通道的O1TURN路由算法相比，WRD路由算法在所有通訊模式下的網絡吞吐率均有所提升。與使用四條虛擬通道的RLB算法相比，新提出的WRD路由算法性能接近于RLB算法，甚至在多個通訊模式下的網絡吞吐率要好于RLB算法，而且WRD路由算法僅使用兩條虛擬通道，降低了網絡系統成本和功耗。
關鍵詞：Torus網絡；隨機Oblivious路由算法；平均情況網絡吞吐率；最壞情況網絡吞吐率；虛擬通道
中圖分類號：TP393 文獻標識碼：A
