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

Tóm tắt

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