On multicasting with minimum end-to-end delay
Young-Cheol Bang, S. Radhakrishnan, Nageswara S. V. Rao, Stephen G. Batsell · 2003
We develop and evaluate several heuristics for the construction of a multicast tree to transmit a given message of size r from a source to a set of destinations with guarantees on the end-to-end delay over a computer network. Different multicast trees can be constructed for various values of r. We consider delay sources on links to be from propagation and bandwidth availability. The heuristics that we have developed try to minimize the end-to-end delay of the multicast tree taking into consideration various switching architectures that range from pipeline to store-and-forward. Our evaluations of these heuristics consider various network generation models including locality, Waxman I and II, and transit-stub. We have evaluated multicast tree generation heuristics based on both shortest path and Steiner tree heuristics. A novel heuristic called grow-tree is proposed in this paper and it is based on both Kruskal's and Prim's minimum spanning tree algorithm. This heuristic performs admirably well in many network environments.