JOURNAL OF COMMUNICATIONS (JCM)
ISSN : 1796-2021
Volume : 2    Issue : 4    Date : June 2007

Routing in Optical and Non-Optical Networks using Boolean Satisfiability
Fadi A. Aloul, Bashar Al Rawi, and Mokhtar Aboelaze
Page(s): 49-56
Full Text:
PDF (357 KB)


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.

Index Terms
Networks, Boolean Satisfiability, Backtrack Search, Optimization, Routing and Wavelength
Assignments