基于拓扑分割与聚类分析的虚拟软件定义网络映射算法

doi:10.11772/j.issn.1001-9081.2021010015

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (11): 3309-3318.DOI: 10.11772/j.issn.1001-9081.2021010015

基于拓扑分割与聚类分析的虚拟软件定义网络映射算法

陈港(), 孟相如, 康巧燕, 阳勇

空军工程大学信息与导航学院，西安 710077

收稿日期:2021-01-07 修回日期:2021-02-28 接受日期:2021-03-12 发布日期:2021-03-29 出版日期:2021-11-10
通讯作者: 陈港
作者简介:陈港（1997—），男，湖南常德人，硕士研究生，主要研究方向：网络可生存性、网络安全
孟相如（1963—），男，陕西蓝田人，教授，博士，主要研究方向：下一代网络、网络虚拟化
康巧燕（1980—），女，福建永春人，副教授，博士，主要研究方向：下一代网络、网络可生存性
阳勇（1998—），男，湖南衡阳人，硕士研究生，主要研究方向：网络功能虚拟化、虚拟网络可生存性。
基金资助:
陕西省重点研发计划项目(2020-GY-026)

Virtual software defined network mapping algorithm based on topology segmentation and clustering analysis

Gang CHEN(), Xiangru MENG, Qiaoyan KANG, Yong YANG

Information and Navigation School，Air Force Engineering University，Xi’an Shaanxi 710077，China

Received:2021-01-07 Revised:2021-02-28 Accepted:2021-03-12 Online:2021-03-29 Published:2021-11-10
Contact: Gang CHEN
About author:CHEN Gang， born in 1997， M. S. candidate. His research interests include network survivability，network security
MENG Xiangru，born in 1963，Ph. D.，professor. His research interests include next-generation network，network virtualization
KANG Qiaoyan，born in 1980，Ph. D.，associate professor. Her research interests include next-generation network，network survivability
YANG Yong， born in 1998， M. S. candidate. His research interests include network function virtualization， virtual network survivability.
Supported by:
the Key Research and Development Program of Shaanxi Province(2020-GY-026)

摘要/Abstract

摘要：

针对目前大部分基于虚拟软件定义网络（vSDN）的映射算法未充分考虑节点与链路之间的相关性的问题，提出了一种基于网络拓扑分割与聚类分析的vSDN映射算法。首先，通过根据最短跳数进行拓扑分割的方法，降低物理网络的复杂度；然后，通过根据节点拓扑和资源属性进行聚类分析的方法，提升映射算法的请求接受率；最后，通过将链路约束分散到节点带宽资源以及节点的度进行约束考量，对不符合链路要求的节点进行重映射，从而优化了节点与链路映射过程。实验结果表明，该算法有效地提升了基于软件定义网络（SDN）架构的虚拟网络映射算法在较低连通概率物理网络下的请求接受率。

关键词: 网络虚拟化, 虚拟软件定义网络, 映射算法, 拓扑分割, 聚类分析

Abstract:

Aiming at the problem that most mapping algorithms based on virtual Software Defined Network （vSDN） do not fully consider the correlation between nodes and links， a vSDN mapping algorithm based on network topology segmentation and clustering analysis was proposed. Firstly， the complexity of physical network was reduced by the topology segmentation method based on the shortest hop count. Then， the request acceptance rate of mapping algorithm was improved by the clustering analysis method based on node topology and resource attributes. Finally， the nodes that do not meet the link requirements were remapped， by dispersing the link constraints to the bandwidth resources of nodes and the degrees of nodes to perform the consideration with constraints， so that the mapping process between nodes and links was optimized. Experimental results show that， the proposed algorithm can effectively improves the request acceptance rate of virtual network mapping algorithm based on Software Defined Network （SDN） architecture in physical networks with low connectivity probability.

Key words: network virtualization, virtual Software Defined Network (vSDN), mapping algorithm, topology segmentation, clustering analysis

中图分类号:

TP393

陈港, 孟相如, 康巧燕, 阳勇. 基于拓扑分割与聚类分析的虚拟软件定义网络映射算法[J]. 计算机应用, 2021, 41(11): 3309-3318.

Gang CHEN, Xiangru MENG, Qiaoyan KANG, Yong YANG. Virtual software defined network mapping algorithm based on topology segmentation and clustering analysis[J]. Journal of Computer Applications, 2021, 41(11): 3309-3318.

图/表 11

图1 虚拟SDN映射模型

Fig. 1 Virtual SDN mapping model

图2 物理网络拓扑分割示例

Fig. 2 Example of physical network topology segmentation

图3 树形拓扑网络示例

Fig. 3 Example of tree topology network

图4 延展后的树形拓扑图

Fig. 4 Extended tree topology diagram

图5 映射算法流程

Fig. 5 Flow chart of mapping algorithm

表1 底层物理网络分类及参数设置

Tab. 1 Classification and parameter setting of underlying physical network

物理网络类型	连通概率	带宽资源/（Gb·s^-1）		计算资源CPU		存储资源TCAM
物理网络类型	连通概率	数据链路	控制链路	交换机	控制器	交换机	控制器
topo-facebook	约0.018	40	40	12×10³	48×10³	250×10³	1 000×10³
topo-fat-tree	约0.026	40	40	12×10³	48×10³	250×10³	1 000×10³
topo-mesh	0.018	U［35，45］	40	U［8×10³，16×10³］	4× $C n g s$	U［200×10³，300×10³］	4× $T C M n g s$
topo-mesh	0.026	U［35，45］	40	U［8×10³，16×10³］	4× $C n g s$	U［200×10³，300×10³］	4× $T C M n g s$

表1 底层物理网络分类及参数设置

Tab. 1 Classification and parameter setting of underlying physical network

物理网络类型	连通概率	带宽资源/（Gb·s^-1）		计算资源CPU		存储资源TCAM
物理网络类型	连通概率	数据链路	控制链路	交换机	控制器	交换机	控制器
topo-facebook	约0.018	40	40	12×10³	48×10³	250×10³	1 000×10³
topo-fat-tree	约0.026	40	40	12×10³	48×10³	250×10³	1 000×10³
topo-mesh	0.018	U［35，45］	40	U［8×10³，16×10³］	4× $C n g s$	U［200×10³，300×10³］	4× $T C M n g s$
topo-mesh	0.026	U［35，45］	40	U［8×10³，16×10³］	4× $C n g s$	U［200×10³，300×10³］	4× $T C M n g s$

图6 不同比值时算法TSCA-vSDN的请求接受率对比

Fig. 6 Comparison of request acceptance rate of TSCA-vSDN algorithm with different ratios

图7 基于topo-facebook（KP≈0.018）物理网络的算法请求接受率对比

Fig. 7 Comparison of algorithm request acceptance rate based on topo-facebook （KP≈0.018） physical network

图8 基于topo-mesh（KP=0.018）物理网络的算法请求接受率对比

Fig. 8 Comparison of algorithm request acceptance rate based on topo-mesh （KP=0.018） physical network

图9 基于topo-fat-tree（KP≈0.026）物理网络的算法请求接受率对比

Fig. 9 Comparison of algorithm request acceptance rate based on topo-fat-tree （KP≈0.026） physical network

图10 基于topo-mesh（KP=0.026）物理网络的算法请求接受率对比

Fig. 10 Comparison of algorithm request acceptance rate based on topo-mesh （KP=0.026） physical network

参考文献 17

1	PRAJAPATI A， SAKADASARIYA A， PATEL J. Software defined network： future of networking ［C］// Proceedings of the 2018 2nd International Conference on Inventive Systems and Control. Piscataway： IEEE， 2018： 1351-1354. 10.1109/icisc.2018.8399028
2	CHAUDHARI S， MANI R S， RAUNDALE P. SDN network virtualization survey ［C］// Proceedings of the 2016 International Conference on Wireless Communications， Signal Processing and Networking. Piscataway： IEEE， 2016： 650-655. 10.1109/wispnet.2016.7566213
3	CHEN S， SUN W Q， HU W S. On dynamic hypervisor placement in virtualized Software Defined Networks （vSDNs）［C］// Proceedings of the 2020 22nd International Conference on Transparent Optical Networks. Piscataway： IEEE， 2020： 1-5. 10.1109/icton51198.2020.9203137
4	ALSHAER H， UNIYAL N， KATSAROS K， et al. The UK programmable fixed and mobile Internet infrastructure： overview， capabilities and use cases deployment ［J］. IEEE Access， 2020， 8： 175398-175411. 10.1109/access.2020.3020894
5	CAO H T， WU S C， HU Y， et al. A survey of embedding algorithm for virtual network embedding ［J］. China Communications， 2019， 16（12）： 1-33. 10.23919/jcc.2019.12.001
6	ZHU L， SUN W Q， HU W S. Delay constrained vSDN embedding in WAN ［C］// Proceedings of the 2017 Computing Conference. Piscataway： IEEE， 2017： 1283-1289. 10.1109/sai.2017.8252256
7	SANDHU A K， SINGH BATTH R， NAGPAL A. Improved QoS using novel fault tolerant shortest path algorithm in Virtual Software Defined Network （VSDN）［C］// Proceedings of the 2019 International Conference on Automation， Computational and Technology Management. Piscataway： IEEE， 2019： 383-388. 10.1109/icactm.2019.8776762
8	TAN Y S， LI R Z， ZHANG J F， et al. Survivable virtual SDN embedding approach for innovative cloud data network ［C］// Proceedings of the 2017 14th International Symposium on Pervasive Systems， Algorithms and Networks/ 11th International Conference on Frontier of Computer Science and Technology/ 3rd International Symposium of Creative Computing. Piscataway： IEEE， 2017： 265-271. 10.1109/ispan-fcst-iscc.2017.32
9	KUANG H L， FU Y P. VNE-TS： a novel virtual network mapping algorithm in SDN ［C］// Proceedings of the 2016 5th International Conference on Computer Science and Network Technology. Piscataway： IEEE， 2016： 657-661. 10.1109/iccsnt.2016.8070239
10	冉金鹏，王翔，赵尚弘，等.基于果蝇优化的虚拟SDN网络映射算法［J］.信息网络安全，2020，20（6）：65-74. 10.3969/j.issn.1671-1122.2020.06.008
	RAN J P， WANG X， ZHAO S H， et al. Virtual SDN network embedding algorithm based on fruit fly optimization ［J］. Netinfo Security， 2020， 20（6）：65-74. 10.3969/j.issn.1671-1122.2020.06.008
11	王健，赵国生，李志新.面向SDN的虚拟网络映射算法研究［J］.通信学报，2017，38（10）：26-35. 10.11959/j.issn.1000-436x.2017195
	WANG J， ZHAO G S， LI Z X. Research on mapping algorithm of virtual network oriented to SDN ［J］. Journal on Communications， 2017， 38（10）： 26-35. 10.11959/j.issn.1000-436x.2017195
12	LI R Z， ZHANG J F， TAN Y S， et al. Topology-aware VSDN embedding approach on shared software defined networks ［C］// Proceedings of the 2016 5th International Conference on Computer Science and Network Technology. Piscataway： IEEE， 2016： 455-460. 10.1109/iccsnt.2016.8070200
13	YAN Z H， WEI N， JIN Q Z， et al. Latency-aware resource-efficient virtual network embedding in software defined networking ［C］// Proceedings of the 2019 28th Wireless and Optical Communications Conference. Piscataway： IEEE， 2019： 1-5. 10.1109/wocc.2019.8770635
14	赵思逸，陈靖，龚水清.基于粒子群优化的虚拟SDN网络映射算法［J］.计算机工程，2016，42（12）：84-90. 10.3969/j.issn.1000-3428.2016.12.015
	ZHAO S Y， CHEN J， GONG S Q. Virtual SDN network mapping algorithm based on particle swarm optimization ［J］. Computer Engineering， 2016， 42（12）： 84-90. 10.3969/j.issn.1000-3428.2016.12.015
15	冉金鹏，赵尚弘，王翔，等.面向SDN的生存性虚拟网络映射算法［J］.系统工程与电子技术，2020，42（5）：1182-1189. 10.3969/j.issn.1001-506X.2020.05.28
	RAN J P， ZHAO S H， WANG X， et al. Survivability virtual network embedding algorithm oriented to SDN ［J］. Systems Engineering and Electronics， 2020， 42（5）： 1182-1189. 10.3969/j.issn.1001-506X.2020.05.28
16	YAO Y F， GUO S T， LI P， et al. Forecasting assisted VNF scaling in NFV-enabled networks ［J］. Computer Networks， 2020， 168： Article No.107040. 10.1016/j.comnet.2019.107040
17	张一凡.高速SDN交换机性能测试平台的研究与实现［D］.成都：电子科技大学，2020：55-56. 10.30919/esee8c207
	ZHANG Y F. Research and implementation of high-speed SDN switch performance test platform ［D］. Chengdu： University of Electronic Science and Technology of China， 2020： 55-56. 10.30919/esee8c207

[1]	丁雨, 张瀚霖, 罗荣, 孟华. 基于信念子簇切割的模糊聚类算法[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1128-1138.
[2]	郭茂祖, 张雅喆, 赵玲玲. 基于空间语义和个体活动的电动汽车充电站选址方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2819-2827.
[3]	李文全, 毛伊敏, 彭新东. 基于犹豫模糊集的凝聚式层次聚类算法[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3755-3763.
[4]	李由之, 胡志华, 陈春, 杨培蓓, 董雅静. 基于双长短期记忆网络组合的网络货运平台成交定价预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1616-1623.
[5]	戴嫣然, 戴国庆, 袁玉波. 基于肤色学习的多人脸前景抽取方法[J]. 计算机应用, 2021, 41(6): 1659-1666.
[6]	郭佳, 韩李涛, 孙宪龙, 周丽娟. 自动确定聚类中心的比较密度峰值聚类算法[J]. 计算机应用, 2021, 41(3): 738-744.
[7]	赵季红, 吴豆豆, 曲桦, 殷振宇. 基于软件定义网络的可靠性虚拟网络映射保障机制[J]. 计算机应用, 2020, 40(3): 770-776.
[8]	任帅, 徐振超, 王震, 贺媛, 张弢, 苏东旭, 慕德俊. 基于多融合态的低密度三维模型信息隐藏算法[J]. 计算机应用, 2019, 39(4): 1100-1105.
[9]	孙石磊, 王超, 赵元棣. 基于轮廓系数的参数无关空中交通轨迹聚类方法[J]. 计算机应用, 2019, 39(11): 3293-3297.
[10]	陆明炽, 王守华, 李云柯, 纪元法, 孙希延, 邓桂辉. 基于特征匹配和距离加权的蓝牙定位算法[J]. 计算机应用, 2018, 38(8): 2359-2364.
[11]	任帅, 张弢, 徐振超, 王震, 贺媛, 柳雨农. 特征点标注与聚类的三维模型信息隐藏算法[J]. 计算机应用, 2018, 38(4): 1017-1022.
[12]	李晔, 陈奕延, 张淑芬. 基于密度峰值的混合型数据聚类算法设计[J]. 计算机应用, 2018, 38(2): 483-490.
[13]	徐晓伟, 杜一, 周园春. 基于多源出行数据的居民行为模式分析方法[J]. 计算机应用, 2017, 37(8): 2362-2367.
[14]	梁双, 周丽华, 杨培忠. 基于聚类分析分库策略的社交网络数据库查询性能与数据迁移[J]. 计算机应用, 2017, 37(3): 673-679.
[15]	金亮, 于炯, 杨兴耀, 鲁亮, 王跃飞, 国冰磊, 廖彬. 基于聚类层次模型的视频推荐算法[J]. 计算机应用, 2017, 37(10): 2828-2833.

基于拓扑分割与聚类分析的虚拟软件定义网络映射算法

Virtual software defined network mapping algorithm based on topology segmentation and clustering analysis

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 17

相关文章 15

编辑推荐

Metrics