Research On Multi-constrained Dual-path Routing Algorithms In Deterministic Network

With the increasing requirement of Quality of Service(QoS)for various multimedia applications,more and more people pay attention to the Deterministic Network(Det Net),which focuses on the extremely low packet loss rate and bounded end-to-end transmission delay.How to implement multi-constrained dual-path routing in the Deterministic Network has become an urgent problem to be solved.However,the current algorithms for multiconstrained routing are not fully applicable to the Deterministic Network.Among them,the Multi-constrained Path Problem(MCP)and the Multi-constrained Optimal Path Problem(MCOP)are designed to find a single path that meets certain specific requirements.At the same time,the research on dual-path routing takes the disjoint links and nodes as the research objective without considering the reliability of the paths.The innovations and main work of this thesis are summarized as follows:(1)In this thesis,a hierarchical pruning dual routing algorithm framework for multiconstrained optimal path is designed.The core operations of this framework are two different types of simplification operations performed on the network topology.The nodes on the two paths obtained by this algorithm framework are located in different subnetworks,so the second path can still transmit data normally when the nodes and links on the first path fail or even when the subnetworks of the nodes on the first path fail in a large area.We combine the algorithm framework with Heuristic Multi-constrained Optimal Path Algorithm(H_MCOP)and Extended Bellman-Ford Algorithm(EBFA)respectively,and transform them into multi-constrained dual-path routing algorithms for the Deterministic Network,namely Heuristic Multi-constrained Dual-path Algorithm(H_MCDP)and Extended Multiconstrained Dual-path Bellman-Ford Algorithm(EMCDP_BFA).(2)In this thesis,a Highly Reliable Multi-constrained Dual-path Reverse Deletion Algorithm(RMCDP_RD)based on Link-disjoint Multiple Constraints Routing Algorithm(DIMCRA)is proposed without using the hierarchical pruning dual routing algorithm framework.DIMCRA algorithm aims to find two paths that satisfy multi-constrained requirements and have disjoint links.In the process of finding the path,the algorithm performs reverse direction and deletion operations on the links in the network topology without considering the reliability of paths.We combine reverse direction and deletion operations in DIMCRA algorithm with H_MCOP algorithm to produce an algorithm named RMCDP_RD which is able to solve the multi-constrained dual-path routing problem in the Deterministic Network.The experimental results show that H_MCDP algorithm,EMCDP_BFA algorithm and RMCDP_RD algorithm can solve the multi-constrained dual-path routing problem in the Deterministic Network,but the performances of the algorithms are different.Among them,the running time of H_MCDP algorithm is the shortest.The success rates of routing lookup of H_MCDP algorithm and EMCDP_BFA algorithm are better than that of RMCDP_RD algorithm.The overall reliability of the two paths obtained by RMCDP_RD algorithm is highest.Meanwhile,the average delay,average cost and average jitter of two paths obtained by H_MCDP algorithm are lowest.On the whole,the overall performance of H_MCDP algorithm is the best,while the overall performance of the other two algorithms is slightly worse.