Giải thuật di truyền giải bài toán tối ưu đặt và định tuyến trong mạng ảo hóa.
Genetic algorithm for optimizing the Virtual Network Functions Placement and Routing Problem.
Abstract
Recently, the Internet infrastructure is constantly being improved to meet the increasing needs of users. Installing hardware devices in the network server center faces many limitations such as: difficulty in replacing devices; large investment and operating costs,... Network Function Virtualization (NFV) technology was invented to overcome the disadvantages. Specialized hardware will be replaced by software running in visualized environments in this technology. Resource allocation is an important problem in NFV. Reasonable resource allocation can increase service quality and reduce network deployment costs. Optimizing resource allocation can be accomplished through placing virtual network functions (VNFs) on servers and finding appropriate routing for network services. This research explores the network resource allocation to achieve two objectives: i) reduce deployment costs; ii) reduce the delay of the service chain in the network. We transfer the multi-objective problem to single-objective problem (SO-VPTR) by the weighted-sum approach. This research proposes a mixed-integer linear programming (MILP) model to solve the single-objective optimization problem. The MILP model can provide accurate solutions for small datasets. In order to find solutions for larger sized datasets, the research proposes a genetic algorithm to solve the problem. The experimental results on different datasets demonstrated the effectiveness of the proposed algorithm.
References
Q. Zhang, Q. Zhu, M. F. Zhani, R. Boutaba, and J. L. Hellerstein, “Dynamic service placement in geographically
distributed clouds,” IEEE Journal on Selected Areas in Communications, vol. 31, no. 12, pp. 762–772, 2013.
J. W. Jiang, T. Lan, S. Ha, M. Chen, and M. Chiang, “Joint vm placement and routing for data center traffic
engineering,” in 2012 Proceedings IEEE INFOCOM. IEEE, 2012, pp. 2876–2880.
S. Yang, P. Wieder, R. Yahyapour, S. Trajanovski, and X. Fu, “Reliable virtual machine placement and routing in clouds,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 10, pp. 2965–2978, 2017.
W. Ma, O. Sandoval, J. Beltran, D. Pan, and N. Pissinou, “Traffic aware placement of interdependent nfv middleboxes,” in IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE, 2017, pp. 1–9.
R. Cohen, L. Lewin-Eytan, J. S. Naor, and D. Raz, “Near optimal placement of virtual network functions,” in 2015
IEEE Conference on Computer Communications (INFOCOM). IEEE, 2015, pp. 1346–1354.
M. Ghaznavi, N. Shahriar, S. Kamali, R. Ahmed, and R. Boutaba, “Distributed service function chaining,” IEEE
Journal on Selected Areas in Communications, vol. 35, no. 11, pp. 2479–2489, 2017.
B. Spinnewyn, P. H. Isolani, C. Donato, J. F. Botero, and S. Latré, “Coordinated service composition and embedding of 5g location-constrained network functions,” IEEE Transactions on Network and Service Management, vol. 15, no. 4, pp. 1488–1502, 2018.
A. Murray, A. Arulselvan, M. Roper, M. Cashmore, S. K. Mohalik, I. Burdick, and S. David, “The cost of quality
of service: Sla aware vnf placement and routing using column generation,” in 2023 13th International Workshop on Resilient Networks Design and Modeling (RNDM). IEEE, 2023, pp. 1–8.
M. Golkarifard, C. F. Chiasserini, F. Malandrino, and A. Movaghar, “Dynamic vnf placement, resource allocation
and traffic routing in 5g,” Computer Networks, vol. 188, pp. 107830, 2021.
T.-W. Kuo, B.-H. Liou, K. C.-J. Lin, and M.-J. Tsai, “Deploying chains of virtual network functions: On the relation
between link and server usage,” IEEE/ACM Transactions On Networking, vol. 26, no. 4, pp. 1562–1576, 2018.
H. Feng, J. Llorca, A. M. Tulino, D. Raz, and A. F. Molisch, “Approximation algorithms for the nfv service distribution problem,” in IEEE INFOCOM 2017-IEEE Conference on Computer Communications. IEEE, 2017, pp. 1–9.
C. You et al., “Efficient load balancing for the vnf deployment with placement constraints,” in ICC 2019-2019 IEEE International Conference on Communications (ICC). IEEE, 2019, pp. 1–6.
C. Pham, N. H. Tran, S. Ren, W. Saad, and C. S. Hong, “Traffic-aware and energy-efficient vnf placement for service chaining: Joint sampling and matching approach,” IEEE Transactions on Services Computing, vol. 13, no. 1, pp. 172–185, 2017.
T. Wang, H. Xu, and F. Liu, “Multi-resource load balancing for virtual network functions,” in 2017 IEEE 37th
International Conference on Distributed Computing Systems (ICDCS). IEEE, 2017, pp. 1322–1332.
G. Sallam, G. R. Gupta, B. Li, and B. Ji, “Shortest path and maximum flow problems under service function chaining constraints,” in IEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 2018, pp. 2132–2140.
Z. Xu, W. Liang, M. Huang, M. Jia, S. Guo, and A. Galis, “Approximation and online algorithms for nfv-enabled multicasting in sdns,” in 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2017, pp. 625–634.
L. Qu, C. Assi, and K. Shaban, “Delay-aware scheduling and resource optimization with network function virtualization,” IEEE Transactions on communications, vol. 64, no. 9, pp. 3746–3758, 2016.
Z. Zhang, Z. Li, C. Wu, and C. Huang, “A scalable and distributed approach for nfv service chain cost minimization,” in 2017 IEEE 37th international conference on distributed computing systems (ICDCS). IEEE, 2017, pp. 2151–2156.
Q. Li, Y. Jiang, P. Duan, M. Xu, and X. Xiao, “Quokka: Latency-aware middlebox scheduling with dynamic resource allocation,” Journal of Network and Computer Applications, vol. 78, pp. 253–266, 2017.
A. Dwaraki and T. Wolf, “Adaptive service-chain routing for virtual network functions in software-defined networks,” in Proceedings of the 2016 workshop on Hot topics in Middleboxes and Network Function Virtualization, 2016, pp. 32–37.
J. Pei, P. Hong, K. Xue, and D. Li, “Efficiently embedding service function chains with dynamic virtual network
function placement in geo-distributed cloud system,” IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 10, pp. 2179–2192, 2018.
K. Xie, X. Zhou, T. Semong, and S. He, “Multi-source multicast routing with qos constraints in network function virtualization,” in ICC 2019-2019 IEEE International Conference on Communications (ICC). IEEE, 2019, pp. 1–6.
H. Chen, X. Wang, Y. Zhao, T. Song, Y. Wang, S. Xu, and L. Li, “Mosc: A method to assign the outsourcing of service function chain across multiple clouds,” Computer Networks, vol. 133, pp. 166–182, 2018.
S. Agarwal, F. Malandrino, C.-F. Chiasserini, and S. De, “Joint vnf placement and cpu allocation in 5g,” in IEEE
INFOCOM 2018-IEEE conference on computer communications. IEEE, 2018, pp. 1943–1951.