The optimal routing problem in multicomputer networks: an evolutionary approach

Abstract

Optimal resource allocation is an important issue in computer network administration. One of these problems involves finding an optimal route to transport certain traffic from a source node to a destination node. For messages to get from the sender to the receiver it is necessary to make a number of hops choosing, at each of the intermediate nodes, an outgoing line to use. Selection of an outgoing link can depend on amount of traffic, type of link or other criteria based on the associated cost to each line. The total transportation cost through any of the possible routes is to be minimised. Instead of facing the problem in a step by step decision making fashion, a global approach based on long term averages can be successfully used when network traffic is not extremely dynamic. Given the number of nodes in the network and the interconnection topology this later approach leads to a highly combinatorial problem. Evolutionary Algorithms behave efficiently in searching optimal or near optimal solutions in a wide range of hard combinatorial problems. Moreover, when using an evolutionary approach, instead of a single optimal solution a set of near optimal solutions is provided. This property allows us to provide timely acceptable solutions when the network interconnectivity changes over time. This paper describes a genetic algorithm using a sort of edge crossover, operating on variable length chromosomes. Also a macro-mutation operator is introduced by replacing an entire chromosome to avoid costly repair mechanisms. A report on experiments and results contrasted against conventional approaches is also included.