Algorithms for the degree-constrained multicast trees in packet-switched networks
Sung‐Jin Chung, Sung‐Pil Hong, Sang‐Baeg Kim, Hoo-Sang Chung · 2002
In this paper, we propose some algorithms for finding multicast trees in packet-switched networks such as ATM networks, when there exist constraints on the cell-replication capabilities of the switch nodes. This is formulated as a Steiner tree problem with degree constraints on the nodes in a network, so we will refer to it as the degree-constrained Steiner tree problem (DCSP). Our algorithms are as follows: one is a combined version of two heuristics-"Naive" & "SPH"-, others are based on tree reconfigurations, and the last is based on a mathematical formulation for the DCSP. We experiment on the algorithms in three aspects; number of solved instances, quality of solution, and computational time. Experimental results show that there were few cases unsolved by our algorithms and the QoSs were mostly within 5% of optimum values. Computational times were also tolerable.