Performance comparison of multi objective evolutionary algorithms for QoS routing problems in computer networks

Abstract

A computer network is an interconnected group of computers with the ability to exchange data. Today, computer networks are the core of modern communication. Routing is one of the most important issues that have a significant impact on the network s performance. An ideal routing algorithm should strive to find an optimum path for packet transmission within a specified time so as to satisfy the Quality of Service (QoS) requirement. This thesis is concerned with the investigation of Multi-Objective Evolutionary Algorithms (MOEAs) for QoS unicast and multicast routing problems. The routing problem is formulated as a multi-objective mathematical programming problem which attempts to minimize four QoS parameters simultaneously, while satisfying the flow conservation constraints. The four objectives considered are cost, delay, Maximum Link Utilization (MLU) and hop count. In this thesis, Evolutionary Algorithms (EAs) are used to solve multi-objective problems that have been motivated mainly because of their population based nature that allows the generation of several solutions in a single run. The experimental results of the three MOEAs, their performance in terms of Execution Time (ET), Route Optimality (RO) and maximum number of nondominated solutions, and the detailed analysis are presented. The results for the benchmark problems are compared with the other works reported in the literature. From the results obtained, it is observed that, when the size of the network was small, the three algorithms, NSGA, NSGA-II and SPEA performed equally well for both unicast and multicast routing problems. For larger size networks, NSGA-II had better performance in terms of execution time and route optimality and SPEA had better performance in terms of identifying the maximum number of non-dominated solutions. newline newline newline