A fast and efficient heuristic algorithm for the delay- and delay variation-bounded multicast tree problem

More and more multicast communications are becoming real-time. In real-time communications, messages must be transmitted to their destination nodes within a certain amount of time; otherwise the messages will be rendered futile. To support real-time multicast communications, computer networks have to guarantee an upper bound on the end-to-end delay from the source node to each of the destination nodes. This is known as the multicast end-to-end delay problem [10]. On the other hand, if the same message fails to arrive at each destination node at the same time, there will probably arise inconsistency or unfairness problem among users. This is related to the multicast delay variation problem [10]. Our research subject in the present paper is concerned with the minimization of multicast delay variation under the multicast end-to-end delay constraint. The problem is first defined and discussed in Ref. [10]. They have proved it to be an NP-complete problem and proposed a heuristic algorithm for it called DVMA (Delay Variation Multicast Algorithm). In this paper, we find that in spite of DVMA's smart performance in terms of multicast delay variations, its time complexity is as high as O(klmn(4)). It is strongly believed that such a high time complexity does not fit in modern high-speed computer network environment. Therefore, we will present an alternative heuristic algorithm with a much lower time complexity O(mn(2)) and with a satisfactory performance. Computer simulations also testify that our algorithm is both fast and efficient. (C) 2002 Published by Elsevier Science B.V.