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

doi:10.3969/j.issn.1000-3428.2016.07.018

摘要/Abstract

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

关键词: 大规模故障, 网络恢复, 流量修复率, 被切换路径数量, 线性规划

Abstract: 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.

Key words: massive failure, network recovery, flow repair ratio, number of switched path, Linear Programming(LP)

中图分类号:

TP391

刘珂. 基于线性规划的大规模网络故障恢复机制[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.07.018.

LIU Ke. Massive Network Failure Recovery Mechanism Based on Linear Programming [J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.07.018.

参考文献

参考文献［1］Woo S,Kim H.An Empirical Interference Modeling for Link Reliability Assessment in Wireless Networks［J］.IEEE/ACM Transactions on Networking,2013,21(1):272-285. ［2］Silva I,Guedes L A,Portugal P,et al.Reliability and Availability Evaluation of Wireless Sensor Networks for Industrial Applications［J］.Sensors,2012,12(1):806-838. ［3］Dhadwal D,Arora A,Singh V R.Optimization of Shared Path Protection for SONET/SDH Network［J］.International Journal of Scientific and Engineering Research,2014,5(7):1258-1264. (下转第116页) (上接第108页) ［4］Kamamura S,Miyamura T,Pelsser C,et al.Minimum Backup Configuration-creation Method for IP Fast Reroute［C］//Proceedings of GLOBECOM’09.Honolulu,USA:IEEE Press,2009:1-6. ［5］王汝言,吴晴,熊余,等.基于贝叶斯征兆解释度的链路故障定位算法［J］.计算机应用研究,2013,30(3):712-714. ［6］王明鸣,孟相如,庄绪春,等.基于无环替代重路由优化的网络可生存性增强方法［J］.微电子学与计算机,2014,10(2):110-113. ［7］孙伟,罗俊海,肖志辉.基于 SimCT 的多播路由及故障恢复研究［J］.电信科学,2012,27(12):90-96. ［8］Wang J,Qiao C,Yu H.On Progressive Network Recovery After a Major Disruption［C］//Proceedings of the 30th IEEE International Conference on Computer Communications.Washington D.C.,USA:IEEE Press,2011:1925-1933. ［9］Yu H,Yang C.Partial Network Recovery to Maximize Traffic Demand［J］.IEEE Communications Letters,2011,15(12):1388-1390. ［10］Horie T,Hasegawa G,Kamei S,et al.A New Method of Proactive Recovery Mechanism for Large-scale Network Failures［C］//Proceedings of the 23rd IEEE Interna-tional Conference on Advanced Information Networking and Applications.Bradford,UK:IEEE Press,2009:951-958. ［11］Maurras J F,Vanier S.Network Synthesis Under Survivability Constraints［J］.Quarterly Journal of the Belgian,French and Italian Operations Research Societies,2004,2(1):53-67. ［12］Madry A.Faster Approximation Schemes for Fractional Multicommodity Flow Problems via Dynamic Graph Algorithms［C］//Proceedings of the 42nd ACM Symposium on Theory of Computing.New York,USA:ACM Press,2010:121-130. ［13］Xu K,Liu H,Liu J,et al.LBMP:A Logarithm-barrier-based Multipath Protocol for Internet Traffic Management［J］.IEEE Transactions on Parallel and Distributed Systems,2011,22(3):476-488. ［14］Labovitz C,Iekel-Johnson S,McPherson D,et al.InternetInter-domain Traffic［J］.ACM SIGCOMM Computer Communication Review,2011,41(4):75-86. ［15］Edmonds J,Karp R M.TheoreticalImprovements in Algorithmic Efficiency for Network Flow Problems［J］.Journal of the ACM,2002,19(2):248-264. ［16］Medina A,Lakhina A,Matta I,et al.BRITE:An Approach to Universal Topology Generation［C］//Proceedings of the 9th International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems.Cincinnati,USA:IEEE Press,2001:346-353. 编辑索书志

[1]	信文倩, 孙兵, 李超. LiCi算法的基于比特积分攻击[J]. 计算机工程, 2020, 46(7): 136-142.
[2]	朱国晖, 刘璐, 雷兰洁. 基于VNF组合的服务功能链设计及映射算法[J]. 计算机工程, 2020, 46(4): 183-188,197.
[3]	杨天, 田霖, 孙茜, 张宗帅, 王园园. 移动边缘计算中基于用户体验的计算卸载方案[J]. 计算机工程, 2020, 46(10): 33-40.
[4]	王丁玎, 丁煦, 赵冲, 石雷, 韩江洪. 带无线能量补充设备的无线传感器网络基站部署策略[J]. 计算机工程, 2020, 46(1): 164-171,178.
[5]	刘尧, 宋元斌, 李云祥. 融入逻辑关系的项目调度遗传算法[J]. 计算机工程, 2020, 46(1): 279-285.
[6]	苑乐天,李国峰. 基于业务优先级划分的虚拟网可靠性映射算法[J]. 计算机工程, 2019, 45(2): 76-81.
[7]	刘莹莹,邱崧,孙力,周梅,徐伟. 基于多视角自步学习的人体动作识别方法[J]. 计算机工程, 2018, 44(2): 257-263.
[8]	耿海军,刘洁琦,张举. 基于不相交路径的域内路由保护方案[J]. 计算机工程, 2018, 44(12): 140-144,149.
[9]	侯小静,姬孟洛,黄辰林,舒云星,阎奔. 实时控制系统程序模式的WCET自动分析方法[J]. 计算机工程, 2017, 43(8): 56-62,68.
[10]	李靖,乔蕊,刘志中. 结合对策论与多目标MILP的Web服务组合调度问题求解[J]. 计算机工程, 2016, 42(1): 11-17.
[11]	于广州. WSN中基于线性规划的多类别目标覆盖算法[J]. 计算机工程, 2014, 40(3): 152-157,162.
[12]	李磊,谢小璐. 区间数信息下的多属性群决策研究[J]. 计算机工程, 2014, 40(10): 210-213.
[13]	徐力，史少波. 一种非对称多核SDR的任务调度和分配算法[J]. 计算机工程, 2014, 40(1): 83-87,97.
[14]	王国辉，张晓宇，关永，刘永梅. SpaceWire总线冗余备份优化方法[J]. 计算机工程, 2014, 40(1): 305-308,314.
[15]	王刚, 骆志刚. 制服调换问题中的路圈子图与圈包装研究[J]. 计算机工程, 2013, 39(4): 305-308.