A fault-tolerant routing strategy for k-ary n-direct s-indirect topologies based on intermediate nodes

摘要

Exascale computing systems are being built with thousands of nodes. The high number of componentsrnof these systems significantly increases the probability of failure.Akey component for themrnis the interconnection network. If failures occur in the interconnection network, theymay isolaterna large fraction of the machine. For this reason, an efficient fault-tolerant mechanism is neededrnto keep the system interconnected, even in the presence of faults. A recently proposed topologyrnfor these large systems is the hybrid k-ary n-direct s-indirect family that provides optimal performancernand connectivity at a reduced hardware cost. This paper presents a fault-tolerant routingrnmethodology for the k-ary n-direct s-indirect topology that degrades performance gracefully inrnpresence of faults and tolerates a large number of faults without disabling any healthy computingrnnode. In order to tolerate network failures, the methodology uses a simple mechanism. For anyrnsource-destination pair, if necessary, packets are forwarded to the destination node through a setrnof intermediate nodes (without being ejected from the network) with the aim of circumventingrnfaults. The evaluation results shows that the proposed methodology tolerates a large number ofrnfaults. For instance, it is able to toleratemore than 99.5% of fault combinations when there are 10rnfaults in a 3-D network with 1000 nodes using only 1 intermediate node and more than 99.98%rnif 2 intermediate nodes are used. Furthermore, the methodology offers a gracious performancerndegradation.Asan example, performance degrades onlyby1%for a2-D network with1024nodesrnand 1%faulty links.