More and more multicast communications are becoming real-time. Inreal-time communications, messages must be transmitted to theirdestination nodes within a certain amount of time; otherwise themessages will be rendered futile. To support real-time multicastcommunications, computer networks have to guarantee an upper bound onthe end-to-end delay from the source node to each of the destinationnodes. This is known as the multicast end-to-end delay problem. On theother hand, if the same message fails to arrive at each destination nodeat the same time, there will probably arise inconsistency or unfairnessproblem among users. This is related to the multicast delay variationproblem. Our research subject is concerned with the minimization ofmulticast delay variation under the multicast end-to-end delayconstraint. The problem has been proved to be NP-complete and aheuristic algorithm for it called DVMA (delay variation multicastalgorithm) has been proposed. In this paper we find that in spite ofDVMA's smart performance in terms of multicast delay variations, itstime complexity is as high as O(klmn4). It is stronglybelieved that such a high time complexity does not fit in a modernhigh-speed computer network environment. Therefore, we present analternative heuristic algorithm with a much lower time complexity O(mn2) and with a satisfactory performance. Computer simulationsalso testify that our algorithm is both fast and efficient
展开▼
