Fast Network Design for Telecommunications
McMahon, Marcus Randall and Steve Sugden
In designing a telecommunications network, nodes that represent telephone exchanges or communication switching centres need to be connected in an economical way to handle expected point-to-point traffic. Various constraints on the topology, node and link capacities are to be respected. Two methods are investigated for optimal network synthesis. The first is a heuristic which rapidly obtains a solution of moderate quality. The second is a fast genetic method which can produce significantly better solutions.
We discuss heuristics for the following problem of network design: nodes such as telephone exchanges are to be linked in order to carry expected traffic between origin-destination (O-D) pairs. Each possible link has a cost per unit of traffic carried and a capacity limit on traffic carried. There are also constraints on traffic carried through each individual node and on the number of connections to each node (degree limit). In addition, there is a limit on the number of links on each path along which traffic is carried (hop limit). We would like to satisfy the traffic demand by identifying the links which give us the lowest cost solution while respecting the constraints. It is planned to eventually extend the work to nonlinear cost functions.
Our previous work (Berry, Murtagh, McMahon, Sugden and Welling 1999) in this field provided a novel (Genetic Algorithm - Linear Program) GA-LP approach for finding near-optimal solutions. The GA-LP method generates many alternative topologies. For each topology, the LP provides an optimal allocation of lows. However, this approach has limitations in regard to network size for both CPU time and memory requirements (the LP may be quite large). In this paper, we investigate more rapid methods in which the optimality of flow allocation is not guaranteed. These methods extend the range of applicability to very large networks.
Let G be the set of all undirected graphs on n nodes with G a member of this set. We represent G by its upper triangular node-node adjacency matrix B with elements bij. The problem is to find a member G* which minimises the cost of transporting required origin-destination (O-D) flows subject to specified link, node capacity, node degree and chain hop-limit constraints. The total bandwidth (flow) requirement on virtual path connections between O-D pair p-q is given by Fpq (without loss of generality represented as an element of an upper triangular matrix). The partial flow along the rth route between node p and node q is denoted by and is the cost per unit flow on this route.
n is the number of nodes.
is the cost per unit flow on route r between O-D pair p-q.
Fpq is the total bandwidth (flow) requirement between O-D pair p-q.
is 1 if the link p-q exists on route r between nodes i,j, 0 otherwise.
is the upper bound on the available capacity (total flow) on the link i,j.
is the upper bound on total flow at node i. This flow comprises traffic originating at, terminating at and traversing node i.
Hmax is the upper bound imposed on the number of links in a route (the hop limit).
is the amount of traffic routed between p and q on route r.
Equations 1 to 8 represent the model of the network synthesis problem. Equation 1 is the objective function in which the traffic costs along the routes is minimised. Equation 2 is used to calculate the total flow on each link. Constraint 3 ensures that the bandwidth is distributed among the appropriate routes. Constraint 4 ensures that the node capacities are not exceeded while 5 ensures that the link capacities are not exceeded. The hop-limit is preserved in 6 and the constraints that ensure that the nodes meet the node degree constraints are modeled in 7.
Solutions may be expressed in several different ways. In this work, they are generated as flows on chains. Thus we seek an optimal network synthesis and optimal chain flow pattern. Various alternative formulations of the problem are discussed in Berry, McMahon, Murtagh and Sugden (1997); the formulation has a significant impact on the appropriate solution technique. The problem is related to classical work on network flows, but adds further realistic constraints, thus making it applicable to industry based problems.
We develop a solution using a greedy constructive heuristic. The solution consists of a set of chains (sequences of directed links), with each chain carrying a specified quantity of traffic from a source to a destination. We start with an empty set of chains and terminate when all traffic is handled or when the method can find no more useful chains. The latter may occur because the problem is infeasible or the method is inadequate to find a feasible solution (these cases cannot be distinguished).
At each stage, we add the chain of lowest cost which carries traffic between a source and destination (other greedy heuristics are also possible). We search exhaustively through the whole network for such a chain. The traffic allocated to each chain is the largest possible and is determined by either the traffic demand, or by the lowest unused capacity of the nodes and links on the chain.
We respect the various constraints as follows: if the capacity of any link becomes fully used, then the cost of making further use of that link is made prohibitive. If the flow capacity of a node is reached, all links to that node are effectively removed by the same method. If the maximum degree of a node is reached, unused links to that node are removed.
It is not difficult to construct cases where the method will find a non-optimal solution or will fail to find any solution. However, the heuristic has the following desirable properties:
The algorithm takes the following form:
Solution begins as empty set of flows;
Search whole network for the cheapest available chain which
can carry useful traffic (see below);
Find the largest flow which can be carried on the chain and
add this to the solution;
Update remaining link and node capacities;
Until problem is solved or no useful path can be found;
The search for a path is made by a modified shortest path algorithm carried out from each node in the graph. There is scope for improving efficiency by placing paths in some form of priority queue. The network is now searched for the cheapest chain that can carry useful traffic. This is done as follows:
Set C = cost of current cheapest chain to infinity;
For each node in graph which is source of traffic do
Use depth first search (limited by C) to find chains which can
carry useful traffic from this node;
Update C if a cheaper chain is found;
Note that more investigation is needed to find whether it is more efficient to use a special purpose algorithm in place of the depth first method used at present. Some results obtained by using this heuristic appear later in the paper.
A Genetic Algorithm
Our solution techniques use a GA approach. For extensive discussions on GAs, see Goldberg (1989). In this section we describe our method which being a genetic algorithm generates a large number of different solutions rather than the single solution described above.
There are considerable difficulties in generating a feasible child solution whose properties are a combination of the properties of two parent solutions. For methods which do this see Berry et al. 1999.
In this investigation, a chromosome is used which consists simply of a permutation of the node numbers. This permutation is used as input into a solution generating procedure which shares some properties with the heuristic described above. In this procedure, each node in the permutation is taken in turn and a modified shortest path search used to find flow paths for traffic originating or terminating at that node. The same depth first algorithm is used, although it is unlikely to be the best. Since each search is restricted to paths with a particular endpoint, the generation process is faster than in the method above.
If constraints are absent, then the procedure always finds the same optimum solution, independent of the permutation. However, if the constraints induce competition among the flows for low cost paths, then flows from nodes early in the permutation have a distinct advantage over flows from later nodes.
The process commences by generating a random set of node permutations, from which a starting population is obtained via the solution generating procedure. Our experience shows that a considerable variety of solutions with a wide range of costs are generated.
Several alternative ways of effecting crossover for permutations have been discussed in the literature (Goldberg 1989). A single point crossover was chosen where a crossover point within the chromosome is chosen randomly. The initial section of the permutation from one parent is copied up to this point. The child permutation is completed by placing the unused node numbers in the remaining positions in the same order in which they appear in the second parent. This is known as PMX (Goldberg 1989).
It was decided to use a replacement technique where each new child replaces the current worst solution in the population. If the child is even worse, no replacement takes place. This constitutes a form of selection. Given this decision, the population must gradually improve in quality, or remain static. In the current version, no bias is introduced to favour better parents for breeding. All solutions are chosen with equal probability. This means that convergence to a good solution takes place more gradually. However the best solutions are never removed from the population so that good genes are not lost.
Mutation can be effected by simply interchanging two randomly chosen nodes in a permutation before a solution is generated.
Some experimentation was undertaken to find good values for the population size, number of solutions generated and mutation rate. In the Results section below, we show the best solutions obtained after several such experiments.
A simple four node problem is used to illustrate the method, which is applicable to both directed and undirected graphs. The link costs appear in Figure 1. Note that because of the symmetry between origins and destinations, the flow from node 4 to node 1 satisfies the demand which was originally expressed as being from node 1 to node 4.
Figure 1: A simple four node network.
The matrix of traffic demands is as follows:
The capacity of each link is 10 units, and the capacity of each node is 30 units. The hop limit is 2 links. If our chromosome is the permutation 4 2 3 1, then the following solution is obtained, which has a cost of 248 units.
With a slightly different permutation of 4 3 1 2, we obtain a different solution, with a cost of 224 units.
Heuristic A finds the same solution as the second solution above, but chooses paths in a different order.
In this trivial example, the genetic algorithm quickly converges on the second solution, which is optimal.
Preliminary results for the genetic algorithm appear below, with the results from Heuristic A appended for comparison. The methods were used on just two problems, but with various hop limits. Each result is the best obtained in three runs of the genetic algorithm. For the 10 job problem, a population of 10 solutions is adequate, with a mutation rate of 0.5 and 200 solutions generated. With the 50 job problem, a population of 20 solutions worked better, with a mutation rate of 0.5 and 300 solutions generated. A high mutation rate is used to ensure genetic diversity.
With the 10 node problem, the population tended to converge to a group of similar permutations which generated solutions of the same value. With the 50 job problem, convergence did not always take place in 300 solutions, so improved solutions would be expected with longer runs. Computational results are shown in Table 1.
Table 1: Computational results.
For the smaller problem, Heuristic A is quick and successful. However for the larger problem, the genetic algorithm is more successful. Even the initial population contains better solutions than the one obtained from Heuristic A when the hop limit is very restrictive.
The methods have not been precisely timed, but the time taken by Heuristic A is measured in seconds for all problems. The genetic algorithm takes a few seconds for the small problem and a few minutes for the large problem. One or both of these methods may have a place in a commercial product that we are developing which uses more elaborate but slower methods to generate better solutions.
In future, we wish to test other heuristic techniques including simulated annealing, tabu search. An early description of this work is found in Randall, McMahon and Sugden (1999).
The authors gratefully acknowledge the support of the Australian Research Council under Large Grant #A69601975.