A regular scalable fault tolerant interconnection network for distributed processing

Bounded degree networks like deBruijn graphs or wrapped butterfly networks are very important from VLSI implementation point of view as well as for ap plications where the computing nodes in the interconnection networks can ha ve only a fixed number of I/O ports. One basic drawback of these networks i s that they cannot provide a desired level of fault tolerance because of th e bounded degree of the nodes. On the other hand, networks like hypercube ( where degree of a node grows with the size of a network) can provide the de sired fault tolerance but the design of a node becomes problematic for larg e networks. In their attempt to combine the best of the both worlds, author s in [IEEE Transactions on Parallel and Distributed Systems 4(9) (1993) 962 ] proposed hyper-deBruijn (HD) networks that have many additional features of logarithmic diameter, partitionability, embedding, etc. But, HD networks are not regular, are not optimally fault tolerant and the optimal routing is relatively complex. Our purpose in the present paper is to extend the co ncepts used in the above-mentioned reference to propose a new family of sca lable network graphs that retain all the good features of HD networks and a t the same time are regular and maximally fault tolerant; the optimal point to point routing algorithm is significantly simpler than that of the HD ne tworks. We have developed some new interesting results on wrapped butterfly networks in the process. (C) 2001 Elsevier Science B.V. All rights reserve d.