Đề tài Ứng dụng GA trong bài toán định tuyến đường tối ưu cho một SFC request

Ứng dụng GA trong bài toán định tuyến đường tối ưu cho một SFC request Báo cáo Sinh viện thực hiện: Trần Anh Vũ – MSSV: 20183674 Giảng viên hướng dẫn: PGS.TS Huỳnh Thị Thanh Bình 1 Giới thiệu 2 Bài toán 3 Đề xuất phương án 4 Kết quả thực nghiệm 5 Kết luận 1 Giới thiệu 1 Giới thiệu 1.1 Giới thiệu Sự phát triển của điện toán đám mây cộng với công nghệ thực tế ảo => Mở rộng mô hình mạng 1 Giới thiệu 1.1 Giới thiệu Trong mô hình cung cấp dịch vụ mạng truyền thống, các Network function (Firewall, Load Balancer, ) được lắp đặt thủ công =>Tốn kém chi phí vận hành và lắp đặt hệ thống 1 Giới thiệu 1.1 Giới thiệu Giải pháp: Vận hành các Network function trong môi trường ảo =>Linh hoạt trong việc lắp đặt và bảo trì 1 Giới thiệu 1.1 Giới thiệu Trong môi trường ảo, các network function (hay virtual network function – VNF) được xếp theo trình tự xác định tạo nên chuỗi dịch vụ (Service function chaining –SFC) 1 Giới thiệu 1.1. Giới thiệu Vấn đề đặt ra: Phân phối tài nguyên vận hành các SFC request =>Sinh ra bài toán VPTR (VNF Placement and Traffic Routing) và các biến thể: VNFP (VNF Placement) TRR (TRaffic Routing) VRC (VNF Redeployment and Consolidation) 1 Giới thiệu 1.2 Tài liệu tham khảo -S. Yang, F. Li, S. Traianovski, R. Yahyapour and X. Fu, “Recent Advances of Resource Allocation in Network Function Virtualization”, IEEE Trans. Parallel Distrib. Syst., vol. 32, no. 2, pp. 295–314, Feb. 2021. Link: https://tstojan.github.io/pub/IEEE_TPDS2020_resource_aloc_nfv_survey.pdf -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 Trans. Parallel Distrib. Syst., vol. 30, no. 10, pp. 2179–2192, Oct. 2019. Link: 2 Bài toán 2 Bài toán 2.1 Tóm tắt bài toán Cho một mô hình mạng đã biết sẵn: Tài nguyên bang thông còn lại trên các liên kết Tài nguyên bộ nhớ còn lại trên các node Tài nguyên CPU trên các VNF instance đã đặt sẵn tại các node cùng với số lượng và chủng loại của các VNF instance Cho biết thông tin một SFC request(Điểm bắt đầu, kết thúc, danh sách các VNF yêu cầu, ) Yêu cầu định tuyến cho SFC request trên (Có thể có đặt thêm VNF instance) sao cho tối thiểu hóa chi phí vận hành và chi phí đặt 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán Cho Mạng G(V, L) trong đó V: tập các đỉnh L: tập các liên kết 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán Các thông số trên một liên kết : : Băng thông tối đa (Bandwidth Capacity) của liên kết uv : Tỉ lệ băng thông còn lại của liên kết uv trước khi thêm SFC request i Ví dụ: liên kết 24 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán Trong tập đỉnh V có 2 loại tập đỉnh con: MDC node: Các đỉnh có thể đặt được VNF ( - thể hiện bằng màu đỏ) Switch node: Các đỉnh không đặt được VNF ( - thể hiện bằng màu đen) 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán Các thông số của 2 loại đỉnh: Switch node: Nếu : Bộ nhớ tối đa của switch node u : Tỉ lệ bộ nhớ còn lại của switch node u trước khi thêm SFC request i MDC node: Nếu : Số lượng thực thể VNF tối đa mà MDC node u có thể đặt được = 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán Thực thể VNF (VNF instance): là các VNF được đặt trên các MDC node Mỗi thực thể sẽ thuộc một loại VNF nhất định ( : VNF loại , K: Tập các loại VNF) VD: Thực thể VNF thuộc loại Trên MDC node có thể đặt nhiều thực thể cùng loại VD: MDC node 11 có thể đặt các thực thể VNF thuộc VNF loại a và VNF thuộc VNF loại b , 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán Các thông số của thực thể VNF: Nếu ta có thực thể VNF (Trong đó M là tập hợp các thực thể VNF có thể đặt trên các MDC node ) : Tài nguyên CPU tối đa (CPU Capacity) của thực thể VNF m : Tỉ lệ CPU còn lại của của thực thể VNF m trước khi thêm SFC request i 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán 1 SFC request i được thể hiện qua bộ tham số: : Ingress node : Egress node : Yêu cầu băng thông : Yêu cầu bộ nhớ : Yêu cầu CPU : Yêu cầu thời gian trễ tối đa của request (Không cần thiết do bài toán chỉ 1 SFC request) : Tập các yêu cầu VNF (đã xếp theo thứ tự) 2 Bài toán 2.2 Mô tả bài toán 2.2.1 Đầu vào bài toán Ví dụ một SFC request = 0 = 13 = 10 = 10 = 10 Danh sách các VNF instance trên các MDC node , , , 2 Bài toán 2.2 Mô tả bài toán 2.2.2 Rằng buộc bài toán Giả sử ứng với 1 SFC request i, ta định được một hành trình thể hiện bằng một đồ thị : Tập các đỉnh mà hành trình đi qua : Tập các cạnh mà hành trình đi qua Ví dụ: đường tô vàng ở hình dưới 2 Bài toán 2.2 Mô tả bài toán 2.2.2 Rằng buộc bài toán Các biến nhị phân: : Hành trình định được có đi qua cạnh uv không? : Hành trình định được có đi qua node u không? : Hành trình định được có sử dụng VNF instance m tại node không? Kết quả của các biến nhị phân: 0: không; 1: có 2 Bài toán 2.2 Mô tả bài toán 2.2.2 Rằng buộc bài toán Khi một SFC request i được định tuyến, nó phải thỏa mãn các điều kiện về lượng băng thông trên các liên kết, bộ nhớ trên các node switch và tài nguyên của CPU trên các VNF instance như sau: 2 Bài toán 2.2 Mô tả bài toán 2.2.2 Rằng buộc bài toán Phân phối VNF instance sao cho số lượng instance đặt tại 1 MDC node u không được vượt quá khả năng đặt của node u đó Trong đó: : Thực thể VNF m đã đặt tại node u chưa : Thực thể VNF m đã có sẵn tại node u sau khi định được tuyến đường chưa 2 Bài toán 2.2 Mô tả bài toán 2.2.2 Rằng buộc bài toán 1 VNF request trong 1 SFC request chỉ được phục vụ bởi 1 VNF instance Trường hợp không hợp lệ do SFC request (đường màu cam) đi qua VNF instance a1 2 lần Trường hợp hợp lệ 2 Bài toán 2.2 Mô tả bài toán 2.2.3 Hàm mục tiêu Chi phí băng thông của liên kết uv, bộ nhớ của node u và tài nguyên CPU của thực thể VNF m sau khi định được 1 tuyến đường cho SFC request i : Tập hợp các thực thể VNF cùng loại với thực thực thể VNF m 2 Bài toán 2.2 Mô tả bài toán 2.2.3 Hàm mục tiêu Tổng chi phí băng thông, bộ nhớ và CPU sau khi định được tuyến đường cho SFC request i: Trong đó: : Thực thể VNF m đã có sẵn tại node u sau khi định được tuyến đường chưa : Thực thể VNF m đã có sẵn tại node u trước khi định được tuyến đường chưa : Thực thể VNF m có thuộc loại k không :Chi phí đặt thực thể VNF loại k 2 Bài toán 2.2 Mô tả bài toán 2.2.3 Hàm mục tiêu Chi phí đặt thêm các thực thể VNF để nhúng các SFC request i: 2 Bài toán 2.2 Mô tả bài toán 2.2.3 Hàm mục tiêu Hàm mục tiêu: Tối thiểu hóa chi phí băng thông, bộ nhớ và CPU trên hành trình định tuyến và chi phí đặt thêm các thực thể VNF 3 Đề xuất phương án 3 Đề xuất phương án Khởi tạo quần thể Lai ghép Đánh giá cá thể trong quần thể Đột biến Chọn lọc cá thể để tạo quần thể mới Đánh giá, hiển thị kết quả tốt nhất Chọn lọc cá thể để lai ghép và đột biến Nếu số generation chưa đạt đủ điều kiện Nếu số generation đạt đủ điều kiện Sử dụng GA để giải quyết bài toán Giả sử có một SFC request biết , , 3 Đề xuất phương án 3.1 Khởi tạo quần thể 1 cá thể sẽ là tuyến đường đi từ đến và đi qua các node MDC chứa các thực thể VNF thuộc 3 Đề xuất phương án 3.1 Khởi tạo quần thể Các bước khởi tạo một cá thể Bước 1: Chọn các điểm MDC node ngẫu nhiên trong tập (Có thể trùng nhau) Giả sử các MDC node được chọn lần lượt là MDC node 1, MDC node 2, ,MDC node k Ingress node MDC Node 2 MDC Node 1 Egress node MDC Node k 1 3 5 Si Q1 Q2 Qk Ti Bước 2: Định ra các hành trình giữa Ingress và MDC node 1, giữa các MDC kề nhau và giữa Egress và MDC node 2 (Các hành trình không có điểm nào trùng nhau) 3 Đề xuất phương án 3.2 Đánh giá cá thể Chi phí băng thông, bộ nhớ và CPU của 1 hành trình 0 2 6 7 3 2 5 4 8 3 6 5 4 Ingress Egress VNFa VNFb Chi phí đặt thêm các thực thể VNF trên các MDC node (Nếu có) 3 Đề xuất phương án 3.2 Đánh giá cá thể Do có thể tồn tại các cá thể không hợp lệ => Hàm phạt + + Nremain ) Trong đó: Nremain : Số VNF instance đã có sẵn trên MDC node u N: Số VNF đặt thêm trên MDC node u => Fitness = 1/(P+D+R) 3 Đề xuất phương án 3.3 Lai ghép 0 2 6 7 3 2 5 4 8 3 6 5 4 Ingress Egress VNFa VNFb 0 14 11 12 2 11 9 12 4 3 15 17 18 Ingress Egress VNFa VNFb Cha Mẹ Lai ghép theo điểm cắt Ví dụ: Giả sử có 2 cá thể cha mẹ như hình dưới 0 2 6 7 3 2 6 4 8 3 6 5 4 Ingress Egress VNFa VNFb 0 14 11 12 2 11 9 12 4 3 15 17 18 Ingress Egress VNFa VNFb Cha Mẹ 3 Đề xuất phương án 3.3 Lai ghép Bước 1:Tìm điểm chung giữa các cặp hành trình (giữa các điểm màu xanh) Nếu có nhiều điểm chung trên 2 hành trình => chọn ngẫu nhiên 1 điểm chung 3 Đề xuất phương án 3.3 Lai ghép 0 2 6 7 3 2 6 4 8 3 6 5 4 Ingress Egress VNFa VNFb 0 14 11 12 2 11 9 12 4 3 15 17 18 Cha Mẹ 0 2 6 7 3 2 4 8 3 6 5 4 0 14 11 12 2 11 9 12 4 3 15 17 18 Con 1 Con 2 6 Bước 2:Thực hiện đảo theo các điểm chung 3 Đề xuất phương án 3.3 Lai ghép Sau khi lai ghép xong phải kiểm tra xem có tồn tại: Các MDC node chứa VNF request trùng nhau 0 6 7 3 9 2 5 4 6 11 9 12 4 3 Các vòng lặp trong các đoạn giữa các MDC node chứa VNF kề nhau, đoạn giữa Ingress và MDC node chứa VNF request đầu tiên và đoạn giữa MDC node chứa VNF request cuối cùng đến Egress Điều chỉnh lại 0 6 7 3 9 2 5 4 6 12 Bước 3: Điều chỉnh lại cá thể con 0 2 5 7 3 2 6 4 8 3 6 5 4 0 16 6 7 4 11 9 12 5 10 15 17 18 Ingress Egress VNFa VNFb Cha Mẹ 3 Đề xuất phương án 3.3 Lai ghép Vấn đề : khi cha và mẹ không có điểm chung giữa các đoạn => Con 1 sinh ra giống cha, Con 2 sinh ra giống mẹ 3 Đề xuất phương án 3.4 Đột biến 0 2 5 7 3 2 6 4 8 3 6 5 4 Ingress Egress VNFa VNFb Đột biến thay đổi 1 đoạn Bước 1: Chọn 1 điểm bất kì (trừ các nút xanh) 0 2 5 7 3 10 6 ? 4 8 3 6 5 4 Bước 2: Thay đổi điểm đã chọn (chọn 1 điểm bất kì có liên kết với node trước đó) 1 2 9 13 0 2 5 7 3 10 ? 4 8 3 6 5 4 Ingress Egress VNFa VNFb 3 Đề xuất phương án 3.4 Đột biến Bước 2: Tìm một hành trình mới từ điểm đột biến tới điểm màu xanh gần nhất bên phải Tìm lại 1 hành trình từ 10 -> 5 (Bằng cách DFS) Bước 3: Điều chỉnh lại cá thể đột biến (Giống bước 3 của lai ghép) 1 2 9 13 0 2 5 7 3 10 ? 4 8 3 6 5 4 Ingress Egress VNFa VNFb 3 Đề xuất phương án 3.4 Đột biến Bước 2: Tìm một hành trình mới từ điểm đột biến tới điểm màu xanh gần nhất bên phải Tìm lại 1 hành trình từ 10 -> 5 (Bằng cách DFS) Bước 3: Điều chỉnh lại cá thể đột biến (Giống bước 3 của lai ghép) 3 Đề xuất phương án 3.4 Đột biến Vấn đề Node trước Node đột biến chỉ có liên kết với 1 điểm => Node đột biến không thay đổi, tìm một hành trình khác với hành trình cũ 0 6 4 2 5 Ingress VNFa Node đột biến 0 6 4 2 5 Ingress VNFa Đột biến 5 3 Đề xuất phương án 3.4 Đột biến Vấn đề Node trước Node đột biến chỉ có liên kết với 1 điểm => Node đột biến không thay đổi, tìm một hành trình khác với hành trình cũ Nếu Vấn đề 1 xảy ra cộng thêm với việc chỉ có duy nhất một hành trình từ node đột biến đến MDC node gần nhất => Cá thể không đột biến 3 Đề xuất phương án 3.5 Lựa chọn Sử dụng bánh xe roullete để chọn cá thể Nếu ta có Quẩn thể S gồm n cá thể {a1, a2, , an}, mỗi cá thể có độ fitness lần lượt là {f1, f2, , fn} Lập một mảng tổng tích lũy độ thích nghi 0 f1 f1+f2 f1+f2+f3 3 Đề xuất phương án 3.5 Lựa chọn Random một giá trị p từ 0 đến Nếu giá trị random p nằm trong khoảng từ: <p< => ak là cá thể được chọn 0 f1 f1+f2 f1+f2+f3 4 Kết quả thực nghiệm 4 Kết quả thực nghiệm 4.1 Kết quả Kiểm thử trên mạng 1 8 đỉnh và 23 liên kết tồn tại trên mạng có 4 MDC node 2, 6, 11, 14. 4 Kết quả thực nghiệm 4.1 Kết quả Thông số về trên các liên kết: Băng thông tối đa trên một liên kết: 25 Tỉ lệ bang thông còn lại: thể hiện như hình dưới 4 Kết quả thực nghiệm 4.1 Kết quả Thông số về các node switch (màu đen): Bộ nhớ tối đa trên một node switch: 25 Tỉ lệ bộ nhớ còn lại: thể hiện như hình dưới Thông số về các node MDC (màu đỏ): Số VNF instance tối đa có thể đặt: 5 b :2, e:1 a :1, c:1 a :1, b:2, e:2 c :2, d:2, e:1 4 Kết quả thực nghiệm 4.1 Kết quả Thông số về VNF instance: Có 5 loại VNF: a, b, c, d, e CPU tối đa của một VNF instance: 25 Chi phí đặt 1 VNF instance: 15 Thông tin về các VNF instance đã được đặt trên các MDC node và tỉ lệ CPU còn lại trên các VNF instance đó thể hiện như hình dưới 4 Kết quả thực nghiệm 4.1 Kết quả Xét 3 ví dụ kiểm thử: SFC request 1: a->b SFC request 2: a->c->a SFC request 3: e->c->d Các SFC request trên có chung bang thông yêu cầu (5), bộ nhớ yêu cầu (5), CPU yêu cầu (7), Ingress (0), Egress(13) 4 Kết quả thực nghiệm 4.1 Kết quả Các tham số: Số lượng cá thể bằng 100 Số lượng thế hệ bằng 100 Xác suất lai ghép bằng 0.5, Xác suất đột biến bằng 0.2, Tỉ lệ các cá thể được sinh ra bằng DFS trong quần thể gốc đầu tiên bằng 0.5, Hệ số phạt bộ nhớ, CPU và số lượng VNF instance bằng 10 4 Kết quả thực nghiệm 4.1 Kết quả Ví dụ 1: SFC request 1: a->b Kết quả chạy thuật toán GA Kết quả chạy thuật toán vét cạn 4 Kết quả thực nghiệm 4.1 Kết quả Ví dụ 2: SFC request 2: a->c->a Kết quả chạy thuật toán GA Kết quả chạy thuật toán vét cạn 4 Kết quả thực nghiệm 4.1 Kết quả Ví dụ 3: SFC request 3: e->c->d Kết quả chạy thuật toán GA Kết quả chạy thuật toán vét cạn Từ kết quả thu được bằng phương án đề xuất và kết quả thu được bằng vét cạn, ta có thể khẳng định rằng phương án đề xuất có thể đưa ra kết quả tối ưu 4 Kết quả thực nghiệm 4.2 Demo code 5 Kết luận 5 Kết luận 5.1 Kết luận Phương án đề xuất chạy khá tốt với mô hình thực nghiệm trong phần 4, tuy nhiên do điều kiện thời gian có hạn nên chưa thể tối ưu được các hệ số hàm phạt, xác suất lai ghép, đột biến, tỉ lệ các cá thể sinh ra bằng DFS trong quần thể gốc đầu tiên, cũng như xây dựng một mô hình thực nghiệm có kích thước lớn hơn để có thể kiểm thử. Phương án đề xuất vẫn còn tồn tại một số vấn đề trong lai ghép và đột biến, dẫn đến có thể sinh ra nhiều cá thể giống cá thể trong quần thể gốc, có thể gây ảnh hưởng đến chất lượng lời giải 5 Kết luận 5.2 Hướng phát triển 1. Tối ưu các hệ số trong bài toán 2. Xây dựng một mẫu ví dụ lớn hơn 3. Phát triển phương án vét cạn để có thể chạy trên nhiều trường hợp hơn 4. Tìm phương pháp lai ghép và đột biến tối ưu hơn 5. Xây dựng phương án với bài toán được mở rộng yêu cầu (thay vì xét 1 SFC request, thì mở rộng bài toán xét nhiều SFC request với biến thời gian) THANK YOU FOR WATCHING