Fault-Tolerant Communication In Interconnection Networks

In this thesis, several approaches of fault-tolerant communication in multicomputer interconnection networks are proposed, including an improved planar adaptive routing scheme by making use of the idle channels, a deadlock-free adaptive routing scheme in 3D mesh networks based on channel overlapping and a cost-effective deadlock-free routing scheme in n-dimensional mesh networks.The adaptive routing scheme by making use of the idle channels is an improvement of the classic planar adaptive routing scheme which uses three virtual channels to establish deadlock-free routing in mesh networks. However, there exists idle channels along the highest and lowest dimensions of the topology. The proposed algorithm efficiently makes use of the idle channels and obtains deadlock freedom with only two virtual channels.A new deadlock avoidance technique based on channel overlapping is proposed. Classic deadlock avoidance techniques partition the network into different subnetworks, each of which uses separate virtual channels. In the proposed channel overlapping scheme, different sub-networks are allowed to share some virtual channels. By using channel overlapping, a fully adaptive deadlock-free routing scheme is proposed for three dimensional meshes.A cost-effective routing scheme for n-dimensional meshes is also proposed. This scheme uses channel overlapping to avoid deadlocks between any consecutive planes and two virtual channels are sufficient for the deadlock-free routing. Moreover, this scheme obtains higher adaptivity by making use of the idle channels along the highest dimension of the network.Extensive simulation results are presented to demonstrate the effectiveness of the proposed approaches compared to some other existing methods.