ADAPTIVE MESSAGE ROUTING IN A CLASS OF FAULT-TOLERANT MULTISTAGE INTERCONNECTION NETWORKS

Multistage interconnection networks (MINs) are often used to provide i nterconnections in multiprocessor systems. A unique path MIN usually h as lower hardware complexity and simple control algorithm, but it lack s fault-tolerance. This paper proposes a class of multipath MINs,which are obtained by adding auxiliary links at the final stage in quad tre e networks so that they can provide more paths between each source-des tination pair, and presents their routing algorithm which is both dest ination tag based and adaptive. Starting with the routing: tag for the minimum path between a given source-destination pair, the routing alg orithm uses a set of rules to select switches and modify routing tag. In addition to trying the auxiliary link when both of the output links are unavailable, the second output link is tried before the auxiliary link when the first output link is unavailable. This feature distingu ishes the proposed routing algorithm from the one for quad tree networ ks and makes better use of all the possible paths between the given so urce-destination pair. At the end of this paper, an index of performan ce called capacity is introduced to compare different kinds of MINs. C omparison shows that the proposed MINs have better capacity than quad tree networks. (C) 1997 Elsevier Science Ltd.