A tabu search approach towards congestion and total flow minimization in optical networks

Abstract

This paper considers rearrangeable multihop lightwave networks whereby each network node is equipped with a number p of transmitters and receivers, and a spectrum of wavelengths is accessible by, and shared among, all nodes by using the Wavelength Division Multiplexing (WDM). Depending on input traffic flow, nodal transmitters and receivers can be re-tuned to create virtual connectivity best suited with respect to a given optimization criterion. We present an efficient heuristic algorithm that combines two criteria for optimization: throughput maximization, as well as total flow minimization. Throughput maximization criterion is equivalent to congestion minimization, while minimizing total flow under the assumption of having links with equal lengths implies minimization of the average number of hops. Taking into account lengths of the links (i.e. link costs proportional with distances), the total flow minimization becomes equivalent to the total delay minimization. Tabu search is implemented as a two-phase strategy dealing with diversification as well as intensification of search. Computational experiments include consecutive runs with different sets of weights associated with the two criteria. Results for a benchmark set of problems are presented.

Keywords

Heuristic solvability / tabu search / multihop / rearrangeable optical networks / minimal total flow / maximal throughput

References

[1] Alves A.J., Climaco J.. An iterative method for 0–1 multiobjective problems using simulated annealing and tabu search. Journal of Heuristics, 2000, 6: 385-403.

[2] Antunes C.H., Craveirinha J.F., Climaco J. N.. Planning the evolution to broadband access networks: A multicriteria approach. European Journal of Operational Research, 1998, 109: 530-540.

[3] Bienstock D., Günlük O.. Computational experience with a difficult mixed-integer multicommodity flow problem. Mathematical Programming, 1995, 68: 213-237.

[4] Costamagna E., Fanni A., Giacinto G.. A tabu search algorithm for the optimization of telecommunication networks. European Journal of Operational Research, 1998, 106: 357-372.

[5] “CPLEX 7.0” ILOG, 2000.

[6] Ehrgott, M. and X. Gandibleux, “An annotated bibliography of multiobjective combinatorial optimization”, working paper, Universitat Kaiserslautern, No.62, 2000.

[7] Gandibleux X., Freville A.. Tabu search based procedure for solving the 0–1 multiobjective knapsack problem: The two objectives case. Journal of Heuristics, 2000, 6: 361-383.

[8] Glover F., Laguna M.. Tabu Search, 1997, Hingham, MA: Kluwer Academic Publishing

[9] Jia, X., X.-D. Hu and D.-Z. Du, Multiwavelength Optical Networks, Kluwer Academic Publishers, 2002.

[10] Jones D.F., Mirrazavi S.K., Tamiz M.. Multi-objective meta-heuristics: An overview of the current state-of-art. European Journal of Operational Research, 2002, 137: 1-9.

[11] Labourdette J.-F.. Traffic optimization and reconfiguration management of multieavelength broadcast lightwave networks. Computer Networks and ISDN Systems, 1998, 30: 981-998.

[12] Labourdette J.-F., Acampora A.. Logically rearrangeable multihop lightwave networks. IEEE Transactions on Communication, 1991, 39: 1223-1230.

[13] Mukherjee, B., S. Rammamurthy, D. Banerjee and A. Mukherje, “Some principles for designing a wide-area optical network”, Proceedings Infocom’ 94, Toronto, Canada, 1994.

[14] Mukherjee B., Rammamurthy S., Banerjee D., Mukherje A.. Some principles for designing a wide-area WDM optical network. IEEE/ACM Transactions on Networking, 1996, 4(5): 684-696.

[15] Shyur C.-C., Wen U.-P.. Optimizing the system of virtual paths by tabu search. European Journal of Operational Research, 2001, 129: 650-662.

[16] Skorin-Kapov J., Labourdette J.-F.. On minimum congestion on routing in rearrangeable multihop lightwave networks. Journal of Heuristics, 1995, 1: 129-154.

[17] Stern, T.E. and K. Bala, Multiwavelength Optical Networks: A Layered Approach, Addison-Wesley, 2000.

[18] Steuer, R. E., Multiple Criteria Optimization: Theory, Computation, and Application, John Wiley and Sons, 1986.

[19] Viana A., de Sousa J.P.. Using metaheuristics in multiobjective resource constrained project scheduling. European Journal of Operational Research, 2000, 120: 359-374.

[20] Yener, B. and E. Boult, “A study of upper and lower bounds for minimum congestion routing in lightwave networks”, Proceedings of Infocom’94, Toronto, Canada, 1994.