Multipath Fault-Tolerant Routing Policies to deal with Dynamic Link Failures in High Speed Interconnection Networks

Abstract

In this thesis, we present fault-tolerant routing policies based on concepts of adaptability and deadlock freedom, capable of serving interconnection networks affected by a large number of dynamic link failures. The strongest point of this thesis is that it provides a simple but complete solution to the problem of dynamic fault tolerance in interconnection networks. The proposed solution does not require any information about network faults when the system is started or restarted. Throughout the thesis, we present the conception, design, implementation and evaluation of two contributions. The first of these contributions is the adaptive multipath routing method Fault-Tolerant Distributed Routing Balancing (FT-DRB). This method has been designed to exploit the communication path redundancy available in many network topologies, allowing interconnection networks to perform in the presence of a large number of faults. The second contribution is the scalable deadlock avoidance technique Non-blocking Adaptive Cycles (NAC), specifically designed for interconnection networks suffering from a large number of failures. This technique has been designed and implemented with the aim of ensuring freedom from deadlocks in the proposed fault-tolerant routing method FT-DRB.