The Dynamic Short-circuit Algorithm In Application Research In The Planning Of The Ip Network Weights

The traffic distribution in intra-domain is determined by the weights of the links in IP networks. As a result, the traffic distribution can be optimized by tuning the weights of links. The local search algorithm is widely known as the most effective way to optimize weight setting. In order to obtain a better solution of weight setting, the local search algorithm needs to evaluate a large number of neighborhood weights from some candidate weights. The calculation of all-pairs shortest path and flow distribution are two important steps for weight evaluation. So the efficiency of weight evaluation is directly determined by the performance of computing the all-pairs shortest path. Therefore, we can greatly enhance the efficiency of the local search algorithm by improving the calculation of all-pairs shortest path.The traditional way to calculate the all-pairs shortest path has a poor efficiency in large network, which makes the local search algorithm hard to find a useful solution in a reasonable time. According to the characteristic that a few weights of links are different between two neighborhood solutions, a more efficient dynamic shortest path algorithm is applied to the local search algorithm. In the second chapter, firstly, the traditional static and dynamic shortest path algorithm are introduced. Secondly, the problems that should take consider in realizing the dynamic shortest path algorithm and some effective suggestions are proposed. Then, the performance of three different all-pairs shortest path algorithms are compared, in order to offer some references to the local search algorithm. Finally, as some essential information used in traffic distribution can be dynamically updated during the calculation of dynamic shortest path, a combination algorithm of flow distribution and dynamic shortest path is proposed.As we know, an IGP network is usually divided into multiple areas for the sake of administrative convenience, where the nodes in TSA area are not aware of the external areas’nodes. The nodes in TSA area can only forward data to their nearest ABR. As a result, the existing shortest path algorithms are no longer suitable for multi-area networks. As none suitable shortest path algorithm can be found, the static and dynamic shortest path algorithms for multi-area network are proposed in the third chapter. In the application of anti-destroy in IP network weight programming, every link should be broken one time to analyze the performance in each weight evaluation. As a result, the time of weight evaluation is m times more than the ordinary weight evaluation, which m is the number of links. A new dynamic algorithm for the anti-destroy network is proposed to decrease the time of doing anti-destroy weight iteration.