Constructing application-layer multicast trees for minimum-delay message distribution

This paper considers the problem of disseminating messages from a source to multiple destinations in an overlay network in which nodal delays for processing messages are taken into account in addition to communication delays. The objective is to find a multicast tree to deliver a message from a source to multiple destinations in the minimum delay time. This problem is referred to as the minimum-delay multicast problem with nodal processing delays. This paper develops several heuristic algorithms that are based on the principle of iteratively selecting one of the destination nodes not yet on the current multicast tree and attaching the selected node to it until all destination nodes are on the multicast tree. A new delay measure called reception-and-processing delay is introduced in this paper as one of the delay measures used in selecting one of the destination nodes for attaching to the current multicast tree. This paper finds that the least-delay path from the current multicast tree to a destination node not yet on the tree may intersect or overlap with the current multicast tree if a commonly used method is employed to find the least-delay path. An efficient method is devised to avoid this undesirable phenomenon. The performances of the four heuristic algorithms and the effects of various characteristics of the overlay networks on the performances of the heuristic algorithms are studies via simulations.