S.-C. Chau and T. Xiao (Canada)
Optical multistage interconnection network, message routing and scheduling, and crosstalk
Multistage Interconnection Networks (MINs) are popular in switching and communication applications. Recently, there have also been significant advances in electro-optic switches that have made Optical MINs (OMINs) a good choice for the high channel bandwidth and low communication latency of high performance computing and/or communication applications. However, OMINs introduce crosstalk which results from coupling two signals within one Switching Element (SE). Under the constraint of avoiding crosstalk, what we are interested in is how to realize a permutation that requires the minimum number of passes. Many heuristic algorithms, including the sequence increasing algorithm, sequence decreasing algorithm, degree-ascending algorithm, and degree descending algorithm have been proposed to perform this routing problem. Some researchers have adopted the Genetic Algorithm (GA) and the Simulated Annealing (SA) algorithm to improve the performance of the routing and scheduling for a permutation. In this paper, we propose a new algorithm, called the Remove Last Pass (RLP) algorithm, to avoid crosstalk and route the traffic in an OMIN more efficiently. The results of the RLP algorithm are analyzed and compared with those of other algorithms (except the GA) in an Omega network. The RLP algorithm outperforms all the other algorithms in terms of the number of passes that are required for one permutation.
Important Links:
Go Back
