@article{11279,
  author = {Jos{\'e} Flich and Tor Skeie and Andres Mej{\'\i}a and Olav Lysne and Pedro Lopez and Antonio Robles and Jose Duato and Michihiro Koibuchi and Tomas Rokicki and Jos{\'e} Sancho},
  title = {A Survey and Evaluation of Topology Agnostic Routing Algorithms},
  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.},
  year = {2012},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  volume = {23},
  number = {3},
  pages = {405-425},
  month = {March},
  publisher = {IEEE},
}