Đề tài Áp dụng GA cho bài toán đặt các VNF đảm bảo luồng cực đại trong mạng

Áp dụng GA cho Bài toán đặt các VNF đảm bảo luồng cực đại trong mạng Nguyễn Xuân huy - 20183555 G. Sallam, G. R. Gupta, B. Li, and B. Ji, “Shortest path and maximum flow problems under service function chaining constraints,” in Proc. IEEE INFOCOM , 2018, pp. 2132–2140 Nội dung trình bày Đặt vấn đề Các nghiên cứu liên quan Phát biểu bài toán đặt VNFs Mô hình hóa bài toán Áp dụng GA cho bài toán Kết quả đạt được Hướng phát triển Đặt vấn đề Ảo hóa chức năng mạng là một cách tiếp cận sử dụng tài nguyên mạng mới giúp tách các chức năng mạng khỏi phần cứng độc quyền và cho phép các dịch vụ thích ứng với các yêu cầu của người dùng cuố i Với sự ra đời của Ảo hóa chức năng mạng (NFV), Chức năng mạng vật lý (PNFs) đang dần được thay thế bởi Chức năng mạng ảo (VNFs) được lưu trữ trên các máy chủ mục đích chung. Đặt vấn đề Công nghệ ảo hóa chức năng mạng giúp việc triển khai, quản lý, điều phối và tái triển khai các VNF trở nên linh hoạt và dễ dàng hơn. Đặt vấn đề L àm thế nào chúng ta có thể phân bổ tài nguyên mạng một cách hợp lý để thiết lập (các) SFC được yêu cầu ? Có thể tưởng tượng được trong vài năm tới trong quá trình chuyển đổi này, các mạng này sẽ có sự kết hợp của PNF và VNF. Đặt vấn đề VNF Placement Cho một mạng G(N,L) với tập các yêu cầu R. Đối với mỗi yêu cầu r i ( α ; F; Bài toán là đặt các VNF được yêu cầu vào các nút mạng mà không vi phạm khả năng của nút mạng, nghĩa là được thỏa mãn.(VNFP) TRaffic Routing Cho một mạng G(N,L) với tập các yêu cầu R. Giả sử các VNF của mỗi yêu cầu r i đã được đặt vào các nút mạng. Bài toán là tìm đường đi giữa các cặp VNF mà không vi phạm khả năng của liên kết(link capacity), cũng như được thỏa mãn. (TRR) VNF Redeployment and Consolidation Cho một mạng G(N,L) với các VNF đã được triển khai, bài toán Tái triển khai và Hợp nhất của VNF (VRC) là triển khai lại các SFC đã có sao cho vectơ yêu cầu được thỏa mãn.(VRC) Một số lớp các bài toán trong phân bổ tài nguyên trong mạng ảo hóa Đặt vấn đề Mục tiêu Sử dụng liên kết tối đa (MLU): tối đa của việc sử dụng liên kết trên tất cả các liên kết của nó , với mỗi liên kết l , hiệu suất Thông số QoS: Các thông số QoS chính bao gồm độ trễ của dịch vụ, tính khả dụng, mức tiêu thụ năng lượng, v.v. Các thông số này có thể phản ánh một cách định lượng mức độ tốt của dịch vụ NFV cung cấp cho khách hàng. Chi phí và Doanh thu: K hía cạnh tài chính của việc triển khai các VNF trên các nút và định tuyến giao thông giữa các liên kết được sử dụng. Chú trọng phục vụ nhu cầu của người dân . Mục tiêu giảm thiểu chi phí hoạt động của việc bổ sung các máy chủ trong mạng để hỗ trợ các VNF Tối thiểu số lượng nút mạng được ảo hóa T rong khi luồng cực đại tối đa của mạng ban đầu vẫn có thể đạt được ngay cả dưới ràng buộc SFC Đặt vấn đề Xét b ài toán cụ thể: Đặt các VNF trong mạng kết hợp PNF (VNFP) Đặt vấn đề Tùy thuộc vào các luồng cuộc gọi cho các dịch vụ cụ thể, các gói cần phải đi qua một tập hợp các chức năng mạng có thứ tự (vật lý hoặc ảo hóa ) được gọi là “ Chuỗi chức năng dịch vụ ” (SFC) trước khi đến đích.  Các nghiên cứu liên quan G. Sallam, G. R. Gupta, B. Li, and B. Ji, “Shortest path and maximum flow problems under service function chaining constraints,” in Proc. IEEE INFOCOM, 2018, pp. 2132–2140. Song Yang, Fan Li, T. Stojan , R. Yahyapour, F. Xiaoming ,“Recent Advances of Resource Allocation in Network Function Virtualization”, IEEE Transactions on Parallel and Distributed Systems, 2020. H. Feng, J. Llorca , A. M. Tulino, D. Raz, and A. F. Molisch. “Approximation Algorithms for the NFV Service Distribution Problem”. IEEE INFOCOM 2017 , Atlanta, GA, May 2017.[1] A. Sinha and E. Modiano. Optimal Control for Generalized NetworkFlow Problems. IEEE INFOCOM 2017, Atlanta, GA, May 2017 L. Fleischer. “Approximating fractional multicommodity flow independent of the number of commodities ”. 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), 13(4):1–16, 1999. Phát biểu bài toán Với một mạng gồm các nút vật lý cho trước có đồ thị biểu diễn mạng là G = (V, E). Ràng buộc SFC với luồng yêu cầu (v s , φ1, ..., φ r, v d ) : với v s và v d lần lượt là nguồn và đích, và ( φ 1 , ..., φ r ) biểu thị một chuỗi các chức năng mạng (VNFs) mà tất cả các gói của luồng cần được xử lý trước khi đến vd. Giả thuyết cùng một chức năng mạng có thể có nhiều thể hiện ở các đỉnh khác nhau và một đỉnh có thể đặt nhiều chức năng mạng Với mục đích sử dụng tối đa liên kết giữa các nút mạng, yêu cầu đặt các VNF sao cho tối thiểu lượng nút vật lý cần ảo hóa đồng thời đạt luồng cực đại như ban đầu không có ràng buộc SFC Phát biểu bài toán Đồ thị G(V,E) biểu diễn mạng vật lý: Mỗi cạnh e thuộc E có khả năng thông qua là c(e) Tập đỉnh V = {v 1 ,v 2 ,v 3 ,v n } , trong đó ta coi v 1 là nguồn , v n là đích Ràng buộc SFC = {v 1, φ 1 , φ 2, φ 3 ..., φ r , v n } Ràng buộc về khả năng xử lý tại nút: Vertex_Capity = {a 1 ,a 2 ,a n } Input: Output : Một cách đặt các VNFs cho vẫn đạt luồng cực đại ban đầu khi không có ràng buộc SFClên các đỉnh sao Phát biểu bài toán Phát biểu bài toán Độ khó của vấn đề đến từ hai phần: Đầu tiên, luồng cực đại có thể đạt được thông qua một tập hợp các đường dẫn khác nhau, khó liệt kê và mỗi tập hợp các đường dẫn có thể mang lại một vị trí khác nhau. Hơn nữa, việc tìm số lượng nút tối thiểu để bao phủ một tập hợp các đường đi cũng là một điều khó khăn [1]. Ngoài ra, cần lưu ý rằng nếu chúng ta xem xét các chuỗi chức năng dịch vụ trong đó các chức năng không thể được lưu trữ tại một nút, thì vấn đề trở nên khó khăn hơn Phát biểu bài toán Xét trường hợp đặc biệt: Các đỉnh có thể lưu trữ toàn bộ các VNF Phát biểu bài toán Xét trường hợp đặc biệt: Các đỉnh có thể lưu trữ toàn bộ các VNF VNFs Phát biểu bài toán Xét trường hợp đặc biệt: Các đỉnh có thể lưu trữ toàn bộ các VNF VNFs VNFs Giả sử đặt toàn bộ VNFs tại 3 đỉnh của đồ thị 100 đỉnh: C 3 100 = 161700 Mô hình hóa bài toán: P ′ sd biểu thị tập hợp các đường dẫn có thể chấp nhận (đi qua đầy đủ các VNFs theo đúng thứ tự) từ nút s đến nút d cho một ràng buộc SFC đã cho. k i là một biến nhị phân để biểu thị liệu nút i có lưu trữ các VNF bắt buộc hay không (tức là nút i là một nút được ảo hóa). x p biểu thị giá trị luồng trên đường dẫn p . F s,d để biểu thị lưu lượng cực đại ban đầ u Áp dụng thuậ toán GA giải bài toán đặt VNF Thuật toán tạo đồ thị phụ Mã hóa nhị phân Áp dụng GA giải bài toán đặt VNF: Khởi tạo quần thể: ngẫu nhiên, ưu tiên n phần tử chỉ chứa 1 đỉnh ảo hóa Mã hóa: mỗi cá thể có gen là vector nhị phân . Vector Y = (y 1 ,y 2 ,y 3 ,,y nxr ) biểu diễn một cách đặt VNF trong đó y i là biến nhị phân y i = 1: VNF φ a được đặt tại đỉnh v b với ( b-1)*r + a = i ( b ∈ 2,3,,n-1 , a ∈ 1,2,.,r ) k j là một biến nhị phân để biểu thị liệu nút i có lưu trữ VNF nào không , k j ∈{0,1} , i ∈(1,n) k j = Max y i , y i ∈ Y và (j-1)*r+1 < i < j*r+1 Lai ghép: Sử dụng lai ghép một điểm cắt với xác suất lai ghép cho trước, giữ lại một vài cá thể tốt nhất( elitismCount ), chọn cha mẹ theo bánh xe roulette. Đột biến: Đột biến đảo bit với xác suất đột biến, giữ lại một vài cá thể tốt nhất( elitismCount) . Áp dụng GA giải bài toán đặt VNF: Ví dụ mã hóa gen Áp dụng GA giải bài toán đặt VNF: Khởi tạo quần thể: ngẫu nhiên, ưu tiên n phần tử chỉ chứa 1 đỉnh ảo hóa Mã hóa: mỗi cá thể có gen là vector nhị phân . Vector Y = (y 1 ,y 2 ,y 3 ,,y nxr ) biểu diễn một cách đặt VNF trong đó y i là biến nhị phân y i = 1: VNF φ a được đặt tại đỉnh v b với ( b-1)*r + a = i ( b ∈ 2,3,,n-1 , a ∈ 1,2,.,r ) k j là một biến nhị phân để biểu thị liệu nút i có lưu trữ VNF nào không , k j ∈{0,1} , i ∈(1,n) k j = Max y i , y i ∈ Y và (j-1)*r+1 < i < j*r+1 Lai ghép: Sử dụng lai ghép một điểm cắt với xác suất lai ghép cho trước, giữ lại một vài cá thể tốt nhất( elitismCount ), chọn cha mẹ theo bánh xe roulette. Đột biến: Đột biến đảo bit với xác suất đột biến, giữ lại một vài cá thể tốt nhất( elitismCount) . Áp dụng GA giải bài toán đặt VNF: Chọn lọc cá thể: Chọn lọc cá thể dựa theo fitness, thực hiện tại mỗi bước lai ghép/ đột biến. Đánh giá quần thể: Tính Fitness: Với mỗi cá thể tạo đồ thị phụ G’(V’,E’) ánh xạ từ G sao cho mọi đường đi từ nguồn tới đích trong G’ đều thỏa mãn rang buộc SFC và nó ánh xạ 1-1 với đồ thị G. Khi đó gọi F’ s,d là giá trị luồng cực đại trên G’ , đây chính là giá trị luồng cực đại thỏa mãn ràng buộc SFC. fitness =1/( F s,d - F’ s,d )) Với các cá thể không hợp lệ do đặt thiếu VNF : khi tính fitness sẽ sửa lại gen cho hợp lệ hoặc gán F’ s,d =0 luôn rồi tính fitness mà không cần tạo đồ thị phụ (với xác suất định trước). Áp dụng GA giải bài toán đặt VNF: Khởi tạo G’ từ G: Khởi tạo tập đỉnh: Với mỗi đỉnh thuộc G tạo thêm r+1 đỉnh ảo với r là số VNFs Khởi tạo cạnh: Với mỗi cạnh thuộc G xét từng cặp cạnh của các đỉnh (bao gồm đỉnh gốc và đỉnh phụ) tương ứng, nếu thỏa mãn điều kiện VNF thì thực hiện thêm cạnh vào G’ Cắt tỉa G’: Tìm và loại bỏ những đỉnh không có cạnh đi vào hoặc không có cạnh đi ra (trừ nguồn và đích ) vì những đỉnh đó không có đường đi từ nguồn tới đích. Lặp lại quá trình trên đến khi không tìm thấy đỉnh nào cần loại bỏ Thuật toán tạo đồ thị phụ Áp dụng GA giải bài toán đặt VNF: Thuật toán tạo đồ thị phụ Áp dụng GA giải bài toán đặt VNF: SFC = (v 1 , φ 1 , φ 2 , v 5 ) Áp dụng GA giải bài toán đặt VNF: Độ phức tạp của thuật toán: Với mỗi cá thể cần phải đánh giá độ thích nghi: Với G ban đầu, G’ có số đỉnh nhiều nhất sẽ là |V’| = (r + 1) | V |, và các cạnh | E’ | = (r + 1) | E |. Độ phức tạp của việc xây dựng G¯ là O (| V ‘| 2 ). Sau bước cắt tỉa, số đỉnh, cạnh sẽ nhiều nhất là | V ′ | = 0.5z | V’ |, | E ′ | = 0.5z | E |) (số cạnh và đỉnh giảm còn 0.5z với z là xác suất khả dụng của các chức năng mạng tại bất kỳ đỉnh nào) Tìm luồng cực đại sử dụng Ford–Fulkerson: O(|E’|f) với f là giá trị luồng cực đại trong đồ thị Tổng quát: O(G N (r + 1) 2 | V | 2 |E| f ) G: số thế hệ N: số cá thể trong quần thể Kết quả trong bài báo (quy hoạch nguyên) Random ngẫu nhiên số đỉnh từ 10-100, số cạnh có tỉ lệ bằng 3 lần số đỉnh, trọng số của cạnh ngẫu nhiên từ 1-10, lặp lại 20 lần thu được đồ thị dưới Với các test nhỏ xử lý trong vài giây và vài phút với test lớn Random đồ thị với số đỉnh 20,30,50,80, số cạnh gấp 3 lần số đỉnh, lặp lại 5 lần cho mỗi đỉnh Số lượng cá thể: 500 Số vòng lặp dừng: 1000 Tỉ lệ lai ghép: 0.95 Tỉ lệ đột biến: 0.05 elitismCount : 2 Kết quả đạt được với giải thuật GA Kết quả sử dụng GA Đối với các đồ thị kể cả lớn và nhỏ, nếu rơi vào trường hợp duy nhất 1 đỉnh sẽ hội tụ chỉ sau trung bình từ 1-15 thế hệ, nếu khởi tạo tham lam sẽ đạt được kết quả trong vòng vài giây Khi rơi vào các trường hợp đồ thị thưa hoặc đặc biệt , yêu cầu từ 2 đỉnh ảo hóa trở lên sẽ có thời gian thực hiện vài phút ( 100 thế hệ). Chỉ xấp xỉ được lời giải với các đồ thị lớn , nhưng tỉ lệ cá thể hợp lý đạt được khá cao. Thực tế thời gian hội tụ vẫn khá chậm, cần điều chỉnh lại các tham số và cách triển khai thuật toán. Kết quả đạt được với giải thuật GA Đề xuất hướng phát triển Xét trường hợp tổng quát: Thêm tập r àng buộc về khả năng xử lý tại nút: Vertex_Capity = {a 1 ,a 2 ,a n } Số cá thể không hợp lệ tăng lên rất nhiều trong mỗi thế hệ Cần thay đổi cách mã hóa (sử dụng các cấu trúc dữ liệu?) Đánh giá cá thể vẫn giữ nguyên phương pháp vì đồ thị phụ tạo ra là tổng quát cho mọi cách đặt Cần chú ý đến cá thể sau khi lai ghép/đột biến không hợp lệ Điều chỉnh các tham số dựa trên đồ thị đầu vào? Đề xuất hướng phát triển Xét trường hợp tổng quát: Ví dụ V ={v1,v2,v3,v4,v5} trong đó v1 coi là nguồn, v5 coi là đích SFC ={v1, φ 1 , φ 2 , v5} Vertex_Capity = {0,2,1,1,0} => Độ dài gen : 2+1+1 = 4 1 2 3 4 1 2 2 1 v 2 v 3 v 4 Ví dụ một lời giải được biểu diễn qua gen: Ánh xạ: Tạo HashMap kết hợp Vertex_Capity Cảm ơn mọi người đã chú ý lắng nghe!