| Citation: | Yu LU, Yicen LIU, Xi LI, Xingkai CHEN, Wenxin QIAO, Liyun CHEN. Research on Placement Algorithm of Service Function Chaining Oriented to Software Defined Networking[J]. Journal of Electronics & Information Technology, 2019, 41(1): 74-82. doi: 10.11999/JEIT180264
|
For Network Function Virtualization (NFV) environment, the existing placement methods can not guarantee the mapping cost while optimizing the network delay, a service function chaining optimal placement algorithm is proposed based on the IQGA-Viterbi learning algorithm. In the training process of Hidden Markov Model (HMM) parameters, the traditional Baum-Welch algorithm is easy to fall into the local optimum, so the quantum genetic algorithm is proposed, which can better optimize the model parameters. In each iteration, the improved algorithm maintains the diversity of feasible solutions and expands the scope of the spatial search by replicating the best fitness population with equal proportion, thus improving the accuracy of the model parameters. In the process of solving Hidden Markov chain, to overcome the problem that can not be directly observed for hidden sequences, Viterbi algorithm can solve the implicit sequences exactly and solve the problem of optimal service paths in the directed graph. Experimental results show that the network delay and mapping costs are lower compared with the existing algorithms. In addition, the acceptance ratio of requests is raised.
|
BHAMARE D, JAIN R, SAMAKA M, et al. A survey on service function chaining[J]. Journal of Network & Computer Applications, 2016, 75(C): 138–155. doi: 10.1016/j.jnca.2016.09.001
|
|
MEDHAT A and TALEB T. Service function chaining in next generation networks: State of the art and research challenges[J]. IEEE Communications Magazine, 2017, 55(2): 216–223. doi: 10.1109/mcom.2016.1600219rp
|
|
MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: Enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69–75. doi: 10.1145/1355734
|
|
HAN Bo, GOPALAKRISHNAN V, JI Lusheng, et al. Network function virtualization: Challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90–97. doi: 10.1109/mcom.2015.7045396
|
|
KIM S, PARK S, KIM Y, et al. VNF-EQ: Dynamic placement of virtual network functions for energy efficiency and QoS guarantee in NFV[J]. Cluster Computing, 2017, 20(3): 1–11. doi: 10.1007/s10586-017-1004-3
|
|
BHAMARE D, SAMAKA M, ERBAD A, et al. Optimal virtual network function placement in multi-cloud service chaining architecture[J]. Computer Communications, 2017, 102(C): 1–16. doi: 10.1016/j.comcom.2017.02.011
|
|
BARI M F, CHOWDHURY S R, AHMED R, et al. On orchestrating virtual network functions[C]. International Conference on Network and Service Management, Barcelona, Spain, 2015: 50–56. doi: 10.1109/cnsm.2015.7367338.
|
|
XIONG Gang, Hu Yuxiang, TIAN Le, et al. A virtual service placement approach based on improved quantum genetic algorithm[J]. Information and Electronic Engineering Frontiers, 2016, 17(7): 661–671. doi: 10.1631/fitee.1500494
|
|
LUKOVSZKI T, ROST M, and SCHMID S. It’s a match!: Near-optimal and incremental middlebox deployment[J]. ACM SIGCOMM Computer Communication Review, 2016, 46(1): 30–36. doi: 10.1145/2875951.2875956
|
|
MOENS H and TURCK F. VNF-P: A model for efficient placement of virtualized network functions[C]. International Conference on Network and Service Management, Beijing, China, 2014: 418–423. doi: 10.1109/cnsm.2014.701.
|
|
ZHANG Lijun, HERMANS H, and JANSEN D. Logic and model checking for Hidden Markov Models[C]. International Conference on Formal Techniques for Networked and Distributed Systems, Berlin, Germany, 2005: 98–112. doi: 10.1007/11562436_9.
|
|
ZHANG Zengyin, YUAN Changan, HU Jianjun, et al. HMM training method based on GEP and Baum-Welch algorithms[J]. Computer Engineering & Design, 2010, 31(9): 2027–2029.
|
|
XIONG Yan, CHEN Huanhuan, MIAO Fuyou, et al. A quantum genetic algorithm to solve combinatorial optimization problem[J]. Acta Electronica Sinica, 2004, 32(11): 1855–1858.
|
|
BOULOUTAS A, HART G W, and SCHWARTZ M. Two extensions of the Viterbi algorithm[J]. IEEE Transactions on Information Theory, 2002, 37(2): 430–436. doi: 10.1109/18.75270
|
|
ZHANG Lifang and ZHANG Xiping. Network traffic prediction based on BP neural networks optimized by quantum genetic algorithm[J]. Computer Engineering & Science, 2016, 10(3): 12–20.
|
|
ZHANG Ying, BEHESHTI N, BELIVEAU L, et al. StEERING: A software-defined networking for inline service chaining[C]. IEEE International Conference on Network Protocols, Raleigh, USA, 2014: 1–10. doi: 10.1109/icnp.2013.673.
|
|
BASTA A, HOFFMANN K, HOFFMANN K, et al. Applying NFV and SDN to LTE mobile core gateways, the functions placement problem[C]. The Workshop on All Things Cellular: Operations, Chicago, USA, 2014: 33–38. doi: 10.1145/2627585.2627592.
|
|
刘彩霞, 卢干强, 汤红波, 等. 一种基于Viterbi算法的虚拟网络功能自适应部署方法[J]. 电子与信息学报, 2016, 38(11): 2922–2930. doi: 10.11999/JEIT1650507
LIU Caixia, LU Ganqiang, TANG Hongbo, et al. Adaptive deployment method for virtualized network function based on Viterbi algorithm[J]. Journal of Electronics &Information Technology, 2016, 38(11): 2922–2930. doi: 10.11999/JEIT1650507
|
|
ZEGURA E, CALVERT K, and BHATTACHARJEE S. How to model an Internetwork[J]. Proceedings of IEEE Infocom, 1996, 2: 594–601. doi: 10.1109/infcom.1996.493353
|
|
ORLOWSKI S, WESSALY R, PIORO M, et al. SNDlib 1.0-survivable network design library[J]. Networks, 2010, 55(3): 276–286. doi: 10.1002/net.20371
|
|
CLAYMAN S, MAINI E, GALIS A, et al. The dynamic placement of virtual network functions[C]. Network Operations and Management Symposium, Seoul, Korea, 2014: 1–9. doi: 10.1109/noms.2014.6838412.
|
|
SAHHAF S, TAVERNIER W, ROST M, et al. Network service chaining with optimized network function embedding supporting service decompositions[J]. Computer Networks the International Journal of Computer & Telecommunications Networking, 2015, 93(P3): 492–505. doi: 10.1016/j.comnet.2015.09.035
|
Figures(10) / Tables(2)
DownLoad:
