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

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

• Sami Baraketi
• Jean-Marie Garcia
• Olivier Brun

• WDM
• lightpath
• RWA
• wavelength fragmentation
• optimization
• linear programming
• heuristic

[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.”