Re-routing and resequencing in multistage interconnection networks

Abstract : 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.
Document type :
Complete list of metadatas
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 7:32:15 PM
Last modification on : Tuesday, November 13, 2018 - 2:38:01 AM
Long-term archiving on : Friday, May 13, 2011 - 1:15:47 PM


  • HAL Id : inria-00075887, version 1



Alain Jean-Marie. Re-routing and resequencing in multistage interconnection networks. [Research Report] RR-0666, INRIA. 1987, pp.30. ⟨inria-00075887⟩



Record views


Files downloads