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

摘要

Many future applications of computer networks such as distance education, remote collaboration, and teleconferencing will rely on the ability of the network to provide multicast services. 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 or 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.