Routing in optical multistage networks with limited crosstalk using ant colony optimization

Abstract

Ant Colony Optimization (ACO) techniques can be successfully implemented to solve many combinatorial optimization problems, After the traveling salesman problem was successfully solved using the ACO technique, other researchers have concentrated on solving other problems like the quadratic assignment and the job-shop scheduling problems using the same technique. 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 log2N. 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 have to be routed in a different group. The focus is to minimize the number of passes required for routing allowing upto 'C' limited crosstalks in an N × N optical network. This routing problem is an NP-hard problem. In this paper we show how the ACO technique can be applied to the routing problem and compare the performance of the ACO technique 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.1142/S0129054105003005

Keywords

Ant Colony Optimization, Degree-descending algorithm, Lower Bound Estimate, OMIN, Optical networks, Routing

Publication Date

4-1-2005

Journal Title

International Journal of Foundations of Computer Science

Link to Full Text

Share

COinS