Roman Novak, J. Stefan Institute, Ljubljana,
Slovenia
Email: roman.novak@ijs.si
Multicasting is a mechanism for group communications in communication networks. It reduces transmission overhead on the senders side and the overall network traffic as only one copy of each data packet passes particular network connections. We consider communication networks that are based on point-to-point connectivity and are connection oriented. Steiner problem can be defined as a problem of determining a minimum cost connected weighted graph that spans a given subset of vertices (terminal nodes).
There is a number of specific restrictions in communication networks which prevent us from using well-known general solutions for Steiner problem, such as time complexity and limited knowledge about the status of the network in particular network nodes. Therefore the activities for multicast connection construction need to be distributed over network nodes. In such a way that most processing is done in nodes where the required data are available. Global algorithm for Steiner tree construction is broken into a set of node algorithms. Node algorithms are implemented in all network nodes and are modest as regards memory and processing requirements. Node algorithms are similar to distributed stigmetric algorithms which allow a swarm of simple insects to build coherent structures. Steiner tree heuristics is decomposed into a finite number of building steps. We adapted the definitions, given by Theraulaz and Bonabeau for social insects, to the distributed Steiner tree construction.
We designed the Distributed Cheapest Insertion (DCI) algorithm for constructing Steiner trees in networks. The algorithm begins with one singleton tree and iteratively connects the nearest unconnected terminal node to it, until all terminal nodes are connected. In point-to-point networks, where in general particular pairs of nodes cannot communicate directly, it is inevitable that the distributed tree construction should be based on a single tree growth. The existing partially built tree is used for the dissemination of information about the construction process. The node algorithm is relatively simple. An innovative approach was used in the construction of the distributed rerouting algorithms, which dynamically adapt multicast connection to the changing situation in the network.