Routing and wavelength assignment in optical networks using bin packing based algorithms. (English) Zbl 1109.90015
Summary: This paper addresses the problem of routing and wavelength assignment (RWA) of static lightpath requests in wavelength routed optical networks. The objective is to minimize the number of wavelengths used. This problem has been shown to be NP-complete and several heuristic algorithms have been developed to solve it. We suggest very efficient, yet simple, heuristic algorithms for the RWA problem developed by applying classical bin packing algorithms. The heuristics were tested on a series of large random networks and compared with an efficient existing algorithm for the same problem. Results indicate that the proposed algorithms yield solutions significantly superior in quality, not only with respect to the number of wavelength used, but also with respect to the physical length of the established lightpaths. Comparison with lower bounds shows that the proposed heuristics obtain optimal or near optimal solutions in many cases.
MSC:
| 90B18 | Communication networks in operations research |
| 90B80 | Discrete location and assignment |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Alvim, A. C.F.; Glover, F.; Ribeiro, C. C.; Aloise, D. J., A hybrid improvement heuristic for the one-dimensional bin packing problem, Journal of Heuristics, 10, 205-229 (2004) |
| [2] | Banerjee, D.; Mukherjee, B., A practical approach for routing and wavelength assignment in large wavelength-routed optical networks, IEEE Journal on Selected Areas in Communications, 14, 903-908 (1996) |
| [3] | Chlamtac, I.; Ganz, A.; Karmi, G., Lightpath communications: An approach to high-bandwidth optical WANs, IEEE Transactions on Communications, 40, 1171-1182 (1992) |
| [4] | J.S. Choi, N. Golmie, F. Lapeyere, F. Mouveaux, D. Su, A functional classification of routing and wavelength assignment schemes in DWDM networks: Static case, in: Proceedings of the VII International Conference on Optical Communication and Networks, January 2000.; J.S. Choi, N. Golmie, F. Lapeyere, F. Mouveaux, D. Su, A functional classification of routing and wavelength assignment schemes in DWDM networks: Static case, in: Proceedings of the VII International Conference on Optical Communication and Networks, January 2000. |
| [5] | Coffman, E. G.; Csirik, J.; Woeginger, G., Bin packing theory, (Pardalos, P.; Resende, M., Handbook of Applied Optimization (2002), Oxford University Press: Oxford University Press New York) · Zbl 1120.90046 |
| [6] | Coffman, E. G.; Garey, M. R.; Johnson, D. S., Bin packing approximation algorithms: A survey, (Hochbaum, D., Approximation Algorithms for NP-Hard Problems (1996), PWS Publishing Co.: PWS Publishing Co. Boston, MA) · Zbl 0558.68062 |
| [7] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [8] | Hyytiä, E.; Virtamo, J., Wavelength assignment and routing in WDM networks, Nordic Telegraffic Seminar, 14, 31-40 (1998) |
| [9] | R. Inkret, A. Kuchar, B. Mikac, Advanced Infrastructure for Photonic Networks: Extended Final Report of COST Acteion 266, Zagreb: Faculty of Electrical Engineering and Computing, University of Zagreb, 2003, pp. 19-21.; R. Inkret, A. Kuchar, B. Mikac, Advanced Infrastructure for Photonic Networks: Extended Final Report of COST Acteion 266, Zagreb: Faculty of Electrical Engineering and Computing, University of Zagreb, 2003, pp. 19-21. |
| [10] | Jia, X.; Hu, X.-D.; Du, D.-Z., Multiwavelength Optical Networks (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA · Zbl 1052.68011 |
| [11] | Lee, K.; Kang, K. C.; Lee, T.; Park, S., An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion, ETRI Journal, 24, 2, 131-141 (2002) |
| [12] | G. Li, R. Simha, The partition coloring problem and its application to wavelength routing and assignment, in: Proceedings of Optical Networks Workshop, Richardson, Texas, February 2000.; G. Li, R. Simha, The partition coloring problem and its application to wavelength routing and assignment, in: Proceedings of Optical Networks Workshop, Richardson, Texas, February 2000. |
| [13] | Manohar, P.; Manjunath, D.; Shevgaonkar, R. K., Routing and wavelengths assignment in optical networks from edge disjoint path algorithms, IEEE Communication Letters, 6, 5, 211-213 (2002) |
| [14] | Mukherjee, B., Optical Communication Networks (1997), McGraw-Hill: McGraw-Hill New York |
| [15] | Noronha, T. F.; Ribeiro, C. C., Routing and wavelength assignment by partition coloring, European Journal of Operational Research, 171, 3, 797-810 (2006) · Zbl 1116.90073 |
| [16] | Ramaswami, R.; Sivarajan, K. N., Design of logical topologies for wavelength-routed optical networks, IEEE Journal on Selected Areas in Communication, 14, 5, 840-851 (1996) |
| [17] | Sharafat, A. R., The most congested cutset: Deriving a tight lower bound for the chromatic number in the RWA problem, IEEE Communication Letters, 8, 7, 473-475 (2004) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
