Abstract:
The open shortest path first (OSPF) routing protocol
is a well-known approach for routing packets from
a source node to a destination node. The protocol assigns
weights (or costs) to the links of a network. These weights
are used to determine the shortest paths between all sources
to all destination nodes. Assignment of these weights to
the links is classified as an NP-hard problem. The aim
behind the solution to the OSPF weight setting problem is
to obtain optimized routing paths to enhance the utilization
of the network. This paper formulates the above problem
as a multi-objective optimization problem. The optimization
metrics are maximum utilization, number of congested
links, and number of unused links. These metrics are conflicting
in nature, which motivates the use of fuzzy logic
to be employed as a tool to aggregate these metrics into a
scalar cost function. This scalar cost function is then optimized
using a fuzzy particle swarm optimization (FPSO)
algorithm developed in this paper. A modified variant of the
proposed PSO, namely, fuzzy evolutionary PSO (FEPSO),
is also developed. FEPSO incorporates the characteristics of the simulated evolution heuristic into FPSO. Experimentation
is done using 12 test cases reported in literature. These
test cases consist of 50 and 100 nodes, with the number of
arcs ranging from 148 to 503. Empirical results have been
obtained and analyzed for different values of FPSO parameters.
Results also suggest that FEPSO outperformed FPSO
in terms of quality of solution by achieving improvements
between 7 and 31 %. Furthermore, comparison of FEPSO
with various other algorithms such as Pareto-dominance
PSO, weighted aggregation PSO, NSGA-II, simulated evolution,
and simulated annealing algorithms revealed that
FEPSO performed better than all of them by achieving best
results for two or all three objectives.
