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

doi:10.11772/j.issn.1001-9081.2021010015

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (11): 3309-3318.DOI: 10.11772/j.issn.1001-9081.2021010015

• Network and communications • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP393

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.

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

Figures/Tables 11

Fig. 1 Virtual SDN mapping model

Fig. 2 Example of physical network topology segmentation

Fig. 3 Example of tree topology network

Fig. 4 Extended tree topology diagram

Fig. 5 Flow chart of mapping algorithm

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$

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$

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

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

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

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

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

References 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]	Yu DING, Hanlin ZHANG, Rong LUO, Hua MENG. Fuzzy clustering algorithm based on belief subcluster cutting [J]. Journal of Computer Applications, 2024, 44(4): 1128-1138.
[2]	Wenquan LI, Yimin MAO, Xindong PENG. Agglomerative hierarchical clustering algorithm based on hesitant fuzzy set [J]. Journal of Computer Applications, 2023, 43(12): 3755-3763.
[3]	Youzhi LI, Zhihua HU, Chun CHEN, Peibei YANG, Yajing DONG. Prediction model of transaction pricing in internet freight transport platform based on combination of dual long short-term memory networks [J]. Journal of Computer Applications, 2022, 42(5): 1616-1623.
[4]	DAI Yanran, DAI Guoqing, YUAN Yubo. Multi-face foreground extraction method based on skin color learning [J]. Journal of Computer Applications, 2021, 41(6): 1659-1666.
[5]	GUO Jia, HAN Litao, SUN Xianlong, ZHOU Lijuan. Comparative density peaks clustering algorithm with automatic determination of clustering center [J]. Journal of Computer Applications, 2021, 41(3): 738-744.
[6]	ZHAO Jihong, WU Doudou, QU Hua, YIN Zhenyu. Survivable virtual network embedding guarantee mechanism based on software defined network [J]. Journal of Computer Applications, 2020, 40(3): 770-776.
[7]	REN Shuai, XU Zhenchao, WANG Zhen, HE Yuan, ZHANG Tao, SU Dongxu, MU Dejun. Low-density 3D model information hiding algorithm based on multple fusion states [J]. Journal of Computer Applications, 2019, 39(4): 1100-1105.
[8]	SUN Shilei, WANG Chao, ZHAO Yuandi. Parameter independent clustering of air traffic trajectory based on silhouette coefficient [J]. Journal of Computer Applications, 2019, 39(11): 3293-3297.
[9]	REN Shuai, ZHANG Tao, XU Zhenchao, WANG Zhen, HE Yuan, LIU Yunong. Information hiding algorithm for 3D models based on feature point labeling and clustering [J]. Journal of Computer Applications, 2018, 38(4): 1017-1022.
[10]	XU Xiaowei, DU Yi, ZHOU Yuanchun. Resident behavior model analysis method based on multi-source travel data [J]. Journal of Computer Applications, 2017, 37(8): 2362-2367.
[11]	LIANG Shuang, ZHOU Lihua, YANG Peizhong. Query performance and data migration for social network database with shard strategy based on clustering analysis [J]. Journal of Computer Applications, 2017, 37(3): 673-679.
[12]	JIN Liang, YU Jiong, YANG Xingyao, LU Liang, WANG Yuefei, GUO Binglei, Liao Bin. Video recommendation algorithm based on clustering and hierarchical model [J]. Journal of Computer Applications, 2017, 37(10): 2828-2833.
[13]	GAO Xianming, WANG Baosheng, LI Tongbiao, XUE Huawei. Design and implementation of resource management plane in virtual router platform [J]. Journal of Computer Applications, 2017, 37(1): 1-5.
[14]	YAUN Ying, WANG Cong, WANG Cuirong, SONG Xin, LYU Yanxia. Virtual network embedding algorithm for dynamic virtual network requests [J]. Journal of Computer Applications, 2017, 37(1): 6-11.
[15]	SONG Guozhi, WANG Cheng, TU Yao, ZHANG Dakun. Low power mapping based on improved genetic algorithm with Prim initial population selection for 3D network-on-chip [J]. Journal of Computer Applications, 2017, 37(1): 90-96.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 17

Related Articles 15

Recommended Articles

Metrics