Luận án Cung cấp tài nguyên cho dịch vụ ảo hóa dựa trên nền tảng máy chủ chia sẻ trong tính toán đám mây

Lời cam đoan i

Lời cảm ơn ii

Danh mục viết tắt iii

Danh mục các ký hiệu v

Mục lục viii

Danh mục bảng, biểu xi

Danh mục hình vẽ xii

Mở đầu 1

Chương 1. Tổng quan và đề xuất bài toán cung cấp tài nguyên cho

dịch vụ ảo hóa 6

1.1 Hệ thống tính toán đám mây 6

1.1.1 Đặc điểm của hệ thống tính toán đám mây 7

1.1.2 Mô hình dịch vụ của hệ thống tính toán đám mây 7

1.1.3 Mô hình triển khai của hệ thống tính toán đám mây 9

1.2 Yêu cầu và thách thức của hệ thống tính toán đám mây 10

1.2.1 Yêu cầu của một hệ thống tính toán đám mây 10

1.2.2 Thách thức của một hệ thống tính toán đám mây 11

1.3 Máy ảo 12

1.4 Công nghệ ảo hóa 13

1.4.1 Ảo hóa máy chủ 13

1.4.2 Ảo hóa tích hợp 14

1.5 Công cụ mô phỏng hệ thống tính toán đám mây 15

1.5.1 Khảo sát các công cụ mô phỏng 15

1.5.2 Công cụ mô phỏng CloudSim 17

1.6 Cung cấp tài nguyên trong hệ thống tính toán đám mây 19

1.6.1 Mô hình cung cấp tài nguyên 19

1.6.2 Cung cấp ứng dụng 20

1.6.3 Cung cấp máy ảo 21

1.6.4 Cung cấp tài nguyên vật lý 23

1.7 Các nghiên cứu liên quan đến cung cấp tài nguyên cho dịch vụ ảo hóa . 24

1.7.1 Mô hình hệ thống cung cấp tài nguyên cho dịch vụ ảo hóa . 24

1.7.2 Mô hình cung cấp tài nguyên cho dịch vụ ảo hóa với mục tiêu

tối thiểu số lượng máy vật lý được dùng 25

1.7.3 Mô hình cung cấp tài nguyên cho dịch vụ ảo hóa với mục tiêu

tối thiểu nang lượng tiêu thụ 26

1.7.4 Mô hình cung cấp tài nguyên cho dịch vụ ảo hóa với mục tiêu

cân bằng tải 27

1.8 Mục tiêu và nội dung của luận án 28

1.8.1 Mục tiêu nghiên cứu của luận án 28

1.8.2 Nội dung nghiên cứu của luận án 28

1.9 Tiểu kết Chương 1 30

Chương 2. Cung cấp tài nguyên cho dịch vụ ảo hóa từ nền tảng máy

chủ chia sẻ đồng nhất 32

2.1 Mô hình tài nguyên và nhu cầu tài nguyên 32

2.2 Bài toán MDRAVS 33

2.2.1 Phát biểu bài toán MDRAVS 33

2.2.2 Độ phức tạp bài toán MDRAVS 35

2.3 Đề xuất giải pháp cho bài toán MDRAVS 36

2.3.1 Giải pháp áp dụng các thuật toán First Fit và Best Fit 36

2.3.2 Giải pháp dựa trên thuận toán Tối ưu đàn kiến 39

2.3.2.1 Giới thiệu thuận toán Tối ưu đàn kiến 39

2.3.2.2 Đề xuất thuật toán MDRAVS-MMAS 41

2.3.3 Thực nghiệm và nhận xét 46

2.3.3.1 Phương pháp mô phỏng 46

2.3.3.2 Nhận xét kết quả thực nghiệm các thuật toán First

Fit*, Best Fit* 47

2.3.3.3 Nhận xét kết quả thực nghiệm các thuật toán MDRAVS-

MMAS, First Fit* và Best Fit* 49

2.4 Tiểu kết Chương 2 52

Chương 3. Cung cấp tài nguyên cho dịch vụ ảo hóa từ nền tảng máy

chủ chia sẻ không đồng nhất 54

3.1 Mô hình tài nguyên và nhu cầu tài nguyên 54

3.2 Mô hình nang lượng tiêu thụ 57

3.3 Phát biểu bài toán ECRAVS 58

3.4 Đề xuất giải pháp cho bài toán ECRAVS 59

3.4.1 Giải pháp dựa trên thuật toán Tối ưu bầy đàn 59

3.4.1.1 Giới thiệu thuật toán Tối ưu bầy đàn 59

3.4.1.2 Đề xuất thuật toán ECRAVS-PSO 60

3.4.2 Giải pháp dựa trên thuật toán Mô phỏng luyện kim 67

3.4.2.1 Giới thiệu thuật toán Mô phỏng luyện kim 67

3.4.2.2 Đề xuất thuật toán ECRAVS-SA 68

3.4.3 Thực nghiệm và nhận xét 72

3.4.3.1 Phương pháp mô phỏng 72

3.4.3.2 Đặc điểm của các thuật toán FFD, ECRAVS-PSO và

ECRAVS-SA 74

3.4.3.3 Kết quả và nhận xét 76

3.5 Tiểu kết Chương 3 78

Chương 4. Cung cấp tài nguyên đa mục tiêu cho dịch vụ ảo hóa từ

nền tảng máy chủ chia sẻ không đồng nhất 80

4.1 Mô hình cân bằng tải 80

4.2 Phát biểu bài toán MORA 82

4.3 Giải pháp cho bài toán MORA 84

4.3.1 Phương pháp tối ưu Pareto 84

4.3.2 Đề xuất thuật toán MORA-ACS 85

4.3.3 Thực nghiệm và nhận xét 90

4.3.3.1 Phương pháp mô phỏng 90

4.3.3.2 Đặc điểm của thuật toán Round Robin và MORA-ACS 92

4.3.3.3 Kết quả thực nghiệm và nhận xét 93

4.4 Tiểu kết Chương 4 95

Kết luận và hướng phát triển 96

Danh mục các công trình của tác giả liên quan đến luận án 99

Tài liệu tham khảo 100

 

docx118 trang | Chia sẻ: trungkhoi17 | Lượt xem: 299 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu Luận án Cung cấp tài nguyên cho dịch vụ ảo hóa dựa trên nền tảng máy chủ chia sẻ trong tính toán đám mây, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
X|PM| để lưu các giải pháp mà mỗi con kiến tạo ra, các phần tử eij 2 {0,1g biểu diễn ánh xạ từ dịch vụ ảo hóa i đến các máy vật lý j. Tức là, phần tử eij bằng 1 nếu dịch vụ ảo hóa i được cung cấp tài nguyên từ máy vật lý j, bằng 0 nếu ngược lại. Sau đó, thực hiện việc tìm kiếm nhị phân trong từng ma trận giải pháp BINARYnA mà mỗi kiến tạo ra để so sánh và xác định giá trị tốt nhất của giải pháp trong mỗi lần lặp, Sbest, giá trị của giải pháp được thính theo Công thức (2.7). Giá trị tốt nhất nàygọi là f (Sbest). Mục đích của thuật toán là nhằm tối thiểu số lượng máy vật lý, vì thế cần tang lợi ích trung bình tài nguyên của các máy vật lý cần dùng. Do vậy, mùi con kiến tìm ra giải pháp tốt nhất của lần lặp được gửi vào cặp " dịch vụ ảo hóa-máy vật lý" được tính bằng nghịch đảo của giá tri hàm mục tiêu được áp dụng trên giải pháp tốt nhất Sbest của lần lặp và thể hiện bằng Công thức (2.12): (2.12) Atbest _ í f (S1est), nếu eij = 1,2 VS, 8j 2 PM ij 1 0, trường hợp khác Tuy nhiên, chỉ con kiến tốt nhất của lần lặp mới được phép gửi mùi, nên sự tắc nghẽn (stagnation) trong thuật toán có thể sớm xảy ra, dẫn đến tình huống mà tất cả con kiến sau đó đều chọn cùng một dịch vụ ảo hóa để được cung cấp tài nguyên. Điều này, làm cho khả nang thuật toán khám phá các giải pháp tối ưu khác sẽ giảm. Để tránh hiệu ứng này, thuật toán Hệ kiến Max-Min sử dụng miền giới hạn cho giá trị mùi Tij trong đoạn [Tmin ,Tmax]. Công thức (2.13) và (2.14) được sử dụng để tính cho các giá trị này (Các công thức này được chọn từ [105] để áp dụng cho đối tượng "máy vật lý - dịch vụ ảo hóa"). Tmax 1 (2 13) (avg — 1) X ụpbest = f (Sbest) X (1 - p) ( ) (2.14) Trong đó, N là số lượng dịch vụ ảo hóa, avg = N=2 và 0 < pbest < 1 là tham số điều chỉnh biên của vệt mùi. Tóm lại, thuật toán MDRAVS-MMAS để giải bài toán MDRAVS được trình bày như Thuật toán 5. Thuật toán này được trình bày trong công trình số 2. - Hoạt động của thuật toán: Đầu tiên, thuật toán khởi tạo giá trị ban đầu cho các tham số và giá trị mùi ban đầu của các cặp "dịch vụ ảo hóa-máy vật lý ". Tiếp đến, thuật toán thực hiện numLoop lần lặp để các con kiến xây dựng giải pháp cung cấp tài nguyên (từ Lệnh 2 đến Lệnh 22). Trong đó, tương ứng mỗi lần lặp, từng con kiến chọn một máy vật lý j (gọi là máy vật lý hiện hành) và bắt đầu xây dựng giải pháp (từ Lệnh 3 đến Lệnh 12). Đe đạt điều này, khởi tạo ma trận giải pháp BINARYnA có các phần tử eij := 0 (Lệnh 5). Thuật toán 5: Thuật toán MDRAVS-MMAS. Đầu vào: Tập dịch vụ ảo hóa VS với các vector ri*, r**. Tập các máy vật lý PM. Các tham số: a, g, p,pbest,Tmax, số lần lặp numLoop và số kiến numAnt. Đầu ra : Giải pháp tốt nhất, Sbest~toan~cuc, là số lượng máy vật lý được dùng. Khởi tạo các tham số a,fi, p,rpbest, Tmax và thiết lập giá trị mùi Tij = Tmax; for nL := 1 ! numLoop do for nA := 1 ! numAnt do j := 1 ; /* Sử đụng một máy vật lý j, j là chỉ số lượng máy vật lý. */ BINARYnA := [eij := 0], 8i 2 VS, 8j 2 PM; while (VS = 0) do 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 M i 2 VS V Xij = 0 j=1 if (VStemp = 0) then Chọn ngẫu nhiên một dịch vụ ảo hóa i 2 VStemp theo xác suất - : [Tij]ax[w]\ \tic VStemP- pij EueVStemp [Tuj A An»j k , 8i 2 ; eij := 1; VS := VS — {i}; Loadj := Loadj + (ri* + ri**); else j := j +1; VStemP = Loadj + r* + r** ; /* Sử đụng thêm một máy vật lý j. */ So sánh các giải pháp thông qua các ma trận BINARYnA của mỗi tạo ra dựa vào giá trị f (Sbesft) và lưu giải pháp tốt nhất vào biến S best—vong—lap; if (nL =1 V Best — Toan — Cuc(Sbest~vong~lap)) then Sbest~toan~cuc := Sbest~vong~lap ; /* Chọn giải pháp tốt nhất toàn con cục kiến mối. có Trong đó, Hàm Best - Toan - Cuc(Sbest-vong-laP') kiểm tra Sbest-vong-laP phải là giải pháp tốt nhất đến thời điểm hiện tại hay không. */ Tính giá trị Tmin,Tmax dựa vào các Công thức (2.13) và (2.14); foreach (i, j) 2 (VS X PM) do Tij := p X Tij + ATjesí; if (Tij > Tmax) then T. . — Tmax. |_ ‘ij : 1 ; if (Tij < Tmin then T" Tmin. T ij T ; return Giải pháp tốt nhất toàn cục Sbest toan cuc; Tiếp đến, con kiến chọn các dịch vụ ảo hóa để được cung cấp tài nguyên từ các máy vật lý cho đến khi tài nguyên của máy vật lý được bão hòa. Điều này đạt được bằng cách khởi tạo tập VStemp chứa các dịch vụ ảo hóa i chưa được cung cấp tài nguyên từ bất kỳ máy vật lý nào và không vượt quá nang lực tài nguyên của máy vật lý hiện hành (Lệnh 7). Nếu (VS = 0) thì áp dụng phưìng pháp roulette wheel (dựa trên giá trị hàm xác suất pij) chọn một dịch vụ ảo hóa i để được cung cấp tài nguyên từ máy vật lý hiện hành j (Lệnh 9). Thiết lập giá trị phần tử eij của ma trận BINARYnA bằng 1, loại bỏ dịch vụ đó ra khỏi tập (VS và cập nhật tải của máy vật lý (Lệnh 10). Tiến trình này thực hiện cho đến khi nang lực tài nguyên của máy vật lý hiện hành còn khả nang đáp ứng (từ Lệnh 6 đến Lệnh 11). Sau đó, khi nang lực của máy chủ được bảo hòa (tức là rỗng) thì chon một máy vật lý mới và thực hiện tiến trình cung cấp tài nguyên cho đến khi tất cả các dịch vụ ảo hóa được được cung cấp tài nguyên (từ Lệnh 6 đến Lệnh 12). (Lệnh 13). Sau khi tất cả các con kiến đã xây dựng giải pháp cung cấp tài nguyên, thuật toán thực hiện so sánh các giải pháp để tìm ra giải pháp tốt nhất vòng lặp (thông qua hàm mục tiêu: tối thiểu số máy chủ vật lý), giải pháp tốt nhất này được lưu vào biến S best—vong—lap Tiếp đến, nếu chỉ có một lần lặp thì giải pháp tốt nhất của lần lặp này trở thành giải pháp tốt nhất toàn cục. Ngược lại, thuật toán so sánh với giải pháp tốt nhất toàn cục hiện hành. Nếu giá trị hàm mục tiêu của giải pháp tốt nhất lần lặp hiện hành được cải thiện thì giải pháp này trở thành giải pháp tốt nhất toàn cục mới (Lệnh 14 đến 15). Cuối cùng, tính các giá trị Tmin, Tmax và cập nhật mùi trên tất cả các cặp "dịch vụ ảo hóa-máy vật lýNếu một cặp "dịch vụ ảo hóa-máy vật lý" nhận giá trị mùi cao hìn Tmax thì giá trị mùi này được khởi tạo lại ở mức giá trị Tmax. Tưìng tự, khi giá trị mùi thấp hìn giá trị Tmin thì giá trị này được cập nhật ở mức Tmin. Thuật toán sẽ kết thúc sau numLoop lần lặp và trả về giải pháp tốt nhất toàn cục (từ Lệnh 16 đến Lệnh 23) - Phân tích thuật toán: + Bài toán MDRAVS như đã trình bày tại Mục 2.2.1 là bài toán cung cấp tài nguyên tĩnh. Vì thế, tại thời điểm cung cấp tài nguyên, tập dịch vụ ảo hóa VS với các nhu cầu tài nguyên ri*, ri**, tập các máy vật lý PM cũng như nang lực tài nguyên của máy vật lý hoàn toàn xác định được. + Độ hội tụ của thuật toán MDRAVS-MMAS: gọi P(numLoop) là xác suất tìm thấy giải pháp của thuật toán Hệ kiến Max-Min sau numLoop bước lặp, sử dụng mô hình Markov không đồng nhất, Stutzle [105] và Dorigo [28] chứng minh rằng: 8" > 0 và nếu numLoop đủ lớn thì P(numLoơp} > 1 —Do đó, lim P (numLoop) = 1. numLoopn Vì thế, thuật toán MDRAVS-MMAS sẽ hội tụ sau numLoop bước lặp. + Độ phức tạp của thuật toán MDRAVS-MMAS: gọi số kiến là numAnt, số lần lặp là numLoop, số lượng dịch vụ ảo hóa là N, số lượng máy vật lý là M và số loại tài nguyên là D thì độ phức tạp của thuật toán là O(numLoop X numAnt X N X M X D). Nếu cố định số loại tài nguyên D, độ phức tạp của thuật toán là O(numLoop X numAnt X N X M). Thực nghiệm và nhận xét Phương pháp mô phỏng Để đánh giá các thuật toán, luận án sử dụng tập các mẫu dữ liệu thực nghiệm được tạo ra theo phương pháp ngẫu nhiên của Stillwell [100], như sau: Xét N dịch vụ ảo hóa và M máy vật lý với số loại tài nguyên D. Tương ứng với mỗi dịch vụ ảo hóa, số nhu cầu tất yếu là D/2 và số nhu cầu tùy biến là D/2. Tất cả các nhu cầu tài nguyên được lấy mẫu từ một phân bố xác suất với trung bình /lỵ' và độ lệch chuẩn SN. Mỗi dịch vụ ảo hóa có pN xác suất để có một yêu cầu QoS. Luận án giả định giá trị của các tham số này là: Số lượng dịch vụ ảo hóa N lần lượt là: 32; 64; 128; 256 và 512. Số loại tài nguyên D = 6, trong đó, số nhu cầu tất yếu bằng số nhu cầu tùy biến và bằng 3. Nang suất dịch vụ bij = 0,5 (tức là, một nửa nhu cầu tùy biến của dịch vụ ảo hóa phải được cung cấp), giá trị của yêu cầu QoS là 0,5, giá trị tham số pN = 0,5, giá trị ỖN lần lượt là: 0,25; 0,5 và 1,0 và giá trị pN lần lượt là: 0,25; 0,5; 1,0. Thực nghiệm với các giá trị khác hoặc với các giá trị ngẫu nhiên cũng dẫn đến kết quả tương tự. Như vậy, tổ hợp giá trị từ các tham số ở trên sẽ có 5 X 1 X 1 X 3 X 3 X 1 = 45 kịch bản. Với mỗi kịch bản tạo ra 100 mẫu ngẫu nhiên, vì thế sẽ có 4500 mẫu dữ liệu đầu vào để đánh giá thuật toán. Các mẫu thực nghiệm được tạo ra lưu vào tập tin có cấu trúc như Hình 2.2. Để đánh giá hiệu quả các thuật toán, luận án sử dụng hai thước đo: số lượng máy vật lý được sử dụng và thời gian thực hiện thuật toán tính bằng giây. Giá trị của hai thước đo được lấy trung bình từ 900 (tức là, 1 X 1 X 3 X 3 X 1 X 100) mẫu thực nghiệm. Chương trình mô phỏng các thuật toán được thực hiện bằng ngôn ngữ C++ và thời gian thực hiện được đo trên máy tính đơn có bộ vi xử lý Intel Core Duo 1.86 GHz, RAM 2Gb. Í Giá trị QoS 1> ... ... Giá trị QoS 2> ... <nhu cầu tất yếu 1 của dịch vụ 2> ... ... <nhu cầu tất yếu 1 cùa dịch vụ 3> ... Hình 2.2: Cấu trúc tập tin dữ liệu thực nghiệm. Nhận xét kết quả thực nghiệm các thuật toán First Fit*, Best Fit* Số lượng máy vật lý được dùng tương ứng với số lượng dịch vụ ảo hóa khi thực hiện các thuật toán được trình bày trong Bảng 2.1 và Hình 2.3. Thời gian thực hiện các thuật toán tương ứng với số lượng dịch vụ ảo hóa được trình bày trong Bảng 2.2 và Hình 2.4. Bảng 2.1: số lượng máy vật lý đã sử dụng khi thực hiện các thuật toán First Fit*, Best Fit*. Tên thuật toán Số lương dich vụ ảo hóa N=32 dich vụ N=64 dich vụ N=128 dich vụ N=256 dich vụ N=512 dich vụ FirstFitDesMax 24 47 90 174 344 FirstFitDesLex 24 47 90 174 344 FirstFitDesSum 24 47 90 174 344 BestFitDesMax 24 47 90 174 344 BestFitDesLex 24 47 89 170 327 BestFitDesSum 24 47 90 174 344 Bảng 2.2: Thời gian thực hiện các thuật toán First Fit*, Best Fit*. Tên thuật toán Số lương dich vụ ảo hóa N=32 dich vụ N=64 dich vụ N=128 dich vụ N=256 dich vụ N=512 dich vụ FirstFitDesMax 0,00009 0,00107 0,00303 0,01076 0,03193 FirstFitDesLex 0,00010 0,00114 0,00214 0,00827 0,02529 FirstFitDesSum 0,00016 0,00113 0,00268 0,00932 0,02791 BestFitDesMax 0,00121 0,00254 0,00833 0,03741 0,13107 BestFitDesLex 0,00123 0,00232 0,00783 0,03500 0,12253 BestFitDesSum 0,00128 0,00234 0,00800 0,03693 0,13380 Hình 2.3: Đồ thị biểu diễn số lượng máy vật lý đã sử dụng khi thực hiện các thuật toán First Fit*, Best Fit*. Căn cứ kết quả trẽn bảng số liệu và đồ thị, thấy rằng: Thời gian thực hiện thuật toán và số lượng máy vật lý được sử dụng tỷ lệ thuận với số lượng dịch vụ ảo hóa, thời gian thực hiện thuật toán tương đối nhỏ và có thể áp dụng trong thực tế. Khi số lượng dịch vụ ảo hóa nhỏ thì giá trị của hai thước đo này không khác biệt nhau nhiều giữa các thuật toán. Ngược lại, trong trường hợp số lượng dịch vụ ảo hóa lớn (N > 256) thì có sự khác biệt rõ rệt, trong đó thuật toán BestFitDesLex cho số lượng máy vật lý được dùng thấp nhất còn thời gian thực hiện thuật toán FirstFitDesLex có giá trị ngắn nhất. 0,16 0,14 »0,12 í|- 0,1 o £ 0,08 iz ra O) 0,06 '& í— 0,04 0,02 0 FirstFitDesMax E3 FirstFitDesLex B FirstFitDesSum BestFitDesMax ■ BestFitDesLex BestFitDesSum — I N=32 N=64 N=128 N=256 SỐ lượng dịch vụ ào hóa N= Hình 2.4: Đồ thi biểu diễn thời gian thực hiện các thuật toán First Fit*, Best Fit*. Do đó, khi cung cấp tài nguyên cho dich vụ ảo hóa (số dich vụ lớn) mà quan tâm về thời gian thực hiện thì thuật toán FirstFitDesLex phù hợp, ngược lại khi quan tâm về số lượng máy vật lý tối thiểu được dùng thì thuật toán BestFitDesLex phù hợp. Sự khác nhau của kết quả thực nghiệm có thể lý giải như sau: Về bản chất các thuật toán này giống nhau, nên quá trình thực hiện sẽ cho kết quả giống nhau. Tuy nhiên, nguyên nhân có sự khác biệt trong kết quả thực nghiệm là: dữ liệu đầu vào của các thuật toán được sắp xếp lại theo 03 tiêu chí khác nhau, điều này tác động đến kết quả đầu ra của thuật toán. Vậy nên có thể kết luận rằng: giá trị hàm mục tiêu và thời gian thực hiện của các thuật toán phụ thuộc vào dữ liệu đầu vào, ở đây chính là nhu cầu tài nguyên của các dich vụ ảo hóa. Nhận xét kết quả thực nghiệm các thuật toán MDRAVS- MMAS, First Fit* và Best Fit* Lựa chọn giá trị các tham số của thuật toán MDRAVS-MMAS: Theo tài liệu [102], Stutzle và các cộng sự cho rằng: việc lựa chọn giá trị tham số thích hợp sẽ cải thiện đáng kể của hành vi của thuật toán theo thời gian tính toán mà không ảnh hưởng đến chất lượng của giải pháp cuối còng. Hiện nay, để xác đinh giá tri các tham số a,/3,p của thuật toán Hệ kiến Max - Min các nhà nghiên cứu thường sử dụng phương pháp Thích ứng tham so (Parameter Adaptation), đó là thay đổi việc thiết lập giá tri các tham số của thuật toán khi giải một bài toán cụ thể. Trong phạm vi của đề tài, luận án thực hiện theo phương pháp được công bố trong tài liệu [29]. Tức là, giá tri các tham số được xác đinh thông qua việc kiểm tra thực nghiệm trên tổ hợp các tham số: giá tri a lần lượt là 0; 0,5; 1; 2 và 5 , giá tri lần lượt là 0; 1; 2 và 5, giá tri p lần lượt là 0,3; 0,5; 0,7; 0,9; và 0,999. Nhận thấy, các giá tri tốt nhất sẽ là: a =1; = 2; p = 0; 9 và các giá tri pbest = 0,05, Tmax = 3, numLoop = 5, numAnt = 5. Kết quả thực nghiệm: Kết quả giá tri số lượng máy vật lý được dùng (giá tri hàm mục tiêu) tương ứng với số lượng dich vụ ảo hóa khi thực hiện các thuật toán được trình bày trong Bảng 2.3 và Hình 2.5. Thời gian thực hiện (tính bằng giây) các thuật toán tương ứng với số dich vụ được trình bày trong Bảng 2.4 và Hình 2.6. Các kết quả thực nghiệm được lấy từ trung bình của 100 lần thực thi thuật toán. Trong đó: Giá tri thời gian thực hiện và số lượng máy vật lý được dùng của thuật toán First Fit* được lấy từ giá tri trung bình cộng giá tri của 03 thuật toán FirstFitDesSum, FirstFitDesMax, FirstFitDesLex. Giá tri thời gian thực hiện và số lượng máy vật lý được dùng của thuật toán Best Fit* được lấy từ giá tri trung bình cộng giá tri của 03 thuật toán BestFitDesSum, BestFitDesMax, BestFitDesLex như đã trình bày trong Bảng 2.1 và Bảng 2.2, tương ứng. Bảng 2.3: số lượng máy vật lý đã sử dụng khi thực hiện thuật toán MDRAVS-MMAS và các thuật toán khác. Tên Số lương dịch vụ ảo hóa thuật toán N=32 dịch vụ N=64 dịch vụ N=128 dịch vụ N=256 dịch vụ N=512 dịch vụ First Fit* 24 47 90 174 344 Best Fit* 24 47 89,7 172,7 338,3 MDRAVS-MMAS 24 47 88 172 323 Bảng 2.4: Thời gian thực hiện của thuật toán MDRAVS-MMAS và các thuật toán khác. Tên thuật toán SỐ lương dich vụ ảo hóa N=32 dich vụ N=64 dich vụ N=128 dich vụ N=256 dich vụ N=512 dich vụ First Fit* 0,000117 0,001113 0,002617 0,009450 0,028377 Best Fit* 0,001240 0,002400 0,006553 0,036447 0,129133 MDRAVS-MMAS 0,001000 0,003000 0,020890 0,040120 0,174100 Hình 2.5: Đồ thi biểu diễn số lượng máy vật lý đã sử dụng khi thực hiện thuật toán MDRAVS-MMAS và các thuật toán khác. Từ kết quả thực nghiệm, thấy rằng: Thời gian thực hiện thuật toán và số lượng máy vật lý được dùng tỷ lệ thuận với số lượng dich vụ ảo hóa, thời gian thực hiện thuật toán tưìng đối nhỏ và có thể áp dụng trong thực tế. Khi số lượng dich vụ ảo hóa nhỏ thì giá tri của hai thước đo này không khác biệt nhau nhiều giữa các thuật toán. Ngược lại, trong trường hợp số lượng dich vụ ảo hóa lớn (N > 256) thì có sự khác biệt, trong đó thuật toán MDRAVS-MMAS cho giá tri số lượng máy vật lý được dùng ít hìn (tức là, giá tri hàm mục tiêu tốt hìn) thuật toán First Fit* và Best Fit*. Tuy nhiên, thời gian thực hiện của thuật toán MDRAVS-MMAS cao hìn thuật toán First Fit* và Best Fit*. Hình 2.6: Đồ thi biểu diễn thời gian thực hiện thuật toán MDRAVS-MMAS và các thuật toán khác Nguyên nhân khác biệt này được lý giải như sau: Thuật toán MDRAVS-MMAS hoạt động theo phương pháp tìm kiếm tối ưu toàn cục, sử dụng các tham số như: số kiến numAnt, số lần lặp numLoop nên ảnh hưởng đến thời gian thực thi của thuật toán. Hơn nữa, đối với các bài toán kích thước lớn (trường hợp này là số lượng dich vụ ảo hóa lớn), sử dụng các thuật toán tối ưu truyền thống (ở đây là 02 thuật toán First Fit* và Best Fit*) sẽ không đủ về mặt thời gian tính toán, thậm chí không tìm được giải pháp tối ưu. Do đó, những thuật toán thuộc lớp Meta-Heuristic như thuật toán MDRAVS-MMAS phù hợp để giải các bài toán kích thước lớn và có thể tìm được giải pháp tối ưu hoặc gần tối ưu trong thời gian đa thức. Tiểu kết Chương 2 Dựa trên mô hình hệ thống cung cấp tài nguyên cho dich vụ ảo hóa do Mark Stillwell và các cộng sự [100] đề xuất. Trên cơ sở đó, đề xuất mô hình toán học của vấn đề cung cấp tài nguyên đa chiều (xét nhiều loại tài nguyên, như: CPU, RAM, Disk,...) cho dich vụ ảo hóa từ nền tảng máy chủ chia sẻ đồng nhất, với mục tiêu tối thiểu số lượng máy vật lý cần dòng. Đây là bài toán cung cấp tài nguyên hạn chế thuộc lớp bài toán NP-đầy đủ. Đe ước lượng bài toán, luận án thực hiện các thuật toán để giải, cụ thể: Dựa trên các thuật toán chuẩn giải bài toán Vector Packing, áp dụng các thuật toán First Fit và Best Fit [63], [72] để đưa ra 06 phiên bản khác nhau của thuật toán. Các thuật toán này đã công bố trong công trình số 1; Đề xuất thuật toán MDRAVS-MMAS trên cì sở thuật áp dụng thuật toán tối ưu Hệ kiến Max-Min [105]. Thuật toán MDRAVS-MMAS đã công bố trong công trình số 2. Các thuật toán được đánh giá thông qua một loạt các kịch bản mô phỏng trên 4500 mẫu dữ liệu, các dữ liệu thực nghiệm được tạo ra theo phưìng pháp xác suất ngẫu nhiên, kết quả so sánh giữa các thuật toán dựa trên 02 thước đo: số lượng máy vật lý cần dùng (hàm mục tiêu của bài toán) và thời gian thực hiện của thuật toán. Chưìng trình mô phỏng các thuật toán được thực hiện bằng ngôn ngữ C++ và thời gian thực hiện thuật toán được đo trên máy tính đìn có bộ vi xử lý Intel Core Duo 1.86 GHz, RAM 2Gb. Các kết quả thực nghiệm cho thấy: Độ phức tạp của các thuật toán thực hiện trong thời gian đa thức; Khi số lượng (miền của bài toán) dịch vụ ảo hóa nhỏ thì các thước đo trên các thuật toán này không khác nhau nhiều. Trường hợp, số dịch vụ lớn thì kết quả có sự khác nhau, đó là: thuật toán MDRAVS-MMAS cho số lượng máy vật lý cần dùng ít hìn (tức là, tiết kiệm tài nguyên hìn) 02 thuật toán First Fit* và Best Fit*. Hìn nữa, thời gian thực hiện của các thuật toán nhỏ, nên phù hợp khi áp dụng triển khai trong hệ thống tính toán đám mây thực tế. Chương 3. CUNG CẤP TÀI NGUYÊN CHO DỊCH VỤ ẢO HÓA TỪ NỀN TẢNG MÁY CHỦ CHIA SẺ KHÔNG ĐỒNG NHẤT Nền tảng máy chủ chia sẻ tại các trung tâm dữ liệu trong hệ thống tính toán đám mây có 02 loại: nền tảng máy chủ chia sẻ đồng nhất và nền tảng máy chủ chia sẻ không đồng nhất. Hơn nữa, nhu cầu sử dụng các máy vật lý cho dịch vụ ảo hóa tại các trung tâm dữ liệu ngày càng tang. Điều này, dẫn đến việc gia tang nang lượng tiêu thụ trong các trung tâm dữ liệu sẽ ảnh hưởng đến tuổi thọ, hiệu suất của hệ thống và gia tang khí thải CO2 có thể trở thành mối đe dọa đối với môi trường sống. Vì thế, trên cơ sở mô hình hệ thống được trình bày tại Mục 1.7.1, nội dung của chương này mở rộng bài toán đã trình bày ở Chương 2 để nghiên cứu mô hình tài nguyên và nhu cầu tài nguyên trong nền tảng máy chủ chia sẻ không đồng nhất. Qua đó, xây dựng mô hình toán học của vấn đề cung cấp tài nguyên cho dịch vụ ảo hóa từ nền tảng máy chủ chia sẻ không đồng nhất với mục tiêu tối thiểu năng lượng tiêu thụ của hệ thống. Đề xuất thuật toán ECRAVS-PSO và ECRAVS-SA để giải. Giá trị hàm mục tiêu và thời gian thực hiện các thuật toán này được so sánh với thuật toán FFD [101] trong môi trường mô phỏng đám mây CloudSim, dữ liệu thực nghiệm được thu thập từ các đám mây thực tế [33], [6]. Nội dung chương này đã trình bày trong các công trình số 3, số 4, số 6 và số 7. Mô hình tài nguyên và nhu cầu tài nguyên Khác với Chương 2 là xét môi trường đồng nhất, nội dung chương này khảo sát một nền tảng máy chủ chia sẻ không đồng nhất (Heterogeneous Shared Hosting Platform), gồm cụm các máy vật lý có cấu hình tài nguyên không giống nhau, được kết nối qua thiết bị mạng để chia sẻ tài nguyên nhằm cung cấp cho dịch vụ ảo hóa (trường hợp tĩnh). Vì thế, mô hình tài nguyên và nhu cầu tài nguyên được mở rộng như sau: Xét một nền tảng máy chủ chia sẻ không đồng nhất, gồm tập PM máy vật lý có cấu hình tài nguyên không giống nhau, PM = fj I j = 1,..., M g và M là số lượng máy vật lý. Các máy vật lý được kết nối qua các thiết bị mạng tốc độ cao để chia sẻ tài nguyên nhằm cung cấp cho tập VS dịch vụ ảo hóa, VS = {i I i = 1,..., Ng và N là số lượng dịch vụ ảo hóa với mỗi dịch vụ ảo hóa là ánh xạ tài nguyên từ máy vật lý vào một máy ảo riêng lẻ. Mỗi máy vật lý cung cấp tập D loại tài nguyên, với D = {k I k = 1,..., Dg và D là số loại tài nguyên. Theo tài liệu [101], đối với mỗi loại tài nguyên tại một máy vật lý có thể có một hoặc nhiều thành phần tài nguyên riêng biệt (ví dụ, một hoặc nhiều CPU, một hoặc nhiều RAM,...) và tài nguyên tổng hợp. Nếu một loại tài nguyên k trên một máy vật lý có nhiều thành phần thì tất cả các thành phần đều bằng nhau. Vì thế, tài nguyên của mỗi máy vật lý được biểu diễn bởi một cặp vector (Ce, Ca). Trong đó, Ce = {cek I j = 1,..., M; k =1, ...,Dg là vector tài nguyên thành phần mà mỗi phần tử cek 2 Q+ biểu diễn một phần tử đơn lẻ của loại tài nguyên k trên máy vật lý j và Ca = {cak I j = 1,..., M; k = 1,..., Dg là vector tài nguyên tểng hợp mà mỗi phần tử cak 2 Q+ biểu diễn tổng các phần tử đơn lẻ của loại tài nguyên k trên máy vật lý j . Tương tự, nhu cầu tài nguyên của dịch vụ ảo hóa cũng được biểu diễn bởi cặp vector, bao gồm: vector nhu cầu tài nguyên thành phần và vector nhu cầu tài nguyên tổng hợp. Hơn nữa, nhu cầu tài nguyên của dịch vụ ảo hóa có hai loại: nhu cầu tất yếu và nhu cầu tùy biến. Trong đó: Nhu cầu tất yếu tài nguyên loại k của dịch vụ ảo hóa i được biểu diễn bởi một cặp vector (Re, Ra) để biểu thị nhu cầu tài nguyên cần thiết để cung cấp tài nguyên cho dịch vụ ảo hóa ở mức tối thiểu chấp nhận được. Nếu nhu cầu tài nguyên tất yếu không được đáp ứng thì việc cung cấp tài nguyên thất bại. Trong đó, Re = {rfk I i = 1,...,N; k = 1,...,Dg và Ra = {r“k I i = 1,..., N; k = 1,..., Dg là các vector biểu thị nhu cầu tài nguyên tất yếu thành phần và nhu cầu tài nguyên tất yếu tểng hợp, tương ứng. úk 2 Q+ là phần tử nhu cầu tất yếu thành phần loại tài nguyên k của dịch vụ ảo hóa i và r“k 2 Q+ là phần tử nhu cầu tất yếu tểng hợp loại tài nguyên k của dịch vụ ảo hóa i. Nhu cầu tùy biến tài nguyên loại k của dịch vụ ảo hóa i được biểu diễn bởi một cặp vector (Fe, Fa). Trong đó, vector thứ nhất Fe = {fa I i = 1,..., N; k = 1,..., Dg chứa các phần tử fa 2 Q+ để biểu diễn nhu cầu tùy biến thành phần đối với loại tài nguyên k của dịch vụ ảo hóa i. Vector thứ hai Fa = {fa I i = 1,..., N; k = 1,..., Dg chứa các phần tử fa 2 Q+ để biểu diễn nhu cầu tài nguyên tùy biến tểng hợp đối với loại tài nguyên k của dịch vụ ảo hóa i. Như vậy, cặp vector nhu cầu tùy biến (Fe, Fa) biểu thị tài nguyên bổ sung cần thiết để cung cấp tài nguyên cho dịch vụ ảo hóa ở mức tối đa. Nên, nhu cầu tùy biến có thể được biểu diễn bởi tích giữa nhu cầu tùy biến với vector hệ so bể sung Q = {qij I i =1;...; N; j = 1;...; Mg và được gọi là nhu cầu tùy biến ràng buộc. Trong đó, mỗi phần tử qij 2 Q+ gọi là hệ so bể sung nhu cầu tùy biến của dịch vụ ảo hóa i đối với máy vật lý j. Vì thế, cặp vector biểu diễn nhu cầu tài nguyên của dịch vụ ảo hóa là (Re + Q X Fe; Ra + Q X F“). Cung cấp tài nguyên bị lỗi nếu nhu cầu tài nguyên tổng hợp của dịch vụ ảo hóa vượt quá dung lượng tài nguyên máy vật lý. Tương tự như [101], luận án cũng giả sử rằng nhu cầu tài nguyên thành phần của dịch vụ ảo hóa không vượt quá dung lượng tài nguyên thành phần của máy vật lý. Hình 3.1: Tài nguyên của 2 máy vật lý và nhu cầu tài nguyên của 1 dịch vụ ảo hóa. Hình 3.1, minh họa về mô hình tài nguyên và nhu cầu tài nguyên, gồm có 02 máy vật lý và một dịch vụ ảo hóa. Trong đó, máy vật lý A gồm có 04 lõi CPU (tức là, 04 tài nguyên CPU thành phần) và 01 bộ nhớ RAM (tức là, 01 tài nguyên RAM thành phần). Như vậy, cặp vector tài nguyên CPU của máy vật lý A là (1,0; 4,0) và cặp vector tài nguyên RAM của máy vật lý A là (2,0; 2,0). Máy vật lý B có 02 lõi CPU và 01 RAM nên cặp vector tài nguyên CPU của máy vật lý B là (1,0; 2,0) và cặp vector tài nguyên RAM của máy vật lý B là (1,0; 1,0). Đối với dịch vụ ảo hóa, cặp vector nhu cầu tài nguyên CPU là (0; 5+qij X 0; 5; 2; 0 + qij X 1; 0), cặp vector nhu cầu tài nguyên RAM là (1; 0 + qij X 0; 0; 1; 0 + qij X 0; 0). Nếu trường hợp qij = 1; 0 thì chỉ máy vật lý A đáp ứng nhu cầu cung cấp tài nguyên cho dịch vụ ảo hóa. Ngược lại, qij = 0; 5, thì máy vật lý B cũng đáp ứng việc cung cấp tài nguyên nhưng với chi phí tài nguyên giảm. Mô hình năng lương tiêu thụ Như đã trình bày trong Mục 3.1, gọi PM là tập các máy vật lý có cấu hình tài nguyên không giống nhau, PM = {j I j = 1;...; Mg và M là số lượng máy vật lý. VS là tập dịch vụ ảo hóa, VS = {i I i = 1;...; Ng và N là số lượng dịch vụ ả

Các file đính kèm theo tài liệu này:

  • docxluan_an_cung_cap_tai_nguyen_cho_dich_vu_ao_hoa_dua_tren_nen.docx
  • pdftoanvanluanan_phamnguyenminhnhut_31355_9561_2172976.pdf
Tài liệu liên quan