ARIES: a rearrangeable inexpensive edge-based on-line Steiner algorithm

In this paper, we propose and evaluate ARIES, a heuristic for updating multicast trees dynamically in large point-to-point networks. The algorithm is based on monitoring the accumulated damage to the multicast tree within local regions of the tree as nodes are added and deleted, and triggering a rearrangement when the number of changes within a connected subtree crosses a set threshold. We derive an analytical upper-bound on the competitiveness of the algorithm. We also present simulation results to compare the average-case performance of the algorithm with two other known algorithms for the dynamic multicast problem, GREEDY and EBA (edge-bounded algorithm). Our results show that ARIES provides the best balance among competitiveness, computational effort, and changes in the multicast tree after each update.