Aggregated bandwidth allocation: Investigation of performance of classical constrained and genetic algorithm based optimisation techniques

Abstract

We consider a high speed integrated services network, and investigate compare and contrast the performance of two algorithms for solving the Aggregated Bandwidth Allocation (BA) problem. The algorithms we focus our attention are: (1) a classical constrained optimisation (CCO) algorithm and (2) a constrained optimisation Genetic Algorithm (GA). We adopt the Virtual Path concept for Asynchronous Transfer Mode networks as an example, but expect the findings to be equally applicable for other aggregated BA problems, such as in networks using Multiprotocol Label Switching. We define a fair multiobjective criterion for maximisation of network throughput, based on a probability (density) function for bandwidth demand. We convert to single optimisation problem and study network topologies involving varying number of nodes. We compare throughput, fairness and time complexity of GA-BAVP and CCO-BAVP. The results on maximising the throughput obtained with GA-BAVP and CCO-BAVP are in close agreement, however, when considering fairness GA-BAVP outperforms CCO-BAVP especially for more complex topologies. Convergence of the two algorithms appears similar, with GA-BAVP outperforming CCO-BAVP in initial stages, and vice versa for longer time scales. However, as problem complexity increases the solution time for the GA does not increase as fast as the CCO algorithm. A hybrid scheme is also introduced, combining the benefits of both algorithms. It exhibited better overall convergence rate but the same solution as CCO-BAVP. More work is needed to investigate the usefulness of GAs in larger network topologies, as well as to multiobjective BA problems. © 2002 Published by Elsevier Science B.V.