作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (6): 209-215. doi: 10.19678/j.issn.1000-3428.0054783

• 体系结构与软件技术 • 上一篇    下一篇

基于混合软件定义网络的路由保护算法

耿海军1, 张伟2, 尹霞3   

  1. 1. 山西大学 软件学院, 太原 030006;
    2. 中国劳动关系学院 计算机应用教研室, 北京 100048;
    3. 清华大学 计算机科学与技术系, 北京 100084
  • 收稿日期:2019-04-30 修回日期:2019-06-03 发布日期:2020-06-10
  • 作者简介:耿海军(1983-),男,讲师、博士,主研方向为网络体系结构、路由算法;张伟,副教授;尹霞,教授、博士。
  • 基金资助:
    国家自然科学基金(61702315);山西省高等学校科技创新项目(201802013)。

Routing Protection Algorithm Based on Hybrid Software Defined Network

GENG Haijun1, ZHANG Wei2, YIN Xia3   

  1. 1. School of Software Engineering, Shanxi University, Taiyuan 030006, China;
    2. Computer Application Teaching and Research Section, China University of Labor Relations, Beijing 100048, China;
    3. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
  • Received:2019-04-30 Revised:2019-06-03 Published:2020-06-10

摘要: 为使混合软件定义网络(SDN)体系架构能够应对网络中的单链路故障情形,提出一种基于混合软件定义网络的路由保护算法。在混合SDN网络中部署应对单链路故障的路由保护算法,将其归结为一个0-1整数规划问题,并利用启发式算法计算该问题对应的近似最优解。通过实例介绍算法的执行过程,分析算法对应的时间复杂度。实验结果表明,该算法仅需将传统网络中的少部分节点升级为SDN节点,即可应对网络中可能出现的单链路故障情形,且对应的路径拉伸度在1.4以内。

关键词: 混合软件定义网络, 单链路故障, 启发式算法, 整数规划模型, 故障保护率

Abstract: In order to enable the Software Defined Network(SDN) to cope with the possible situations of single link failure in network,this paper proposes a routing protection algorithm based on hybrid SDN.The routing protection algorithm coping with the single link failure is deployed in the hybrid SDN,which is reduced to a 0-1 integer programming problem and a heuristic algorithm is used to calculate the approximate optimal solution to the problem.The execution process of the algorithm is introduced through an example and the corresponding time complexity of the algorithm is analyzed.Experimental results show that the proposed algorithm can cope with all possible situations of single link failure only by upgrading a small number of nodes in the traditional network to SDN nodes,and the corresponding path stretch is within 1.4.

Key words: hybrid Software Defined Network(SDN), single link failure, heuristic algorithm, integer programming model, failure protection ratio

中图分类号: