Delay Constrained Multicast Routing Algorithm

With the rapid development in networking technologies and applications, for many applications such as streaming media, Video On Demand, netgame, the demand for providing multi-media services is rapidly increasing. Network is required to provide multicast services by many of these applications. In many cases, to realize multicast communication, packets are transmitted along a multicast tree constructed by multicast routing algorithms. Therefore, it is very important to do some research on efficient multicast routing algorithms. At the same time, these multi-media applications also require the underlying network to provide quality of service (QoS) such as high network bandwidth, low transmitting cost and delay, small delay-variation and tolerable packet loss rate. Among these, the multicasting applications with delay constraint are especially widely used. As one of the key techniques supporting multi-media applications, the research on the delay-constrained multicast routing problem has become a hot topic in computer networks.This thesis concentrates on the multicast routing problem with bounded end-to-end delay. Aiming at the delay-constrained static multicast routing problem and the delay-constrained dynamic multicast routing problem, we present an algorithm respectively. The content mainly includes:This thesis first deeply investigates on the delay-constrained static multicast routing problem. After discussing multicast routing algorithms satisfying delay constraint in detail, we present a Delay-constrained Multicast Routing Algorithm. Theoretical analyses indicate the time complexity of our algorithm is the same as that of CDKS. Besides, simulation results prove that this algorithm can construct a multicast tree whose cost is lower than CDKS. Compared with KPP, this algorithm can construct a multicast tree with lower time complexity, thus can be used for large network to confirm multicast routing conveniently. After proper modification to this algorithm, routing algorithms can easily be applied to solve other problems, such as the delay-constrained dynamic multicasting routing problems, and the delay and bandwidth constrained multicasting routing problems.Secondly, this thesis concentrates on the delay-constrained dynamic multicast routing problem, which requires the network not only to provide the delay-constrained service but also to support dynamic change of group members. Based on full research into existing algorithms, we present a distributed algorithm to solve the Delay-constrained Dynamic Multicast Routing problem. This algorithm can be used for large network to confirm multicast routing conveniently. Taking the cost and delay into account, this algorithm allows the new destination nodes to select attached existing nodes according to a more reasonable standard. This not only reduces the cost of the multicast tree, but also provides more opportunities for the later joined destination nodes to select attached existing nodes. Simulation results demonstrate that this algorithm can construct a multicast tree in which the cost is much lower than NAIVE and FAST.