The Steiner Tree Problem in Networks

The Steiner Tree Problem is an optimization problem, whose practical applications can be found in different scientific and technological fields.
In this project, we are interested in its network version, since multicast trasmission protocols require to determine a minimal spanning tree covering a subset of the nodes on a network.
Aim of this project is to explore the Steiner Tree problem from the prospective of the multicast trasmission in computer networks.

The project

We developed a software framework to test and compare the most effective heuristics on a wide variety of topologies.
Recent works on network topologies have shown that typical computer networks own particular statistical properties about their node degree distribution and some graph generation tools were developed.
The aim of this project is the detection of the most suitable methods for building multicast tree on graphs that present topological features similar to the real Internet and its subnetwork.
To this end we generated a large set of graphs containing ranging from 2000 to 5000 nodes that can be used as the samples for the experiments.

Try out demo

Two Java based frontends for applying the Steiner codes to the sample graphs has been developed.
The user interafece enables users to interactively run and compare the Steiner heuristics over some small sized networks:

- the first one uses Java Swing, and enable users to build their own networks and run the Steiner heuristics over them.
- the second one uses Java AWT so it's compatible with all best known browsers, and the user is able to choose a test network only from a predefined set.

Both the applications use J2EE RMI (Remote Method Invocation) technology to communicate with the application server and remotely execute the Steiner heuristics;
if your JVM does not support RMI, you can download the Sun's Java plug-in which support RMI. We succesfully run it under Linux, Macintosh and Windows platforms.

People

Staff

Giuseppe Di Fatta

Giuseppe Lo Presti

Giuseppe Lo Re

Student

References

P. Winter, Steiner problem in networks: a survey, Networks, 17, 1987, pp. 129-167.

M. B. Doar, A better model for generating test networks, 1996, www.geocities.com/ResearchTriangle/3867/sourcecode.html

F. Bauer, Multicast routing in point-to-point networks under constraints, Ph.D. Dissertation, Univ. of California Santa Cruz, 1996.

S. Raghavan, G. Maniraman, C. S. R. Murthy, A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees, IEEE/ACM Trans. on Netw., 7, 4, Agosto 1999, pp. 514-528.

M. Faloutsos, P. Faloutsos, C. Faloutsos, On Power-Law Relationships of the Internet Topology, ACM SIGCOMM 1999.

V.J. Rayward-Smith, A.S. Wade, Effective Local Search for the Steiner Tree Problem in Studies in Locational Analysis, in Advances in Steiner Trees 2000, www.sys.uea.ac.uk.

A. Medina, A. Lakhina, I. Matta, J. Byers, BRITE Universal Topology Generator, April 2001, www.cs-pub.bu.edu/brite.

S. Voss, A. Martin, T. Koch, SteinLib Testdata Library, elib.zib.de/steinlib/steinlib.php.

Reports

G. Di Fatta, G. Lo Presti, G. Lo Re, Computer Network Topologies: Models and Generation Tools, CE.R.E. Technical Report, July 2001, Palermo - Italy [report].

G. Lo Presti, Il problema di Steiner nelle reti, final report for the AI course at University of Palermo, Dept. of Computer Science Engineering, September 2000, [report (italian version only)].

G. Di Fatta, G. Lo Re, Efficient tree construction for the multicast problem, Special issue of the Journal of the Brazilian Telecommunications Society, 1999.

last update: 2002-12-12