Optimization of metrics in OSPF/IS-IS routing using accelerated iterative heuristics

Abstract

Efficient network utilization using available resources is the main goal of traffic engineering and routing is the core criteria which regulates traffic over Internet links. Open Shortest Path First (OSPF) is a routing protocol which is widely used in the industry. Its functionality depends mainly on the weights of the links and optimizing these link weights leads to efficient network utilization. Setting weights on links for given traffic demands such that congestion can be avoided is an NP-hard problem. Therefore, an approach to OSPF weight setting problem (OSPFWS) is proposed which resorts to non-deterministic heuristics to come up with a desirable solution. In this research work, the application of these heuristic algorithms on the OSPFWS problem is investigated and Tabu Search (TS) implemented to improve the existing results. Parallelization of modem iterative heuristic algorithms has been proved to produce improved solution precision and timing. A study of parallelization strategies and implementation of two varying parallel algorithms for OSPFWS problem was also conducted in this work. It is shown through experimental results that both Parallel Tabu Search (PTS) algorithms produced better solution quality specifically for larger topologies. The other part of this research work involved addressing the issue of finding optimum OSPF weights to handle single link failures. In this work, we propose and implement two new strategies for handling this issue. Both strategies were found efficient in handling weight setting for single link failures.