An Evaluation on Fault-Tolerant Multicasting Schemes in Multistage Interconnection Networks

H. Masuyama, Y. Sakono, and T. Kawamura (Japan)


multistage interconnection network,multicasting, Omega network, fault-tolerant.


In this paper, we study fault-tolerant multicastings in multistage interconnection networks for constructing efficient communication algorithms. Efficient multicast routing is critical to the performance of parallel processing systems. This paper only focuses on the efficient multicasting in the omega networks, that is, the use of multicasting schemes has been discussed in detail in the omega networks with a finite number of passes through the network. On this condition, this paper evaluates three fault-tolerant multicasting approaches with different principles in terms of required routing steps. In this paper, the scheme to guarantee non blocking operation is also classified into three categories: In an occasion of blocking, one of two packets is made to proceed at the blocking switching element, necessary process for splitting or routing is delayed until the next rear stage, and the last one is that the packet is detoured in advance on the front stage. Therefore, total nine fractionalized schemes are evaluated in terms of required routing steps. The second two fault-tolerant algorithms are found to provide similar results and are recommended.

Important Links:

Go Back