King Topologies for Fault Tolerance

This paper analyzes the robustness of the king networks for fault tolerance. To this aim, a performance evaluation of two well known fault tolerant routing algorithms in king as well as 2d networks is done. Immunet that uses two virtual channels and Immucube, that has a better performance while requiring three virtual channels. Experimental results confirm the excellent behavior, both in performance and scalability, of the king topologies in the presence of failures. Finally, taking advantage of the topological features of king networks, a new fault tolerance routing algorithm for these networks is presented. From a cost/performance point of view this algorithm is a compromise between the two previous algorithms.