## Stigmergic building algorithms for multicast virtual connections
in point-to-point networks

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.