Luận án tiến sĩ Kỹ thuậ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

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:123

Thêm vào BST

Báo xấu

57
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của luận án là 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 có độ phức tạp trong thời gian đa thức để 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuậ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

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 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 *** 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 LUẬN ÁN TIẾN SĨ KỸ THUẬT 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 ĐÀ NẴNG, 2018
LỜI CAM ĐOAN Tôi xin cam đoan: Luận án này là công trình nghiên cứu thực sự của cá nhân tôi, được thực hiện tại Trường Đại học Bách khoa, Đại học Đà Nẵng dưới sự hướng dẫn khoa học của PGS.TS. Lê Văn Sơn và PGS.TS. Đoàn Văn Ban. Các kết quả, những kết luận nghiên cứu được trình bày trong luận án này là trung thực và chưa từng được công bố ở bất kỳ công trình nào của tác giả khác. Tôi xin chịu trách nhiệm về những lời cam đoan của tôi. Nghiên cứu sinh Phạm Nguyễn Minh Nhựt i
LỜI CẢM ƠN 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 " được hoàn thành dưới sự hướng dẫn tận tình, cùng những yêu cầu nghiên cứu nghiêm túc của PGS.TS. Lê Văn Sơn và PGS.TS. Đoàn Văn Ban. Các Thầy đã truyền đạt nhiều kiến thức chuyên môn quý báu cũng như những kinh nghiệm nghiên cứu khoa học trong thời gian nghiên cứu để viết luận án này. Tôi xin được bày tỏ lòng biết ơn chân thành và sự kính trọng sâu sắc đối với các Thầy. Để hoàn thành luận án này, tôi cũng đã tiếp nhận được những kiến thức quý giá, sự đóng góp ý kiến và quan tâm chân tình từ quý Thầy, Cô trong Khoa Công nghệ Thông tin, Trường Đại học Bách khoa Đà Nẵng. Quý Thầy, Cô đã tạo mọi điều kiện thuận lợi cho quá trình học tập, nghiên cứu khoa học, tham gia hội thảo và trao đổi chuyên môn, tiếp xúc với chuyên gia. Tôi xin chân thành cảm ơn sự quan tâm, động viên và sự hỗ trợ nhiệt tình tất cả quý Thầy, Cô. Xin chân thành cảm ơn các tác giả về những tài liệu, bài báo và các công bố nghiên cứu khoa học mà tôi có sử dụng tham khảo, trích dẫn trong đề tài nghiên cứu này. Tôi xin cảm ơn bạn bè, đồng nghiệp đã có nhiều động viên và đóng góp ý kiến để luận án được hoàn chỉnh. Nghiên cứu sinh Phạm Nguyễn Minh Nhựt ii
DANH MỤC VIẾT TẮT Viết tắt Dạng đầy đủ Diễn giải ý nghĩa API Application Programming In- Giao diện lập trình ứng dụng. terface. ACO Ant Colony Optimization. Tối ưu đàn kiến. AS Ant System. Hệ kiến. ACS Ant Colony System. Hệ đàn kiến. BW BandWidth. Băng thông. BWAS Best-Worst Ant System. Hệ kiến Best-Worst. CPU Center Processing Unit. Đơn vị xử lý trung tâm. CIS Cloud Information Service. Dịch vụ thông tin đám mây. DC Data Center Trung tâm dữ liệu. ECRAVS Energy Consumption Resource Cung cấp tài nguyên với mục Allocation for Virtual Services. tiêu ràng buộc năng lượng tiêu thụ cho dịch vụ ảo hóa. FFD Firt Fit Decreasing. Thuật toán Firt Fit Decreasing GA Genetic Algorithm. Thuật toán Di truyền. HaaS Hardware as a Service. Phần cứng như một dịch vụ. IaaS Infrastructure as a Service. Cơ sở hạ tầng như một dịch vụ. I/O Input/Output. Thiết bị vào/ra. MDRAVS Multi-Dimensional Resource Cung cấp tài nguyên đa chiều Allocation for Virtual Services. cho dịch vụ ảo hóa. MMAS Max-Min Ant System. Hệ kiến Max-Min. MORA Multi-Objective Resource Al- Cung cấp tài nguyên đa mục location. tiêu. NSDV Năng suất dịch vụ. Năng suất dịch vụ. OS Operation System. Hệ điều hành. PSO Particle Swarm Optimization. Tối ưu bầy đàn. PaaS Platform as a Service. Nền tảng như một dịch vụ. PM Physical Machine. Máy vật lý. RBAS Rank-Based Ant System. Hệ kiến Rank-Based. RAM Random Access Memory. Bộ nhớ truy xuất ngẫu nhiên. RaaS Resource as a Service. Tài nguyên như một dịch vụ. iii
Viết tắt Dạng đầy đủ Diễn giải ý nghĩa SaaS Software as a Service. Phần mềm như một dịch vụ. QoS Quality of Service. Chất lượng dịch vụ. SLA Service Level Agreement. Thỏa thuận mức dịch vụ. SA Simulated Annealing. Mô phỏng luyện kim. VM Virtual Machine. Máy ảo. VMM Virtual Machine Manager. Bộ giám sát máy ảo. VMCS Virtual Machine Control Cấu trúc giám sát máy ảo. Structure. iv
DANH MỤC CÁC KÝ HIỆU Ký hiệu Diễn giải ý nghĩa VS Tập các dịch vụ ảo hóa. i Dịch vụ ảo hóa thứ i. N Số lượng dịch vụ ảo hóa. PM Tập các máy vật lý. j Máy vật lý thứ j. M Số lượng máy vật lý. D Tập các loại tài nguyên. D Số loại tài nguyên. rik Nhu cầu tài nguyên của dịch vụ ảo hóa thứ i với loại tài nguyên k. Q+ Tập số hữu tỷ dương. R Tập số thực. xij Biến nhị phân, có giá trị 1 nếu dịch vụ ảo hóa i được cấp tài nguyên từ máy vật lý j và bằng 0 nếu ngược lại. aik Biến nhị phân, có giá trị 1 nếu rik là một nhu cầu tất yếu, bằng 0 nếu rik là một nhu cầu tùy biến. bij Năng suất dịch vụ của dịch vụ ảo hóa i trên máy vật lý j. yj Biến nhị phân, có giá trị 1 nếu máy vật lý j được sử dụng để cung cấp tài nguyên cho các dịch vụ ảo hóa và có giá trị 0 nếu ngược lại. pij Xác suất để con kiến chọn một dịch vụ ảo hóa i như là dịch vụ kế tiếp để được cung cấp tài nguyên từ máy vật lý j hiện hành. τij Vệt mùi để con kiến dựa vào đó chọn dịch vụ ảo hóa i như là dịch vụ ảo hóa kế tiếp để được cung cấp tài nguyên từ máy vật lý hiện hành j. τijmax Vệt mùi cực đại. τijmin Vệt mùi cực tiểu. α, β Hệ số nhằm làm nổi bật mùi và thông tin heuristic. VStemp Tập các dịch vụ ảo hóa hội đủ điều kiện sẽ được chọn để được cung cấp tài nguyên từ máy vật lý hiện hành j. v
Ký hiệu Diễn giải ý nghĩa ri∗ Vector nhu cầu tất yếu của dịch vụ ảo hóa i. ri∗∗ Vector nhu cầu tùy biến của dịch vụ ảo hóa i. Loadj Tải của máy vật lý hiện hành j. Cj Vector năng lực tài nguyên của máy vật lý j. ηij Thông tin heuristic. ∆τijbest Tổng mùi tăng cường được sinh ra từ con kiến có giải pháp tốt nhất của lần lặp. ρ Độ bay hơi của vệt mùi. nA BIN ARY Ma trận lưu các giải pháp. eij Biểu diễn ánh xạ từ dịch vụ ảo hóa i đến các máy vật lý j. f (S best ) Hàm tính giải pháp tốt nhất. S best Giải pháp tốt nhất. best p Tham số điều chỉnh biên của vệt mùi. S best−vong−lap Giải pháp tốt nhất vòng lặp. S best−toan−cuc Giải pháp tốt nhất toàn cục. P (numLoop) 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. Ce Vector tài nguyên thành phần. cejk Phần tử đơn lẻ của loại tài nguyên k trên máy vật lý j. a C Vector tài nguyên tổng hợp. cajk Phần tử tổng hợp của loại tài nguyên k trên máy vật lý j. Re Vector nhu cầu tài nguyên tất yếu thành phần. a R Vector nhu cầu tài nguyên tất yếu tổng hợp. e rik 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. a rik 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. Fe Vector nhu cầu tùy biến thành phần. e fik Phần tử 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. Fa Vector nhu cầu tài nguyên tùy biến tổng hợp. a fik Phần tử 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. Q Vector hệ số bổ sung. qij 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. vi
Ký hiệu Diễn giải ý nghĩa Pj (uj ) Điện năng tiêu thụ tại máy vật lý j. Pjmax 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. Pjidle Công suất của máy vật lý j tương ứng ở trạng thái trạng thái không hoạt động. uj 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. E(t) 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. Vp Vận tốc của partical. Xp Vị trí của partical. t Fijk Tổng tài nguyên loại k mà dịch vụ ảo hóa i được cung cấp tài nguyên từ máy vật lý j. FjP SO Làm thích nghi của partical. EF F D Năng lượng tiêu thụ của hệ thống khi sử dụng thuật toán FFD. ∗ E Năng lượng tiêu thụ của hệ thống khi sử dụng thuật toán ECRAVS-PSO hay thuật toán ECRAVS-SA. Rj Tài nguyên còn lại của máy vật lý j khi cung cấp tài nguyên cho dịch vụ ảo hóa. R Giá trị tài nguyên trung bình còn lại của tất cả các máy vật lý. E(s0 ) Năng lượng tiêu thụ của giải pháp s0 . σ(s0 ) Độ lệch chuẩn của giải pháp s0 . ηijσ Thông tin heuristic cho mục tiêu cân bằng tải. ηijE Thông tin heuristic cho mục tiêu tối thiểu năng lượng tiêu thụ. best E(s ) Năng lượng tiêu thụ tương ứng với giải pháp tốt nhất toàn cục. σ(sbest ) Độ lệnh chuẩn tương ứng với giải pháp tốt nhất toàn cục. E RoundRobin Năng lượng tiêu thụ của hệ thống khi sử dụng thuật toán RoundRobin. E M ORA−ACS Năng lượng tiêu thụ của hệ thống khi sử dụng thuật toán M ORA − ACS. vii
MỤC LỤC 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 năng lượng tiêu thụ . . . . . . . . . . . . . . . . . . . . 26 viii
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 năng 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 ix
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 x
DANH MỤC BẢNG, BIỂU 1.1 Đặc tính của một số công cụ mô phỏng hệ thống tính toán đám mây tiêu biểu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 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*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2 Thời gian thực hiện các thuật toán First Fit*, Best Fit*. . . . . . . . . 48 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. . . . . . . . . . . . . . . . . . . . . . . 50 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.1 Đặc tính cấu hình tài nguyên của các loại máy vật lý. . . . . . . . . . . 73 3.2 Đặc tính nhu cầu tài nguyên CPU và RAM của các loại máy ảo. . . . . 73 3.3 Đặc tính nhu cầu tài nguyên BW và DISK của các loại máy ảo. . . . . 73 3.4 Kết quả thực nghiệm của các thuật toán ECRAVS-PSO, ECRAVS-SA và FFD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.1 Năng lượng tiêu thụ và độ lệch chuẩn của các thuật toán MORA-ACS và Round Robin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 xi
DANH MỤC HÌNH VẼ 1.1 Kiến trúc ảo hóa máy chủ [107]. . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Kiến trúc ảo hóa tích hợp [27]. . . . . . . . . . . . . . . . . . . . . . . 15 1.3 Các thành phần của công cụ mô phỏng CloudSim [14]. . . . . . . . . . 18 1.4 Mô hình cung cấp tài nguyên trong hệ thống tính toán đám mây. . . . 20 1.5 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ẻ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1 Mục tiêu tối thiểu số lượng máy vật lý được dùng khi cung cấp tài nguyên cho dịch vụ ảo hóa. . . . . . . . . . . . . . . . . . . . . . . . . 36 2.2 Cấu trúc tập tin dữ liệu thực nghiệm. . . . . . . . . . . . . . . . . . . 47 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*. . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.4 Đồ thị biểu diễn thời gian thực hiện các thuật toán First Fit*, Best Fit*. 49 2.5 Đồ thị 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. . . . . . . . . . . . . . 51 2.6 Đồ thị 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 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. 56 3.2 Cấu trúc của particle. . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.3 Đồ thị biểu diễn thời gian thực hiện các thuật toán ECRAVS-PSO, ECRAVS-SA và FFD. . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.4 Đồ thị biểu diễn năng lượng tiêu thụ khi thực hiện các thuật toán ECRAVS-PSO, ECRAVS-SA và FFD. . . . . . . . . . . . . . . . . . . 77 4.1 Mục tiêu cân bằng tải khi cung cấp tài nguyên cho dịch vụ ảo hóa. . . 83 4.2 Biểu diễn các giải pháp trong không gian giải pháp của bài toán tối ưu 02 mục tiêu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3 Biểu diễn đường cong Pareto trong không gian giải pháp của bài toán tối ưu 02 mục tiêu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.4 Đồ thị biểu diễn năng lượng tiêu thụ khi thực hiện thuật toán MORA- ACS và Round Robin. . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.5 Đồ thị biểu diễn độ lệch chuẩn khi thực hiện thuật toán MORA-ACS và Round Robin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 xii
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ẻ. Bên cạnh đó, sự phát triển công nghệ ảo hóa (Virtualization Technology) giúp cho quá trình triển khai hệ thống tính toán đám mây trở nên dễ dàng. Trong kiến trúc phân tầng của công nghệ ảo hóa, tầng ảo hóa có khả năng phân chia hoặc kết hợp tài nguyên của nhiều máy chủ vật lý ở tầng bên dưới thành các máy ảo để cung cấp cho các nhu cầu khác nhau trong đám mây. Hệ thống gồm nhiều máy vật lý được kết nối với nhau qua các thiết bị mạng để chia sẻ tài nguyên, nhằm cung cấp cho dịch vụ ảo hóa được gọi là nền tảng máy chủ chia sẻ (Shared Hosting Platform). Những đặc điểm của hệ thống tính toán đám mây, như: tính linh hoạt, khả năng truy cập mạng diện rộng, khả năng tổng hợp tài nguyên, dịch vụ cung cấp tự động theo nhu cầu và có khả năng đo lường,... đã đ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 1
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 ". Hơn nữa, cung cấp tài nguyên cho dịch vụ ảo hóa là bài toán tối ưu tổ hợp (Combinatorial Optimization Problem), thuộc lớp bài toán NP-đầy đủ. Các thuật toán để giải lớp bài toán này được chia thành 02 nhóm [53]: các thuật toán chính xác (Exact Algorithms) và các thuật toán xấp xỉ (Approximation Algorithms). Các thuật toán chính xác có thể tìm được lời giải tối ưu nhưng thời gian tính toán rất lớn. Ngược lại, các thuật toán xấp xỉ có thể thực hiện trong thời gian cho chép và lời giải đạt gần tối ưu. Hiện nay, các thuật toán xấp xỉ người ta thường dùng các tiếp cận: (1) tìm kiếm heuristic để tìm lời giải đủ tốt; (2) tìm kiếm cục bộ để tìm lời giải tối ưu địa phương; (3) tìm lời giải gần đúng nhờ các thuật toán mô phỏng tự nhiên (Meta heuristic). Trong đó, cách tiếp cận (1) và (2) cho lời giải nhanh nhưng không cải thiện thêm mục tiêu tối ưu. Vì thế, luận án nghiên cứu cách tiếp cận (3), đề xuất các thuật toán Meta heuristic để giải bài toán đưa ra trong luận án. 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: 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. 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 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 2
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 có độ phức tạp trong thời gian đa thức để 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) Dựa trên mô hình hệ thống cung cấp tài nguyên cho dịch vụ ảo hóa của Mark Stillwell [100] và đặc tính tài nguyên của máy vật lý, nhu cầu tài nguyên của dịch vụ ảo hóa từ [99] trong nền tảng máy chủ chia sẻ đồng nhất để đề xuất mô hình toán học cho 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ẻ đồng nhất (Homogeneous Shared Hosting Platform) 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 (Max-Min Ant System- MMAS)[105], đề 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 [63], [72] 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. 3
(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 của Mark Stillwell [100], đặc tính tài nguyên của máy vật lý và nhu cầu tài nguyên của dịch vụ ảo hóa từ [101] trong nền tảng máy chủ chia sẻ không đồng nhất cùng với việc cải tiến mô hình năng lượng tiêu thụ của Eugen Feller [36] để đề xuất mô hình toán học cho vấn đề cung cấp tài nguyên từ nền tảng máy chủ chia sẻ không đồng nhất (Heterogeneous shared hosting platform) với mục tiêu tối thiểu năng lượng tiêu thụ của hệ thống. Cải tiến thuật toán Tối ưu bầy đàn (Particle Swarm Optimization-PSO)[31] để đề xuất thuật toán ECRAVS-PSO và áp dụng thuật toán Mô phỏng luyện kim (Simulated Annealing-SA) [59] để đề xuất thuật toán ECRAVS-SA để giải bài toán. Các thuật toán đề xuất được so sánh với thuật toán với thuật toán Firt Fit Decreasing (FFD) [101] 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) Trên cơ sở mô hình hệ thống, mô hình tài nguyên và nhu cầu tài nguyên của bài toán cung cấp tài nguyên từ nền tảng máy chủ chia sẻ không đồng nhất (trong đóng góp (2)), 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 cho dịch vụ ảo hóa, 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ụ của hệ thống. Áp dụng thuật toán Hệ đàn kiến (Ant Colony System - ACS)[28] để đề xuất thuật toán MORA-ACS nhằm ước lượng bài toán và so sánh với thuật toán Round Robin [79] 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 này trình bày kết quả nghiên cứu tổng quan về các vấn đề nghiên cứu trong luận án. Cụ thể: tìm hiểu các khái niệm, đặc điểm, yêu cầu, công nghệ và các mô hình trong hệ thống tính toán đám mây. Thông qua việc phân tích, đánh giá các công trình liên quan về lĩnh vực cung cấp tài nguyên trong đám mây, nêu ra một số vấn đề tồn tại và đề xuất nội dung nghiên cứu. Bên cạnh đó, nội dung của chương còn 4
trình bày kết quả đánh giá các công cụ mô phỏng hệ thống tính toán đám mây thông dụng hiện nay. Qua đó, nhận thấy CloudSim là môi trường phù hợp để triển khai thực nghiệm mô phỏng nhằm đánh giá thuật toán giải các bài toán trong phạm vi nghiên cứu của luận án. - 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. 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 [100] và đặc tính tài nguyên của máy vật lý, nhu cầu tài nguyên của dịch vụ ảo hóa từ [99] trong nền tảng máy chủ chia sẻ đồng nhất. Trên cơ sở đó, đề xuất mô hình toán học của việc 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. Áp dụng thuật toán First Fit, Best Fit và đề xuất thuật toán MDRAVS-MMAS để giải và đánh giá thông qua nhiều kịch bản thực nghiệm trên dữ liệu được tạo ra bằng phương pháp xác suất ngẫu nhiên. - 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. 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 [100] đề xuất và đặc tính tài nguyên của máy vật lý, nhu cầu tài nguyên của dịch vụ ảo hóa từ [101] trong nền tảng máy chủ chia sẻ không đồng nhất của. Qua đó, xây dựng mô hình bài toá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. Đề xuất thuật toán ECRAVS-PSO và ECRAVS-SA để giải. Các thuật toán được thực thi trên môi trường mô phỏng đám mây CloudSim với dữ liệu thực nghiệm được thu thập từ các đám mây thực 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. Dựa trên mô hình hệ thống, đặc tính tài nguyên và nhu cầu tài nguyên được trình bày ở Chương 3, chương này đề xuất mô hình bài toán 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 mục tiêu tối ưu gồm: 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 trên các máy vật lý. Đề xuất thuật toán MORA-ACS để giải và đánh giá trên môi trường mô phỏng đám mây CloudSim với dữ liệu thực nghiệm được thu thập từ các đám mây thực tế. Các kết quả của luận án được công bố trong 07 công trình khoa học được đăng trong các hội nghị và tạp chí chuyên ngành trong và ngoài nướ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. 5
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 này trình bày kết quả nghiên cứu tổng quan về hệ thống tính toán đám mây, các mô hình áp dụng trong hệ thống tính toán đám mây, công nghệ ảo hóa và máy ảo, các đặc điểm cũng như một số thách thức khi triển khai đám mây. Thông qua việc phân tích, đánh giá các công trình liên quan về lĩnh vực cung cấp tài nguyên trong đám mây, nêu ra một số vấn đề tồn tại của 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ẻ. Từ đó, đề xuất nội dung cải tiến mô hình cũng như bài toán nghiên cứu. Bên cạnh đó, nội dung của chương còn trình bày kết quả đánh giá các công cụ mô phỏng hệ thống tính toán đám mây thông dụng hiện nay. Nhận thấy rằng, CloudSim là công cụ phù hợp để triển khai thực nghiệm mô phỏng và đánh giá các thuật toán đề xuất trong luận án. 1.1. Hệ thống tính toán đám mây Hệ thống 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 tiến bộ kỹ thuật, công nghệ trong lĩnh vực ảo hóa, tính toán lưới, tính toán tiện ích, tính toán cụm và tính toán tự động. Theo Rajkumar Buyya [117]: đám mây là một loại hệ thống tính toán song song và phân tán, gồm một tập các máy tính thực được kết nối với nhau và các máy ảo để cung cấp động tài nguyên tính toán hợp nhất dựa trên thỏa thuận đàm phán về cung cấp dịch vụ giữa nhà cung cấp và người dùng. Có nhiều định nghĩa về mô hình của hệ thống tính toán đám mây được đề xuất trong những năm qua. Tuy nhiên, đến nay vẫn chưa có định nghĩa chuẩn, trong đó Peter Mell và Tim Grance [73] đị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. 6