一種基于Torus網(wǎng)絡(luò)的高效隨機(jī)Oblivious路由算法

任一曼

摘 要：一個(gè)好的路由算法應(yīng)同時(shí)滿足：最小的路由跳數(shù)以減小傳輸延時(shí)，保持通訊的局域性；最大的平均情況和最壞情況吞吐率；簡(jiǎn)單的路由器結(jié)構(gòu)。隨機(jī)Oblivious路由算法在低功耗并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)以及片上網(wǎng)絡(luò)中得到廣泛應(yīng)用。針對(duì)Torus網(wǎng)絡(luò)下已提出的Oblivious路由算法所需虛通道數(shù)目多的缺點(diǎn)，提出了隨機(jī)Oblivious路由算法WRD，該算法僅使用兩條虛擬通道即可實(shí)現(xiàn)算法的無(wú)死鎖性。通過(guò)仿真對(duì)所提算法的性能進(jìn)行了驗(yàn)證，結(jié)果表明，該算法與使用兩條虛擬通道的O1TURN路由算法相比，WRD路由算法在所有通訊模式下的網(wǎng)絡(luò)吞吐率均有所提升。與使用四條虛擬通道的RLB算法相比，新提出的WRD路由算法性能接近于RLB算法，甚至在多個(gè)通訊模式下的網(wǎng)絡(luò)吞吐率要好于RLB算法，而且WRD路由算法僅使用兩條虛擬通道，降低了網(wǎng)絡(luò)系統(tǒng)成本和功耗。

關(guān)鍵詞：Torus網(wǎng)絡(luò)；隨機(jī)Oblivious路由算法；平均情況網(wǎng)絡(luò)吞吐率；最壞情況網(wǎng)絡(luò)吞吐率；虛擬通道

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A