基于网状光网络中P圈启发式算法的研究

发布时间：2018-03-03 20:25

本文选题：生存性　切入点：网状网　出处：《南京邮电大学》2017年硕士论文　论文类型：学位论文

【摘要】：网络的生存性在研究在互联网高速发展的时代显得尤为重要。P圈是一种新兴的生存性保护技术,这一生存性保护技术集合了环网的恢复速度快和网状网资源利用率高的优点,成为了众多学者研究的一个热点。P圈保护技术分为两部分,第一部分是P圈的构造,第二部分是P圈的配置。P圈的保护类型有两种,节点环绕型P圈和链路型P圈。在节点环绕型P圈中,深度优先搜索算法(DFS)在对中心节点构造圈时,通常不是简单圈,如果以此为基础进行扩张得到的P圈先验效率不高。因此,本文提出改进的DFS构造算法,将由DFS算法构造出的节点环绕型P圈收缩成简单圈,而且在扩张过程中,区别于Grow算法选择第一条边扩张,改进算法选择扩张后先验效率最高的边进行扩张。仿真结果表明,改进的DFS算法构造节点环绕型P圈算法先验效率明显高于传统DFS算法。在链路型P圈中,针对Grow算法构造出来的圈集合P圈数量多,而且Grow算法在扩张时选择第一条进行扩张,先验效率可能较低的缺点,本文提出了一种圈合并算法,将SLA算法、SP-Add算法和改进的Grow算法构造的P圈集合进行相交边的合并,合并后先验效率高的加入备选P圈,低于合并前的P圈则丢弃。仿真结果表明,合并后的P圈数量明显减少,同时先验效率高于传统Grow构造的P圈。对于构造好的P圈需要进行空闲容量的分配。针对容量迭代CIDA算法采用Grow算法进行备选P圈的构造,可能会丢失性能良好的候选圈。本文采用了基于K最短路径构造P圈法,将所有的P圈作为候选圈,优先选取容量效率CE大的圈,如果CE一样大,则选取引入跨接边多的圈进行配置,如果选取的跨接边还是一样多,那么就选取浪费空闲容量小的圈进行配置。同时引入保护时隙比和保护开销比来确定对实际网络的保护能力。仿真结果表明,新的容量分配算法配置的P圈在大规模网络中能达到与最优解相差4.5%的冗余度优于CIDA的6.1%,同时运行的时间低于1.6秒,且能够利用较少的资源提供100%的保护。
[Abstract]:The survivability of the network is especially important in the era of the rapid development of the Internet. P circle is a new survivability protection technology. This survivability protection technology combines the advantages of the fast recovery speed of the ring network and the high utilization rate of the mesh network resources. The protection technology of P cycle, which has become a hot topic of many scholars, is divided into two parts: the first part is the construction of P cycle, the second part is the configuration of P cycle. There are two kinds of protection types of P cycle. In the node-surrounded P-cycle, the depth-first search algorithm (DFS) is usually not a simple loop when constructing a circle for the central node. If the priori efficiency of P-cycle expansion based on this is not high, an improved DFS construction algorithm is proposed in this paper, in which the node-encircling P-cycle constructed by DFS algorithm is reduced to a simple cycle, and in the process of expansion, Different from the Grow algorithm, the first edge extension is selected, and the improved algorithm is used to select the edge with the highest prior efficiency after the expansion. The simulation results show that, The priori efficiency of the improved DFS algorithm is obviously higher than that of the traditional DFS algorithm. In the link-type P-cycle, the number of cycles constructed by the Grow algorithm is large, and the Grow algorithm chooses the first one to expand when it is extended. In this paper, a cycle merging algorithm is proposed, in which the set of P cycles constructed by the SLA algorithm and the improved Grow algorithm are combined with the intersection edges, and the priori cycles are added into the alternative P cycles with high prior efficiency. The results of simulation show that the number of P-cycles after merging is obviously reduced. At the same time, the priori efficiency is higher than the P-cycle constructed by traditional Grow. The free capacity allocation is needed for the constructed P-cycle. The Grow algorithm is used to construct the alternative P-cycle for the capacity iterative CIDA algorithm. In this paper, we use the method of constructing P-cycle based on the shortest path of K, take all P-cycles as candidate cycles, select the cycle with large capacity efficiency CE, if CE is as large, Then select the number of loops that introduce more straddle edges, and if the number of cross-edges is the same, At the same time, the protection time slot ratio and the protection overhead ratio are introduced to determine the protection ability of the actual network. The simulation results show that, The P-cycle configured by the new capacity allocation algorithm can achieve the redundancy of 4.5% different from the optimal solution in large-scale networks, which is better than that of CIDA in 6.1 seconds, and the time of running at the same time is less than 1.6 seconds, and can provide 100% protection with less resources.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN929.1

【参考文献】