A new multipath multistage interconnection network called the recursively constructed composite banyan network is proposed.The basic building blocks of the network are 3×3 switching elements.The advantage of this network is to resolve the problem that the composite banyan network proposed by Seo and Feng can't perform arbitrary permutation by adding middle stages.The network can easily generate a primary routing tag and more alternate tags through simple binary operations

which increase the degree of fault-tolerance.A permutation routing algorithm suitable for the network is introduced.The major feature of the network is pre-fault-tolerance.By setting a flag bit to identify whether the status of one witch is usable or not

the network can choose appropriate routing tag to avoid the switch that can't work in advance.