Multicast routing tree optimisation

High bandwidth networks allow new distributed applications which involve all the hosts of a target group. These applications send messages to all members of the group, and such multipoint communications require techniques which must efficiently use network resources. An effective method of multicast routing is achieved by using a spanning tree which connects all target nodes in the network. An important objective is to minimize the overall network cost of the spanning tree. This is known as the Steiner Tree Problem in networks, and it is proved to be NP-complete. Many heuristics have been proposed in the past years, which are capable of isolating sub-optimal solutions in polynomial times. In this paper we present a new method which is used to obtain more accurate approximations of the optimal solutions. An algorithm is proposed which is capable of improving the solutions obtained by well known heuristics, by means of a stirring process of the nodes in solution trees. Solutions obtained by the best available heuristics are used as starting points. An enumerative method is also used as comparison term in the experimental analysis which demonstrates the goodness of the method discussed in this paper.