應用於寬頻頂端樹狀網路之局部具容錯之 群播路由器的設計與實作

Design and Implementation of a Local Fault-Tolerant Multicast Router in Fat Trees

李冠賦(Kuan-Fu Li)

指導教授 ： 邱瀞德

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2012年)

https://doi.org/10.6843/NTHU.2012.00548

摘要

對於大規模fat-tree 網路，除了效能與容錯的能力之外,其網路路由器所佔的面
積與消耗功率也是一個重要的議題。在本篇論文中，我們設計與實作了一個應用
於fat tree 網路架構下之具容錯的局部群播路由器，應用於k-ray n-tree 的
fat-tree 網路，具有無死結以及在k 個錯誤同時發生時的仍具連接性。路徑選
擇演算法會利用路由器及接收端的位址來決定要送往的路徑。利用切割封包成
flit 循環送出的方法及群播先行的方法來避免死結的發生。我們改良了使用於
紀錄與分配flit 新舊ID 的表格架構，以減少其所占的面積與消耗的功率。而
在群播優先設計中所需的flit 選擇與傳送的優先權安排架構，我們發展一個新
的機制，用來除去多餘的訊號。於容錯中，我們設計了一個改良的路徑選擇模組，
以減少在路由器中的訊號連線。為了評估面積和功率，我們使用的verilog 進行
實作，來模擬評量所佔的面積與功率。最後與之前相關的論文做比較，我們提出
的設計相對於修改型fat tree(MFT)[8]與多重區域標識群播設計，當網路架構
為2元6樹時，我們提出的設計所占的面積與功率已小於多重區域標識群播設計，
而與修改型的fat tree(MFT)的面積與功率相近。當網路架構增大至2 元7 樹時，
我們提出的設計相對於修改型fat tree(MFT)[8]與多重區域標識群播設計都有
較小的面積與消耗功率。為了減少flit 在容錯傳播上的延遲，我們採用one-hop
向量來分辨出故障之路由器，容錯性能提高。我們設計的路由器的面積和功率的
增長是非常緩慢的，這意味著我們所提出的方案是適合大規模fat-tree 路由器
設計。

關鍵字

群播路由 ； 資料中心網路 ； 動態容錯 ； 路由器設計

並列摘要

Besides performance and fault tolerance, area and power are the important issues
in large scale fat-tree networks. In this work, we implement a router with local
fault-tolerant multicast routing that guarantees connection and deadlock-free in
k-ray n-tree up to k simultaneous faults. The
it is routed by the label of the
routers and processing nodes. We design a modied ID table to reduce the table
size, and develop a method to remove the extra signal in priority arrangement for
solving the problem of the multicast-rst routing mechanism. For fault tolerance,
we design a modied path selection to decrease the interconnection in a router.
To evaluate area and power of the proposed schemes, we use the verilog to im-plement the proposed scheme and related works. Compared to the modied fat
tree(MFT)[8]and MLID, when fat tree size increase to 2-ary 6-tree, the area and
power of our proposed scheme is smaller than MLID, and closed to the MFT. In
2-ary 7-tree, the area and power of our proposed method are smaller than that
of the MFT and MLID. To reduce the extra latency, the proposed scheme adopts
the one-hop vector to detect link and switch faults. When the one-hop vector is
used, the performance increases up to 42%. Because of the local routing scheme,
the growth of the area and power of the proposed scheme is very slow that means
our proposed scheme is suitable for large scale fat tree router design.

並列關鍵字

Multicast routing ； Data center ； Dynamic fault tolerance ； Router design

參考文獻

[2] X. Lin, Y. Chung, and T. Huang, A Multiple LID Routing Scheme for Fat-Tree-Based InniBand Networks," in Proc. IEEE International Paral lel and

[4] S. Coll, F. J. Mora, J. Duato, and F. Petrini, Ecient and Scalable Hardware-Based Multicast in Fat-Tree Networks," IEEE Transactions on Paral lel and

A Dynamic Fault-Tolerant Routing Methodology for Fat Trees with Exclusion

[6] F. O. Sem-Jacobsen, T. Skeie, O. Lysne, and J. Duato, Dynamic Fault Tol-erance in Fat Trees," IEEE Transactions On Computers, vol. 60, no. 4, pp.

508-525, Apr. 2011.