Efficient Distributed Algorithms for
the Steiner Tree Problem in Networks
Luca Gatani1,2, Giuseppe Lo Re1 and Alfonso Urso1
1 Istituto di Calcolo e Reti ad Alte Prestazioni
Consiglio Nazionale delle Ricerche
Palermo, Italy
Phone: +39-091-238 111, Fax: +39-091-6529124
E-mail: {gatani, lore, urso}@pa.icar.cnr.it
2 Dipartimento di Ingegneria Informatica
Universitą di Palermo
Palermo, Italy.
Abstract - Establishing a minimum cost distribution
tree in a point-to-point network can be modeled as the
NP-complete Steiner Tree Problem in Networks
(SPN). Conventional centralized SPN heuristics
provide effective solutions, but they require a
complete knowledge of the network topology. The
centralized approach of these algorithms is not
practical for large networks. In this paper we
introduce and evaluate two distributed algorithms for
the heuristic solution of the SPN. The proposed
algorithms allow the construction of effective
distribution trees using a coordination protocol among
the involved network nodes. The intrinsic distributed
features of our algorithms allow their straightforward
implementations as routing protocols for multicast
transmissions on large dimension networks like the
Autonomous Systems of the Internet. The algorithms
have been implemented and tested both in simulation
and on experimental active networks. Performance
evaluation indicates that both of our algorithms
perform as well as the centralized versions, providing
good levels of convergence time and communication
complexity. Moreover, the results show that proposed
heuristics scale reasonably well for both multicastgroup
and network size.
I. INTRODUCTION
Multimedia networking applications such as distance
education, remote collaboration, video-on-demand
services and teleconferencing will become widespread,
relying on the ability of the network to provide multicast
services effectively and efficiently. Multicasting refers to
the simultaneous transmission of data to multiple
destinations, and can be seen as the generalized concept
of one-to-one unicasting and one-to-all broadcasting.
Multicast routing for data transmission adopts trees
isolated over the network topology, in order to achieve a
resource usage minimization by the simultaneous sharing
of links when transmitting from one source to many
destinations.
In this context, an underlying specific multicast routing
algorithm should determine, with respect to certain
optimization objectives, a multicast tree connecting
source (or sources) and group members. Data belonging
to the source flow will reach their destinations, traversing
tree edges once only and being replicated at branching
points. One of the main goals of multicast routing is to
minimize the overall tree cost. Tree cost refers to the
amount of network resources needed to transport packets
over the tree, and, consequently, minimizing tree cost is
equivalent to the efficient use of network resources.
Determining the optimal (i.e., minimum cost) multicast
tree connecting all the members of a group is a difficult
problem: it can be modeled as the Steiner problem in
networks (SPN) which has been proved to be NPcomplete
in its decisional version [Karp , 1972]. The NPcomplete
nature of the problem means that the
computation of explicit solutions in large networks is
prohibitively expensive. For example, two popular
explicit algorithms, the Spanning Tree Enumeration
Algorithm (STEA) and the Dynamic Programming
Algorithm (DPA), present time complexities of O(p2 ·
2n-p + n3) and O(n · 3p + n2 · 2p + n3), respectively, where n
is the number of nodes in the network and p is the number
of multicast members.
Centralized heuristics for approximate Steiner trees have
been proposed in the literature [Winter, 1987]. Most of
them produce solutions whose cost has been analytically
demonstrated to be less than twice the cost of the optimal
solution. However, experimental observations indicate
that in most cases they are capable of singling out near
optimal solutions with reasonable speed.
.....