Cc. Su et Kg. Shin, ADAPTIVE FAULT-TOLERANT DEADLOCK-FREE ROUTING IN MESHES AND HYPERCUBES, I.E.E.E. transactions on computers, 45(6), 1996, pp. 666-683
We present an adaptive deadlock-free routing algorithm which decompose
s a given network into two virtual interconnection networks, VIN1 and
VIN2. VIN1 supports deterministic deadlock-free routing, and VIN2 supp
orts fully-adaptive routing. Whenever a channel in VIN1 or VIN2 is ava
ilable, it can be used to route a message. Each node is identified to
be in one of three states: safe, unsafe, and faulty. The unsafe state
is used for deadlock-free routing, and an unsafe node can still send a
nd receive messages. When nodes become faulty/unsafe, some channels in
VIN2 around the faulty/unsafe nodes are used as the detours of those
channels in VIN1 passing through the faulty/unsafe nodes, i.e., the ad
aptability in VIN2 is transformed to support fault-tolerant deadlock-f
ree routing. Using information on the state of each node's neighbors,
we have developed an adaptive fault-tolerant deadlock-free routing sch
eme for n-dimensional meshes and hypercubes with only two virtual chan
nels per physical link. In an n-dimensional hypercube, any pattern of
faulty nodes can be tolerated as long as the number of faulty nodes is
no more than [n/2]. The maximum number of faulty nodes that can be to
lerated is 2(n-1), which occurs when all faulty nodes can be encompass
ed in an (n-1)-cube. in an n-dimensional mesh, we use a more general f
ault model, called a disconnected rectangular block. Any arbitrary pat
tern of faulty nodes can be modeled as a rectangular block after findi
ng both unsafe and disabled nodes (which are then treated as faulty no
des). This concept can also be applied to k-ary n-cubes with four virt
ual channels, two in VIN1 and the other two in VIN2. Finally, we prese
nt simulation results for both hypercubes and 2-dimensional meshes by
using various workloads acid fault patterns.