基于线性规划的大规模网络故障恢复机制

Massive Network Failure Recovery Mechanism Based on Linear Programming

从大规模故障中进行网络恢复时可用的修复资源有限,需要经过多个修复阶段才能实现网络恢复。在过渡修复期间,网络运营商需确保重要流量的可达性。基于此,研究多个过渡修复阶段流量恢复率最大化和被切换路径数量最小化的问题,将其建模为线性规划问题,针对数百个节点构成的网络,基于分而刺穿思想提出启发式算法,获得流量恢复率和被切换路径数量的帕类托最优解。仿真实验结果表明,该算法生成的次优解与线性规划生成的最优解只相差4%,与现有算法相比,可将受影响的路由元素数量下降60%左右,同时保证流量比相当。

In a scenario of recovery from massive failures, a network is repaired through multiple restoration stages because availability of repair resources is limited. During repair transition, it is crucial to ensure the accessibility of important flow for network operators. Therefore, this paper discusses the problem of maximizing the flow recovery ratio involving,transient repairing stages and minimizing the number of switched paths. It formulates the problem as Linear Programming（LP） ,proposes a heuristic algorithm based on the dividing and impaling idea for networks consisting of a few hundred nodes,and obtains pareto-optimal solutions of the flow recovery ratio and the number of switched paths. Simulation results show that the algorithm can produce sub-optimal solutions within a 4% difference from optimal solutions,produced by LP,and it reduces the number of affected routing entries by about 60% compared with the current method while ensuring equivalent flow ratio.