@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 {Simula.ND.41,
	title = {A Survey and Evaluation of Topology Agnostic Routing Algorithms},
	journal = {IEEE Transactions on Parallel and Distributed Systems},
	volume = {23},
	number = {3},
	year = {2012},
	month = {March},
	pages = {405-425},
	publisher = {IEEE},
	abstract = {Most standard interconnect technologies that have emerged over the last decade, mainly for clusters, are flexible with respect to network topology. This has spawned a substantial amount of research on topology agnostic routing algorithms, and some of the developed algorithms are widely deployed. These algorithms make no assumption about the structure of the network, thus they provide the flexibility needed to route on a network in the presence of faulty components. On the other hand, the advent of massive multi-core chips challenges the state of the art in interconnection networks. The topology of choice for point to point Networks on-chip (NoC) is the two dimensional mesh which is well understood, but the need of high yield, out of a production line for such chips requires that they should be functional even if some components suffer from manufacturing defects. Such defects will turn the regular topology into a slightly irregular one, making topology dependent routing algorithms inapplicable. Also, heterogeneous multi-core chips, where different cores could have different sizes and shapes, naturally lead to (slightly) irregular topologies. Therefore, topology agnostic routing algorithms proposed for clusters find a new environment to be applied since they provide the flexibility needed to route on a NoC in the presence of faulty or missing components. Moreover, in some cases, they have been shown to perform comparably to special purpose algorithms for regular topologies. Unfortunately, the existing topology agnostic routing algorithms have been developed for varying purposes, giving them different and not always comparable properties. Furthermore, the information on these routing algorithms is scattered on different papers where they have been evaluated under different and not comparable conditions. In this paper, we present a comprehensive overview of the topology agnostic routing algorithms that have been proposed to date. The algorithms are classified with respect to their most important properties, and their performance under equal, but varying conditions is analyzed. Thereby, we provide significant new insight into the properties of the different routing algorithms, and give substantial support for, given a set of requirements, finding the most suitable both for the on and off-chip environments.},
	author = {Flich, Jos{\'e} and Skeie, Tor and Mej{\'\i}a, Andres and Lysne, Olav and Lopez, Pedro and Robles, Antonio and Duato, Jose and Koibuchi, Michihiro and Rokicki, Tomas and Sancho, Jos{\'e}}
}
@article {Simula.simula.410,
	title = {Region-Based Routing: a Mechanism to Support Efficient Routing Algorithms in NoCs},
	journal = {IEEE Transactions on Very Large Scale Integration},
	volume = {17},
	number = {3},
	year = {2009},
	pages = {356-369},
	publisher = {IEEE},
	author = {Mejia, A. and Palesi, M. and Flich, J. and Kumar, S. and Lopez, Pedro and Holsmark, R. and Duato, Jose}
}
@inproceedings {Simula.simula.420,
	title = {Deterministic Versus Adaptive Routing in Fat-Trees},
	journal = {IEEE International Parallel and Distributed Processing Symposium},
	year = {2007},
	pages = {292-300},
	publisher = {IEEE Computer Society},
	type = {1},
	isbn = {1-4244-0909-8},
	author = {Gomez, C. and Gilabert, F. and M. E. {G{\'o}mez} and Lopez, Pedro and Duato, Jose},
	editor = {Dhabaleswar K. {Panda}}
}
@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}
}
@inproceedings {Mora.2006.1,
	title = {Towards and Efficient Switch Architecture for High-Radix Switches},
	journal = {ACM/IEEE Symposium on Architectures for Networking and Communications Systems},
	year = {2006},
	month = {December},
	pages = {11-20},
	publisher = {ACM Press},
	type = {Conference},
	isbn = {1-59593-580-0},
	author = {Mora, Gaspar and Flich, Jos{\'e} and Duato, Jose and Lopez, Pedro and Lysne, Olav},
	editor = {Dubois, Michel and Eatherton, Will}
}
@inproceedings {ND.5.Gomez.2004,
	title = {An Effective Fault-Tolerant Routing Methodology for Direct Networks},
	journal = {Proceedings of International Conference on Parallel Processing},
	year = {2004},
	month = {August 15-18},
	pages = {222-231},
	publisher = {IEEE Computer Society Press},
	type = {1},
	abstract = {Current massively parallel computing systems are being built with thousands of nodes, which significantly affect the probability of failure. M. E. Gomex proposed a methodology to design fault-tolerant routing algorithms for direct interconnection networks. The methodology uses a simple mechanism: for some source-destination pairs, packets are first forwarded to an intermediate node, and later, from this node to the destination node. Minimal adaptive routing is used along both subpaths. For those cases where the methodology cannot find a suitable intermediate node, it combines the use of intermediate nodes with two additional mechanisms: disabling adaptive routing and using misrouting on a per-packet basis. While the combination of these three mechanisms tolerates a large number of faults, each one requires adding some hardware support in the network and also introduces some overhead. In this paper, we perform an in-depth detailed analysis of the impact of these mechanisms on network behaviour. We analyze the impact of the three mechanisms separately and combined. The ultimate goal of this paper is to obtain a suitable combination of mechanisms that is able to meet the trade-off between fault-tolerance degree, routing complexity, and performance.},
	author = {M. E. {G{\'o}mez} and Flich, J. and Lopez, Pedro and Robles, Antonio and Duato, J. and N. A. {Nordbotten} and Lysne, Olav and Skeie, Tor}
}
@article {ND.4.Gomez.2004,
	title = {An Efficient Fault-Tolerant Routing Methodology for Meshes and Tori},
	journal = {IEEE Computer Architecture Letters},
	volume = {3},
	year = {2004},
	month = {May},
	pages = {3},
	publisher = {IEEE},
	abstract = {In this paper we present a methodology to design fault-tolerant routing algorithms for regular direct interconnection networks. It supports fully adaptive routing, does not degrade performance in the absence of faults, and supports a reasonably large number of faults without significantly degrading performance. The methodology is mainly based on the selection of an intermediate node (if needed) for each source-destination pair. Packets are adaptively routed to the intermediate node and, at this node, without being ejected, they are adaptively forwarded to their destinations. In order to allow deadlock-free minimal adaptive routing, the methodology requires only one additional virtual channel (for a total of three), even for tori. Evaluation results for a 4x4x4 torus network show that the methodology is 5-fault tolerant. Indeed, for up to 14 link failures, the percentage of fault combinations supported is higher than 99.96\%. Additionally, network throughput degrades by less than 10\% when injecting three random link faults without disabling any node. In contrast, a mechanism similar to the one proposed in the BlueGene/L, that disables some network planes, would strongly degrade network throughput by 79\%.},
	doi = {10.1109/L-CA.2004.1},
	author = {M. E. {G{\'o}mez} and Duato, J. and Flich, J. and Lopez, Pedro and Robles, Antonio and N. A. {Nordbotten} and Lysne, Olav and Skeie, Tor}
}
@inproceedings {ND.5.Nordbotten.2004,
	title = {A Fully Adaptive Fault-Tolerant Routing Methodology Based on Intermediate Nodes},
	journal = {Proceedings of IFIP International Conference on Network and Parallel Computing},
	year = {2004},
	month = {October 18-20},
	pages = {341-356},
	publisher = {Springer-Verlag},
	type = {1},
	abstract = {Massively parallel computing systems are being built with thousands of nodes. Because of the high number of components, it is critical to keep these systems running even in the presence of failures. Interconnection networks play a key-role in these systems, and this paper proposes a fault-tolerant routing methodology for use in such networks. The methodology supports any minimal routing function (including fully adaptive routing), does not degrade performance in the absence of faults, does not disable any healthy node, and is easy to implement both in meshes and tori. In order to avoid network failures, the methodology uses a simple mechanism: for some source-destination pairs, packets are forwarded to the destination node through a set of intermediate nodes (without being ejected from the network). The methodology is shown to tolerate a large number of faults (e.g., five/nine faults when using two/three intermediate nodes in a 3D torus). Furthermore, the methodology offers a gracious performance degradation: in an 8 {\texttimes} 8 {\texttimes} 8 torus network with 14 faults the throughput is only decreased by 6.49\%.},
	author = {N. A. {Nordbotten} and M. E. {G{\'o}mez} and Flich, J. and Lopez, Pedro and Robles, Antonio and Skeie, Tor and Lysne, Olav and Duato, J.}
}
@inproceedings {ND.5.Skeie.2004,
	title = {LASH-TOR: a Generic Transition-Oriented Routing Algorithm},
	journal = {Proceedings of the IEEE International Conference on Parallel and Distributed Systems (ICPADS)},
	year = {2004},
	pages = {595-604},
	publisher = {IEEE Computer Society Press},
	type = {1},
	author = {Skeie, Tor and Lysne, Olav and Flich, J. and Lopez, Pedro and Robles, Antonio and Duato, J.}
}
@inproceedings {ND.5.Gomez.2004.b,
	title = {A New Adaptive Fault-Tolerant Routing Methodology for Direct Networks},
	journal = {Proceedings of the International Conference on High Performance Computing},
	year = {2004},
	month = {December 19-22},
	pages = {462-473},
	publisher = {Springer-Verlag},
	type = {1},
	abstract = {Interconnection networks play a key role in the fault tolerance of massively parallel computers, since faults may isolate a large fraction of the machine containing many healthy nodes. In this paper, we present a methodology to design fully adaptive fault-tolerant routing algorithms for direct interconnection networks that can be applied to different regular topologies. The methodology is mainly based on the selection of an intermediate node (if needed) for each source-destination pair. Packets are adaptively routed to the intermediate node and, from this node, they are adaptively forwarded to their destination. This methodology requires only one additional virtual channel, even for tori. Evaluation results show that the methodology is 7-fault tolerant, and for up to 14 faults, more than 99\% of the combinations are tolerated, also without significantly degrading performance in the presence of faults.},
	author = {M. E. {G{\'o}mez} and Duato, J. and Flich, J. and Lopez, Pedro and Robles, Antonio and N. A. {Nordbotten} and Skeie, Tor and Lysne, Olav}
}
