基于优化链路权值的域内路由保护方案

目前,互联网部署的域内链路状态路由协议,如开放最短路径优先(Open Shortest Path First,OSPF)和中间系统到中间系统(Intermediate System-to-Intermediate System,IS-IS),采用被动恢复方案应对网络故障。随着网络的发展,大量的实时应用部署在互联网上,OSPF的收敛时间无法满足这些实时应用对收敛时间的需求。因此,学术界和工业界提出采用路由保护方案来应对网路中出现的故障。然而,已有的路由保护方案存在两个方面的问题:1)默认路径和备份路径的交叉度较高,如LFA;2)为了计算两条交叉度低的路径,对默认路径加以限制,即默认路径不采用最短路径,如Color Tree。为了解决上述两个问题,首先将上述问题归结为整数规划模型,接着利用启发式方法计算近似最优解,最后在实际网络和模拟网络中对所提算法进行了大量实验。实验结果表明,所提算法可以降低默认路径和备份路径的交叉度,极大地提高网络的可用性。

Intra-domain Routing Protection Scheme by Optimizing Link Weight

The current deployed intra-domain link state routing protocols on the Internet,such as Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS),generally adopt proactive recovery schemes to cope with network failures.In addition,with the emergence of real-time and mission-critical applications,stringent reliability and high availability are required.However,the deployed intra-domain link-state routing protocols need a global link-state advertisement and need to recalculate routing tables when link failures occur,inevitably causing network outage.As a result,academics and industry proposed to employ reactive routing protection solutions to deal with network failures in the network.The proactive schemes compute backup paths in advance,so that packets can be forwarded over those precomputing paths after the detection of network failures.However,the existing routing protection algorithms are facing two problems:1)the disjointness of the default path with respect to the backup path is very low,i.e.,ECMP and LFA,2)in order to compute two paths which have high disjointness,some restrictions must be impressed on default path,i.e.,the default path is not the shortest path.This paper first introduced the problem of constructing disjoint paths into integer programming problems,and then proposed to use the heuristic algorithm to calculate the approximate optimal solution.Finally,the algorithms were carried out in the real,measured and generated networks.The experimental results show that the proposed algorithms can greatly enhance the disjointness of the shortest path and the backup path,and improve the network availability.