Simulated evolution and simulated annealing algorithms for solving multi-objective open shortest path first weight setting problem

Abstract

Optimal utilization of resources in present- day communication networks is a challenging task. Rout- ing plays an important role in achieving optimal re- source utilization. The open shortest path rst (OSPF) routing protocol is widely used for routing packets from a source node to a destination node. This protocol as- signs weights (or costs) to the links of a network. These weights are used to determine the shortest path be tween all sources to all destination nodes. Assignment of these weights to the links is classi ed as an NP-hard problem. This paper formulates the OSPF weight set- ting problem as a multi-objective optimization prob- lem, with maximum utilization, number of congested links, and number of unused links as the optimization objectives. Since the objectives are con icting in na- ture, an e cient approach is needed to balance the trade-o between these objectives. Fuzzy logic has been shown to e ciently solve multi-objective optimization problems. A fuzzy cost function for the OSPF weight setting problem is developed in this paper based on the Uni ed And-OR (UAO) operator. Two iterative heuris- tics, namely, simulated annealing (SA) and simulated evolution (SimE) have been implemented to solve the multi-objective OSPF weight setting problem using a fuzzy cost function. Results are compared with that found using other cost functions proposed in the literature [1]. Results suggest that, overall, the fuzzy cost function performs better than existing cost functions, with respect to both SA and SimE. Furthermore, SimE shows superior performance compared to SA. In addi- tion, a comparison of SimE with NSGA-II shows that, overall, SimE demonstrates slightly better performance in terms of quality of solutions.-