Routing in Optical and Non-Optical Networks using Boolean Satisfiability
|
| Title | Routing in Optical and Non-Optical Networks using Boolean Satisfiability |
| Authors | |
| Abstract | Today, most routing problems are solved using Dijkstra’s shortest path algorithm. Many efficient implementations of Dijkstra’s algorithm exist and can handle large networks in short runtimes. Despite these advances, it is difficult to incorporate user-specific conditions on the solution when using Dijkstra’s algorithm. Such conditions can include forcing the path to go through a specific node, forcing the path to avoid a specific node, using any combination of inclusion/exclusion of nodes in the path, etc. In this paper, we propose a new approach to solving the shortest path problem using advanced Boolean satisfiability (SAT) techniques. SAT has been heavily researched in the last few years. Significant advances have been proposed and has lead to the development of powerful SAT solvers that can handle very large problems. SAT solvers use intelligent search algorithms that can traverse the search space and efficiently prune parts that contain no solutions. These solvers have recently been used to solve many problems in Engineering and Computer Science. In this paper, we show how to formulate the shortest path problem in non-optical networks as a SAT problem. We also show how to use SAT in finding routing and wavelength assignments in optical networks. Our approach is verified on various network topologies. The results are promising and indicate that using the proposed approach can improve on previous techniques. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2007-06-01 |
| Source | Journal of Communications Vol 2, No 4 (2007): Special Issue: Selected Best Papers of Innovations in Information Technology Co |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |