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
Ngày nay, hạ tầng mạng Internet không ngừng được cải thiện để đáp ứng nhu cầu sử dụng ngày càng cao của người dùng. Việc lắp đặt các thiết bị phần cứng trong trung tâm máy chủ của mạng gặp phải nhiều hạn chế như: khó thay thế thiết bị; chi phí đầu tư, vận hành lớn,... Công nghệ ảo hóa các chức năng mạng (Network Function Virtualization - NFV) ra đời đã khắc phục các nhược điểm nêu trên. Trong công nghệ này, các phần cứng chuyên dụng sẽ được triển khai thay thế bằng các phần mềm chạy trong môi trường ảo hoá. Phân bổ tài nguyên là một vấn đề quan trọng trong NFV. Việc phân bổ tài nguyên hợp lý có thể giúp tăng chất lượng dịch vụ và giảm chi phí triển khai. Tối ưu việc phân bổ tài nguyên có thể được thực hiện thông qua việc đặt các chức năng mạng ảo (VNF) trên các máy chủ và tìm đường định tuyến hợp lý cho các dịch vụ mạng. Bài báo này nghiên cứu bài toán đặt các chức năng mạng ảo và định tuyến cho các chuỗi dịch vụ để đáp ứng hai mục tiêu: i) giảm chi phí triển khai; ii) giảm độ trễ của các chuỗi dịch vụ. Tối ưu đa mục tiêu được chuyển về tối ưu đơn mục tiêu (SO-VPTR) bằng cách tiếp cận tổng có trọng số. Nghiên cứu đề xuất mô hình quy hoạch tuyến tính nguyên hỗn hợp (MILP) để giải tối ưu hoá đơn mục tiêu này. Mô hình MILP có thể đưa ra lời giải chính xác cho các bộ dữ liệu có kích thước nhỏ. Để tìm lời giải cho các bộ dữ liệu có kích thước lớn hơn, nghiên cứu đề xuất thuật toán di truyền để giải bài toán. Kết quả thực nghiệm trên các bộ dữ liệu khác nhau đã chứng minh hiệu quả của thuật toán đề xuất.
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.
