-
Properties of Steiner Minimum Trees
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 7-by-7checkerboard.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.
-
Minimum Orientation-Constrained Networks in Microchips
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, meaning 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 Manhattan geometry. For this reason, routing algorithms for individual multi-terminal nets are often based on exact or heuristic 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 to the hexagonal and octo-square models, and also in more general geometries where a range 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.
-
Minimum three-dimensional Steiner networks
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 cube.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 understood.
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 operations.
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.
-
Efficient Algorithms for Multicast Routing
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).
-
Ant-Colony Algorithms in Network Routing and Design
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 environment.
Return to Marcus Brazil's Home Page
Return to EEE Department Home Page
Marcus Brazil - Research Interests and ActivitiesBelow 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.
|