9
The Genetic Adaptive Routing
Algorithm
Masaharu Munetomo
9.1 Introduction
A routing algorithm constructs routing tables to forward communication packets based on
network status information. Rapid inflation of the Internet increases demand for scalable
and adaptive network routing algorithms. Conventional protocols such as the Routing
Information Protocol (RIP) (Hedrick, 1988) and the Open Shortest-Path First protocol
(OSPF) (Comer, 1995) are not adaptive algorithms; they because they only rely on hop
count metrics to calculate shortest paths. In large networks, it is difficult to realize an
adaptive algorithm based on conventional approaches. This is because they employ
broadcasts to collect information on routing tables or network link status, which causes
excessive overheads in adaptive algorithms.
In this chapter, we describee an adaptive routing algorithm called the Genetic Adaptive
Routing Algorithm (GARA). The algorithm maintains a limited number of alternative
routes that are frequently used. Instead of broadcasting a whole routing table or link status,
it only observes communication latency for the alternative routes. It also tries to balance
link loads by distributing packets among the alternative routes in its routing table. The
alternative routes are generated by path genetic operators.
9.2 Routing algorithms in the Internet
From the early history of the Internet, vector distance routing algorithms based on Bellman-
Ford’s algorithm (Bellman, 1957; Ford and Fulkerson, 1962) have usually been employed.
Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith
© 2000 John Wiley & Sons, Ltd
Telecommunications Optimization: Heuristic and Adaptive Techniques.
Edited by David W. Corne, Martin J. Oates, George D. Smith
Copyright © 2000 John Wiley & Sons Ltd
ISBNs: 0-471-98855-3 (Hardback); 0-470-84163X (Electronic)
Telecommunications Optimization: Heuristic and Adaptive Techniques
152
The Routing Information Protocol (RIP) (Hedrick, 1988) based on the vector-distance
algorithm with hop count metric is commonly used even now in small local area networks.
The algorithm yields many communication overheads in larger networks because they
periodically send broadcast messages that contain a whole routing table. More precisely,
the number of messages to broadcast routing tables is proportional to 2
n (n is the number
of nodes in a network) and the size of a routing table is proportional to n, which means that
the total communication overhead for the routing information exchange becomes ).( 3
nO
The vector distance algorithm also suffers from its slow convergence because it is
necessary for the routing tables to reach all the nodes in the network to obtain the correct
distance.
To reduce communication overhead, routing algorithms based on link status information
such as the SPF (Shortest Path First protocol) send broadcast messages that only contain
information on link status. Based on a topological database generated from the collected
link status, the algorithm calculates the shortest paths employing Dijkstra’s shortest path
algorithm (Dijkstra, 1959) in each node. The SPF broadcasts messages that only contain the
nodes’ link status instead of the entire routing table. Therefore, the size of a message that
contains link status information becomes )1(O when the degree of nodes is constant such
as in a mesh network, and the size becomes )(log nO in a hypercube network. However,
the number of messages is also proportional to ,
2
n which leads to extensive overheads in
larger size network. Therefore, the OSPF (Open Shortest Path First protocol) (Moy, 1989),
a widely used network routing protocol for Interior Gateway Protocol (IGP) (Comer, 1995)
based on the SPF, relies on hop count metric and detects topological changes such as link
failure.
It seems easy to collect information on the communication latency of links and calculate
routes with minimum delay; however, it is almost impossible in large networks. This is
because we need to collect the communication latency of all the links frequently by
broadcast messages, which leads to extremely heavy communication overheads. In
addition, delayed information for the latency may create far from optimal routes. In a huge
network such as the Internet, it is essentially important for routing algorithms to be
scalable. To achieve scalability in adaptive network routing algorithms, it is necessary to
observe communication latency with as few communication overheads as possible.
9.3 GAs in Network Resource Management
Before introducing our routing algorithm by GA, this section gives a brief review of related
work concerning the application of GAs to network resource management problems. Since
many of the problems are classified into combinatorial optimization problems, they can
directly be solved by GAs. For example, an application of GA to network routing in
telecommunication networks is proposed in the Handbook of Genetic Algorithms (Davis,
1991) by Cox et al. (1991). The authors solved a constrained optimization problem that
allocates link bandwidth to each connection. For another approach, Munakata and Hashier
(1993) solved the maximum network flow problem. The objective of this optimization
problem is to maximize the network flow based on the global information of the network.
These two algorithms cannot be applied directly to routing in packet-switching networks
such as the Internet because they are based on circuit-switching networks, in which the
The Genetic Adaptive Routing Algorithm 153
bandwidth of the network is allocated to circuits – connections between nodes (Tanenbaum,
1988). On the other hand, Carse et al. (1995; and Chapter 8) applied a Fuzzy Classifier
System (FCS) to a distributed routing algorithm on packet-switching networks in which
each packet is routed independently by a routing table. This routing algorithm, however,
only decides whether a packet should take a direct route or an indirect route by using a
FCS. Therefore, the algorithm cannot be directly applied to actual routing algorithms.
9.4 Overview of the GARA
The Genetic Adaptive Routing Algorithm (GARA) is an adaptive routing algorithm that
employs genetic operators to create alternative routes in a routing table. It is based on
source routing algorithms, which determine the entire route of a packet in its source node.
Each node has a routing table containing a set of alternative routes, each of which is created
by genetic operators. Each packet selects one of the alternative routes to the destination.
The algorithm observes the communication latency of routes frequently used.
Figure 9.1 Overview of the GARA.
Figure 9.1 shows an overview of the GARA. Each node has a routing table that contains
routes to destinations. For each destination, a set of alternative routes is assigned. Each
route has its weight value (as its fitness) that specifies the probability for the route to be
selected from a set of alternative routes. The weight is calculated from the communication
latency, observed by sending delay query packets. At the beginning, the routing table is
empty. When a packet must be sent to a destination, a default route to the destination is
generated by using Dijkstra’s shortest path algorithm based on hop count metric. After a
specified number of packets are sent along a route, a packet is sent to observe the
Node
Routing table
Dest. Route Delay Weight
0
1
2
3
4
5
6
1 (0 1) 100 1.0
4 (0 6 4) 70 0.7
(0 3 4) 90 0.3
5 (0 3 5) 100 0.7
(0 3 4 5) 150 0.1
(0 6 4 5) 130 0.2
6 (0 6) 50 1.0
Delay
Query &
Answer
Applying
Path Genetic Operators
(Only contains routes frequently used)
Network
Telecommunications Optimization: Heuristic and Adaptive Techniques
154
communication latency of the route. To generate alternative routes, path genetic operators
are invoked at a specified probability after every evaluation of weight values. To prevent
overflow of a routing table, selection operators are applied to reduce its size. A selection
operator deletes a route that has the lowest weight among the routes to a destination.
Moreover, another selection operator may be applied; this deletes all the routes to a
destination to which the number of packets sent is the smallest among all the destinations in
a routing table.
The GARA can greatly reduce communication overheads for dynamic observation of
network status by limiting the observation to alternative routes frequently used. It can also
reduce the possibility of congestion by distributing packets probabilistically among the
alternative routes.
9.5 Path Genetic Operators
For the GARA, path genetic operators such as path mutation and path crossover are
designed to generate alternative routes based on the topological information of the network.
The path mutation operator causes a perturbation of a route in order to create an alternative
route. The path crossover exchanges sub-routes between a pair of routes.
A route (path) is encoded into a list of node IDs from its source node to its destination.
For example, a route from node 0 to node 9 is encoded into a list of nodes along the route:
(0 12 5 8 2 9). The route is constrained to the network topology; that is, each step of a route
must pass through a physical link of the network.
9.5.1 Path Mutation
The path mutation generates an alternative route by means of a perturbation. Figure 9.2
shows how to perform this mutation operator. To perform a mutation, first, a node is
selected randomly from the original route, which is called a mutation node. Secondly,
another node is randomly selected from nodes directly connected to the mutation node.
Thirdly, an alternative route is generated by connecting the source node to the selected node
and the selected node to the destination employing Dijkstra’s shortest path algorithm.
More precisely, the path mutation proceeds according to the following sequence where r
is the original route and r′ is its mutated one.
1. A mutation node m
n is selected randomly from all nodes along the route r, except its
source and destination nodes.
2. Another node m
n′ is selected randomly from neighbors of the mutation node, i.e.
m
n′).( m
n
ε
∈
3. It generates a shortest path 1
r from the source node to m
n′, and another shortest path
2
r from m
n′ to the destination.
4. If there is no duplication of nodes between 1
r and 2
r, they are connected to have a
mutated route .
21 rrr += Otherwise, they are discarded and no mutation is performed.
The Genetic Adaptive Routing Algorithm 155
Figure 9.2 Path mutation applied to a route.
Suppose that the mutation operator is applied to a route r = (0 3 5 6 7 10 12 15). First, we
select, for example, a node 7 as a mutation node. Secondly, another node 8, for example, is
randomly selected from the neighbors of the mutation node. Thirdly, by Dijkstra’s shortest
path algorithm, we connect the source node 0 and the selected node 8 to generate a path
1
r=(0 2 4 8). We also connect node 8 and the destination node 15 to generate another path
2
r= (8 10 12 15). We finish the mutation by connecting the routes 1
r and 2
r to eventually
have r′ = (0 2 4 8 10 12 15). We do not generate a route r′ if any duplication exists between
1
r and .
2
r This is because we need to avoid creating any loop in a route that passes through
the same nodes twice or more.
9.5.2 Path crossover
The path crossover exchanges sub-routes between a pair of routes. To perform the
crossover, the pair should have the same source node and destination node. A crossing site
of the path crossover operator is selected from nodes contained in both routes. The
crossover exchanges sub-routes after the selected crossing site. Figure 9.3 shows an
overview of the operator.
The crossover operator applied to a pair of routes 1
r and 2
r proceeds as the following
sequence.
1. A set of nodes c
Nincluded in both 1
r and 2
r (excluding source and destination nodes)
are selected as potential crossing sites. If c
Nis an empty set, we do not perform the
crossover.
2. A node c
nis selected randomly from c
N as a crossing site.
3. The crossover is performed by exchanging all nodes after the crossing site c
n between
1
r and .
2
r
Suppose that a path crossover is applied to a pair of routes 1
r and 2
r from node 0 to node
20 as in the following:
Original Path
Mutation
Mutated Path
r1
r2
n’
m
n
m