Service function chain construction method based on node utility maximization

doi:10.11772/j.issn.1001-9081.2017081971

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (2): 503-508.DOI: 10.11772/j.issn.1001-9081.2017081971

Previous Articles Next Articles

Service function chain construction method based on node utility maximization

ZHANG Chuanhao^1,2, ZHOU Qiao²

1. Police Technology Department, Railway Police College, Zhengzhou Henan 450053, China;
2. China National Digital Switching System Engineering & Technological R & D Center, Zhengzhou Henan 450002, China

Received:2017-08-15 Revised:2017-10-13 Online:2018-02-10 Published:2018-02-10
Supported by:
This work is partially supported by the National Basic Research Program of China (2012CB315901), the Technology Research Project of Chinese Ministry of Public Security (2016JSYJB38), the Foundation of Henan Science and Technology Department (172102210441).

节点效用最大化的服务功能链构建方法

张传浩^1,2, 周桥²

1. 铁道警察学院公安技术系, 郑州 450053;
2. 国家数字交换系统工程技术研究中心, 郑州 450002

通讯作者: 张传浩
作者简介:张传浩(1979-),男,河南郑州人,讲师,博士,CCF会员,主要研究方向:网络信息安全、网络功能虚拟化;周桥(1993-),男,湖北钟祥人,硕士,主要研究方向:网络功能虚拟化、服务功能链。
基金资助:
国家973计划项目（2012CB315901）；公安部技术研究计划项目（2016JSYJB38）；河南省科技厅基金项目（172102210441）。

Abstract

Abstract: Networks heavily rely on middlebox to provide critical service functions, with the development of Software Defined Network (SDN) and Network Function Virtualization (NFV) technology, how to use the new technology to deploy middleboxs and guide flow through a specific sequence of middleboxs to complete the service function chain is still a problem to be solved. A construction method based on the optimal node utility maximization, namely NUM (Node Utility Maximization), was proposed for the service function chain construction problem, which took into account the deployment and steering of the virtual middleboxs in the meantime. Firstly, a service function chain collaborative construction mechanism was designed based on SDN+NFV technology. Secondly, the node selection model and the utility maximization model were introduced in this mechanism, according to the solution of middleware box deployment and traffic guidance problem. Finally, the model was solved by applying Tabu search-combined simulated annealing algorithm. The simulation results show that the proposed method NUM is superior to the traditional algorithm in terms of construction time, success rate and network congestion rate, and the utility of the nodes is improved by about 20% by using the proposed service function chain construction method.

Key words: Software Defined Network (SDN), Network Function Virtualization (NFV), middlebox, service function chain construction, Simulated Annealing (SA)

摘要： 网络严重依赖中间件盒子来提供关键的服务功能，随着软件定义网络（SDN）与网络功能虚拟化（NFV）技术的发展，如何利用新技术部署中间件盒子并引导流量通过特定顺序的中间件盒子完成服务功能链构建成为亟待解决的问题。针对SDN+NFV环境下的服务功能链构建问题，提出一种节点效用最大化的服务功能链协同构建方法NUM（Node Utility Maximization）。首先结合SDN+NFV技术设计了一种服务功能链协同构建机制；其次，根据机制中资源处理器所解决的中间件盒子部署和流量引导问题，建立了节点选择模型和效用最大化模型；最后，利用禁忌搜索改进组合模拟退火算法对该模型进行求解。仿真实验表明，NUM方法与主流方法相比在构建时间、构建成功率以及网络拥塞率上具有优越性，同时采用所提出的服务链构建方法在节点效用上提高约20%。

关键词: 软件定义网络, 网络功能虚拟化, 中间件盒子, 服务功能链构建, 模拟退火

CLC Number:

TP393.02

ZHANG Chuanhao, ZHOU Qiao. Service function chain construction method based on node utility maximization[J]. Journal of Computer Applications, 2018, 38(2): 503-508.

张传浩, 周桥. 节点效用最大化的服务功能链构建方法[J]. 计算机应用, 2018, 38(2): 503-508.

References

[1] GEMBER A, PRABHU P, GHADIYALI Z, et al. Toward software-defined middlebox networking[C]//HotNets-XI:Proceedings of the 201211th ACM Workshop on Hot Topics in Networks. New York:ACM, 2012:7-12.
[2] SHERRY J, HASAN S, SCOTT C, et al. Making middleboxes someone else's problem:network processing as a cloud service[J]. ACM SIGCOMM Computer Communication Review-Special October issue SIGCOMM'12, 2012, 42(4):13-24.
[3] McKEOWN N. Software-defined networking[J]. INFOCOM Keynote Talk, 2009, 17(2):30-32.
[4] CARAPINHA J, JIMÉNEZ J. Network virtualization:a view from the bottom[C]//VISA'09:Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. New York:ACM, 2009:73-80.
[5] ZHANG Y, BEHESHTI N, BELIVEAU L, et al. StEERING:a software-defined networking for inline service chaining[C]//ICNP 2013:Proceedings of the 201321st IEEE International Conference on Network Protocols. Piscataway, NJ:IEEE, 2013:1-10.
[6] QAZI Z A, TU C-C, CHIANG L, et al. SIMPLE-fying middlebox policy enforcement using SDN[C]//SIGCOMM'13:Proceedings of the ACM SIGCOMM 2013 Computer Communication. New York:ACM, 2013:27-38.
[7] FAYAZBAKHSH S K, SEKAR V, YU M, et al. FlowTags:enforcing network-wide policies in the presence of dynamic middlebox actions[C]//HotSDN'13:Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York:ACM, 2013:19-24.
[8] SEKAR V, EGI N, RATNASAMY S, et al. Design and implementation of a consolidated middlebox architecture[C]//NSDI'12:Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2012:24.
[9] MARTINS J, AHMED M, RAICIU C, et al. ClickOS and the art of network function virtualization[C]//NSDI'14:Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2014:459-473.
[10] GEMBER-JACOBSON A, VISWANATHAN R, PRAKASH C, et al. OpenNF:Enabling innovation in network function control[C]//SIGCOMM'14:Proceedings of the 2014 ACM Conference on SIGCOMM. New York:ACM, 2014:163-174.
[11] ANWER B, BENSON T, FEAMSTER N, et al. A slick control plane for network middleboxes[C]//HotSDN'13:Proceedings of the Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York:ACM, 2013:147-148.
[12] ANWER B, BENSON T, FEAMSTER N, et al. Programming slick network functions[C]//SOSR'15:Proceedings of the 1st ACM SIGCOMM Symposium on Software Defined Networking Research. New York:ACM, 2015:Article No. 14.
[13] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598):671-680.
[14] GLOVER F, LAGUNA M. Tabu search[M]//Metaheuristic Procedures for Training Neutral Networks. Boston:Springer, 1993:53-69.
[15] 秦进,倪玲霖,缪立新.多级多商品流物流网络设计的优化模型与组合模拟退火算法[J].计算机应用研究,2010,27(9):3348-3351. (QIN J, NI L L, MIU L X. Optimization model and combined simulated annealing algorithm for multi-level multi-commodity logistics network design[J]. Application Research of Computers, 2010, 27(9):3348-3351.)
[16] LIN Y, BIAN Z, LIU X. Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing Tabu search algorithm to solve the symmetrical traveling salesman problem[J]. Applied Soft Computing, 2016, 49(C):937-952.
[17] METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al. Equation of state calculations by fast computing machines[J]. The Journal of Chemical Physics, 1953, 21(6):1087-1092.
[18] ZEGURA E W, CALVERT K L, ACHARJEE S B. How to model an internetwork[C]//INFOCOM'96:Proceedings of the Fifteenth Annual Joint Conference of the IEEE Computer Societies on Networking the Next Generation. Washington, DC:IEEE Computer Society, 1996, 2:594-602.

Service function chain construction method based on node utility maximization

节点效用最大化的服务功能链构建方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	XU Hongliang, YANG Guiqin, JIANG Zhanjun. Data center adaptive multi-path load balancing algorithm based on software defined network [J]. Journal of Computer Applications, 2021, 41(4): 1160-1164.
[2]	FAN Xiaomao, XIONG Honglin, ZHAO Gansen. Cleaning scheduling model with constraints and its solution [J]. Journal of Computer Applications, 2021, 41(2): 577-582.
[3]	ZENG Minghua, QUAN Ke. Improved hybrid cuckoo search-based quantum-behaved particle swarm optimization algorithm for bi-level programming [J]. Journal of Computer Applications, 2020, 40(7): 1908-1912.
[4]	ZHU Mengdi, SHU Yong’an. Verification of control-data plane consistency in software defined network [J]. Journal of Computer Applications, 2020, 40(6): 1751-1754.
[5]	XIANG Xiong, TIAN Jian. P2P transmission scheduling optimization based on software defined network [J]. Journal of Computer Applications, 2020, 40(3): 777-782.
[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]	CHI Yaping, MO Chongwei, YANG Yintan, CHEN Chunxia. Design and implementation of intrusion detection model for software defined network architecture [J]. Journal of Computer Applications, 2020, 40(1): 116-122.
[8]	ZHU Jie, ZHANG Wenyi, XUE Fei. Storage location assignment optimization of stereoscopic warehouse based on genetic simulated annealing algorithm [J]. Journal of Computer Applications, 2020, 40(1): 284-291.
[9]	SONG Ting, CHEN Mao, WU Chao, ZHANG Gongzhao. Automated course arrangement algorithm based on multi-class iterated local search [J]. Journal of Computer Applications, 2019, 39(6): 1760-1765.
[10]	JIA Mengyao, WANG Xingwei, ZHANG Shuang, YI Bo, HUANG Min. Software defined network based fault tolerant routing mechanism for satellite networks [J]. Journal of Computer Applications, 2019, 39(6): 1772-1779.
[11]	LI Zhaobin, LIU Zeyi, WEI Zhanzhen, HAN Yu. Software defined network path security based on Hash chain [J]. Journal of Computer Applications, 2019, 39(5): 1368-1373.
[12]	ZOU Chengming, LIU Panwen, TANG Xing. Real-time defence against dynamic host configuration protocol flood attack in software defined network [J]. Journal of Computer Applications, 2019, 39(4): 1066-1072.
[13]	FAN Hongwei, HU Yuxiang, LAN Julong. Two-stage hardware acceleration resource deployment mechanism for virtual network function [J]. Journal of Computer Applications, 2018, 38(9): 2575-2580.
[14]	LI Zhaobin, LI Weilong, WEI Zhanzhen, LIU Mengtian. Research and implementation of key module of data security processing mechanism in software defined network [J]. Journal of Computer Applications, 2018, 38(7): 1929-1935.
[15]	FAN Zifu, ZHOU Kaiheng, YAO Jie. Game theory based SDN master controller reselection mechanism [J]. Journal of Computer Applications, 2018, 38(3): 776-779.