Adaptive Fault Tolerant Routing in Interconnection Networks:A Review

A multi-processor/computer systems are connected by varieties of interconnection networks. To enable any non-faulty component (Node/Link ) to communicate with any other non-faulty component in an injured interconnection network, the information on component failure is to be made available to non-faulty components, so as to route messages around the faulty components. In this paper we have reviewed to adaptive routing schemes proposed by Dally and Aloki, Glass and Ni, and also the implementation details of reliable router. Moreover, it is proved that these schemes of routing messages via shortest paths with high probability and the expected length of routing path is very close to that of shortest path.