Optimizing OSPF Routing Using Accelerated Iterative Heuristic

The problem of setting Open Shortest Path First (OSPF) weights on links such that congestion can be avoided is proved to be NP-hard. Many iterative heuristics have been applied to solve the OSPF weight setting (OSPFWS) problem. As the size of any combinatorial optimization problem increases, it becomes more difficult to find an optimum solution using sequential algorithms. In this paper, the authors investigate the parallelization of Tabu Search and apply two variants of a Parallel Tabu Search (PTS) heuristic on the OSPFWS problem. It is shown through experimental results that both PTS approaches produced better solutions quality compared to the sequential heuristics; specifically for larger topologies.