Abstract
A class of multistage interconnection networks (MINs), called two-level MINs, is proposed. A fault-tolerant two-level MINs is constructed. It is shown that the routing scheme of the proposed networks is simple in the presence of faults. In an environment with high locality of accesses, performance analysis of the proposed two-level MINs shows that the acceptance (free of collision) probability is increased and the average path length (delay) is less than that of one-level MINs.