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.

  • Lê Đăng Nguyên Trường Đại học Hải Phòng, Hải Phòng, Việt Nam
  • Trần Bá Tuấn Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Hà Nội, Việt Nam
  • Nguyễn Thị Tâm Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Hà Nội, Việt Nam
  • Lê Trọng Vĩnh Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Hà Nội, Việt Nam
Keywords: network function virtualization, genetic algorithm, resource allocation

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.

Author Biographies

Lê Đăng Nguyên, Trường Đại học Hải Phòng, Hải Phòng, Việt Nam

Lê Đăng Nguyên tốt nghiệp Đại học năm 1996 tại Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, chuyên ngành Tin học, Thạc sĩ năm 2005 tại Trường Đại học Công nghệ, ĐHQGHN chuyên ngành Công nghệ phần mềm, Tiến sĩ năm 2016 tại Trường Đại học Khoa học Tự nhiên, ĐHQGHN, chuyên ngành Cơ sở Toán học cho Tin học. Hiện là giảng viên chính tại Khoa Công nghệ Thông tin, Trường Đại học Hải Phòng. Hướng nghiên cứu chính: thuật toán tiến hóa giải các bài toán tối ưu tổ hợp.

Trần Bá Tuấn, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Hà Nội, Việt Nam

Trần Bá Tuấn Nhận bằng Cử nhân ngành Máy tính và khoa học thông tin tại Trường Đại học Khoa học Tự nhiên vào năm 2022, hiện đang công tác tại Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQGHN. Hướng nghiên cứu chủ yếu bao gồm Khoa học máy tính, Trí tuệ nhân tạo.

Nguyễn Thị Tâm, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Hà Nội, Việt Nam

Nguyễn Thị Tâm tốt nghiệp Thạc sĩ chuyên ngành Cơ sở toán cho tin học tại Đại học Khoa học Tự nhiên vào năm 2015. Tiến sĩ chuyên ngành Khoa học máy tính tại Đại học Bách khoa Hà Nội vào năm 2022. Hiện là đang là giảng viên tại Trường Đại học Khoa học Tự nhiên, ĐHQGHN. Hướng nghiên cứu chính: Computational
Intelligence, Artificial Intelligence, và Memetic Computing.

Lê Trọng Vĩnh, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Hà Nội, Việt Nam

Lê Trọng Vĩnh tốt nghiệp Đại học năm 1994 tại trường Đại học Tổng hợp Hà Nội, chuyên ngành Tin học, Thạc sĩ năm 1997 tại trường ĐH KHTN, ĐHQG Hà Nội chuyên ngành Đảm bảo Toán học cho Máy tính và các Hệ thống tính toán, Tiến sĩ năm 2006 tại Viện Khoa học và Công nghệ Tiên tiến Nhật Bản chuyên ngành Công nghệ Thông tin. Được phong Phó Giáo sư năm 2012. Hiện là giảng viên cao cấp tại Khoa Toán - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQGHN. Hướng nghiên cứu chính là các thuật toán tiến hóa giải các bài toán tối ưu tổ hợp, đặc biệt là các bài toán liên quan đến mạng máy tính.

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.

Published
2024-11-25