Marcus Brazil - Research Interests and Activities
Below is a summary of my current research interests. Most of this work is done in collaboration with Prof. Doreen Thomas
and Dr Jia Weng, who are also in the Department of Electrical and Electronic Engineering. I would be happy to supervise
postgraduate students in any of these areas, or in related areas from network design and optimisation.
The Steiner Tree Problem involves constructing a shortest network
interconnecting a given set of points. Such networks differ from minimum
spanning trees in that they may contain extra vertices (of degree 3 or
more) other than those originally given. The inclusion of these extra
points makes the construction of Steiner networks an NP-hard problem. In
the Euclidean and rectilinear planes, however, these networks have many
nice geometric properties which can be exploited to obtain exact algorithms
which perform well for (uniformly) randomly generated point sets.
My Research in this area includes looking at special cases where exact polynomial-time solutions
to this problem exist, and developing good heuristic and exact algorithms for solving the problem.
Much of this work involves developing a deep understanding of the geometric and combinatorial properties
of these minimum networks.
The diagram above shows an example of a Steiner minimum tree interconnecting the vertices of a
The project on the Steiner Tree Problem is joint work with Prof. J.H. Rubinstein and Prof. N.C. Wormald,both from the
Department of Mathematics.
One of the most important industrial applications of the Steiner tree
problem is the use of rectilinear Steiner minimum networks in the physical
design of very large scale integrated circuits (VLSI). Their main use in VLSI
design is in helping solve the routing problem, which involves determining the
layout of wires interconnecting modules in the chip. Here the overall design of
the circuit has already been determined and in particular the nets between the
modules are known. Routing generally takes place after the placement stage,
that the position of each module on the chip has been fixed. The routing
problem involves translating each net into a geometric design representing the
physical network of wires interconnecting the modules (or terminals)
corresponding to that net.
A key objective in good VLSI design is to produce a minimum area
layout. The physical design rules dictate a minimum separation
between wires, hence the area occupied by the wires is
approximately proportional to the total wire length. Added
wirelength also generally increases signal delay and power
consumption, and decreases reliability. For these
reasons circuit interconnections should in general be realised
with the minimum total wirelength. For nets containing more than
two terminals, this corresponds to finding Steiner minimum trees
for such nets. Of course there are many other objectives that also
need to be considered, including the problem of finding a feasible
routing for the entire collection of nets within the design rules.
The wirelength minimisation problem, however, is of sufficient
importance to warrant independent investigation.
Traditionally it is assumed that the wires are restricted to running in two
orthogonal directions (each on a separate layer), and that the circuits can be
effectively modelled as planar networks in a rectilinear or
geometry. For this reason, routing
algorithms for individual multi-terminal nets are often based on exact or
solutions for the rectilinear Steiner tree problem. The importance of this
application has lead to intense study of the rectilinear Steiner tree
problem, and a
large body of literature.
The above approach accurately models traditional practice in VLSI
design and manufacture, but does not reflect advances in
fabrication technologies which allow much more sophisticated
wiring patterns in VLSI. In particular, the use of three or more
routing layers is becoming common, and opens up the possibility of
new routing models based non-rectilinear grids. This has been
reflected in the VLSI routing literature over the past decade,
particularly in papers on channel routing, and in recent industrial projects such as the X-initiative.
The alternative routing models that have received the most attention are
routing in a
hexagonal grid and in an octo-square grid, in which there are, respectively,
three and four uniformly distributed directions available for routing wire segments. In this research
we consider the Steiner problem in geometries corresponding
hexagonal and octo-square models, and also in more general geometries where
of uniformly distributed directions are available for edge segments.
The diagram above shows an example of wire routing in part of a multi-layer VLSI chip using
the octo-square model.
This is an ARC funded research project and, in 2002, will include joint work with M. Zachariasen
and P. Winter of the University of Copenhagen.
The Steiner network problems described above are planar problem. The Steiner Tree
problem in three dimensions is a significantly harder problem, and, in general,
cannot be solved exactly even for a small number of points. We have been studying this
problem in a number of contexts, particularly in it's applications to the design of underground mines.
The diagram above shows an example of a three-dimensional Steiner network interconnecting the vertices of a
Reducing the cost of mining operations is an important issue for mine
developers and operators faced with an extremely competitive market place for
mineral commodities. Efficient optimisation algorithms exist for the design of
open pit mines, and have been successfully implemented as commercial software
systems. The problem of optimising underground mines is, however, less well
This project involves the development and application of network optimisation
methods to reduce costs of underground mining. The main thrust of the work
is to reduce life-of-mine costs by finding the most efficient
layout of the shafts, declines, drives and ore-passes to support mining
This project is joint work with Prof. J.H. Rubinstein, Prof. N.C. Wormald and Prof. D. Lee from the
Department of Mathematics. The project is jointly funded by the Australian government and an industry sponsor.
The aim of Multicast Routing is to efficiently interconnect a set of destinations in a network, for group communications (e.g teleconferences).
The resulting subnetwork , known as a multicast tree, avoids unnecessary duplication of data while optimising a cost parameter, such as bandwidth cost.
Such optimal trees are known as Steiner Minimum Trees in Networks. Constructing them is an NP-complete problem.
One of the aims of this project is to develop good heuristic algorithms for building such trees in a dynamic environment where new nodes are continually being added or subtracted from the set of destinations. In particular, I am developing and analysing a heuristic using ant colony optimisation (see the topic below) for multicast routing. Initial experiments suggest that this is a very promising approach. One of the next steps in this work is to incorporate Quality of Service requirements (such as delay).
Modelling the behaviour of ant colonies in finding efficient paths to food can be a powerful technique for solving network problems.
If there are a number of alternative routes from an ant's nest to a source of food, the ants will eventually find the shortest one. How do they do this? The answer lies in pheromones. The ants lay a track of pheremones to attract other ants. If different ants are taking two different routes between the nest and the food, the ants on the shorter route will travel between the nest and the food in a shorter period of time, and hence over time will lay a greater concentration of pheremone than the ants on the other route.
The ants are more strongly attracted to the route with more pheremone and eventually abandon the longer path.
Algorithms that model this kind of behaviour have proved to be very effective in heuristically solving difficult
optimisation problems such as the Travelling Salesman Problem and the Quadratic Assignment Problem. We plan
to study the application of this technique to developing new routing protocols in a dynamic data or communication network
Return to Marcus Brazil's
Return to EEE Department