Research Of QoS-Based Dynamic Multicast Routing Algorithm And Protocol

With the popularity and development of Internet, there appears many newapplications, especially the multimedia applications, which require highbandwidth usually. These multimedia communications, such as teleconferencing,computer cooperate work, update of distributed database, stock marked issue andso on, have the one-to-many characteristic,which result in bandwidth consumeand congestion. Therefore, IP multicast techonlogy was proposed to resolve thebottleneck problem of Internet.Multicast routing sends the single copy of a data packet to multiple receiverssimultaneously to fulfill one-to-many or many-to-many communication, and thedata only be replicated at forking nodes to minimize the overload of network.Compared with unicast, multicast needs less data copies, it can save the netresource also, and optimize the network performance to make distributedapplicaton possible.The key of multicast is how to determine an efficient multicast routing. Themulticast routing algorithm can build a multicast tree to connect the source andmulti receivers, and the multicast packet, which is forwarded only once at eachlink, was sent to all receivers simultaneously to make use of the resourcesefficiently. Because of the topology and variability of network, the multicastrouting algorithm should have the dynamic characteristic and support QoSconstraints. QoS-based dynamic multicast routing algorithm is to build a multicasttree to meet multi-QoS restraints with the dynamic joining or leaving members,which including source and receivers. This is a NP-complete problem that can notget the best solution in polynomial time.In this thesis, we mainly research the problem on QoS-based dynamicmulticast routing, analysed and studied the relative algorithms and protocolsthoroughly. At the same time, we also proposed a QoS-based half-rearrangeablealgorithm—DSCT (Dynamic Source-Core Tree), implementedand simulate thealgorithm. We also extended a draft based on DSCT, exploring the practicalityprecess of the algorithm.At first, the thesis introduced the development and applications of multicast,expounded the content and significance of the thesis. The second part presentedtwo kinds of multicast routing algorithm, and the popular multicast routingprotocol. Following, in point of QoS constraints, we described the definition,mathematic model, summarized the international QoS-based multicast routingalgorithms and protocols in recent years. Based on above research and analysis, we discovered that most of the currentmulticast routing algorithms try to implement the receivers dynamic joining orleaving, and little algorithm considered about dynamic source. We also find thatmany algorithms and protocols implemented based on uni-source, but in fact, it isregular that multi-sources take part in the multicast communication. When solving the dynamic multi-source problem, the source-based tree andcore-based tree have respective disadvantages, which were presented in existedalgorithms and protocols. The source-base tree only supports single source in eachmulticast group. If there are many sources, the same numbers of trees are needed.The source-based tree added the router's burden, and can not share the internetresource well. As for core-based tree, which can serve multi-source perfectly, butthe core is the bottleneck of transmission, and the position of it affected multicastcapabilities greatly, resulted in weak dynamic. After analyzed the advantage and disadvantage of source-base tree andcore-based tree, we found that source-based tree can offer end-to-end "optimizingrouting", and core-based tree can provide a "core"for multi sources to share thenetwork resource well. If we integrate the two methods'virtue, we could get themulticast tree that has optimizing routing and high sharing capability. Based onthis purpose, we presented a dynamic source-core tree (DSCT) algorithm. DSCT algorithm used the idea of hierarchical routing, combining the virtuesof source-based and shared-based tree, adopting "stable tree"idea to build a"source-core tree". By multi-path searching method, the receiver chose the pathwith better QoS characteristic to reach the selected source, building "subsource-based tree"which connected to stable tree. The mechanism improvedwhole performance of the multicast tree. Compared with other nodes on the tree, the sources are more stable to form a"stable tree". On the stable tree, the routers among sources are agency nodes. Thestable tree is transparent for external nodes and becomes an abstract "kernel",which link sources to all receivers to form multi sub source-based trees. Thestable tree and sub source-based trees compose "source-core tree", and the sourcesin kernel send packets to rest receivers via their directed sources. As for receivers,the packet looks like coming from its directed source.