13-08-2012, 11:34 AM
The Application of a Genetic Algorithm to Trunk Network Routing Table
Optimisation
1The Application.pdf (Size: 83.83 KB / Downloads: 42)
Introduction
Traditionally, research into circuit-switched (C-S) networks has been divided into two areas, reliability
and performance, each making little reference to the other. More recently, however, research has focused
on unification of the two. One possible choice for a combined performance and reliability measure is the
overall network grade-of-service (NGOS), i.e. the overall probability of blocking, averaged over all node
pairs, taking into account both the offered traffic between node pairs and the link (trunk group)
availabilities.
In a 1991 paper [1], this author gave a method for the overall NGOS, by single-moment analysis, of fixedalternative-
routing (FAR) circuit-switched communications networks with reliable nodes but unreliable
links. The method employs a Markov model for an unreliable link, in combination with earlier work [2-4],
so as to greatly reduce execution time compared to prior algorithms.
In two subsequent papers [5,6], this author used the analysis method as part of three heuristic routing table
optimisation algorithms, which obtain routing tables such that the overall NGOS is minimised under
different call control rules. These algorithms were then used to demonstrate the improvements in trunk
network fault-tolerance (assessed in terms of the overall NGOS) that can be achieved both through
routing table updating in the event of link failure [5], and through network augmentation i.e. the addition
of extra links to a network, either in parallel with existing links, or between nodes that previously had no
direct connection [6].
In the current paper, an alternative approach to routing table optimisation is taken, based on combining a
genetic algorithm with Sinclair’s analysis method. “Genetic algorithms are search algorithms based on
the mechanics of natural selection and natural genetics. They combine survival of the fittest [amongst a
population of] string structures with a structured yet randomised information exchange [between
population members] to form a search algorithm with some of the innovative flair of human search. In
every generation, a new set of artificial creatures (strings) is created using bits and pieces of the fittest of
the old; an occasional new part is tried for good measure. [7]”
Analysis of a Network Using a Markov Model for Unreliable Links
A method for the single-moment overall NGOS analysis of FAR C-S communications networks with
reliable nodes but unreliable links was described in [1]. It was developed using techniques given by Lin e t
a l . [2] and Chan [3], in combination with a recursive algorithm for path-loss sequences and a Markov model
for unreliable links both developed by this author. The method uses the iterative approach to network
analysis first developed by Katz & Cooper [8], and it relies on the standard eight assumptions discussed
by Lin et al., as well as the assumption that all the nodes in the network are perfectly reliable. For
details of the method, and a comparison with a method based on earlier work, see [1].
Heuristic Routing Table Optimisation
Using Sinclair's method for the necessary network analysis, three heuristic routing table optimisation
algorithms were described in [5] for C-S networks with unreliable links employing OOC, SOC and OOC-SF
routing. The three methods do not carry out an exhaustive search of all possible loop-free routing tables,
and therefore cannot provide the optimum routing table for the chosen call control rule. They were
devised, however, to provide the best possible routing table within the assumptions made. The
optimisation criterion used by all three methods is the minimisation of overall NGOS. For details of the
three routing table optimisation algorithms, and their application to a larger example network, see [5].
Basics of Genetic Algorithms
Instead of searching directly through the desired problem space for an optimum (in this case, a routing
table of minimum overall NGOS), genetic algorithms decouple the problem into genotypes, analogous to
the chromosomes inherited by an individual, and phenotypes, analogous to the organism that develops
from those chromosomes. The only link between them in the algorithm is that any given genotype can be
decoded into a phenotype and its raw fitness assessed; this is analogous to the organism's ability to
survive and reproduce in the environment. In this case, the genotypes are strings of integers, and the
phenotypes are the routing tables decoded from them, with their raw fitness assessed in terms of their
overall NGOS.
Routing Table Encoding
For the example network of Section 9, genotypes of total length 64 were used. For each of the valid node
pairs, i.e. (0,1), (0,2), (0,3), (0,4), (1,0), (1,2), ..., an entry of d integers, equal to the degree of the
originating node, was used. The range of integers permitted in each position, within an entry, was from 0
up to a maximum of d-1 for the first and second, between 0 and d-2 for the third, down to between 0 and 1
for the last. For example, node 0, of degree 4, would have a four integer entry to encode the routing for node
pair (0,1), with the first and second positions in the range 0 to 3, the third in the range 0 to 2 and the
fourth in the range 0 to 1.
When decoding a genotype, for any given entry, the numbers of the d nodes directly connected to the
originating node would be placed in numeric order. An integer x in the first position in the genotype entry
being decoded would determine the first-choice route as being via the (x+1)th node in the list. For example,
for node pair (1,3), the directly connected node numbers are: 0,2,3,4. An entry of 2121 would mean that the
first choice route was the 3rd node i.e. 3. For the second and subsequent positions, a 0 is taken to indicate no
further choices (routes), and an integer x (greater than 0) to indicate the xth remaining node. The full
routing for (1,3) would thus be decoded as (3,0,4,2). If the entry had instead been 2101, then this would
have been decoded as (3,0); any integers beyond a zero in the second or subsequent positions are ignored.
Penalty Function for Looped Routing Tables
The example network, for OOC routing, has some 1.85x1026 valid routing tables. However, the vast
majority of these are not loop free: when routes are generated from the table, several of these would, if
they were not eliminated, traverse the same node more than once! Clearly, the random nature of the
initial genotype population will result in many, if not all, the initial routing tables containing a large
number of such loops. As a result of the automatic removal of these routes in the course of analysis [1], the
fitness of looped routing tables is comparatively low, but the differential is insufficient to ensure the rapid
elimination of looped tables from the population. Consequently, a penalty function [7] must be introduced
to reduce the raw fitness returned by the phenotype in the event that the routing table is looped. Several
penalty functions were examined, and the best and worst are illustrated in Figures 1 and 2 below.
Conclusions and Further Work
Despite the promise of genetic algorithms, before the commencement of the study, to be highly suitable for
this type of optimisation problem, they have yet to fulfil that promise. Sinclair's heuristic optimisation
algorithm, at least for the example network examined, would appear to be far superior. Nevertheless,
there are still some possibilities unexplored.
With regard to the genetic algorithm itself, three areas of further work occur to this author. Firstly, the
penalty function could be modified to include a penalty for routing tables that result in one or more high
individual node-to-node grades-of-service; such a penalty might serve to enhance the overall convergence.
Secondly, other routing table encodings could be explored, possibly leading to improved algorithm
performance. Finally, some of the more advanced genetic algorithms reviewed by Goldberg [7] could be
tried.