Tóm tắt 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
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
***
PHẠM NGUYỄN MINH NHỰT
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
CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 62.48.01.01
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT
ĐÀ NẴNG, 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
***
Người hướng dẫn khoa học:
1. PGS. TS. Lê Văn Sơn
2. PGS. TS. Đoàn Văn Ban
Phản biện 1: GS. TS. Nguyễn Thúc Hải
Phản biện 2: GS. TS. Nguyễn Thanh Thủy
Phản biện 3: PGS. TS. Võ Thanh Tú
Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Cơ sở họp
tại: Đại học Đà Nẵng.
Vào hồi: 08 giờ 30 ngày 12 tháng 7 năm 2018
Có thể tìm hiểu luận án tại:
- Thư viện Quốc gia Việt Nam.
- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng.
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC
CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN
1. Phạm Nguyễn Minh Nhựt, Đoàn Văn Ban, Lê Văn Sơn. Mô hình nền tảng máy
chủ chia sẻ và bài toán Vector Packing trong cung cấp tài nguyên cho dịch vụ ảo
hóa, Tạp chí Tin học và Điều khiển học, 30(1):63-72, 2014.
2. Phạm Nguyễn Minh Nhựt, Lê Văn Sơn, Đoàn Văn Ban. Thuật toán Max-Min Ant
System trong cung cấp tài nguyên cho dịch vụ ảo hóa từ nền tảng máy chủ chia
sẻ. Hội thảo quốc gia lần thứ XVII: Một số vấn đề chọn lọc của Công nghệ thông
tin và Truyền thông, trang 331-336, 2014.
3. Nguyen Minh Nhut Pham, Thu Huong Nguyen, Van Son Le. Resource Allocation
for Virtual Service Based on Heterogeneous Shared Hosting Platforms. In the 8th
Asian Conference Intelligent Information and Database Systems, 9622:51-60.
Springer, 2016.
4. Phạm Nguyễn Minh Nhựt, Lê Văn Sơn, Hoàng Bảo Hùng. Thuật toán PSO cải
tiến trong 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ẻ không đồng nhất. Chuyên san Các công trình nghiên cứu, phát triển và ứng
dụng Công nghệ thông tin và Truyền thông, 2(36):80-95, 2016.
5. Nguyen Minh Nhut Pham, Van Son Le. Applying Ant Colony System Algorithm
in Multi-Objective Resource Allocation for Virtual Services. Journal of
Information and Telecommunication, 1(4):319-333. Taylor & Francis, 2017.
6. Nguyen Minh Nhut Pham, Van Son Le, Ha Huy Cuong Nguyen. Energy-Efficient
Resource Allocation for Virtual Service in Cloud Computing Environment. In the
4th International conference on information system design and intelligent
applications, Advances in Intelligent Systems and Computing, vol 672: 126-136.
Springer, 2018.
7. Nguyen Minh Nhut Pham, Van Son Le, Ha Huy Cuong Nguyen. Energy Efficient
Resource Allocation for Virtual Service Based on Heterogeneous Shared Hosting
Platforms in Cloud Computing. Cybernetics and Information Technologies,
17(3): 47-58. BAS, 2017.
MỞ ĐẦU
1. Lý do chọn đề tài
Mô hình tính toán đám mây (Cloud Computing) phát triển dựa trên
kết quả việc thích ứng của Internet cũng như những phát triển công nghệ
trong các lĩnh vực: tính toán lưới (Grid Computing), tính toán cụm (Cluster
Computing), tính toán tiện ích (Utility Computing) và tính toán tự động
(Automatic Computing). Mục đích của các hệ thống này là tạo ra một nền
tảng tính toán hiệu quả, sử dụng chung các tài nguyên máy tính được tích
hợp thông qua các thiết bị phần cứng, mạng và phần mềm nhằm nâng cao
hiệu suất, khả năng chịu lỗi, đảm bảo tính sẵn sàng về tài nguyên từ các
máy tính đơn lẻ.
Những đặc điểm của hệ thống tính toán đám mây đã đem lại nhiều lợi
ích cho người dùng và thuận lợi cho nhà cung cấp dịch vụ trên đám mây.
Tuy nhiên, những thách thức trong việc tối ưu hệ thống cần được quan tâm
nghiên cứu, như: tiết kiệm tài nguyên và năng lượng tiêu thụ trong cung
cấp tài nguyên, tối ưu các mô hình chi phí, khả năng cân bằng tải,... là
những chủ đề nghiên cứu quan trọng.
Đặc biệt, nhu cầu sử dụng các máy vật lý (Physical Machine) để cung
cấp tài nguyên cho dịch vụ ảo hóa (Virtual Service) tại các trung tâm dữ liệu
(Data Center) ngày càng tăng. Điều này, dẫn đến việc sử dụng tài nguyên
các máy vật lý trong các trung tâm dữ liệu tăng, làm tăng năng lượng tiêu
thụ và lượng 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ế, tối ưu trong cung cấp tài nguyên máy vật lý cho dịch vụ ảo hóa
từ nền tảng máy chủ chia sẻ tại các trung tâm dữ liệu, đáp ứng nhu cầu về
chất lượng dịch vụ, khả năng cân bằng tải và giảm thiểu tối đa sử dụng tài
nguyên vật lý, năng lượng tiêu thụ là cần thiết. Đó cũng là mục đích chính
của đề tài: "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".
2. Đối tượng và phạm vi nghiên cứu
Cung cấp tài nguyên trong hệ thống tính toán đám mây có thể được
phân thành 03 lớp bài toán: cung cấp ứng dụng, cung cấp máy ảo và cung
cấp tài nguyên vật lý (máy vật lý) cho dịch vụ ảo hóa để tạo ra các máy ảo
cung cấp cho đám mây. Các lớp bài toán này liên quan đến các đối tượng
sử dụng các dịch vụ trên đám mây như: người dùng, nhà cung cấp dịch vụ
SaaS, nhà cung cấp dịch vụ PaaS và nhà cung cấp cấp dịch vụ IaaS.
Trong phạm vi và đối tượng nghiên cứu, luận án tập trung nghiên cứu
mô hình cung cấp tài nguyên máy vật lý cho dịch vụ ảo hóa để tạo ra các
máy ảo, đáp ứng nhu cầu của nhà cung cấp dịch vụ IaaS. Nghiên cứu các
thuật toán Meta Heuristic, như: thuật toán Tối ưu bầy đàn, thuật toán Tối
ưu đàn kiến và thuật toán Mô phỏng luyện kim nhằm đề xuất các thuật
1
toán để giải bài toán cung cấp tài nguyên cho dịch vụ ảo hóa.
3. Phương pháp nghiên cứu
3.1 Phương pháp nghiên cứu tài liệu
- Tìm kiếm, thu thập về các công trình nghiên cứu đã được công bố
trong các tạp chí, kỷ yếu hội thảo, báo cáo khoa học, sách đã xuất bản về
lĩnh vực cung cấp tài nguyên trong hệ thống tính toán đám mây;
- Trên cơ sở các tài liệu sưu tâp, thực hiện phân tích, tổng hợp và đề
xuất bài toán nghiên cứu. Đồng thời, dựa trên các tài liệu về thuật toán
Tối ưu bầy đàn, Tối ưu đàn kiến và Mô phỏng luyện kim đề xuất các thuật
toá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ẻ
trong tính toán đám mây.
3.2 Phương pháp thực nghiệm khoa học
- Tạo và lựa chọn dữ liệu thực nghiệm;
- Cài đặt và đánh giá các thuật toán đề xuất trên tập dữ liệu thực
nghiệm. Sử dụng công cụ mô phỏng hệ thống tính toán đám mây CloudSim
để triển khai thử nghiệm, phân tích và đánh giá hiệu suất của các thuật
toán đề xuất.
4. Ý nghĩa thực tiễn
- Xây dựng mô hình cung cấp tài nguyên vật lý cho dịch vụ ảo hóa từ
nền tảng máy chủ chia sẻ để tạo ra các máy ảo và đề xuất các thuật toán
để giải, góp phần nâng cao hiệu suất cung cấp tài nguyên của lớp dịch vụ
IaaS trong hệ thống tính toán đám mây.
- Luận án có thể được sử dụng làm tài liệu tham khảo cho sinh viên,
người đọc quan tâm về vấn đề cung cấp tài nguyên cho dịch vụ ảo hóa và
nghiên cứu các phương pháp Meta heuristic, phương pháp xấp xỉ để giải
các bài toán tối ưu.
5. Đóng góp chính của luận án
(1) Đề xuất mô hình toán học của vấn đề cung cấp tài nguyên đa chiều
cho dịch 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 dùng. Áp dụng thuật toán Hệ kiến Max-Min,
đề xuất thuật toán MDRAVS-MMAS để ước lượng và so sánh với thuật toán
Firt Fit, Best Fit thông qua 02 thước đo: số lượng máy vật lý cần dùng và
thời gian thực hiện thuật toán. Kết quả thực nghiệm nhận thấy rằng: thuật
toán đề xuất MDRAVS-MMAS cho giá trị hàm mục tiêu tốt hơn (tức là, số
lượng máy vật lý cần dùng ít hơn) thuật toán First Fit, Best Fit. Độ phức
tạp của thuật toán đề xuất thực hiện trong thời gian đa thức.
(2) Đề xuất mô hình toán học cho vấn đề cung cấp tài nguyên đa chiều
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. Áp dụng thuật toán Tối
2
ưu bầy đàn, cải tiến và đề xuất thuật toán ECRAVS-PSO. Áp dụng thuật
toán Mô phỏng luyện kim, đề xuất thuật toán ECRAVS-SA để ước lượng
và so sánh với thuật toán với thuật toán Firt Fit Decreasing (FFD) thông
qua 02 thước đo: năng lượng tiêu thụ và thời gian thực hiện thuật toán. Kết
quả thực nghiệm nhận thấy rằng: 02 thuật toán đề xuất ECRAVS-PSO và
ECRAVS-SA cho giá trị hàm mục tiêu tốt hơn (tức là, năng lượng tiêu thụ
ít hơn) thuật toán FFD. Độ phức tạp của các thuật toán thực hiện trong
thời gian đa thức.
(3) Xây dựng mô hình toán học cho việc cung cấp tài nguyên đa mục
tiêu, gồm: mục tiêu cân bằng tải trên các máy vật lý và mục tiêu tối thiểu
năng lượng tiêu thụ. Áp dụng thuật toán Hệ đàn kiến, đề xuất thuật toán
MORA-ACS để ước lượng và so sánh với thuật toán Round Robin thông qua
03 thước đo: năng lượng tiêu thụ, độ lệch chuẩn và thời gian thực hiện thuật
toán. Kết quả thực nghiệm nhận thấy rằng: thuật toán đề xuất MORA-ACS
cho giá trị hàm mục tiêu tốt hơn (tức là, năng lượng tiêu thụ ít hơn và khả
năng cân bằng tải tốt hơn) thuật toán Round Robin. Độ phức tạp của thuật
toán thực hiện trong thời gian đa thức.
7. Bố cục luận án
Ngoài phần mở đầu và kết luận, nội dung của luận án được tổ chức gồm
có 04 chương với cấu trúc như sau:
- 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.
- 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.
- 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.
- 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.
Các kết quả của luận án được công bố trong 07 công trình khoa học.
Trong đó, có 01 bài đăng trong kỷ yếu hội thảo quốc gia, 02 bài đăng trong
các tạp chí chuyên ngành trong nước, 02 bài đăng trong tạp chí quốc tế và
02 bài đăng tại các hội thảo quốc tế chuyên ngành.
3
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
1.1.Hệ thống tính toán đám mây
Peter Mell và Tim Grance định nghĩa mô hình hệ thống tính toán đám
mây như sau: "Một mô hình cho phép việc truy cập mạng một cách rộng rãi,
tiện lợi và theo nhu cầu nhằm chia sẻ tài nguyên tính toán (ví dụ: mạng,
máy chủ, thiết bị lưu trữ, các ứng dụng và dịch vụ) và có thể được cấp phát
nhanh với khả năng tối thiểu các nỗ lực quản lý, cung cấp dịch vụ. Mô hình
đám mây gồm có 5 đặc điểm chính, 3 mô hình dịch vụ và 4 mô hình triển
khai."
- 05 đặc điểm chính của đám mây, gồm: truy cập mạng diện rộng, dịch
vụ cung cấp tự động theo nhu cầu, tổng hợp tài nguyên, tính co dãn nhanh
và dịch vụ có thể đo lường.
- 03 mô hình dịch vụ, đó là: cơ sở hạ tầng như một dịch vụ, nền tảng
như một dịch vụ và phần mềm như một dịch vụ. Ngoài ra, phần cứng như
một dịch vụ cũng được xem như là một mô hình dịch vụ của hệ thống tính
toán đám mây.
- Phân loại dựa vào tiêu chí triển khai, có 04 loại đám mây: đám mây
riêng, đám mây công cộng, đám mây cộng đồng và đám mây lai.
1.2.Yêu cầu và thách thức của hệ thống tính toán đám mây
- Yêu cầu: mục đích của hệ thống, các dịch vụ, sự ảo hoá, đàm phán
QoS động, giao diện truy cập người dùng, dịch vụ giá trị gia tăng.
- Thách thức: bảo mật, mô hình chi phí, mô hình tính phí, tiết kiệm tài
nguyên, thỏa thuận mức dịch vụ, di trú máy ảo.
1.3.Máy ảo
Theo Goldberg, máy ảo được định nghĩa là "một bản sao cô lập của một
hệ thống máy tính thực, trong đó tập các bộ vi xử lý ảo được thực hiện trên
bộ vi xử lý máy chủ thực một cách tự nhiên".
1.4.Công nghệ ảo hóa
Công nghệ ảo hóa bao gồm việc kết hợp hoặc phân chia tài nguyên tính
toán để biểu diễn trong một hoặc nhiều môi trường hoạt động. Trong kiến
trúc phân tầng của công nghệ ảo hóa, tầng ảo hóa sẽ phân vùng tài nguyên
hiện hành của một hoặc nhiều máy chủ vật lý bên dưới thành nhiều hoặc
một máy ảo, tương ứng. Hiện nay, công nghệ ảo hóa có 02 loại: ảo hóa phân
chia còn gọi là ảo hóa máy chủ và ảo hóa tích hợp.
1.5.Công cụ mô phỏng hệ thống tính toán đám mây
Triển khai đám mây thực tế hoặc sử dụng đám mây thương mại để thử
nghiệm là rất tốn kém. Vì thế, sử dụng các công cụ mô phỏng có các chức
4
năng tương tự như đám mây thực tế để triển khai nghiên cứu thử nghiệm
là cách thức thông dụng. Dựa trên đặc tính chi phí, chức năng và yêu cầu
thử nghiệm của đề tài, luận án chọn công cụ CloudSim để triển khai thực
nghiệm, đánh giá thuật toán giải các bài toán đề xuất.
1.6.Cung cấp tài nguyên trong hệ thống tính toán đám mây
Mô hình cung cấp tài nguyên trong tính toán đám mây được trình bày
như Hình 1.1. Trong đó, V là số ứng dụng và mỗi ứng dụng có T tác vụ.
Mỗi ứng dụng nhận các yêu cầu từ các người dùng. Các ứng dụng chạy trên
N máy ảo và các máy ảo này được cung cấp tài nguyên từ M máy vật lý.
Theo mô hình này, có 03 đối tượng tham gia hoạt động trong một hệ thống
Hình 1.1: Mô hình cung cấp tài nguyên trong hệ thống tính toán đám mây.
tính toán đám mây, bao gồm: nhà cung cấp đám mây (cloud provider), nhà
cung cấp ứng dụng (application provider) và người dùng đầu cuối (User).
Trong đó, nhà cung cấp đám mây sẽ cung cấp tài nguyên phần cứng và
tài nguyên được ảo hóa chạy trên nền tài nguyên phần cứng. Người dùng
đầu cuối chỉ truy cập trực tiếp vào tài nguyên đã được ảo hóa. Nhà cung
cấp ứng dụng sẽ chọn lựa các máy ảo và cài đặt môi trường hoạt động trên
máy ảo như: hệ điều hành khách, các phần mềm triển khai ứng dụng thông
qua các giao diện ứng dụng được cung cấp từ nhà cung cấp đám mây. Ngoài
ra, nhà cung cấp ứng dụng sẽ phát triển và triển khai các ứng dụng trên hệ
thống máy ảo đến người dùng đầu cuối.
Như vậy, cung cấp tài nguyên trong đám mây có 03 loại: cung cấp ứng
dụng, cung cấp máy ảo và cung cấp tài nguyên vật lý cho dịch vụ ảo hóa.
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
1.7.1.Mô hình hệ thống cung cấp tài nguyên cho dịch vụ ảo hóa
Mục tiêu của luận án là nghiên cứu bài toán cung cấp tài nguyên tĩnh,
mô hình hệ thống cung cấp tài nguyên tĩnh cho dịch vụ ảo hóa dựa trên
nền tảng máy chủ chia sẻ do Mark Stillwell và các cộng sự đề xuất, được
trình bày như Hình 1.2.
5
Hình 1.2: Mô hình cung cấp tài nguyên cho dịch vụ ảo hóa từ nền tảng máy
chủ chia sẻ.
- Nền tảng máy chủ chia sẻ (Shared Hosting Platform): gồm cụm các
máy vật lý (Physical Machine) đượ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 (Virtual Service). Nếu các máy
vật lý có cấu hình tài nguyên giống nhau thì gọi là nền tảng máy chủ chia
sẻ đồng nhất (Homogeneous Shared Hosting Platform). Ngược lại, các máy
vật lý có cấu hình tài nguyên không giống nhau thì gọi là nền tảng máy chủ
chia sẻ không đồng nhất (Heterogeneous Shared Hosting Platform).
- Dịch vụ ảo hóa (Virtual Service): mỗi dịch vụ ảo hóa là một ánh xạ
tài nguyên f : S → R. Sao cho, với sk ∈ S và rk ∈ R thì f(sk) = rk nếu
rk biểu diễn tài nguyên thực tương ứng tài nguyên ảo sk của tài nguyên
loại k. Trong đó, S = {sk|k = 1...D} là tập tài nguyên ảo trên máy ảo,
R = {rk|k = 1, ..., D} là tập tài nguyên thực trên các máy vật lý và D số
loại tài nguyên.
- Bộ giám sát máy ảo (Virtual Machine Manager): giám sát, quản lý
các máy ảo thực thi trên máy vật lý.
- Hệ thống quản lý các máy ảo (Virtual Machine Manager System):
điều khiển các các Bộ giám sát máy ảo nhằm xác định tỷ lệ tài nguyên tiêu
thụ trong các máy ảo, di trú các máy ảo từ máy vật lý này sang máy vật lý
khác trong hệ thống.
- Bộ cung cấp tài nguyên (Resource Allocator): cung cấp tài nguyên
cho dịch vụ ảo hóa để đáp ứng nhu cầu tạo ra các máy ảo.
Theo mô hình này, khi hệ thống nhận được yêu cầu cung cấp cụm máy
ảo (yêu cầu tĩnh) để thực thi các ứng dụng trên đám mây, hệ thống sẽ đáp
ứng bằng cách thiết lập một hoặc nhiều máy ảo để thực thi yêu cầu đó. Các
máy ảo chạy trên máy vật lý dưới sự quản lý của các Bộ giám sát máy ảo
và tiêu thụ tài nguyên theo tỷ lệ khác nhau. Hệ thống quản lý các máy ảo
có nhiệm vụ kiểm soát các Bộ giám sát máy ảo để xác định tỷ lệ tiêu thụ
tài nguyên của các máy ảo. Cuối cùng, Bộ cung cấp tài nguyên dựa trên
nhu cầu tài nguyên của máy ảo và tài nguyên hiện có của máy vật lý để ra
6
quyết định từ chối hoặc đáp ứng yêu cầu, phân chia tỷ lệ tài nguyên đến
các dịch vụ ảo hóa để đáp ứng tài nguyên cho máy ảo.
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
Nghiên cứu cải tiến 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ần dùng thì phải xét trên nhiều loại
tài nguyên (còn gọi là tài nguyên đa chiều - Multi Dimensional Resource).
Đề xuất thuật toán để giải và so sánh với thuật toán FFD là cần thiết.
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 năng lượng tiêu thụ
Nghiên cứu cải tiến 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 năng lượng tiêu thụ cần tính đến việc tiêu thụ năng
lượng trên tất cả các tài nguyên và xét trong nền tảng máy chủ chia sẻ
không đồng nhất là cần thiết.
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
Nghiên cứu cải tiến mô hình 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 cần xét đến mô hình đa mục
tiêu: mục tiêu tối thiểu năng lượng tiêu thụ và mục tiêu cân bằng tải giữa
các máy vật lý. Thiết kế thuật toán để giải và so sánh với thuật toán Round
Robin là cần thiết.
1.8.Mục tiêu và nội dung của luận án
1.8.1.Mục tiêu nghiên cứu của luận án
Mục tiêu của luận án là: đề xuất giải pháp tối ưu cho bài toán cung cấp
tài nguyên vật lý đa chiều (nhiều loại tài nguyên, như: CPU, RAM, Disk,...)
từ nền tảng máy chủ chia sẻ cho dịch vụ ảo hóa tại trung tâm dữ liệu của
hệ thống tính toán đám mây, đảm bảo tối thiểu tài nguyên máy vật lý được
sử dụng, tối thiểu năng lượng tiêu thụ của hệ thống và đảm bảo cân bằng
tải trên các máy vật lý.
1.8.2.Nội dung nghiên cứu của luận án
Nội dung nghiên cứu được triển khai thông qua 03 bài toán cụ thể như
sau:
- Bài toán 1: Cung cấp tài nguyên đa chiều cho dịch 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 (Multi-Dimensional Resource Allocation for Virtual Services –
MDRAVS).
- Bài toán 2: Cung cấp tài nguyên đa chiều 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ụ (Energy Consumption Resource Allocation for Virtual Services -
7
ECRAVS). Đây là sự mở rộng của Bài toán 1, xét trong nền tảng máy chủ
chia sẻ không đồng nhất và thay đổi mục tiêu tối ưu của Bài toán 1.
- Bài toán 3: Cung cấp tài nguyên đa chiều, đ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 (Multi-Objective
Resource Allocation - MORA). Với 02 mục tiêu tối ưu: tối thiểu năng lượng
tiêu thụ và đảm bảo cân bằng tải. Bài toán này là sự mở rộng Bài toán 2.
Để triển khai nghiên cứu, luận án xem xét tiếp cận trên các phương diện
cụ thể như sau:
- Áp dụng mô hình hệ thống cung cấp tài nguyên được trình bày như
(Hình 1.2);
- Xây dựng mô hình toán học dưới dạng bài toán tối ưu;
- Đề xuất các thuật toán Meta-heuristic để giải bài toán;
- Xây dựng, lựa chọn dữ liệu thực nghiệm phù hợp với đám mây thực
tế.
1.9.Tiểu kết Chương 1
Trong nội dung của chương này, luận án đã trình bày tổng quan về hệ
thống tính toán đám mây, các mô hình dịch vụ và mô hình triển khai của
nó. Công nghệ ảo hóa và máy ảo chính là trái tim của hệ thống tính toán
đám mây cũng được trình bày. Dựa trên các mô hình và công nghệ ảo hóa,
luận án đã đưa ra các kết quả khảo sát toàn diện về các vấn đề cung cấp
tài nguyên trong đám mây cũng như các bài toán liên quan đến nó.
Cung cấp tài nguyên trong hệ thống tính toán đám mây có thể được
phân thành 03 lớp bài toán: bài toán cung cấp ứng dụng, bài toán cung cấp
máy ảo và bài toán cung cấp tài nguyên vật lý (máy vật lý) cho dịch vụ ảo
hóa để tạo ra các máy ảo cung cấp cho đám mây.
Tuy nhiên, hầu hết các giải pháp, các mô hình tập trung vào các bài
toán cung cấp ứng dụng và cung cấp máy ảo, chỉ có số ít nghiên cứu bài
toán cung cấp tài nguyên vật lý nhưng phần lớn chỉ xét đến hai loại tại
nguyên là CPU và bộ nhớ. Vì thế, luận án tập trung nghiên cứu bài toán
cung cấp tài nguyên vật lý đa chiều cho dịch vụ ảo hóa trong hệ thống tính
toán đám mây, đảm bảo tối thiểu số máy vật lý cần dùng, tối thiểu năng
lượng tiêu thụ và cân bằng tải là cần thiết.
Bên cạnh đó, để giảm thiểu rủi ro khi triển khai đám mây và chi phí
thực nghiệm, việc nghiên cứu các công cụ mô phỏng đám mây để cài đặt,
thử nghiệm và đánh giá các thuật toán trước khi áp dụng vào các đám mây
thực tế là cách thức thông dụng hiện nay. Vì thế, luận án cũng đã khảo
sát toàn diện và đánh giá các công cụ mô phỏng đám mây thông dụng hiện
có. Dựa trên yêu cầu chi phí, chức năng của công cụ mô phỏng CloudSim
và yêu cầu thử nghiệm của đề tài, luận án chọn công cụ CloudSim để triển
khai thực nghiệm, đánh giá các thuật toán giải các bài toán đề xuất.
8
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
2.1.Mô hình tài nguyên và nhu cầu tài nguyên
Để đáp ứng nhu cầu tài nguyên cho dịch vụ ảo hóa, mỗi máy vật lý cung
cấp một số loại tài nguyên, như: CPU, RAM, Disk, ... Mỗi dịch vụ ảo hóa
có hai loại nhu cầu tài nguyên: nhu cầu tất yếu và nhu cầu tùy biến.
- Nhu cầu tất yếu biểu thị phần cụ thể của tài nguyên yêu cầu, dịch vụ
không hưởng lợi từ phần lớn hơn và không thể hoạt động với phần nhỏ hơn
từ tài nguyên được cung cấp.
- Nhu cầu tùy biến biểu thị phần tối đa của tài nguyên mà dịch vụ có
thể sử dụng, dịch vụ không hưởng lợi từ phần lớn hơn nhưng có thể hoạt
động với phần nhỏ hơn với chi phí giảm.
- Tỷ số giữa phần tài nguyên được cung cấp và phần tài nguyên nhu cầu
tùy biến gọi là năng suất dịch vụ (NSDV).
2.2.Bài toán MDRAVS
2.2.1.Phát biểu bài toán MDRAVS
Bài toán cung cấp tài nguyên đa chiều cho dịch vụ ảo hóa (Multi-
Dimensional Resource Allocation for Virtual Services - MDRAVS) từ nền
tảng máy chủ chia sẻ đồng nhất với mục tiêu tối thiểu hóa số máy vật lý
cần dùng được biểu diễn như sau:
xij, yj, aik ∈ {0, 1}, bij, rik ∈ Q+,
∀i ∈ VS, j ∈ PM, k ∈ D
∀i ∈ VS
(2.1)
(2.2)
(2.3)
(2.4)
M
X
xij = 1,
j=1
∀i ∈ VS, j ∈ PM
yj ≥ xij,
N
X
∀k ∈ D, j ∈ PM
(((bij × (1 − aik) + aik) × rik) × xij) ≤ 1,
i=1
M
X
yj → min
(2.5)
j=1
2.2.2.Độ phức tạp bài toán MDRAVS
Định nghĩa 2.1. Gọi bài toán quyết định của MDRAVS là MDRAVS-Dec
được phát biểu: có hay không việc cung cấp tài nguyên từ M máy vật lý
cho N dịch vụ ảo hóa mà mỗi dịch vụ ảo hóa có nhu cầu tài nguyên rik?.
Mệnh đề 2.1. Bài toán quyết định MDRAVS-Dec là bài toán thuộc lớp
NP-đầy đủ.
9
2.3.Đề xuất giải pháp cho bài toán MDRAVS
2.3.1.Giải pháp áp dụng các thuật toán First Fit và Best Fit
Áp dụng các thuật toán First Fit, Best Fit để giải bài toán MDRAVS
được trình bày như Thuật toán 1. Nội dung này công bố trong công trình
số 1.
Thuật toán 1: thuật toán First Fit, Best Fit.
Đầu vào:
• Tập các dịch vụ ảo hóa VS = {i | i = 1, ..., N}, mỗi dịch vụ ảo hóa có các nhu cầu
tài nguyên rik tương ứng với loại nhu cầu aik, tập loại tài nguyên D = {k | k =
1, ..., D}.
• Tập các máy vật lý PM = {j | j = 1, ..., M} với năng suất dịch vụ bij.
Đầu ra : Tập các máy vật lý được dùng (tương ứng xij =1)
1 Dựa trên nhu cầu tài nguyên của tập các dịch vụ ảo hóa VS, xây dựng N vector,
mỗi phần tử của vector là rik.
2 Áp dụng các tiêu chuẩn sắp xếp, sắp xếp giảm dần các phần tử của tập VS.
3 Áp dụng thuật toán First Fit, Best Fit để đặt lần lượt các phần tử của N vector
vào các máy vật lý sao cho thỏa mãn điều kiện:
N
P
∀k ∈ D, j ∈ PM
(((bij × (1 − aik) + aik) × rik) × xij) ≤ 1,
i=1
4 Nếu đáp ứng nhu cầu tài nguyên chưa hoàn tất, quay lại Bước 3.
5 Nếu đáp ứng nhu cầu tài nguyên đã hoàn tất thì đầu ra là tập các máy vật lý được
dùng (đây chính là giá trị của hàm mục tiêu của bài toán MDRAVS).
Trước khi áp dụng các thuật toán First Fit, Best Fit, các phần tử của
tập VS được sắp xếp theo thứ tự giảm dần theo 3 tiêu chuẩn, đó là: Từ
điển, Thành phần cực đại, Tổng cực đại.
Tổ hợp từ hai thuật toán tham lam First Fit, Best Fit với 3 tiêu chí sắp
xếp, có được 06 phiên bản thuật toán, đó là: BestFitDesSum, BestFitDes-
Max, BestFitDesLex, FirstFitDesSum, FirstFitDesMax và FirstFitDesLex.
Cố định số loại tài nguyên D, độ phức tạp của mỗi Thuật toán 1 là
O(N × M)
2.3.2.Đề xuất thuật toán MDRAVS-MMAS
Dựa trên thuật toán Hệ kiến Max-Min đề xuất thuật toán MDRAVS-
MMAS và được trình bày như Thuật toán 2. Nội dung này được trình bày
trong công trình số 2.
- 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ư năng lực tài nguyên của máy vật lý hoàn toàn xác định được.
- Gọi P(numLoop) là xác suất tìm thấy giải pháp của thuật toán sau
numLoop bước lặp, Stutzle và Dorigo chứng minh rằng:
10
Thuật toán 2: Thuật toán MDRAVS-MMAS.
Đầu vào:
• Tập dịch vụ ảo hóa VS với các vector ri∗, ri∗∗. Tập các máy vật lý PM.
• Các tham số: α, β, ρ, pbest, τmax, 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ố máy vật lý được dùng.
1 Khởi tạo các tham số α, β, ρ, pbest, τmax và thiết lập giá trị mùi τij = τmax
2 for nL := 1 → numLoop do
;
3
4
for nA := 1 → numAnt do
j := 1 ;
/* Sử dụng một máy vật lý j, j là chỉ số máy vật lý. */
5
6
BINARY nA := [eij := 0], ∀i ∈ {1, ..., N}, ∀j ∈ {1, ..., M};
while (VS = ∅) do
ꢀ
ꢀ
ꢀ
(
)
M
P
7
VStemp
=
i ∈ VS
xij = 0 ∧ Rj + ri∗ + ri∗∗ ≤ Cj, ∀j ;
ꢀ
ꢀ
j=1
8
9
if (VStemp = ∅) then
Chọn ngẫu nhiên một dịch vụ ảo hóa i ∈ VStemp theo xác
[τij]α×[ηij]β
P
suất pij :=
β , ∀i ∈ VStemp
;
temp [τuj]α×[ηuj
]
u∈VS
10
11
12
eij := 1; VS := VS − {i}; Rj := Rj + (ri∗ + ri∗∗);
else
j := j + 1 ;
/* Sử dụng thêm một máy vật lý j. */
13
So sánh các giải pháp thông qua các ma trận BINARY nA của mỗi con
kiến tạo ra dựa vào giá trị f(Sbest) và lưu giải pháp tốt nhất vào biến
Sbest−vong−lap
;
14
15
if (nL = 1 ∨ Best − Toan − Cuc(Sbest−vong−lap)) then
Sbest−toan−cuc := Sbest−vong−lap ; /* Đây giải pháp tốt nhất toàn cục mới.
Trong đó, hàm Best − Toan − Cuc(Sbest−vong−lap) kiểm tra Sbest−vong−lap có
phải là giải pháp tốt nhất đến thời điểm hiện tại hay không. */
16
17
18
Tính giá trị τmin, τmax
;
foreach (i, j) ∈ (VS × PM) do
τij := ρ × τij + ∆τibjest
;
19
20
if (τij > τmax) then
τij := τmax
;
21
22
if (τij < τmin) then
τij = τmin
;
23 return Giải pháp tốt nhất toàn cục Sbest−toan−cuc
;
∀ε > 0 và nếu numLoop đủ lớn thì numLliomop→∞ P (numLoop) = 1. Vì thế,
thuật toán MDRAVS-MMAS sẽ hội tụ sau numLoop bước lặp.
- 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 × numAnt × N × M).
2.3.3.Thực nghiệm và nhận xét
11
2.3.3.1.Phương pháp mô phỏng
Để đánh giá các thuật toán, sử dụng 4500 mẫu dữ liệu đầu vào được tạo
ra theo phương pháp ngẫu nhiên như trong.
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
Kết quả thực nghiệm các phiên bản của thuật toán First Fit và Best Fit
được trình bày trong Bảng 2.1 và Bảng 2.2.
Bảng 2.1: Thời gian thực hiện các thuật toán First Fit và Best Fit.
Tên thuật toán N=32
N=64 N=128 N=256 N=512
FirstFitDesMax
FirstFitDesLex
FirstFitDesSum
BestFitDesMax
BestFitDesLex
BestFitDesSum
0,00009 0,00107 0,00303
0,01076
0,00827
0,00932
0,03741
0,03500
0,03693
0,03193
0,02529
0,02791
0,03741
0,12253
0,13380
0,00010 0,00114 0,00214
0,00016 0,00113 0,00268
0,00121 0,00254 0,00833
0,00123 0,00232 0,00783
0,00128 0,00234 0,00800
Bảng 2.2: Số máy vật lý đã sử dụng khi thực hiện các thuật toán First Fit
và Best Fit.
Tên thuật toán N=32 N=64 N=128 N=256 N=512
FirstFitDesMax
FirstFitDesLex
FirstFitDesSum
BestFitDesMax
BestFitDesLex
BestFitDesSum
24
24
24
24
24
24
47
47
47
47
47
47
90
90
90
90
89
90
174
174
174
174
170
174
344
344
344
344
327
344
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
Giá trị các tham số của thuật toán MDRAVS-MMAS: α = 1, β =
2, ρ = 0, 9, pbest = 0,05, τmax = 3, numLoop = 5, numAnt = 5. Kết quả
thực nghiệm các thuật toán MDRAVS-MMAS, First Fit và Best Fit trình
bày trong Bảng 2.3 và Bảng 2.4.
Bảng 2.3: Số 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 thuật toán N=32 N=64 N=128 N=256 N=512
FirstFit
BestFit
MDRAVS-MMAS
24
24
24
47
47
47
90
89,7
88
174
172,7
172
344
338,3
323
12
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
FirstFit
N=32
N=64
N=128
N=256
N=512
0,000117 0,001113 0,002617 0,009450 0,028377
0,001240 0,002400 0,006553 0,036447 0,129133
BestFit
MDRAVS-MMAS 0,001000 0,003000 0,020890 0,040120 0,074100
2.4.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 dịch vụ ảo hóa do
Mark Stillwell và các cộng sự đề xuất, luận án đề 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 dịch 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
đủ. Để ướ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 để đư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. 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ì 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 triển khai
trong hệ thống tính toán đám mây thực tế.
13
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
3.1.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 = {j | j = 1, ..., M}
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 = 1, ..., N} và N là số lượng dịch vụ ảo hóa với mỗi dịch
vụ ảo hóa là một máy ảo. Mỗi máy vật lý cung cấp tập D loại tài nguyên,
với D = {k | k = 1, ..., D} và D là số loại tài nguyên.
Đố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. 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 = {cejk |
j = 1, ..., M; k = 1, ..., D} là vector tài nguyên thành phần mà mỗi phần tử
cejk ∈ 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 = {cajk | j = 1, ..., M; k = 1, ..., D} là vector tài nguyên tổng hợp
mà mỗi phần tử cajk ∈ 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 = {riek | i = 1, ..., N; k = 1, ..., D} và
Ra = {riak | i = 1, ..., N; k = 1, ..., D} 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. riek ∈ 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à riak ∈ Q là phần tử nhu cầu tất yếu tổng hợp loại tài
14
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 = {fiek |
+
i = 1, ..., N; k = 1, ..., D} chứa các phần tử fiek ∈ 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 = {fiak | i = 1, ..., N; k = 1, ..., D} chứa các phần tử fiak ∈ 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ệ số bổ sung Q = {qij | i = 1, ..., N; j = 1, ..., M}
+
và được gọi là nhu cầu tùy biến ràng buộc. Trong đó, mỗi phần tử qij ∈ Q
gọi là hệ số 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 × Fe, Ra + Q × Fa).
3.2.Mô hình năng lượng tiêu thụ
Xét hệ thống cung cấp tài nguyên cho dịch vụ ảo hóa như đã trình bày
Mục 1.7.1 (Hình 1.2) và mô hình tài nguyên và nhu cầu tài nguyên cho dịch
vụ ảo hóa như Mục 3.1.
Để ước lượng năng lượng tiêu thụ của các máy vật lý, luận án đề xuất
tính nguồn điện năng tiêu thụ tại máy vật lý j là hàm tuyến tính Pj(uj)
như Công thức (3.1).
ꢁ
ꢂ
Pj (uj) = Pjmax − Pjidle × uj + Pjidle, ∀j ∈ PM
(3.1)
+
+
Trong đó, Pjmax ∈ Q và Pjidle ∈ Q là công suất của máy vật lý j tương
ứng ở trạng thái sử dụng tiện ích tài nguyên tối đa và trạng thái không hoạt
động. Luận án mở rộng công suất được tính cho tất cả các loại tài nguyên,
tức là uj là tổng tiện ích sử dụng của tất cả các loại tài nguyên trên máy
vật lý j, uj ∈ [0, 1] và được tính theo Công thức (3.2).
N
P
(riak + qij × fiak) × xij
D
D
X
X
ujk
cajk
i=1
uj =
=
,
∀j ∈ PM
(3.2)
cajk
k=1
k=1
Do vậy, năng lượng tiêu thụ của M máy vật lý khi cung cấp tài nguyên
cho N dịch vụ ảo hóa trong khoảng thời gian ∆t được tính như Công thức
(3.3).
M
X
E (t) = ∆t ×
P (uj)
(3.3)
j=1
15
3.3.Phát biểu bài toán ECRAVS
Với những phát biểu như Mục 3.1 cùng với các Công thức (3.1), (3.2) và
(3.3) trong Mục 3.2, bài toá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ụ (Energy Consumption Resource Allocation for Virtual Services -
ECRAVS) được trình bày như sau:
xij ∈ {0, 1}; qij, riek, riak, fiek, fiak, ciek, caik ∈ Q+,
∀i ∈ VS, j ∈ PM, k ∈ D
(3.4)
M
X
xij = 1,
∀i ∈ VS
∀i ∈ VS, j ∈ PM, k ∈ D
(3.5)
(3.6)
j=1
(riek + qij × fiek) × xij ≤ cejk,
N
X
((riak + qij × fiak) × xij) ≤ cajk,
∀j ∈ PM, k ∈ D
(3.7)
i=1
N
P
(riak + qij × fiak) × xij
M
D
X X
ꢁ
ꢂ
i=1
Pjmax − Pjidle
×
+ Pjidle
→ min
cajk
j=1
k=1
(3.8)
3.4.Đề xuất giải pháp cho bài toán ECRAVS
3.4.1.Giải pháp dựa trên thuật toán Tối ưu bầy đàn: Đề xuất thuật
toán ECRAVS-PSO
Dựa trên thuật toán Tối ưu bầy đàn, đề xuất thuật toán ECRAVS-PSO
để giải bài toán ECRAVS được trình bày như Thuật toán 3 và được công
bố trong công trình số 4.
- Bài toán ECRAVS như đã trình bày tại Mục 3.3 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 riek,riak,fiek,fiak, tập các máy vật lý PM
cũng như năng lực tài nguyên của máy vật lý cejk, cjak hoàn toàn xác định
được.
- Van den Bergh đã chứng minh độ hội tụ của thuật toán Tối ưu
bầy đàn như sau: gọi x∗ là giá trị tối thiểu toàn cục của hàm mục tiêu
trong không gian giải pháp S, gọi xnumLoop là chuỗi của các giải pháp được
tạo ra bởi thuật toán Tối ưu bầy đàn sau numLoop lần lặp thì xác suất
16
Thuật toán 3: Thuật toán ECRAVS-PSO.
Đầu vào:
• Tập dịch vụ ảo hóa VS = {i | i = 1, ..., N}, tập loại tài nguyên D = {k | k =
1, ..., D}, các nhu cầu tài nguyên: riek,riak,fiek,fiak và hệ số qij.
• Tập máy vật lý PM = {j | j = 1, ..., M}, tài nguyên của máy vật lý: cejk, cjak.
• Số lượng particle là numParticle và số lần lặp là numLoop.
Đầu ra : Danh sách các dịch vụ ảo hóa đã được cung cấp tài nguyên tại
các máy vật lý (tốt nhất), gBest.
1 int numP: = numParticle;
2 new gBest [M] ;
/* Toán tử new dùng để khai báo mảng */
3 new pBest [numP] [M];
4 new particleLocal [numP] [M];
5 boolean new particleV elocity [numP] [M];
6 while (nL ≤ numLoop) do
7
8
for (nP := 1 → numP) do
particalLocal [nP] := initSolution (nP, PM, VS) foreach (j ∈ PM) do
if (particleLocal [nP] [j] .size = 0) then
particleV elocity [numP] [M] := 0;
9
10
11
particleV elocity [numP] [M] := 1;
12
13
14
for (nP := 1 → numP) do
for (nQ := 1 → parLoca[nP].length) do
pBest [nP] [nQ] := particalLocal [nP] [nQ];
15
16
17
18
19
20
gBest := globalBestParticle(particalLocal, PM)
for (nP := 1 → numP) do
particleV elocity [nP] := speedUpdate();
particleLocal [nP] := positionUpdate();
pBest[nP] := PBestUpdate(pBest[nP]);
gBest := GBestUpdate(gBest);
21
numLoop + +;
22 return gBest;
P(numLliomop→∞ xnumLoop = x∗) > 0. Vì thế, thuật toán ECRAVS-PSO hội tụ
đến giá trị tối thiểu toàn cục sau numLoop lần lặp.
- Gọi N là số dịch vụ ảo hóa, M là số máy vật lý, numPartical là
số lượng particle, D là số loại tài nguyên và numLoop là số lần lặp. Cố
định số loại tài nguyên, độ phức tạp của thuật toán ECRAVS-PSO là:
O(numLoop × numPartical × N × M).
17
Tải về để xem bản đầy đủ
27 trang
21440
Free
Bạn đang xem 20 trang mẫu của tài liệu "Tóm tắt 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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tom_tat_luan_an_cung_cap_tai_nguyen_cho_dich_vu_ao_hoa_dua_t.pdf
