New Approach for Minimizing Wavelength Fragmentation in Wavelength-Routed WDM Networks

Authors: Sami Baraketi, Jean-Marie Garcia, Olivier Brun

Abstract:

Wavelength Division Multiplexing (WDM) is the dominant transport technology used in numerous high capacity backbone networks, based on optical infrastructures. Given the importance of costs (CapEx and OpEx) associated to these networks, resource management is becoming increasingly important, especially how the optical circuits, called “lightpaths”, are routed throughout the network. This requires the use of efficient algorithms which provide routing strategies with the lowest cost. We focus on the lightpath routing and wavelength assignment problem, known as the RWA problem, while optimizing wavelength fragmentation over the network. Wavelength fragmentation poses a serious challenge for network operators since it leads to the misuse of the wavelength spectrum, and then to the refusal of new lightpath requests. In this paper, we first establish a new Integer Linear Program (ILP) for the problem based on a node-link formulation. This formulation is based on a multilayer approach where the original network is decomposed into several network layers, each corresponding to a wavelength. Furthermore, we propose an efficient heuristic for the problem based on a greedy algorithm followed by a post-treatment procedure. The obtained results show that the optimal solution is often reached. We also compare our results with those of other RWA heuristic methods

Keywords: WDM, lightpath, RWA, wavelength fragmentation, optimization, linear programming, heuristic

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1100837

References:

[1] R. Ramaswami, K. Sivarajan, and G. Sasaki, Optical networks: a practical perspective. Morgan Kaufmann, 2009.
[2] R. Ramaswami, “Multiwavelength lightwave networks for computer communication,” Communications Magazine, IEEE, vol. 31, no. 2, pp. 78–88, 1993.
[3] H. Zang, J. P. Jue, B. Mukherjee et al., “A review of routing and wavelength assignment approaches for wavelength-routed optical wdm networks,” Optical Networks Magazine, vol. 1, no. 1, pp. 47–60, 2000.
[4] B. Jaumard, C. Meyer, and B. Thiongane, “Ilp formulations for the routing and wavelength assignment problem: Symmetric systems,” in Handbook of optimization in telecommunications. Springer, 2006, pp. 637–677.
[5] Z. Liu and G. N. Rouskas, “Link selection algorithms for link-based ilps and applications to rwa in mesh networks,” in Optical Network Design and Modeling (ONDM), 2013 17th International Conference on. IEEE, 2013, pp. 59–64.
[6] I. Chlamtac, A. Ganz, and G. Karmi, “Lightpath communications: An approach to high bandwidth optical wan’s,” Communications, IEEE Transactions on, vol. 40, no. 7, pp. 1171–1182, 1992.
[7] B. Chen and J. Wang, “Efficient routing and wavelength assignment for multicast in wdm networks,” Selected Areas in Communications, IEEE Journal on, vol. 20, no. 1, pp. 97–109, 2002.
[8] S. B. Yoo, “Wavelength conversion technologies for wdm network applications,” Lightwave Technology, Journal of, vol. 14, no. 6, pp. 955–966, 1996.
[9] H. Zang, J. P. Jue, L. Sahasrabuddhe, R. Ramamurthy, and B. Mukherjee, “Dynamic lightpath establishment in wavelength routed wdm networks,” Communications Magazine, IEEE, vol. 39, no. 9, pp. 100–108, 2001.
[10] A. E. Ozdaglar and D. P. Bertsekas, “Routing and wavelength assignment in optical networks,” IEEE/ACM Transactions on Networking (TON), vol. 11, no. 2, pp. 259–272, 2003.
[11] K. Christodoulopoulos, K. Manousakis, and E. Varvarigos, “Comparison of routing and wavelength assignment algorithms in wdm networks,” in Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. IEEE. IEEE, 2008, pp. 1–6.
[12] K. Christodoulopoulos and K. Manousakis, “Offline routing and wavelength assignment in transparent wdm networks,” Networking, IEEE/ACM Transactions on, vol. 18, no. 5, pp. 1557–1570, 2010.
[13] Z. Liu and G. N. Rouskas, “A fast path-based ilp formulation for offline rwa in mesh optical networks,” in Global Communications Conference (GLOBECOM), 2012 IEEE. IEEE, 2012, pp. 2990–2995.
[14] H. Simonis, “Solving the static design routing and wavelength assignment problem,” in Recent Advances in Constraints. Springer, 2011, pp. 59–75.
[15] D. Banerjee and B. Mukherjee, “A practical approach for routing and wavelength assignment in large wavelength-routed optical networks,” Selected Areas in Communications, IEEE Journal on, vol. 14, no. 5, pp. 903–908, 1996.
[16] H. Siregar, H. Takagi, and Y. Zhang, “Efficient routing and wavelength assignment in wavelength-routed optical networks,” in Proc. 7th Asia-Pacific Network Oper. and Mgmt Symposium, 2003, pp. 116–127.
[17] M. Shiva Kumar and P. Sreenivasa Kumar, “Static lightpath establishment in wdm networksnew ilp formulations and heuristic algorithms,” Computer Communications, vol. 25, no. 1, pp. 109–114, 2002.
[18] B. Chen, G. N. Rouskas, and R. Dutta, “On hierarchical traffic grooming in wdm networks,” IEEE/ACM Transactions on Networking (TON), vol. 16, no. 5, pp. 1226–1238, 2008.
[19] N. Skorin-Kapov, “Routing and wavelength assignment in optical networks using bin packing based algorithms,” European Journal of Operational Research, vol. 177, no. 2, pp. 1167–1179, 2007.
[20] S. Baroni, P. Bayvel, and R. J. Gibbens, “On the number of wavelengths in arbitrarily-connected wavelength-routed optical networks,” University of Cambridge, Statistical Laboratory Research Report 1998-7, 1998.
[21] B. Mukherjee, Optical communication networks. McGraw-Hill New York, 1997, vol. 1999.
[22] O. Brun and S. Baraketi, “Routing and wavelength assignment in optical networks,” 2014.
[23] L. K. Fleischer, “Approximating fractional multicommodity flow independent of the number of commodities,” SIAM Journal on Discrete Mathematics, vol. 13, no. 4, pp. 505–520, 2000.
[24] N. Garg and J. Koenemann, “Faster and simpler algorithms for multicommodity flow and other fractional packing problems,” SIAM Journal on Computing, vol. 37, no. 2, pp. 630–652, 2007.
[25] T. Erlebach, “Approximation algorithms for edge-disjoint paths and unsplittable flow,” in Efficient Approximation and Online Algorithms. Springer, 2006, pp. 97–134.
[26] S. G. Kolliopoulos and C. Stein, Approximating disjoint-path problems using greedy algorithms and packing integer programs. Springer, 1998.
[27] Gurobi, “Gurobi optimization.”