Abstract: Network failures cause a large number of packet losses and seriously affect network performance. How to deal with network failures efficiently and quickly is the basic requirement and main task of designing routing protocols. Currently, the most effective methods for Internet deployment are open shortest path first (OSPF) and intermediate system-to-intermediate system (IS-IS). Network faults are resolved by dynamic routing protocols, but a large number of packets are still discarded during the dynamic convergence of protocols. Therefore, router manufacturers widely adopt the route protection method with better performance to overcome network faults. However, the existing route protection schemes generally have high implementation complexity or low fault protection rate. Aiming at the above problems, this paper realizes the network programmability based on SRv6. In this paper, a research on intra-domain routing protection scheme based on SRv6 (RPSRv6) is proposed. Firstly, the calculation rules of backup paths are proposed. According to the backup path calculation rule, the backup path is calculated for all pairs of source and destination nodes affected by link failure in the incremental shortest path tree generated. On this basis, the calculation rule of Segment List is proposed, that is, the value and number of SIDs in the Segment List are calculated. In the process of calculating the backup path, each node affected by the fault and other nodes can be accessed at most once, so the time complexity of RPSRv6 has good performance. The experimental results show that compared with existing DC (downstream criterion) rules and U-Turn algorithms, RPSRv6 algorithm has better experimental results in fault protection rate and path stretch, reaching 100% fault protection rate and the optimal path in path stretch.

Key words: SRv6, intradomain routing, routing protection, network failure, routing availability, incremental shortest path tree

摘要： 网络故障导致大量的数据包丢失，并且严重影响网络性能，如何高效快速地应对网络中的故障是设计路由协议的基本要求和主要任务。目前，比较有效的方法是互联网部署的开放式最短路径优先（open shortest path first， OSPF）和中间系统到中间系统（intermediate system-to-intermediate system，IS-IS），通过动态路由协议解决网络故障，但是在协议动态收敛的过程中仍会有大量的报文被丢弃。因此，路由器厂商广泛采用了性能更好的路由保护方法来克服网络故障，然而，已有的路由保护方案普遍存在实现复杂度较高或者故障保护率偏低情况。针对上述问题，在SRv6实现了网络可编程性的基础上，提出一种基于SRv6的域内路由保护方案（research on intra-domain routing protection scheme based on SRv6，RPSRv6），方案首先提出了备份路径的计算规则，并根据备份路径计算规则在生成的增量最短路径树上，为所有受链路故障影响的源目的结点对计算备份路径，在此基础上，提出了Segment List的计算规则，即计算出Segment List中SID的值与个数。在计算备份路径的过程中，每个受故障影响的结点和其他结点最多被访问一次，因此RPSRv6的时间复杂度具有较好的表现。实验结果表明，与已有的实现DC（downstream criterion）规则和U-Turn算法相比较，RPSRv6算法在故障保护率和路径拉伸度两个度量指标具有更好的实验效果，达到了100%的故障保护率并且在路径拉伸度方面达到了最优路径。

关键词: SRv6, 域内路由, 路由保护, 网络故障, 路由可用性, 增量最短路径树