Abstract: Academia and industry have proposed to employ the routing protection scheme to cope with the network failures in intra-domain routing protocol. The routing protection scheme can speed up the network recovery and reduce the network downtime due when the network failures occur. At present, the popular routing protection algorithms are LFA and U-turn, which attribute to their simplicity and efficiency. However, the protection ratio on all single link failure scenarios of these two schemes is very low. Therefore segment routing is proposed to solve the above problem. However, the existing researches concerning on segment routing have focused on its architecture and use cases. Therefore, this paper focuses on how to compute segments in segment routing. It first describes the problem as an integer programming problem, and then proposes a two phase heuristic algorithm to calculate the approximate optimal solution. Finally, the algorithm is conducted on different network topologies. The simulation results show that the protection ratio on all single link failure scenarios is superior to LFA and U-turn.

Key words: segment routing, integer linear programming, routing protection

摘要： 学术界和工业界提出利用路由保护方案来提高域内路由协议应对故障的能力，从而加速网络故障恢复，降低由于网络故障引起的网络中断时间。目前互联网普遍采用的路由保护方案包括LFA和U-turn，由于它们的简单和高效，受到了互联网服务提供商的支持，但是这两种方案的单链路故障保护率较低。因此，段路由（Segment Routing，SR）被提出解决上述两种方案存在的问题，已有的针对SR的研究主要集中在其体系结构和应用场景。研究如何在SR中计算segments，将该问题表述为一个整数线性规划问题，提出一种两阶段的启发式算法（Two Phase Heuristic Algorithm，TPHA）求解该问题，将算法在不同网络拓扑中进行了模拟。模拟结果表明，TPHA的单链路故障保护率远远高于LFA和U-turn的单链路故障保护率。

关键词: 段路由, 整数线性规划, 路由保护