A Versatile Genetic Algorithm for Network Planning

Anton Riedl Institute of Communication Networks Munich University of Technology Anton.Riedl@ei.tum.de Tel: +49 - 89 - 289 23506

Abstract
In this paper, a new genetic algorithm is introduced which is used as a versatile tool for solving different types of optimization problems arising in the field of network planning. The genetic algorithm is applied to the minimum Steiner tree problem which plays an important role in the design of tree-structured passive optical networks in the access area. Furthermore, the same genetic algorithm is utilized for integrated planning of packet switched data networks.

1. Introduction The great diversity of questions and problems that originate from todays network planning tasks requires a large number of algorithms, each of which specializes in a specific problem with specific constraints. Almost all of the optimization problems relevant in network design are NP-complete. For most problems, there is no known algorithm that could guarantee to find the global optimum in a polynomial amount of time. In many cases, sophisticated heuristics have to be developed to achieve satisfying results. In this paper, a genetic algorithm is introduced that serves as a framework within which only simple heuristics are required. By applying genetic operators to specific solutions of a given problem, the algorithm guides the search towards an optimal point. This concept is applied to two very different fields in network planning. First, it is used to minimize the costs of fiber ducts when building a new passive optical network. As a second example, it is utilized in the context of packet switched network planning. Given the node locations and a requirement matrix, the algorithm determines a topology with routing paths and link capacity assignment so the overall costs are kept to a minimum. The paper is organized as follows: Section 2 introduces the concept of genetic algorithms. Section 3 deals with the application of the algorithm to passive optical network design. In section 4, the same genetic algorithm is used for packet switched network planning. Section 5 concludes the paper.

2. How do Genetic Algorithms Work? Basic Idea Genetic algorithms were first developed by John Holland [1] and are mainly used as search and optimization methods [2]. Given a large solution space, one would like to pick out the point which optimizes an object function while still fulfilling a set of constraints. In network planning, a solution point could be a specific link topology, a routing path structure, or a detailed capacity assignment with minimum costs. Genetic algorithms are based on the idea of natural selection. In nature, the properties of an organism are determined by its genes. Starting from a random first generation with all kinds of possible gene structures, natural selection suggests that over the time, individuals with "good" genes survive whereas "bad" ones are rejected. Genetic algorithms try to copy this principle by coding the possible solution alternatives of a problem as a genetic string. The genes can be bits, integers, or any other type from which a specific solution can be deduced. It is required that all solution points can be represented by at least one string. On the other hand, a specific gene string leads to exactly one solution. A set of a constant number of gene strings, each characterizing one individual, is called a generation. Since the different strings have to be evaluated and compared to each other, the notion of fitness is introduced. The fitness value correlates to the quality of a particular solution. In our case, it is inversely proportional to the cost of a network. Instead of working with the actual solution itself, genetic algorithms operate on the respective string representation. The following three basic operators are applied: reproduction crossover mutation The reproduction process creates a new generation. Starting from an existing generation, strings are reproduced with a probability respective to their fitness value. Strings which represent solutions with good properties have a higher chance to survive than strings depicting solution points with bad characteristics. This principle is also known as "survival of the fittest". The crossover operator exchanges genetic information between two strings. The strings of two randomly selected solutions are broken up at an also randomly chosen position, and parts of the strings are exchanged. One hopes that two solutions with good properties create an even better one. Fig.1 shows the principle of the crossover operator.

Fig.1 Crossover operator

New genetic material is introduced by the mutation operator. The values of individual genes are changed and, hence, new solutions are chosen. Mutation becomes important when after some generations the number of different strings decreases because strong individuals start dominating. In a situation of strong dominance of a few strings, the crossover operator alone would not bring any changes and the search for an optimal solution would be ended. To partially shift the search to new locations in the solution space, the mutation operator randomly alters genes.

Implementation of Genetic Algorithms The flow chart in Fig.2 shows the sequence of the basic operators used in genetic algorithms. We start out with a randomly selected first generation. Every string in this generation is evaluated according to its quality, and a fitness value is assigned. Next, a new generation is produced by applying the reproduction operator. Pairs of strings of the new generation are selected and crossover is performed. With a certain probability, genes are mutated before all solutions are evaluated again. This procedure is repeated until a maximum number of generations is reached. While doing this, the all time best solution is stored and returned at the end of the algorithm.

first generation (randomly)

mutation

crossover

evaluation

reproduction no max. generation ? yes return best solution Fig.2 Genetic algorithm flow chart

As one notices from the flow chart, the genetic algorithm serves as a framework which provides the outer cycle of the search or optimization process. An important part of the loop is the evaluation function which determines the fitness value of a specific string. Within this method, the string has to be mapped to a realistic solution, and the object function has to be evaluated. For this, heuristic methods might be necessary. 3. Planning of Passive Optical Networks Problem Definition Passive Optical Networks (PON) provide a way to gradually introduce fiber optic technology into access networks while still deploying parts of the traditional copper line or coax-cable systems. PONs can be implemented in several topologies. One configuration of choice is a tree structure where the Optical Line Termination (OLT) in the central office can be seen as the root and the Optical Network Units (ONU) as the leaves of the tree. In the field between the OLT and the ONUs only passive elements - the fibers and optical splitters - are deployed. Customer access points are connected to the ONUs via traditional technologies like copper or coax lines. Fig.3 illustrates the PON tree structure.

Fig.3 Structure of passive optical networks

When installing a new network in the access area, the majority of money has to be spent on digging the cable ducts. Thus, minimizing the total cost is mainly a matter of finding the shortest street paths which interconnect all ONUs with the OLT. A city map can be represented by a graph where the streets are the links, and the street junctions together with the ONUs and the OLT make up the nodes. The weights of the links are set to be proportional to the length of the respective streets. In some cases, for example, if some fiber lines exist or if some streets are preferred to be used as duct lines, special weight values can be assigned to theses edges. With this map representation, the optimization problem turns into the classical minimum Steiner tree problem. This means that we want to find a tree within a given graph which spans a designated subset of nodes in such a way that the sum of the costs of the selected edges becomes minimal. There already exists a number of algorithms that solve this problem exactly (see for example [3]). Since the minimum Steiner tree problem is NPcomplete [4], these algorithms have an exponential worst-case running time. Therefore, they are not applicable in the field of network planning where it is quite common to have a great number of nodes and edges. Genetic Algorithm The genetic algorithm that we apply to the design of passive optical networks follows the concept introduced in section 2. The genetic coding of a specific alternative of a Steiner tree consists of a string of integer values with one specific gene for every link in the graph. The integer value is assigned to the respective link as a pseudo link weight which is not correlated to the real cost value of this edge. The pseudo link weights are only auxiliary parameters. Given a genetic string with a pseudo link weight for every edge in the graph, a minimum spanning tree is built over all nodes in this graph. From this minimum spanning tree all nodes and links are cut off which are not essential to connect the Steiner vertices with each other. The remaining tree is a specific Steiner tree solution that connects only the set of ONU and OLT nodes. Fig.4 illustrates the use of two simple heuristics to find a Steiner tree. In this example, the genetic string is 3-1-9-2-2-7-1-5-4-2-3 with the integers assigned to the edges a through k, respectively.

Fig.4 Computation of a specific Steiner tree

This type of genetic coding guarantees that all possible solution alternatives can be represented by a genetic string. To obtain one specific Steiner tree, one has to set the pseudo link weights of the Steiner edges smaller than the ones of the remaining edges. It is another advantage of this coding that the crossover and the mutation operators applied to genetic strings produce again valid strings. Results The diagram in Fig.5 shows the evolution of the costs for a typical run of the genetic algorithm for a network with 463 nodes, including 44 ONUs, and 709 edges. For every generation the maximum and the minimum cost values are shown. Starting from a random first generation with usually high cost values, it can be observed that the costs decrease gradually. This is true for the minimum as well as for the maximum values. It indicates that the principle of "survival of the fittest" also works in the area of network planning, and that a crossover of two good solutions has a high probability of creating another good or even better solution.
35000 30000 Total Costs

Max
25000 20000

Min
15000 10000 10 20 30 40 50 60 70 80 90 100 110 Generation

Fig.5 Genetic algorithm cost evolution

The running time of the genetic algorithm depends on the size of the network, the number of genetic strings per generation, and the total number of evolution cycles. A large portion of the time is spent within the method which maps a genetic string to a specific Steiner tree solution and calculates its costs. For our sample network, the evaluation of one string takes approximately 0.4 to 0.5 seconds on a SPARC workstation. With a generation size of 600 strings and a total of 110 evolution cycles, the test run of Fig.5 required about 9 hours. 4. Planning of Packet Switched Networks Problem Definition The design of packet switched networks requires the solution of different types of problems, e.g. node placement and link dimensioning, routing optimization, server specification, or address assignment. In our paper we consider only the link topology and routing optimization aspects. Our design problem can be formulated as follows: Given a set of node locations and a requirement matrix with traffic values for all node-to-node pairs, the link topology and the routing paths are optimized according to the costs, so the average end-to-end packet delay does not exceed a specified value. The packet arrival process is assumed to be a Poisson process, and the routers are modeled as independent M/M/1 waiting queues.

Since the three design aspects - link topology, capacity assignment, and routing optimization are interdependent, they cannot be considered in isolation. Conventional planning algorithms usually handle this problem by repeatedly applying a sequence of methods to the different sub-problems as shown in Fig.6. For a fixed topology and a certain routing scheme, the capacities of the links are optimized. Afterwards, the capacity values are kept constant while the routing strategy is improved. This is repeated until the results converge. If all constraints are met, the solution is returned and the algorithm exits. If one is not satisfied with this result, a different link topology is chosen, and the optimization procedure is started anew. Unlike this traditional approach, our genetic algorithm looks at the whole picture of a specific network solution and evaluates it.
start link topology
not satisfactory

capacity assignment routing optimization

satisfactory

return solution

Fig.6 Conventional optimization procedure

Genetic Algorithm A genetic string represents a specific network alternative by assigning pseudo link weights to the edges of a fully meshed graph. From this graph, simple heuristics create a valid network with a certain link topology, capacity assignment, and routing specification. These heuristics are contained in the evaluation method of the flow chart in Fig.2.
1 36 2 1 5 7 6 graph with pseudo link weights 8 1 1 5

Shortest Path + Flow Assignment

Capacity Assignment

links with flow 0 links with flow = 0

resulting network

Fig.7 Computation of a specific network topology

Fig.7 shows how a genetic string is converted to a specific network solution. Starting from the fully meshed graph with directed links, the shortest path for every node-to-node pair is determined according to the pseudo link weights, and the selected links are marked. Edges which are not selected at all are discarded. The shortest paths correspond to the packet routes between two end systems. Based on this routing pattern and on the given requirement matrix, it is now possible to compute the traffic load on every link and, furthermore, calculate the optimal capacities [5]. In the case of discrete capacities, the continuous values are rounded up. Since current routing protocols like RIP and OSPF require bi-directional connectivity between neighbor gateways, an opposite edge is inserted for every link in the network if it does not already exist. The smallest possible capacity is assigned to these new edges, since only router messages will be transmitted over them. At the end, the costs for this specific network scenario are calculated and returned to the genetic framework.

Results The cost evolution resulting from the genetic algorithm for packet switched network planning looks similar to the one given in Fig.5. Again, the minimum and maximum values decrease gradually until a convergence point is reached. This indicates that genetic algorithms can be used in the field of packet network planning. A sample network topology which was computed by the genetic algorithm is shown in Fig.8. The structure strongly depends on the composition of the capacity costs. For high basic costs which are only proportional to the length of a link, the network mesh degree will be low. For decreasing fixed link capacity costs, the number of links in the network increases.

Fig.8 Sample network topology

5. Conclusion After a short introduction of the general concept of genetic algorithms, a novel implementation of a genetic algorithm is presented. In combination with simple heuristics, it is a versatile tool for solving different types of optimization problems arising in the field of network design. The genetic algorithm is applied to the minimum Steiner tree problem and to the topology and routing optimization of packet switched networks.

References [1] J.H. Holland, Adaptation in natural and artificial systems, Ann Arbor: The University of Michigan Press, 1975. [2] D.E. Goldberg, Genetic Algorithms in Search, Optimization & Machine Learning, Addison-Wesley, Massachusetts, 1989. [3] S. Chopra, E.R. Gorres, M.R. Rao, Solving the Steiner tree problem on a graph using branch and cut, Oper. Res. Soc. Am. J. Comput. 4 (3), pp. 320-335, 1992 [4] R.M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Plenum Press, New York, 1976 [5] M. Gerla, L.Kleinrock, On the Topological Design of Distributed Computer Networks, IEEE Trans.Commun., 25 (1), Jan 1977