On routing maskable messages in hypercube-derived multistage interconnection networks

A vast number of message patterns can be represented by (^s _d) masks. We consider the problem of routing maskable messages in the hypercube derived multistage interconnection networks. Network contention is settled by delivering conflicting data in different network cycles. We propose an indirect, two phase routing strategy which is optimal within two network cycles. For (^s _d) mask message patterns in which every destination receives data from 2^V sources, we identity a subclass of maskable messages that can be routed in minimal 2^V network cycles, and the other maskable messages can be routed in 2^V+2 network cycles