Fault-tolerant routing is one of the most crucial requirements for reliable multicomputer interconnection networks. For deadlock-free message routing in faulty network, many fault-tolerant routing schemes restrict the shape or number of faults.
In this thesis, we propose a deadlock-free fault-tolerant routing scheme for any random fault in 2D-meshes. Packet buffers are used for preventing deadlock among packets which detour fault regions. First, we show that the proposed routing scheme with single packet buffer per each node and two virtual channels per each physical link provides deadlock-free fault-tolerant routing for non-overlapping fault rings and fault chains. For overlapping cases, we show that four packet buffers per each node and three virtual channel channels per each physical link are enough for deadlock-free fault-tolerant routing.
Finally, we evaluate the performance of the proposed fault-tolerant routing scheme by extensive simulation. The simulation results show that the moderate performance degradation under 10, 20, 30 channel faults.
