Study On QoS Multicast Routing Algorithm In Network Communication

Multicast routing algorithm belongs to the category of network optimization, and it is the core problem of computer network in application and development. It has great significance in reducing the flow of computer network and lightening burden of servers. As people have more and more high expectations for QoS, we need to join more and more limiting conditions during the process of asking multicast tree, which makes the problems to be solved become NP-complete problems.To this kind of problem, we can only design different tactics to seek the approximate optimal solution as soon as possible.In the first two chapters of this text, the main discussion is some basic knowledge to be used in the course, including some basic conceptions and algorithms in the Graph Theory. It mainly prepares for the research work of chapter 3 and chapter 4.In chapter 3 and chapter 4, the main results this text have introduced, can be summarized as follow:1. In chapter 3, we have modified Dijkstra algorithm in order that it can be suitable for the theme that we study at first. Then, use the tactics that we make in fictitious mesh graph, namely arrange in an order for the nodes from great to small at the request of bandwidth; utilize modified Dijkstra algorithm to find the feasible path for each node in the mesh graph according to the order. In this algorithm, it can not guarantee that every node has a feasible path finally, but according to the operation principle of the computer network, can incoporate these nodes into the next task.2. In chapter 4, we have proposed a multicast routing algorithm on the basis of minimum tree algorithm. Construct a tree at first, make sure that all nodes sent requests to server included. Then check them one by one to observe whether its path offered by the multicast tree can satisfy its constraints. As to nodes whose constraints can not be satisfied, we utilize generalized Dijkstra algorithm to search a minimum-cost path which is new and suitable until that all nodes' constraints be satisfied.