Applying ant colony optimization to routing in optical multistage interconnection networks with limited crosstalk

Abstract

Ant Colony Optimization (ACO) technique can be successfully implemented to solve many combinatorial optimization problems. In this paper we use the ACO technique to route messages through an N × N Optical Multistage Interconnection Network (OMIN) allowing upto 'C' limited crosstalk's (conflicts between messages within a switch) where 'C' is a technology driven parameter and is always less than log 2N. Messages with switch conflicts satisfying the crosstalk constraint are allowed to pass in the same group, but if there is any link conflict, then messages are routed in a different group. The focus here is to minimize the number of passes required for routing allowing upto 'C' limited crosstalks in an N × N OMIN. In this paper we show how the ACO technique can be applied to the routing problem, and its performance is compared to that of the degree-descending algorithm using simulation techniques. Finally the lower bound estimate on the minimum number of passes required is calculated and compared to the results obtained using the two algorithms discussed. The results obtained show that the ACO technique performs better than the degree-descending algorithm and is quite close to optimal algorithms to the problem.

Document Type

Conference Proceeding

DOI

https://doi.org/10.1109/IPDPS.2004.1303156

Publication Date

12-1-2004

Journal Title

Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)

Link to Full Text

Share

COinS