@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}}
}
@inproceedings {Simula.simula.516,
	title = {Yield-Oriented Evaluation Methodology of Network-on-Chip Routing Implementations},
	journal = {SOC{\textquoteright}09 Proceedings of the 11th international conference on System-on-chip},
	year = {2009},
	publisher = {IEEE},
	type = {Conference},
	isbn = {978-1-4244-4466-3},
	doi = {10.1109/SOCC.2009.5335667},
	author = {Samuel Rodrigo {Mocholi} and Hernandez, Carles and Flich, Jos{\'e} and Silla, Federico and Duato, Jose and Medardoni, Simone and Bertozzi, Davide and Mej{\'\i}a, Andres and Dai, Donglai},
	editor = {IEEE, }
}
@inproceedings {Reinemo.2007.1,
	title = {Boosting Ethernet Performance by Segment-Based Routing},
	journal = {Proceedings of the 15th Euromicro Conference on Parallel, Distributed and Network-based Processing (PDP 2007)},
	year = {2007},
	month = {February},
	pages = {55-62},
	publisher = {IEEE Computer Society Press},
	type = {Conference},
	abstract = {In this paper we embed an efficient topology agnostic routing algorithm with fault tolerance capabilities into back-pressured Ethernet technology. This makes it possible to use off-the-shelf equipment to build cost-effective systems with an efficient use of all network components. This stands in contrast to the inefficient use of network resources (links) supported by the Spanning Tree Protocol (STP). The Segment-Based Routing Algorithm (SR) is a deterministic routing algorithm that achieves high performance without the use of virtual channels. Furthermore, it is topology agnostic, meaning it can handle any topology and any combination of faults derived from the original topology when combined with static reconfiguration. Through simulations we verify an overall improvement in throughput by a factor of 1.2 to 10.0 compared to the conventional Ethernet routing algorithm, the STP, and other topology agnostic routing algorithms such as Up*/Down* and Tree-based Turn-prohibition, which both are applicable to Ethernet.},
	isbn = {0-7695-2784-1},
	author = {Reinemo, Sven-Arne and Skeie, Tor and Mej{\'\i}a, Andres and Flich, Jos{\'e} and Duato, Jose},
	editor = {D{\textquoteright}Ambra, Pasqua and Mario Rosario {Guarracino}}
}
@inproceedings {Mejia.2006.1,
	title = {Segment-Based Routing: an Efficient Fault-Tolerant Routing Algorithm for Meshes and Tori},
	journal = {20th IEEE International Parallel \& Distributed Processing Symposium},
	year = {2006},
	month = {April},
	pages = {1-10},
	publisher = {IEEE Computer Society},
	type = {Conference},
	address = {Washington, USA},
	abstract = {Computers get faster every year, but the demand for computing resources seems to grow at an even faster rate. Science keeps demanding more processing power for calculations and simulations, growth in E-commerce requires powerful servers to offer seamless online shopping, and massive multiplayer online games requires powerful and stable systems to keep their virtual worlds running 24 hours a day. Depending on the problem domain, this demand for more power can be satisfied by either, massively parallel computers, or clusters of computer. Common for both approaches is the dependence on high performance interconnect networks such as Myrinet, Infiniband, or 10 Gigabit Ethernet. While high throughput and low latency are key features of interconnection networks, the issue of fault-tolerance is now becoming increasingly important. As the number of network components grows so does the probability for failure, thus it becomes important to also consider the fault-tolerance mechanism of interconnection networks. The main challenge then lies in combining performance and fault-tolerance, while still keeping cost and complexity low. This paper proposes a new deterministic routing methodology for tori and meshes, which achieves high performance without the use of virtual channels. Furthermore, it is topology agnostic in nature, meaning it can handle any topology derived from any combination of faults when combined with static reconfiguration. The algorithm, referred to as Segment-based Routing (SR), works by partitioning a topology into subnets, and subnets into segments. This allows us to place bidirectional turn restrictions locally within a segment. As segments are independent, we gain the freedom to place turn restrictions within a segment independently from other segments. This results in a larger degree of freedom when placing turn restrictions compared to other routing strategies. In this paper a way to compute segment-based routing tables is presented and applied to meshes and tori. Preliminary evaluation results show that the concept of segments leads to an increase in performance by a factor of 1.8 over FX and up*/down* routing.},
	isbn = {1-4244-0054-6},
	author = {Mej{\'\i}a, Andres and Flich, Jos{\'e} and Duato, Jose and Reinemo, Sven-Arne and Skeie, Tor},
	editor = {Ali, Shaukat}
}
