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.
References
-
F. Comellas and J. Ozon , An ant algorithm for the graph colouring problem , ANTS'98 - From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization . Google Scholar - Journal of the Operational Research Society 48, 295 (1997). Crossref, ISI, Google Scholar
- Artificial Life 5(2), 137 (1999), DOI: 10.1162/106454699568728. Crossref, ISI, Google Scholar
- IEEE Transactions on Evolutionary Computation 1(1), 53 (1997), DOI: 10.1109/4235.585892. Crossref, Google Scholar
- IEEE transactions on system, man and cybernetics-part B 26(1), 1 (1996), DOI: 10.1109/3477.484436. ISI, Google Scholar
- Journal of Optical Engineering 43(5), 1080 (2004), DOI: 10.1117/1.1690276. Crossref, ISI, Google Scholar
- IEEE Trans. Communications 35(12), 1357 (1987), DOI: 10.1109/TCOM.1987.1096722. Crossref, ISI, Google Scholar
- IEEE Communications Magazine 37(2), 50 (1999), DOI: 10.1109/35.747249. Crossref, ISI, Google Scholar
- J. Lightwave Technology 12(10), 1854 (1994), DOI: 10.1109/50.337500. Crossref, ISI, Google Scholar
- IEEE/ACM Transactions on Networking 9(4), 518 (2001), DOI: 10.1109/90.944348. Crossref, ISI, Google Scholar
-
A. Varma and C. S. Raghavendra , Interconnection networks for Multiprocessors and Multicomputers: Theory and Practice ( IEEE Computer Society Press , 1994 ) . Google Scholar - Krzysztof Walkowiak: Graph coloring using ant algorithms, Wroclaw University of Technology, Faculty of Electronics Division of Systems and Computer Networks . Google Scholar
- Journal of Parallel and Distributed Computing (JPDC) 60(1), 72 (2000), DOI: 10.1006/jpdc.1999.1595. Crossref, ISI, Google Scholar
- Journal of Comp. Science and Technology 13(), 33 (1998). ISI, Google Scholar
| Remember to check out the Most Cited Articles! |
|---|
|
Check out these Handbooks in Computer Science |
