Re-routing and resequencing in multistage interconnection networks

This paper is concerned with load balancing in Omega-like networks. A variation of the Mitra-Cieslak random re-routing algorithm is considered. The global aim of the paper is to analyze the cost of the resequencing algorithm that has to be implemented in order to cope with possible message overtaking due to re-routing. Analytical expressions for the statistics of both network response time and resequencing time are obtained. It is shown through several examples that in "most situations", such random re-routing improves the global network performance, even when including the effects of resequencing.