Enhanced fault tolerant routing algorithms using a concept of “balanced ring”

Fault rings can be used to guide messages bypass faulty nodes/links in a fault tolerant interconnection network. However, nodes on the fault ring become hot spots, thus causing uneven distribution of the traffic loads. To avoid such traffic congestion, a concept of the balanced ring is proposed in this paper. The proposed balanced ring, defined as concentric rings of a given fault ring, can be applied to the fault tolerant routing algorithms for mesh and torus topologies. By properly guiding messages to route on the balanced ring and the fault ring, more balanced link utilization and greatly reduced traffic congestion can be achieved on a fault tolerant network. Methods of applying the balanced ring concept to some published fault tolerant routing algorithms are discussed. Proof of deadlock and livelock freedom is also presented. The use of balanced ring does not need to add new virtual channels. The performance of two routing algorithms with and without the balanced ring is simulated and evaluated. The results indicate that routing algorithms with the balanced rings constantly yield larger throughput and smaller latency than those without.