|
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
Chris Leckie
AI Systems Section
Telecom Australia Research Laboratories
Clayton, Victoria, Australia
Email: c.leckie@trl.oz.au
A central issue in optimisation problems is how to manage the complexity of search. One approach is to use Hopfield nets to search efficiently for near-optimal solutions [1]. This approach is useful in time-critical applications when a good solution is needed quickly rather than waiting for the best solution. A potential problem in the use of Hopfield nets lies in finding an appropriate energy function that encodes both the cost function for the optimisation problem as well as penalty functions for any constraints on the solution [2]. A poor choice of energy function can lead the net to a highly sub-optimal solution that satisfies the constraints, or a low cost solution that violates some constraints.
In this paper, we describe an alternative connectionist approach for solving resource allocation problems. The critical difference in this approach is that we restrict the changes that can be made to each node so that the state of our network always represents a feasible solution to the problem. Although we cannot guarantee that the network will converge on a local minima, as is the case with Hopfield networks, we demonstrate that our approach can quickly find near optimal solutions in practice.
We begin in the next section by describing our application domain, which is the problem of resource allocation in telecommunication network optimisation. In Section 3, we present the connectionist method that we have used to solve this problem. In Section 4, we demonstrate how our approach can efficiently find near-optimal solutions for a typical problem instance. We conclude with a discussion of these results and areas for further study.
The telecommunication network optimisation problem that we have studied is how to allocate transmission capacity in Synchronous Digital Hierarchy (SDH) networks. SDH is a new standard for high capacity backbone networks. Such a backbone network could be used to interconnect the capital cities using transmission links with a capacity of up to 2.5 Gb/s. Figure 1(a) shows a simple example of such a network, comprising three sites (labelled 1, 2 and 3) that are interconnected by three transmission links (labelled A, B and C). In this network configuration, calls from site 1 that are destined for site 2 can follow one of two alternative paths; that is, directly via link A, or indirectly via links B and C (see Figure 1(b)).
Figure 1: A simple example of an SDH network
In general, there may be several alternative paths between any origin-destination pair of sites. The SDH standard provides a flexible method for allocating transmission capacity to these paths. Each path is allocated a certain amount of capacity by reserving capacity on the sequence of transmission links that is followed by the path between the two sites. These paths are maintained by the SDH switching equipment which is located at each site. Whereas previous backbone network technologies required physical changes to network hardware in order to change the capacity allocation to each path, SDH networks can be reconfigured in software.
Given that it is now possible to reconfigure these kinds of networks on-line, this raises the issue of how to optimise the new configuration in a time-efficient manner. In this optimisation problem, we are given as input: (1) the amount of traffic offered between each pair of origin/destination sites - that is, the number of calls offered; (2) the capacity of each link in the network - that is, the number of calls that can be carried on each link; and (3) for each path between a pair of origin/destination sites, the sequence of transmission links used by that path. The aim of optimisation is to find an allocation of link capacity to each path such that the total traffic carried by the network is maximised.
This optimisation problem was first formalised by Gopal, Kim and Weinrib as a nonlinear integer programming problem [3]. The decision variables in the optimisation problem correspond to the capacity assigned to each path. Constraints are added to ensure that the capacity assigned from a link to each path that uses the link is less than the total link capacity. The cost function to be minimised for the problem is based on the Erlang-B function [4], which can be used to determine the expected number of calls blocked, given the number of calls offered and the capacity available to carry those calls. To solve this problem, they developed a heuristic algorithm that used a greedy search strategy.
More recently, Herzberg and Bye have reformulated the problem as a linear programming problem [5]. Since the cost function is monotonically concave, it can be replaced by a piece-wise linear approximation. This enables them to solve the problem using the primal simplex algorithm.
In the model that we have developed to solve the optimisation problem described in the previous section, we encode the problem in a three-layer connectionist network (see Figure 2). The nodes in each layer are characterised as follows: (1) pair nodes (top layer), each of which represents a pair of origin-destination sites in the SDH network to be optimised; (2) link nodes (bottom layer), each of which represents a transmission link in the network; (3) path nodes (middle layer), each of which represents a path between an origin-destination pair of sites. Each path node is connected to a single pair node and one or more link nodes. The pair node connected to a path represents the pair of origin-destination sites connected by the path. The link nodes connected to a path represent the transmission links that are used by the path. Note that each origin-destination pair can be connected by multiple paths, and each path may be made up of one or more links. Figure 2 contains part of the optimisation network that corresponds to the SDH network in Figure 1.
Figure 2: A portion of the optimisation network for the SDH network in Figure 1
Let us now consider the two sets of inputs to the optimisation network. The first set of inputs represent the offered traffic. Each pair node in the upper layer has a single input from outside the network, which represents the number of simultaneous calls that are expected from the origin site to the destination site corresponding to that node. These inputs to the upper layer can be interpreted as the demand to be satisfied. The second set of inputs represent the installed link capacities. Each link node in the lower layer has a single input from outside the network, which represents the maximum number of calls that can be carried by that link. These inputs to the lower layer can be interpreted as the resources available to satisfy the demand.
The outputs from the optimisation network are attached to the pair nodes in the upper layer. Each pair node has a single output to the world outside the network. This output represents the number of calls offered to the pair that could not be carried due to lack of capacity assigned to that pair. These are known as overflow calls, and can be interpreted as the unsatisfied demand in the network. The number of overflow calls from a pair node is calculated using the Erlang-B function, based on the number of calls offered to that pair, and the total capacity assigned to the paths that connect the origin and destination sites of that pair. The sum of the outputs from all the pair nodes thus represents the total number of overflow calls in the network.
The final point to note about our network representation is the interpretation of the state of each node. The internal state of a link node represents the amount of unallocated capacity within that link. Initially, this will be the full capacity of the link. During the course of optimisation, link capacity is assigned to the paths that use the link, and the amount of unallocated capacity in the link decreases. The internal state of a path node represents the capacity that has been assigned to that path. Initially, this will be set to zero and will increase as capacity is allocated to the path from the links that the path uses. The internal state of a pair node is the number of overflow calls from that pair. Initially, this will equal the number of offered calls. It will then decrease as capacity is allocated to the paths used by that pair.
The allocation decisions are made at the middle layer in response to the levels of unsatisfied demand and available resources reported from the upper and lower layers respectively. Optimisation proceeds by iteratively selecting a path node at random, and modifying its capacity allocation using a heuristic update rule. When the capacity allocation of a path is updated, the state of the pair and link nodes connected to that path are also updated. This approach is similar to Hopfield nets, in the sense that optimisation is distributed across the network in the form of update decisions that are made locally to each path node. However, in contrast with Hopfield nets, we restrict the changes that can be made by the node update function so that the state of our optimisation network always represents a feasible solution to the problem.
The critical design issue is the choice of an appropriate update function. The update function must decide whether to increase or decrease the capacity allocated to the path node being examined. The maximum amount by which we can increase the path's capacity is determined by the maximum unallocated capacity that is available from all the link nodes connected to the path. The maximum amount by which we can decrease the path's capacity is simply the capacity that is currently allocated to the path. The change to a path's capacity must be an integer value between these two extremes. The formula that we use to calculate this change is shown below.
This formula makes a trade-off between local demand -
that is, the overflow at the pair connected to the current path -
and global demand -
that is, the average overflow experienced by all pairs in the network.
These competing factors are weighted by the amounts
of unallocated and allocated capacity at the current path.
If there is a lot of capacity unallocated and the level of local
overlow is high, then the path's capacity should be increased.
Conversely, if the global overflow level is high and
a lot of capacity has been allocated to the path, then the path's
capacity should be decreased.
The relative importance of local and global demand is controlled by
the parameter
, which can be assigned a value between 0 and 1.
A non-zero value for
allows allocated capacity to be freed
for re-allocation elsewhere if there is a sufficient level of global overflow.
Using this update function, the optimisation network will iteratively allocate link capacity where there is demand, while de-allocating capacity if there is a greater need elsewhere. After each iteration, the current state of the network is cached if it is the best solution seen so far. The network is allowed to proceed for up to 50 iterations without showing any improvement over the cached solution. If there is no improvement after 50 iterations, then the network is restored to the cached state and optimisation resumes from that state. This gives the network a limited window in which to backtrack out of local minima.
We have tested our approach on an example of an SDH network with
eight sites; that is,
pairs and 14 transmission links.
In addition, three paths were assigned
between each pair, giving 168 paths in total.
We applied both our method and the linear programming method
described in [5] to this problem.
Our optimisation network was run for 2000 iterations,
with the parameter
.
We found that the solutions generated by our method were consistently
within 1% of the optimum found by the linear programming method.
The time required by our system to solve this problem using 2000 iterations was approximately one second on a Sun Sparc 2. In comparison, the linear programming system took approximately two seconds when run on the same computer. An important real time characteristic of our approach is that it can be queried at any time to return the best feasible solution found so far. In contrast, traditional linear programming methods have an initial set-up period during which they are effectively off-line while they search for an initial feasible solution. This difference is important when responding in real time to changes in network capacity or demand.
The other issue that we wished to investigate was how our choice
of update function affected the convergence properties of the
optimisation network.
To do this, we ran the network with
= 0.05, 0.15, 0.3, 0.5 and 0.7.
The results are shown in Figure 3.

Figure 3; Optimisation results for five different values of lambda
Note that
represents the relative importance of global demand
to local demand when we make an allocation decision.
The lower the value of
, the more greedy the network becomes.
Conversely, the higher the value of
, the more likely we are to
de-allocate capacity that has already been allocated.
These expectations were confirmed by the results shown in Figure 3.
Note that if
is large, then the network is highly
volatile, causing promising solutions to be disrupted.
If
is too low, then it is difficult for the network to
backtrack out of a poor solution.
While these initial results are promising, further testing is required
to determine how the performance of our method scales up to larger
problems.
We are also interested in ways of improving the convergence
of the optimisation network.
One approach is to apply a form of simulated annealing by varying
the value of the parameter
with time.
For example, a large value of
may be needed initially to
explore the search space, while a smaller value may be more suitable
during the later iterations as we fine-tune the solution.
Finally, it would be interesting to apply our connectionist model
to other types of resource allocation problems.
The permission of the Director, Telecom Research Laboratories, to publish this paper is hereby acknowledged. I would like to thank Peter Sember for his assistance in understanding the problem of SDH network reconfiguration. I would also like to acknowledge the help of the Network Management Research Section in providing access to their linear programming system for network reconfiguration.
A Connectionist Approach to Telecommunication Network Optimisation
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html clpap.
The translation was initiated by Pam Milliken on Wed Nov 13 16:57:40 EST 1996