A Routing Algorithm for a Modified Multistage Interconnection Network

摘要

In this paper a class of fault-tolerant statically reroutable regular multistage interconnection network named as modular network (MN) is studied. Scheme for augmenting unique-path multistage interconnection networks to create redundant paths between every source-destination pair is presented. MN consists of independent identical subnetworks and each subnetwork has the topology that is of baseline network. Baseline network is a generalized cube network with different labeling of inputs. These independent identical subnetworks in MN are such that a connection path between each source-destination pair can be established through any of the modules. This paper is an attempt on the design of a routing algorithm for MN. Our algorithm yields significant performance improvement over previously known routing algorithms for MN. The analysis for lower bounds and upper bounds of the proposed network has also been carried out. It is observed that although in the improved design an individual component failure reduces MN performance, it does not cause a total network failure.