AuthorsI. T. T. Theiss and O. Lysne
TitleFRoots, a Fault Tolerant and Topology Agnostic Routing Technique
AfilliationNetworks, Communication Systems
StatusPublished
Publication TypeJournal Article
Year of Publication2006
JournalIEEE Transactions on Parallel and Distributed Systems
Volume17
Number10
Pagination1136-1150
Date PublishedOctober
Abstract

Existing solutions for fault tolerant routing in interconnection networks either work for only one given regular topology, or they require slow and costly network reconfigurations which cannot allow full and continuous network access. In this paper we present FRroots, a routing method for fault tolerance in topology-agnostic network technologies. Our method is based on redundant paths, and it can handle single dynamic faults without the need for sending control messages. In the fault-free networks under non-uniform traffic it performs comparable to, or even better than, topology specific and non-fault tolerant routing algorithms in regular networks like meshes and tori. FRoots does not require any other features in the switches than a flexible routing table, and a modest number of virtual channels. For that reason it can be directly applied to several present day technologies like InfiniBand and Advanced Switching.

Citation KeyTheiss.2006.1