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

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