Study Of Fault-Tolerant Routing Strategies On Locally Twisted Cubes

Interconnection networks provide an effective mechanism for communicating data between processors in parallel computing systems. With the increasing size of interconnection networks, it becomes much likely that there exist faulty nodes or/and faulty links in an interconnection network. Consequently, the communication efficiency of an interconnection network in the presence of failing nodes/links is a major concern in evaluating the effectiveness of this network.As a new kind of variants of the well-known hypercubes, a class of graphs known as the locally twisted cubes (LTQs) has recently been proposed as candidates for the topology of interconnection network. While retaining some nice properties of a hypercube, a locally twisted cube outperforms a hypercube of the same size in terms of smaller network diameter as well as better graph-embedding ability. Due to these reasons, LTQs have received considerable attention.This thesis addresses how to route messages in a faulty n-dimensional LTQ. The main contributions of this thesis are listed below.①A node-fault-tolerant unicast routing algorithm is proposed by employing the safety-level technique and exploring the structural properties of LTQ. Under reasonable assumptions, this algorithm can route a message along a shortest path from the source to the destination. Experimental results justify the utility of this algorithm. By simulations, we find that the algorithm can achieve a satisfactory percentage of successful routing even if the number of faulty nodes is more than half of the total number of nodes, and the route selected is highly probable to be a shortest path.②A link-fault-tolerant unicast routing algorithm is advised by using a fault array and utilizing the recollection mechanism. Simulation results demonstrate that, with this algorithm, a message can be routed successfully even when a large number of links break down.③An effieient fault-tolerant unicast routing algorithm is suggested by employing the comcept of routing capability. Simulation results show that this algorithm can ensure an optimal or suboptimal unicasting.④A fault-tolerant broadcast algorithm is developed based on the concept of divisional hypercube. Theoretical analysis shows that an optimal broadcast tree can be formed when the source node is safe, and a broadcast requires at most n + 1 steps when the source is unsafe and there are no more than n failing nodes.⑤A unicast-based multicast routing algorithm is presented by dividing the multicast set into a set of smaller subsets and carrying out the multicast for these subsets, independently.