Message routing and scheduling in optical multistage networks using simulated annealing


Multistage Interconnection Networks (MIN) is popular in switching and communication applications. A major problem called Cross talk is introduced by optical MIN, which is caused by coupling two signals within a switching element. In this paper, we focus on an efficient solution to avoid cross talk, which is routing traffic through an N x N optical network to avoid coupling two signals within each switching element. Under the constraint of avoiding cross talk, what we are interested is how to realize a permutation that will use the minimum number of passes. This routing problem is an NP-hard problem. Many heuristic algorithms are designed by many researchers to perform this routing such as sequential algorithm, degree-descending algorithm, etc. The Simulated Annealing algorithm is used in this research to improve the performance of solving the problem and optimizing the result. Many cases are tested and the results are compared to the results of other algorithms to show the advantages of good quality solution and short execution time of Simulated Annealing algorithm.

Document Type

Conference Proceeding



Publication Date


Journal Title

Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002