• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2023, Vol. 45 ›› Issue (01): 46-56.

• 计算机网络与信息安全 • 上一篇    下一篇

基于软件定义网络的多约束QoS双路径路由优化方法

苟平章,马琳,郭保永,原晨   

  1. (西北师范大学计算机科学与工程学院,甘肃 兰州 730070)

  • 收稿日期:2022-04-17 修回日期:2022-05-27 接受日期:2023-01-25 出版日期:2023-01-25 发布日期:2023-01-25
  • 基金资助:
    国家自然科学基金(71961028)

A multi-constrained QoS dual path routing optimization algorithm based on software defined network

GOU Ping-zhang,MA Lin,GUO Bao-yong,YUAN Chen   

  1. (College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)
  • Received:2022-04-17 Revised:2022-05-27 Accepted:2023-01-25 Online:2023-01-25 Published:2023-01-25

摘要: 针对当前SDN架构存在路由算法复杂度高、QoS流满意度低和单链路故障等问题,提出了一种基于软件定义网络的多约束QoS双路径路由优化算法(SDN_MCQDP)。利用控制器获得全局网络状态信息,生成基于目的节点的有向无环图。在多约束QoS路由选择阶段,通过拉格朗日松弛对偶算法将多约束问题转化为线性规划问题。使用反向链路删减得到满足多约束QoS的节点不相交的双路径冗余链路,使链路故障后的数据传输得到保障。从路由计算时间、链路利用率、QoS流满意度等方面对算法进行仿真实验。结果表明,与MODLARAC、QT、RMCDP_RD、H_MCOP算法比较,SDN_MCQDP能够有效降低传输时延,减少路由计算时间,提高链路利用率,且在链路发生故障后仍能满足QoS需求。

关键词: 软件定义网络, 多约束QoS, 有向无环图, 拉格朗日松弛对偶算法, 双路径冗余链路

Abstract: In order to solve the problems of high routing algorithm complexity, low QoS flow satisfaction and single link failure in current software-defined network (SDN) architecture, a multi- constraint QoS dual-path routing optimization algorithm based on software-defined network (SDN_ MCQDP) is proposed. The controller is used to obtain the global network state information, and generate a directed acyclic graph based on the destination node. In the multi-constraint QoS routing stage, the multi-constraint problem is transformed into a linear programming problem by the Lagrangian relaxation dual algorithm. The reverse link is used to delete redundant dual-path links that meet multi-constraint QoS and ensure data transmission after link failure. The algorithm is simulated and analyzed from the aspects of routing calculation time, link utilization, and QoS flow satisfaction. The results show that, compared with MODLARAC, QT, RMCDP_RD, and H_MCOP algorithms, SDN_MCQDP can effectively reduce the transmission delay and route calculation time, improve the link utilization, and still meet the QoS requirements after link failure.


Key words: software defined network (SDN), multi-constrained QoS, directed acyclic graph, Lagrangian relaxation dual algorithm, dual-path redundant link