About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
ARIES: A rearrangeable inexpensive edge-based on-line steiner algorithm
Abstract
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 edge-bounded algorithm (EBA). Our results show that ARIES provides the best balance among competitiveness, computational effort, and changes in the multicast tree after each update.