Abstract
Performance and fault-tolerance are two dominant issues in large scale fat-trees. In this work, we present a local fault-tolerant multicast routing that guarantees connection and deadlock-free in k-ray n-tree up to k simultaneous faults. For multicast, the path selection utilizes labels of the fat-tree to decide outgoing ports. The multicast-first and the flit-by-flit round robin scheduling are adopted to solve multicast deadlocks. For fault-tolerance, the one-hop vectors stores and determines the link fault status of a switch. The end-routing vector records the number of switch faults in a routing path to avoid unnecessarily re-routing. In addition, we build a spare broadcast tree for fault-tolerance under the worst fault cases including switch faults at the bottom level of the fat-tree. To evaluate performance of the proposed schemes, we have developed a systemC simulator for k-ray n-tree. Compared to the unicast, the multiple local identifier routing scheme(MLID), and the hardware-based Multicast(HWm), the proposed method increases throughput by up to 220%, 85%, and 16% respectively in the adjacent traffic pattern. The average latency of the proposed algorithm is 21% more than the unicast, 62% less than that of MLID and 25% less than that of HWm under the random traffic. Techniques used to realize faulttolerance are often at the expense of considerable performance degradation. Our proposed scheme has a graceful degradation in performance and a moderate increase in area overhead as the number of link or switch faults in the system increases.