Research On Qos Based Multicast Routing Algorithms

With the development of network technology and extension of its application area, the network nowadays can support more and more multi-media applications on the same time, in order to support these applications, multicast communication network is applying widely. Meanwhile, many multi-media services bring forward higher requirements on delay, delay variation,bandwidth,cost,and so on,which means that the current network must have the QoS (quality of service) support capability. Delay and cost are two important but contrary parameters, pursues each node's least delay is not benefit for the cost optimization while the least cost multicast tree is hard to satisfy the delay of the route from source to every destination. Usually, a good multicast algorithm must make a balance between tree's total cost and destination's delay. So this thesis studies on the QoS-based multicast routing problem and designs three multicast routing algorithms characteristic of flexible, speediness, easy to implement and meet the needs of customers'QoS requirements.First, multicast routing problem with delay constraint and its relevant algorithm is analyzed, then a new algorithm DCMRA about delay constraint is proposed. This algorithm put the destination which the cost is better, the delay is suit the delay constraint and its relevant route into the tree, until all the member destinations are on the tree. In process of finding the route, a new algorithm NDUR is used, this algorithm reduces the destruction to the cost least route as far as possible when guarantee the delay constraint. This algorithm can achieve the optimal cost.Then tabu search is imported into multicast routing issue. Making the use of its flexible, easy and strong searching character, a tabu search algorithm TSNSMRA based on steiner nodes changed to deal with delay constraint multicast routing is promoted. This algorithm proposes the concept of node important degree, making the neighborhood's scale is moderate and the quality is higher. After iterations, this algorithm can obtain better multicast tree. Usually, it encounters dynamic group membership in practical multicast applications. Adopting the idea of Greedy algorithm, this thesis presents a delay constraint dynamic multicast routing algorithm DDMP, based on k-shortest paths, finds a path for the node which apply for join in the tree. At the same time, this path makes current tree's adding cost lower. Share-cost'introduction gives certain priorities to the routes which containing the nodes in the tree. In this case, in the condition of assuring delay, more links sharing can be realized and the cost of multicast tree can be reduced.