软件定义网络中一种快速无循环路径迁移策略

doi:10.11959/j.issn.1000-436x.2022088

通信学报 ›› 2022, Vol. 43 ›› Issue (5): 24-35.doi: 10.11959/j.issn.1000-436x.2022088

软件定义网络中一种快速无循环路径迁移策略

燕昺昊¹, 刘勤让¹^,², 沈剑良¹, 汤先拓¹, 梁栋¹

¹ 信息工程大学信息技术研究所，河南郑州 450001
² 国家数字交换系统工程技术研究中心，河南郑州 450001

修回日期:2022-03-17 出版日期:2022-05-25 发布日期:2022-05-01
作者简介:燕昺昊（1994- ），男，山西吕梁人，信息工程大学信息技术研究所博士生，主要研究方向为软件定义网络、低时延通信等
刘勤让（1975- ），男，河南商丘人，博士，信息工程大学信息技术研究所研究员、博士生导师，主要研究方向为新一代网络体系结构、时间敏感网络等
沈剑良（1982- ），男，浙江德清人，博士，信息工程大学信息技术研究所副研究员，主要研究方向为新一代网络信息系统架构设计、大规模集成电路设计等
汤先拓（1984- ），男，湖南长沙人，博士，信息工程大学信息技术研究所副研究员，主要研究方向为新型网络架构、高性能片上网络设计等
梁栋（1992- ），男，河南郑州人，信息工程大学信息技术研究所博士生，主要研究方向为软件定义网络、网络故障恢复等
基金资助:
国家科技重大专项基金资助项目(2017ZX01030301);工业互联网创新发展工程基金资助项目(TC190A446-2)

Fast loop-free path migration strategy in software defined network

Binghao YAN¹, Qinrang LIU¹^,², Jianliang SHEN¹, Xiantuo TANG¹, Dong LIANG¹

¹ Institute of Information Technology, Information Engineering University, Zhengzhou 450001, China
² National Digital Switching System Engineering ＆Technological R＆D Center, Zhengzhou 450001, China

Revised:2022-03-17 Online:2022-05-25 Published:2022-05-01
Supported by:
The National Science and Technology Major Project of China(2017ZX01030301);Industrial Internet Innovation Development Foundation Project(TC190A446-2)

摘要/Abstract

摘要：

针对软件定义网络中数据平面转发设备的分布式部署及异步操作导致的路径迁移缓慢及故障等问题，提出了一种快速无循环路径迁移策略。首先，提出了一种基于节点排序的快速循环检测算法。该算法通过对比流的新旧路径上相邻节点的位置差异，可快速判定路径迁移过程中是否存在转发循环以及检测循环发生位置。然后，提出了一种基于节点松弛依赖关系的贪婪更新机制。该机制利用快速循环检测算法发掘出新旧路径上公有交换机之间存在的松弛依赖关系，进而保证了迁移过程每轮更新的交换机数量最大化。仿真实验结果表明，相比于现有迁移方案，所提策略在不同网络状态下均可有效避免迁移循环且获得最佳更新时间开销。

关键词: 软件定义网络, 路径迁移, 循环避免, 松弛依赖, 贪婪机制

Abstract:

Aiming at the problems of slow and faulty path migration caused by distributed deployment and asynchronous operation of data plane forwarding devices in software defined network, a fast loop-free path migration strategy was proposed.First, a fast loop detection algorithm based on node ranking was proposed.By comparing the position differences of adjacent nodes on the old and new paths of the flow, whether there was a forwarding loop in the path migration process and the location detection where the loop occurs could be quickly determined.Then, a greedy update mechanism based on node relaxation dependency was proposed.The fast loop detection algorithm was used to uncover the relaxation dependency between the common switches on the old and new paths, and the number of switches updated in each round of the migration process was ensured to be maximized.Simulation results show that the proposed strategy can effectively avoid migration loops and obtain the optimal update time overhead under different network states compared with existing migration schemes.

Key words: software defined network, path migration, loop avoidance, relaxation dependency, greedy mechanism

中图分类号:

TP393

燕昺昊, 刘勤让, 沈剑良, 汤先拓, 梁栋. 软件定义网络中一种快速无循环路径迁移策略[J]. 通信学报, 2022, 43(5): 24-35.

Binghao YAN, Qinrang LIU, Jianliang SHEN, Xiantuo TANG, Dong LIANG. Fast loop-free path migration strategy in software defined network[J]. Journal on Communications, 2022, 43(5): 24-35.

图/表 15

图1

表1

网络模型相关参数及含义"

参数	含义
G= (V,E)	网络拓扑
$V = {v_{i} \| i = 1, \dots, n}$	网络中交换机集合
$E = {e_{j} \| j = 1, \dots, m}$	网络中链路集合
C	控制器
f	流
$p_{o} = (v_{1}^{o}, v_{2}^{o}, \dots, v_{q}^{o})$	旧路径
$p_{n} = (v_{1}^{n}, v_{2}^{n}, \dots, v_{p}^{n})$	新路径
$v_{c} \in {v_{p}^{n} \cap v_{q}^{o}, v_{p + 1}^{n} \neq v_{q + 1}^{o}}$	新旧路径公共交换机
$U = {u_{1}, u_{2}, \dots, u_{k}}$	更新轮数
R_v	交换机剩余可用容量

表1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

表2

参考文献 13

[1]	YAN B H , LIU Q R , SHEN J L ,et al. A survey of low-latency transmission strategies in software defined networking[J]. Computer Science Review, 2021,40:100386.
[2]	史久根, 杨旭, 刘雅丽 ,等. 软件定义网络中快速和一致的流更新策略[J]. 电子与信息学报, 2021,43(9): 2617-2623.
	SHI J G , YANG X , LIU Y L ,et al. Fast and consistent flow update in software defined network[J]. Journal of Electronics ＆ Information Technology, 2021,43(9): 2617-2623.
[3]	苏建忠, 张华宇, 朱海龙 . 结合SDN控制器的TSN周期性带宽预留值计算方法[J]. 通信学报, 2021,42(10): 23-31.
	SU J Z , ZHANG H Y , ZHU H L . Computing method for periodic stream reservation in TSN combined with SDN controller[J]. Journal on Communications, 2021,42(10): 23-31.
[4]	汪硕, 黄玉栋, 黄韬 ,等. 基于软件定义的时间敏感网络跨域调度机制[J]. 通信学报, 2021,42(10): 1-9.
	WANG S , HUANG Y D , HUANG T ,et al. Software-defined cross-domain scheduling mechanism for time-sensitive networking[J]. Journal on Communications, 2021,42(10): 1-9.
[5]	FOERSTER K T , SCHMID S , VISSICCHIO S . Survey of consistent software-defined network updates[J]. IEEE Communications Surveys＆ Tutorials, 2019,21(2): 1435-1461.
[6]	WU G H , GAO X F , ZHENG J Q ,et al. Achieving fast loop-free updates with ingress port in software-defined networks[J]. IEEE/ACM Transactions on Networking, 2021,29(4): 1527-1539.
[7]	WANG W , HE W B , SU J S ,et al. Cupid:congestion-free consistent data plane update in software defined networks[C]// Proceedings of the 35th Annual IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2016: 1-9.
[8]	SONG H F , GUO S T , LI P ,et al. FCNR:fast and consistent network reconfiguration with low latency for SDN[J]. Computer Networks, 2021,193:108113.
[9]	VISSICCHIO S , CITTADINI L . FLIP the (flow) table:fast lightweight policy-preserving SDN updates[C]// Proceedings of IEEE INFOCOM 2016-the 35th Annual IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2016: 1-9.
[10]	ZHOU W , JIN D , CROFT J ,et al. Enforcing customizable consistency properties in software-defined networks[C]// Proceedings of the 12th USENIX Symposium on Networked Systems Design and Implementation (NSDI’15). Berkeley:USENIX Association, 2015: 73-85.
[11]	LI P , GUO S T , PAN C S ,et al. Fast congestion-free consistent flow forwarding rules update in software defined networking[J]. Future Generation Computer Systems, 2019,97: 743-754.
[12]	KNIGHT S , NGUYEN H X , FALKNER N ,et al. The Internet topology zoo[J]. IEEE Journal on Selected Areas in Communications, 2011,29(9): 1765-1775.
[13]	RUSEK K , SUáREZ-VARELA J , MESTRES A ,et al. Unveiling the potential of graph neural networks for network modeling and optimization in SDN[C]// Proceedings of the 2019 ACM Symposium on SDN Research. New York:ACM Press, 2019: 140-151.

公共节点数	随机拓扑	GEANT2拓扑	INS-INC拓扑
4	10%	5%	5%
5	30%	10%	10%
6	40%	20%	15%
7	20%	25%	20%
8	—	25%	25%
9	—	15%	20%
10	—	—	5%

[1]	王东滨, 吴东哲, 智慧, 郭昆, 张勖, 时金桥, 张宇, 陆月明. 软件定义网络抗拒绝服务攻击的流表溢出防护[J]. 通信学报, 2023, 44(2): 1-11.
[2]	沙宗轩, 霍如, 孙闯, 汪硕, 黄韬. 基于深度强化学习的转发效能感知流量调度算法[J]. 通信学报, 2022, 43(8): 30-40.
[3]	吴平, 常朝稳, 左志斌, 马莹莹. 基于地址重载的SDN分组转发验证[J]. 通信学报, 2022, 43(3): 88-100.
[4]	李传煌, 陈泱婷, 唐晶晶, 楼佳丽, 谢仁华, 方春涛, 王伟明, 陈超. QL-STCT：一种SDN链路故障智能路由收敛方法[J]. 通信学报, 2022, 43(2): 131-142.
[5]	吴平, 常朝稳, 马莹莹. 基于端址重载的SDN包转发验证[J]. 通信学报, 2021, 42(7): 70-83.
[6]	常朝稳, 金建树, 韩培胜, 祝现威. 基于属性签名标识的SDN数据包转发验证方案[J]. 通信学报, 2021, 42(6): 131-144.
[7]	周启钊, 于俊清, 李冬. SDN控制层泛洪防御机制研究：检测与缓解[J]. 通信学报, 2021, 42(11): 41-53.
[8]	李硕朋, 方娟, 陈肯. 基于SRv6的确定性网络服务共享保护方案[J]. 通信学报, 2021, 42(10): 32-42.
[9]	姚蓝,兰巨龙. 基于联盟博弈的自适应SDN交换机迁移机制[J]. 通信学报, 2020, 41(8): 1-10.
[10]	王耀民,王霞,董易,张松海,施心陵. 基于斐波那契树优化算法的数据中心流量调度策略[J]. 通信学报, 2020, 41(6): 112-127.
[11]	韩珍珍,赵国锋,徐川,周文涛,周洋洋. 基于时延的LEO卫星网络SDN控制器动态放置方法[J]. 通信学报, 2020, 41(3): 126-135.
[12]	赖英旭,蒲叶玮,刘静. 基于最小代价路径的交换机迁移方法研究[J]. 通信学报, 2020, 41(2): 131-142.
[13]	柯文龙,王勇,叶苗,陈俊奇. Ceph云存储网络中一种业务优先级区分的多播流调度方法[J]. 通信学报, 2020, 41(11): 40-51.
[14]	张海波,王子心,贺晓帆. SDN和MEC架构下V2X卸载与资源分配[J]. 通信学报, 2020, 41(1): 114-124.
[15]	董芳,胡宇翔,李鸥. 基于SDN的自组织网络路由框架及构建方法[J]. 通信学报, 2019, 40(9): 33-44.

软件定义网络中一种快速无循环路径迁移策略

Fast loop-free path migration strategy in software defined network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 13

相关文章 15

Metrics

推荐阅读 0