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 study 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 in networks. Steiner heuristics for the degree- constrained case are proposed and their simulation results for sparse, point-to-point networks are presented. The results are compared with respect to their quality of solution, cost (running time), and the number of test cases for which no solution could be found. The results of our research indicate that efficient multicast trees can be found in large, sparse networks with small multicast groups even with limited multicast capability in the individual switches. Some of the Steiner heuristics tested yielded degree- constrained multicast trees within 5% of the best heuristic solution found in most of the cases. Even when the fanout of each switch node was restricted to 2, the heuristics we used were able to generate efficient multicast trees in almost all our test networks. Surprisingly few test networks were unsolvable. In those cases where no solution was found by a heuristic, backtracking solved many of the remaining cases. Among the heuristics we used, degree-constrained versions of simple path- distance heuristics such as SPH and SPH-R provided the best tradeoffs between quality of solution and cost.
