Optimizing weights for OSPF to improve utilization using modern heuristics

Abstract

In the last few years, much research has been done on optimizing the network performance. Many times, traffic streams are inefficiently mapped onto available resources, causing subsets of network resources to become over-utilized while others remain under-utilized. In this research, a problem related to Open Shortest Path First (OSPF) routing protocol is addressed. Given the traffic demands on a network, setting weights on links such that congestion can be avoided is an NP-hard problem. Optimizing these link weights leads to efficient network utilization which is one of the main goals of traffic engineering. The goal of this research is to assign OSPF weights such that all links are utilized efficiently. In this work, three iterative heuristics namely Simulated Annealing (SA), Simulated Evolution (SimE) and Stochastic Evolution (StocE) are implemented to optimize the maximum utilization, the number of congested links and the percentage of extra load. In addition, a new cost function is proposed for this problem. The function that exists in the literature did not address the optimization of the number of congested links. The new cost function optimizes the number of congested links as well as the maximum utilization and the percentage of extra load. For SimE algorithm, a new goodness function is introduced that led to a guided search to find better solutions.