How simple routing algorithms are good for solving RWA problem in survival optical networks?

ABSTRACT

Since Routing and Wavelength Assignment (RWA) in optical networks is NP-complete problem. Many researches have proposed from simple to complex heuristic algorithms for solving this RWA problem. The shortest path of Dijkstra and sometimes the shortest pair of disjoint paths of Suurballe are used for solving this problem. Such simple heuristic algorithms are usually prejudged as inefficient leading to the conception of complex algorithms. In this paper we analyse quantitatively to see how the simple algorithms of Dijikstra and of Suurballe are good in solving RWA problem in survivable optical networks. The comparisons are made against the optimal solution, when it is available, and against a lower bound, otherwise. The results show that simple algorithms once give solutions, they give very good solutions.

References

1. N. Banerjee and S. Sharan. A evolutionary algorithm for solving the single objective static routing and wavelength assignment problem in WDM networks. In Proceedings of International Conference on Intelligent Sensing and Information Processing, 2004., pages 13--18, 2004.
2. I. Chlamtac, A. Ganz, and G. Karmi. Lightpath communications: an approach to high bandwidth optical WAN's. IEEE Transactions on Communications, 40(7): 1171--1182, Jul 1992.
3. 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, pages 1--6, Nov 2008.
4. E. W. Dijkstra. Numerische Mathematik. A note on two problems in connexion with graphs, (1): 269--271, 1959.
5. B. Jaumard, C. Meyer, and B. Thiongane. On column generation formulations for the RWA problem. Discrete Applied Mathematics, 157(6): 1291--1308, 2009. Reformulation Techniques and Mathematical Programming.
6. B. Jaumard, C. Meyer, B. Thiongane, and X. Yu. Ilp formulations and optimal solutions for the rwa problem. In Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE, volume 3, pages 1918--1924 Vol. 3, Nov 2004.
7. K. Li. Heuristic algorithms for routing and wavelength assignment in WDM optical networks. In IEEE International Symposium on Parallel and Distributed Processing (IPDPS 2008), pages 1--8, April 2008.
8. A. E. Ozdaglar and D. P. Bertsekas. Routing and Wavelength Assignment in Optical Networks. IEEE/ACM Transaction on Networking, 11(2): 259--272, Apr. 2003.
9. R. Ramaswami and K. Sivarajan. Routing and wavelength assignment in all-optical networks. Networking, IEEE/ACM Transactions on, 3(5): 489--500, Oct 1995.
10. N. Skorin-Kapov. Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks. IEEE Journal on Selected Areas in Communications, 24(8): 2--15, Aug 2006.
11. J. W. Suurballe. Disjoint paths in a network. Networks, 4(3): 125--145, 1974.
12. J. W. Suurballe and R. E. Tarjan. A quick method for finding shortest pairs of disjoint paths. Networks, 14(2): 325--336, 1984.
13. M. To and P. Neusy. Unavailability analysis of long-haul networks. IEEE Journal on Selected Areas in Communications, 12(1): 100--109, Jan. 1994.
14. Y. Wang, T. H. Cheng, and M. H. Lim. A Tabu search algorithm for static routing and wavelength assignment problem. IEEE Communications Letters, 9(9): 841--843, Sep 2005.
15. H. Zang, J. P. Jue, and B. Mukherjee. A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks. Optical Networks Magazine, 1: 47--60, 2000.