Routing in wormhole-switched clustered networks with applications to faulttolerance

This paper presents a novel technique for routing in wormhole-switched mult iprocessor interconnection networks with clustered configuration. The netwo rk model used here consists of a set of clusters interfaced through a commo n central network. We assume that the central network and the clusters use independent algorithms to route messages between their internal nodes. A te chnique for deriving a global routing algorithm based on the local algorith ms is presented, which allows the transfer of messages between any pair of nodes in the network. This proposed method is shown to be deadlock-free wit h two virtual channels. The clustered network model and the proposed routin g technique can be used to enhance the fault tolerance capability of existi ng routing algorithms. In particular, we describe fault-tolerant routing me thods for meshes, which can tolerate any arbitrary fault distribution witho ut disabling connected healthy nodes.