The Research On Delay And Delay Variation Bounded Multicast Routing Problem

Multicast is a technique for the simultaneous transmission of data to multiple destinations. Typical applications of multicast include multimedia distribution systems, video-conferencing, game communities, and so on. The main purpose of multicast routing is to construct a tree rooted at the source and spanning all destinations, while the quality of services (QoS) be satisfied. Delay and delay variation are two QoS metrics that directly related to real-time interactive applications. In this thesis we further study the problem of delay and delay variation bounded multicast routing.The first part considers the delay constrained multicast routing problem (DCMR). This problem refers to constructing minimum-cost spanning trees constrained by delay, which is known to be NP-Complete. On the basis of some related work in this area, we present a new heuristic algorithm, called STBMR. This algorithm begins with yielding a least-cost spanning tree. Then check every path from source to destination. If one path beyond the maximum delay, replace it with least-delay path in order to satisfying the delay bounded. The idea of this algorithm is simple and easy to implement. Compared with the classical algorithm KPP, STBMR has less time complexity. The simulated experiment indicates that STBMR's tree'cost is up to 4% more than KPP, while average running time is 54% less than it.In the second part, we discuss the significan of delay variation in some multicast applications. We also present a heuristic algorithm for multicast routing problem with delay and delay variation constrains. Firstly, we divide the delay tolerance interval into some equal segments. Then we find the paths that delay is between those time intervals. Obviously, these paths will meet the requirement of delay. Lastly, we select bounded paths satisfying delay variation from them to develop a delay and delay variation constrained multicast tree. We compare the proposed algorithm with some exists algorithm in system running time and success rate.