Overlay Multicast Routing Algorithm with Delay and Delay Variation Constraints

摘要

Overlay multicast is considered as a very effective technique to provide large-scale data dissemination over Internet. In overlay multicast, some applications require the messages should arrive at the destinations within a specified delay bound and these applications also require that the destinations receive the messages from source at approximately the same time. It is defined as the problem of Delay and delay Variation Bounded Multicasting Network (DVBMN) and has been proved to be an NP complete problem. In this paper, by improving the CHAINS algorithm, we present a more efficient heuristic algorithm FCHAINS. We have proved the correctness of our algorithm theoretically, and shown that our algorithm is obviously better than CHAINS in terms of time complexity by performance experiments.