@article {24639,
	title = {A Fault-Tolerant Routing Strategy for KNS Topologies Based on Intermediate Nodes},
	journal = {Concurrency and Computation: Practice and Experience},
	volume = {29},
	year = {2017},
	publisher = {John Wiley \& Sons, Ltd.},
	abstract = {Exascale computing systems are being built with thousands of nodes. The high number of components of these systems significantly increases the probability of failure. A key component for them is the interconnection network. If failures occur in the interconnection network, they may isolate a large fraction of the machine. For this reason, an efficient fault-tolerant mechanism is needed to keep the system interconnected, even in the presence of faults. A recently proposed topology for these large systems is the hybrid k-ary n-direct s-indirect (KNS) family that provides optimal performance and connectivity at a reduced hardware cost. This paper presents a fault-tolerant routing methodology for the KNS topology that degrades performance gracefully in presence of faults and tolerates a large number of faults without disabling any healthy computing node. In order to tolerate network failures, the methodology uses a simple mechanism. For any source-destination pair, if necessary, packets are forwarded to the destination node through a set of intermediate nodes (without being ejected from the network) with the aim of circumventing faults. The evaluation results shows that the proposed methodology tolerates a large number of faults. For instance, it is able to tolerate more than 99.5\% of fault combinations when there are ten faults in a 3-D network with 1,000 nodes using only one intermediate node and more than 99.98\% if two intermediate nodes are used. Furthermore, the methodology offers a gracious performance degradation. As an example, performance degrades only by 1\% for a 2-D network with 1,024 nodes and 1\% faulty links.},
	keywords = {exascale computing, fault-tolerant routing, hybrid topology, KNS topology},
	doi = {10.1002/cpe.4065},
	author = {Pe{\~n}aranda, Roberto and Maria Engracia {G{\'o}mez} and Lopez, Pedro and Ernst Gunnar {Gran} and Skeie, Tor}
}
@inproceedings {23935,
	title = {A New Fault-Tolerant Routing Methodology for KNS Topologies},
	journal = {2nd IEEE International Workshop on High-Performance Interconnection Networks in the Exascale and Big-Data Era (HiPINEB)},
	year = {2016},
	month = {03/2016},
	pages = {1-8},
	publisher = {IEEE},
	abstract = {Exascale computing systems are being built with thousands of nodes. A key component of these systems is the interconnection network. The high number of components significantly increases the probability of failure. If failures occur in the interconnection network, they may isolate a large fraction of the machine. For this reason, an efficient fault-tolerant mechanism is needed to keep the system interconnected, even in the presence of faults. A topology recently proposed for these large systems is the hybrid KNS family that provides good performance and connectivity at a reduced hardware cost. This paper present a fault-tolerant routing methodology for the KNS topology that degrades performance gracefully in the presence of faults and tolerates a reasonably large number of faults without disabling any healthy node. In order to tolerate network failures, the methodology uses a simple mechanism: for some sourcedestination pairs, only if necessary, packets are forwarded to the destination node through a set of intermediate nodes (without being ejected from the network) which allow avoiding faults. The evaluation results shows that the methodology tolerates a large number of faults. Furthermore, the methodology offers a gracious performance degradation. For instance, performance degrades only 1\% for a 2D-network with 1024 nodes and 1\% faulty links.},
	isbn = {978-1-5090-2121-5},
	doi = {10.1109/HIPINEB.2016.9},
	author = {Pe{\~n}aranda, Roberto and Ernst Gunnar {Gran} and Skeie, Tor and Maria Engracia {G{\'o}mez} and Lopez, Pedro},
	editor = {Pedro J. {Garcia} and Escudero-Sahuquillo, Jes{\'u}s}
}
@article {Gomez.2006.1,
	title = {A Routing Methodology for Achieving Fault Tolerance in Direct Networks},
	journal = {IEEE Transactions on Computers},
	volume = {55},
	number = {4},
	year = {2006},
	month = {April},
	pages = {400-415},
	abstract = {Massively parallel computing systems are being built with thousands of nodes. The interconnection network plays a key role for the performance of such systems. However, the high number of components significantly increases the probability of failure. Additionally, failures in the interconnection network may isolate a large fraction of the machine. It is therefore critical to provide an efficient fault-tolerant mechanism to keep the system running, even in the presence of faults. This paper presents a new fault-tolerant routing methodology that does not degrade performance in the absence of faults and tolerates a reasonably large number of faults without disabling any healthy node. In order to avoid faults, for some source-destination pairs, packets are first sent to an intermediate node and then from this node to the destination node. Fully adaptive routing is used along both subpaths. The methodology assumes a static fault model and the use of a checkpoint/restart mechanism. However, there are scenarios where the faults cannot be avoided solely by using an intermediate node. Thus, we also provide some extensions to the methodology. Specifically, we propose disabling adaptive routing and/or using misrouting on a per-packet basis. We also propose the use of more than one intermediate node for some paths. The proposed fault-tolerant routing methodology is extensively evaluated in terms of fault tolerance, complexity, and performance.},
	author = {Maria Engracia {G{\'o}mez} and Nils Agne {Nordbotten} and Flich, Jos{\'e} and Lopez, Pedro and Robles, Antonio and Duato, Jose and Skeie, Tor and Lysne, Olav}
}
