Report Number: CS-TN-99-89
Institution: Stanford University, Department of Computer Science
Title: Extending Greedy Multicast Routing to Delay Sensitive Applications
Author: Goel, Ashish
Author: Munagala, Kamesh
Date: July 1999
Abstract: Given a weighted undirected graph G(V,E) and a subset R of V, a Steiner tree is a subtree of G that contains each vertex in R. We present an online algorithm for finding a Steiner tree that simultaneously approximates the shortest path tree and the minimum weight Steiner tree, when the vertices in the set R are revealed in an online fashion. This problem arises naturally while trying to construct source-based multicast trees of low cost and good delay. The cost of the tree we construct is within an O(log |R|) factor of the optimal cost, and the path length from the root to any terminal is at most O(1) times the shortest path length. The algorithm needs to perform at most one reroute for each node in the tree. Our algorithm extends the results of Khuller etal and Awerbuch etal, who looked at the offline problem. We conduct extensive simulations to compare the performance of our algorithm (in terms of cost and delay) with that of two popular multicast routing strategies: shortest path trees and the online greedy Steiner tree algorithm.
http://i.stanford.edu/pub/cstr/reports/cs/tn/99/89/CS-TN-99-89.pdf