| 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. As the network may very big, and the topological structure and largeamounts of traffic are changing continuously, the mutlicast routing problem isbecoming very important and difficult. Dynamic joining and leaving of member,the participation of QoS information, the need of network hierarchical routing arethe obstacles to solve multicast routing problem. Network routing not only have tosatisfy the need of user's different application, but also develop theresource-efficiency of whole network. QoS-based routing can enable moreeffective and efficient QoS support by allowing dynamic route selection based onnetwork resource availability and QoS requirements.The multicast routing problem that finding the minimum cost multicastrouting tree with many QoS constraints may be formalized to Steiner tree problemin network, which is a NP-complete problem that an algorithm that finds a Steinertree can not get the best solution in polynomial time. Therefore, we would like tofind approximation algorithms which can get a solution that close to optiumum inworst case and average case. There were large amount of valuable method onmulticast routing algorithms and protocols that have been proposed these days.But these algorithms and protocols are so complex and unfit to need of actualnetwork that they are not attain abroad application. Applications urge multicastrouting to combine with correlating protocols, and develop the advantage ofmutlicast routing.In this thesis, we mainly research the problem on QoS-based dynamicmulticast routing. Analyzing and studing the relative algorithms and protocolsthoroughly, we proposed a new multicast communication tree –the Dynamic ShareTree with Unfix Cores (DSTUC) to slove the multi-sources and dynamicproblems in multicast communication.At same time, we implemented andsimulated DSTUC on single QoS parameter (cost) and multi-QoS parameters(width, delay and cost) based on a improved TS searching algorithm, thencompletely compared the test data produced by source tree, CBT tree and DSTUCtree.From the results, which come to the conclusion the DSTUC tree used in somespecial communication condition will be suitable. At last we extended a draftbased on DSTUC tree and hierachical network, exploring the practicality precessof 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.We also find that many algorithms and protocols implemented based onuni-source, but in fact, it is regular that multi-sources take part in the multicastcommunication. When solving the dynami multi-source problem, thesource-based tree and core-based tree have respective disadvantages, which werepresented in existed algorithms and protocols. The source-base tree only supportssingle source in each multicast group. If there are many sources, the samenumbers of trees are needed. The source-based tree added the router's burden, andcan not share the internet resource well. As for core-based tree, which can servemulti-source perfectly, but the core is the bottleneck of transmission, and theposition of it affected multicast capabilities 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 share tree with unfix cores (DSTUC).DSTUC tree used the idea of hierarchical routing, combining the virtues ofsource-based and shared-based tree, part all nodes in multicast communicationinto three sections which are source section, receiver section and cores section,then build the DSTUC tree between the three sections. First DSTUC build the"base trees" between sources and receivers using the source-base tree method, andassemble cores on these paths, which respond for transmission and managementfunctions. All cores would be abstracted to a single core node in which each realcore response for different receivers and sources in multicast.The thesis also studied the dynamic changing of sources and receivers. If thesources join or leave the multicast group,DSTUC just modifies the pathes whichconnect sources and cores, shortening tree convergent time.Receivers and coresalso can inspire rebuilding the tree which receiver inspiration based on the pathQoS and cores inspiration would cause rebuild the DSTUC tree thoroughly or justrebuild the path through cores.The cores inspiration time is important which willinfluence the QoS of all tree.In the last part of the thesis, we did some beneficial work to investigate howto realize the DSTUC tree in the practical environment. We presented a draft ofhierachical multicast QoS protocol frame based on DSTUC and hierachicalnetwork at last, by designing protocol messages and setting timers to solve thedynamic multi-sources problem better.With hierachical network method, DSTUC,RSVP, multicast routing protocol and unicast routing protocol, this hierachicalmulticast QoS protocol is more flexible and expansible. At the same time, we alsopoint out several issues of the draft, and simply discussed them in theory. |
PDF Full Text Request