The Research Of Multi-Constrained Routing Algorithm Based On DAG

With the increasing diversification of network applications and explorations,the network is being forced to meet various traffic demands with clear and critical Quality of Service(Qo S)requirements.Qo S is a prerequisite for communication on the network.Quality of service routing is one of the important parts to guarantee Qo S,it directly affects the performance of the network to a large extent.As a typical multi-constrained routing problem,the quality of service routing problem mainly refers to finding an optimal path between the source node and the destination node under multiple constraints.The solution of this problem needs to be supported by a practical and feasible routing algorithm.In this paper,according to the current status of traditional routing algorithms and routing algorithms based on ant colony algorithm in existing multi-constrained routing algorithms,two new routing algorithms,DAG_DMCOP and DAG_IACS,are proposed.A new multi-constrained optimal routing algorithm based on Directed Acyclic Graph(DAG)and Dijkstra,DAG_DMCOP,is proposed,for the disadvantages of existing traditional routing algorithms,such as high time complexity,low success rate,etc.It draws on the idea of DAG and the theory of index weighting method.The algorithm is divided into two parts:(1)Pruning strategy.Find all the paths from the source node to the remaining nodes that meet the requirements of multiple constraints and convert the network topology into a DAG.(2)Search strategy.The link synthesis cost funct ion is introduced.The weights of multi-constrained conditions(bandwidth,delay,delay jitter,cost and other Qo S metric parameters)are adjusted adaptively by using the G1 method and the standard deviation method in the indicator weighting method,and the neighbor node set in the topology graph.Then the Dijkstra algorithm is used to find out the optimal path that meets the requirements of multiple constraints on the DAG after pruning.A large number of experimental data show that the algorithm can quickly find the optimal path that meets the requirements of multiple constraints,with lower time complexity and higher success rate.The algorithm is simple and easy to extend.It is suitable for large-scale multi-constrained routing networks.It is an efficient new algorithm for solving multi-constrained routing problems.Based on the above algorithm,the search strategy of the DAG_DMCOP algorithm is studied by using the Ant Colony System(ACS).For the problems of routing algorithm based on ant colony algorithm and ACS algorithm,such as slow convergence rate,easy to fall into local optimum,etc.,the ACS algorithm is improved: Prune all the links connected to intermediate nodes that cannot reach the destination node.It can prevent ants from accessing invalid links again and narrow the global search range.The global pheromone updating rule is dynamically adjusted by using the relationships among the global optimal path,iterative optimal path and iterative worst path.It can speed up the convergence rate of the algorithm.Add a parameter to each link in the network topology that represents the status of the ant access link.Then the state transition rule is adjusted by using this parameter and a strategy of multiple choices.It can expand the local search range and improve the local optimal problem.Then,a multi-constrained optimal routing algorithm based on DAG and improved ACS,DAG_IACS,is proposed by combining the pruning strategy of the DAG_DMCOP algorithm with the improved ACS algorithm.A large number of experimental data show that the algorithm can narrow the global search range and expand the local search range,and it has better convergence rate and optimization ability.Its success rate is also higher.In addition,the algorithm has certain scalability for network size and constraints.