Packet switched Multistage Interconnection Networks (MINs) have been mostly proposed to use unique connection path between any source and destination. We propose to add a few extra stages in an MIN to create multiple paths between any source and destination. Connection principles of Multipath MINs (MMINs) for packet switching are presented in this paper. Performance of such network is analyzed for possible use in multiprocessor systems and dataflow computers. For an MMIN with n nodes, the number of required stages is confined in the range [log2n+1, 2log2n-1]. Each stage consists of n/2 buffered 2-by-2 switching cells. In practice, one or two extra stages is sufficient beyond log2n stages required in a unique-path MIN. The delays of MMINs are shown much shorter than that of using unique-path MINs for packet switching. The improvement lies in significantly reduced packet wait delays in buffers, especially under heavy traffic conditions. The tradeoffs between reduced network delays and increased hardware cost are studied. Optimal design criteria and procedures are provided for developing MMINs with a fixed network size and stages.

Most packet switched multistage networks have been proposed to use a unique path between any source and destination. We propose to add a few extra stages to create multiple paths between any source and destination. Connection principles of such multipath networks for packet switching are presented. Performance of such networks is analyzed for possible use in multiprocessor systems or in data flow computers.