Evolutionary computation for topological optimization of 3-connected computer networks

Abstract

In the 3-connected computer network design problem, a set of links is to be assigned to some computer sites (nodes) such that every source-destination pair of nodes can successfully communicate with each other via at least one of three diverse paths. The objective is to minimize the total link connection costs while maintaining the 3-connectivity constraint. We develop two heuristics, a greedy heuristic and a genetic algorithm (GA) based heuristic to approximately solve the design problem. An experimental evaluation shows that the GA consistently outperforms the greedy algorithm for the problem instances considered.