Routing Algorithm Research For Arc-Disjoint Paths

There are many advantages of multi-path routing compared to the single path routing. The multi-path routing does better in fault tolerance, reliability and QoS routing. As the network becomes more and more complex, the advantages of multi-path routing get increasingly evident. As a result, it catches special attention in recent years. Disjoint paths routing is very important in research of multi-path routing, and the arc-disjoint paths routing is one of the most important branchs of multi-path routing.The main work and achievements of this paper are given below.1. The research of algorithm for the widest path problem. The widest path is the base of widest pair of arc-disjoint paths. The widest path problem has been studied maturely. In this paper, we use a FIFO queue to store the vertexes which are going to be optimized. Then we present an algorithm named SPFA, which has lower complexity comparing with the Dijkstra algorithm.2. The research of algorithm for the Widest Pair of Arc-disjoint Paths problem. We have analyzed the Widest Pair of Arc-disjoint Paths problem in directed graph. Then we propose a polynomial algorithm for it with time complexity O (mn). It is not required to reassign flux at common vertices on the widest pair of paths, and this scheme can be implemented easier in real networks.3. The research of algorithm for the min-max delay of the shortest pair of arc-disjoint paths. In this paper, we transform the min-max delay of the shortest pair of arc-disjoint paths problem into parallel machine scheduling problem. After that we solve it by using Simulated Annealing algorithm.And we work out the corresponding pair of paths.