10
Optimization of Restoration and
Routing Strategies
Brian C.H Turton
10.1 Introduction
All point-to-point communication networks have a means of directing traffic from a source
to a destination via intermediate nodes. This routing function must be performed efficiently
as it affects all aspects of network communications including jitter, latency and total
bandwidth requirement. Other issues related to routing, such as policing and traffic control
are not dealt with in this chapter.
There are two distinct approaches to ‘routing’ traffic, namely connection-oriented and
connectionless. Connectionless networks use information contained within the data packet
itself. Typically the destination address is all that is required, however explicit routing
information may also be contained within the packet. Connection oriented networks
establish the route first and subsequently use it for all traffic associated with the connection
until it is torn down. In both cases, a method is required for the efficient identification of
either a route for the packet or a route for the connection being established.
10.1.1 The Traditional Approach
Traditionally, routing has been static with permanent routes established in the switches or
dynamic with routes established according to the traffic flow at the time. In static routing
manual updates to the routing tables is still a common occurrence for connection oriented
networks, and is frequently based on the experience of the network manager. Different
forms of shortest path routing method (Steenstrup, 1995) are usually employed to assist in
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)
168 Telecommunications Optimization: Heuristic and Adaptive Techniques
designing these routes. It should be noted that the ‘length’ of a link may be associated with
time delay, blocking probabilities or financial cost, not just a hop count. In particular flow
deviation (Kershenbaum, 1993) can be very effective if a single route between node pairs is
required. There are no strong time constraints on this activity.
An alternative approach is to establish routes dynamically, allowing the network to
respond to changes in traffic, either when a route is established or a packet is received.
Different forms of link-state and distance vector routing (Tanenbaum, 1996) are used which
are designed to cope with the network’s distributed nature. These are combined with a form
of hierarchical addressing in order to make routing tables both manageable and efficient.
Occasionally node or link failures occur, which requires rerouting a large number of
connections, this activity is known as ‘restoration’. Unlike normal routing, a large number
of routes must be re-established in real-time. Although the normal techniques for dynamic
routing can be applied, it is likely to be far more efficient to look for the best set of routes
for the system as a whole rather than individually route according to the normal methods.
However the network must also ensure that the sudden activity generated by the failure
does not overwhelm the switches and that restoration occurs on an appropriate time scale
(<2 seconds is a generous time scale). Consequently, a new type of distributed algorithm
have been developed to disperse the work of restoring the links across the network. An
alternative to this is to have fixed restoration routes (protection switching) that were
established when the routes were first defined (static routing).
10.1.2 Possibilities for Evolutionary Algorithms
Dynamic routing at the time the connection is established, or when the packet is sent, is
unlikely to benefit from the use of Evolutionary Algorithms (EAs). There is only one
packet to forward or connection to establish, and consequently the existing techniques find
the optimum ‘greedy’ choice. EAs are useful when a large number of routes must be
established and a global optimum is required in order to efficiently utilise the available
bandwidth and ensure a suitable quality of service. This is particularly evident in ATM
where link utilisation levels may be over 85% and consequently any bandwidth savings
have a major effect on performance. This problem has led to research in:
• Static routing
• Restoration algorithms
• Routing Strategies and Benchmarks
• Aids to routing algorithms.
10.2 Problems Associated with Routing
10.2.1 Complexity
The simplest form of routing assessment to consider is to establish a traffic matrix using the
number of connections that can be established as the goal. This produces a number of
Optimization of Restoration and Routing Strategies 169
difficulties, for example, time delay is ignored even though it is a critical parameter for
real-time interactive voice and video traffic. In addition a simple connection count will not
take account of prioritisation. One of the major concerns associated with costing networks
is that the users’ view of the worth of a connection does not correlate well with bandwidth.
Traffic is not constant bandwidth, so connections may be assigned an effective bandwidth
that is believed to be sufficient to ensure the connection can be maintained. In practice, the
smallest effective bandwidth cannot be calculated in isolation from the rest of the traffic.
Two Variable Bit Rate (VBR) connections can share significant bandwidth if there is little
correlation between the two on peak usage. However two Constant Bit Rate (CBR)
connections or a VBR plus CBR cannot. At present, traffic on networks is not well enough
characterised to allow detailed calculations and even if it can be accurately simulated the
time-scale would be prohibitive for evolutionary techniques due to the large number of
evaluations required.
In practice the following metrics are used, ignoring some of the complexities of real
traffic flow.
• Average number of hops (or average number of hops per call)
• Maximum or average residual link capacity
• Maximum or average network delay
• Number of unserved circuit demands or packet discards a closely linked alternative is
the average utilisation or maximum utilisation levels
• Total network throughput
As the M/M/1 queuing model is often assumed the average network delay (T) is:
∑
=
−
=l
iii
i
fC
f
T
1
.
1
γ
where
γ
is the total arrival rate for the network (messages/sec), l is the number of links in
the network, fi is the flow rate for link i (bits/sec), and Ci is the capacity of link i (bits/sec).
In practice the total network delay is faster to calculate than the mean and differs only by
γ
.
Any more detailed calculations are likely to be extremely network-dependant.
Establishing benchmarks for realistic traffic generation and accurate simulations is still a
problem for researchers in this area. The following papers contain or refer to some data on
topolgies and traffic (Dutta and Kim, 1996; Mann, 1995; Turton and Bentall, 1998; Gavish
and Neuman, 1989; Mann and Smith, 1996). In practice the simple M/M/1 queuing model
(Mazda, 1996) is used rather than detailed simulation due to time constraints.
10.2.2 Timing and Efficiency
All evolutionary techniques require significant computational time. Consequently, the
approaches used have either had to deal with small numbers of routes or pre-calculate
170 Telecommunications Optimization: Heuristic and Adaptive Techniques
solutions. A reasonable commercial backbone network may well have over fifty nodes and
a degree of four. The typical number of routes broken by a single link failure depends on
the technology used. In ATM over a hundred paths could be disrupted. Each path is likely
to have hundreds of alternate routes if capacity constraints are ignored. If these values are
used as reasonable guides to the size of the problem the inherent time scale difficulties are
exposed. Despite these problems there are some positive points. Computer power is rising
exponentially and networks are not random meshes, operators want to reduce costs and
often base their networks on rings with additional chords. Consequently, the number of
loop-free alternate routes is much smaller than a worst case scenario indicates.
Nevertheless, EAs often have a run time of hours when sub-second times would be ideal.
10.3 An Evolutionary Approach to Routing and Restoration
A number of issues have been tackled by researchers relating to routing and restoration.
This section will outline some of the approaches taken, followed by more detailed
examples. Despite the real-time nature of restoration algorithms, it is possible to use
evolutionary algorithms to set up a strategy that is continually updated and provides a set of
pre-planned routes to a restoration algorithm. If the system can be informed of traffic
requirements before they need to be routed, the same algorithms can be used for routing.
Chng et al. (1994) describe a multi-layer restoration strategy which uses this technique and
demonstrates its effectiveness. Consequently an evolutionary algorithm is only
disadvantaged by the fact the routes are always based on slightly dated information. The
nature of the network and traffic will therefore determine the usefulness of this approach.
10.3.1 Evolving Paths
A number of authors encode an index to a table of alternate routes (Mann and Smith, 1996;
Shimamoto et al., 1993; Sinclair, 1998; Al-Qoahtani et al., 1998; Tanderdtid et al., 1997).
Typically the k-shortest paths are used within the table, but as pointed out by Mann and
Smith (1996), this may not be the ideal technique. The advantage of this method is that the
alternate routes available can be selected appropriately and then uniform, single point or
two-point crossover can be used to recombine the chromosomes. Mutation is achieved by
simply swapping to another randomly selected path. Results from several authors indicate
that this approach compares well with traditional techniques and performs at roughly the
same level when compared with simulated annealing. The key disadvantage is that only a
limited number of alternate routes are stored and the user, not the algorithm, chooses the set
of routes. By making this choice, before running the GA, some viable and effective options
may not be considered. Alternatively, if all routes are available in the tables, possibly with
limited lengths, a single population cannot contain indices to all routes. The algorithm will
find it difficult to search the set of viable routes. Pre-seeding the populations where useful
solutions are available has been shown to improve performance by ensuring some good sets
of paths are included.
Seo and Choi (1998) developed an evolutionary algorithm designed to find a good set of
alternate paths. Paths between a particular source and destination are stored as an ordered
list of nodes. Where common nodes exist sections of path between the common nodes can
Optimization of Restoration and Routing Strategies 171
be interchanged. A repair operator is used to remove loops caused by the recombination.
Mutation selects two nodes at random and generates a new partial path between the two
nodes. The fitness function is based on the number of common nodes, the common links
ratio and area surrounded by the set of alternate paths. Apart from the computational cost
the authors reported good results.
Cox, Davis and Qui (1991) used a request permutation technique to route the call
requests. For their problem, a series of traffic demands are sent that must be fulfilled at
some future time. A set of paths has been predetermined for each source destination pair
and call type. They suggeet a k-shortest paths (k ~ 4) approach is used with constraints for
the particular call type. In addition a set of path assignment probabilities based on the
traffic patterns is stored. Call requests are initially assigned paths according to the static set
of path selection probabilities. If the initial path selected is feasible then it is added to the
list of pending requests ready to be connected at the assigned time. If the path is not
feasible then an evolutionary algorithm is called that uses crossover and mutation to
permute the order in which the call requests will be considered. The chromosome decoder
will take each request in turn and check if the request can be assigned to any of the k-
shortest paths previously calculated for the appropriate source destination pair. If a suitable
path is found, its bandwidth is subtracted from the capacity available and the next request is
considered. Once all the paths that can be assigned have been placed, a fitness value is
calculated based on the cost of the capacity used for the set of paths and the cost of failing
to route the outstanding requests. Uniform order-based crossover is used with scramble
sublist mutation and an exponential fitness technique (Cox et al., 1991). Once the algorithm
has terminated, the solution undergoes a simple pair wise swapping of each adjacent pair of
requests in turn. If any swap improves the schedule it is incorporated into the schedule. At
this point the new call can be accepted if all requests can be accommodated, or rejected. For
small networks greedy heuristics, integer programming and ‘random’ search were effective.
The evolutionary approach proved best technique for larger networks (~50 nodes or more).
An alternative approach was taken by Bentall et al. (1997), using a two-dimensional
encoding with an unusual permutation based crossover technique. They use loopless paths,
limited in maximum length, within the chromosome. The procedure is quite different from
those discussed so far and so a detailed explanation is given at the end of the chapter.
10.3.2 Evolving Routing Tables
An alternative to defining paths for each traffic requirement or source/destination pair is to
evolve the routing tables themselves. Sinclair (1993) uses a set of integers for each valid
node-pair. The number of integers corresponds to the degree (d) of the originating node.
The integers are ordered and the first two integers must be in the range 0 to d–1. All
subsequent integers must be in the range 0 to d–2. Each node has an ordered list of
connected nodes. The first integer x refers to the (x+1)th node as the first choice node to
transmit to. Subsequent integers refer to the xth node where a zero means no more choices
are available. When trying to establish a call, if none of the choices result in a successful
transmission the call will be referred back to the previous node to ascertain if it can
successfully try another route. In the event of backtracking to the source node, and having
no choices available, the call is lost. Despite using step change and offset inverse penalty