02/01/1995 09:00 AM
Computer Engineering
Establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area ATM network, is often modeled as the NP-complete Steiner problem in networks. In this paper, we present distributed algorithms for finding efficient multicast trees in the presence of constraints on the copying ability of the individual switch nodes in the network. We refer to this problem as the degree-constrained multicast tree problem and model it as the degree- constrained Steiner problem (DCSP) in networks. We consider two distinct approaches to the design of distributed DCPS heuristics. The first approach involves design of distributed versions of centralized DCSP algorithms. We introduce distributed versions of two DCSP heuristics, SPH and K-SPH. The second approach is to modify the solution obtained from an unconstrained heuristic to satisfy the degree constraints using a distributed post-processing algorithm. We compare the algorithms by simulation based on three criteria: quality of solution, convergence time, and the number of unsolved networks. Our results show that each of the heuristics generated degree-constrained multicast trees within 10% of the best solution found. Surprisingly few test networks were unsolvable. The distributed post-processing heuristic presented is of particular interest since it may be used with any Steiner heuristic. When paired with a good unconstrained distributed Steiner heuristic, it gave away little quality of solution while converging rapidly.
