Cấp phát tài nguyên trong điện toán đám mây dựa trên lý thuyết trò chơi

CẤP PHÁT TÀI NGUYÊN TRONG ĐIỆN TOÁN ĐÁM MÂY
DỰA TRÊN LÝ THUYẾT TRÒ CHƠI
Bùi Thanh Khiết(1)
(1)Trường Đại học Thủ Dầu Một,
Ngày nhận bài 15/8/2017; Ngày gửi phản biện 20/8/2017; Chấp nhận đăng 30/1/2018
Email: khietbt@tdmu.edu.vn 
Tóm tắt
	Quản lý tài nguyên trên điện toán đám mây là một thách thức lớn. Có thể chia việc quản lý tài nguyên trong môi trường điện toán đám mây thành hai pha: pha cấp phát tài nguyên và pha lập lịch tài nguyên. Trong bài báo này, chúng tôi đề xuất giải pháp cấp phát tài nguyên đảm bảo cân bằng mục tiêu của các bên liên quan gồm nhà cung cấp dịch vụ và khách hàng dựa trên lý thuyết trò chơi. Phương án cấp phát tài nguyên tối ưu hoặc gần tối ưu được tìm thông qua giải thuật tối ưu đàn kiến dựa trên cân bằng Nash. Trong thực nghiệm, chúng tôi cài đặt các thuật toán Ant System, Max-Min Ant System, Ant Colony System để tìm lời giải. 
Từ khóa: cân bằng tải, cấp phát máy ảo, trò chơi không cộng tác, tối ưu đàn kiến
Abstract
RESOURCE ALLOCATION IN CLOUD COMPUTING BASED ON GAME THEORY
The resource management on cloud computing is a major challenge. Resource management in cloud computing environment can be divided into two phases: resource provisioning, resource scheduling. In this paper, we propose VM provision solution ensures balance the goals of the party stakeholders including service providers and customers based on game theory. The optimal or near the optimal solution is approximated by meta-heuristic algorithm – Ant Colony Optimization (ACO) based on Nash equilibrium. In the experiments, the Ant System (AS), Max-Min Ant System (MMAS), Ant Colony System (ACO) algorithm are applied to solve the game. 
1. Đặt vấn đề
Mô hình dịch vụ cơ sở hạ tầng (IaaS) điện toán đám mây (ĐTĐM) cung cấp cho người dùng cơ sở hạ tầng như mạng, máy chủ, CPU, bộ nhớ, không gian lưu trữ và các tài nguyên tính toán dưới dạng máy ảo bằng công nghệ ảo hóa máy chủ. Công nghệ ảo hóa máy chủ cho phép tạo ra nhiều máy ảo trên một máy chủ vật lý, mỗi máy ảo cũng được cấp phát tài nguyên phần cứng như máy thật với RAM, CPU, card mạng, ổ cứng, hệ điều hành và các ứng dụng riêng. Các máy ảo và các máy vật lý không đồng nhất với nhau về cấu hình, công suất Việc quản lý, sử dụng tài nguyên trên ĐTĐM một cách hiệu quả là một thách thức lớn. Quản lý tài nguyên trong ĐTĐM có thể chia thành hai giai đoạn: cấp phát tài nguyên (resource provisioning), lập lịch tài nguyên (resource scheduling). Giai đoạn cấp phát tài nguyên nhằm xác định yêu cầu tài nguyên và chất lượng dịch vụ của người dùng sẽ được cấp phát ở đâu trong hệ thống. Giai đoạn lập lịch đảm nhận trách nhiệm quản lý vòng đời của tài nguyên được sau khi tài nguyên được cấp phát thành công. Trong môi trường ĐTĐM, người dùng và nhà cung cấp dịch vụ thường có những yêu cầu khác nhau và có thể mâu thuẫn với nhau. Nhà cung cấp dịch vụ muốn tối đa hóa lợi nhuận với chi phí đầu tư là thấp nhất điều đó dẫn đến phải tối đa hóa việc sử dụng tài nguyên. Trong khi đó, khách hàng muốn tối thiểu hóa chi phí sử dụng từ đó dẫn đến phải tối thiểu hóa thời gian sử dụng dịch vụ. Việc thác tối đa tài nguyên sẽ dẫn đến việc hiệu suất, chất lượng dịch vụ cung cấp cho khách hàng sẽ không thể thỏa mãn. Để đảm bảo chất lượng dịch vụ, nhà cung cấp phải mở rộng thêm nguyên hoặc phải từ chối các yêu cầu dịch vụ mới, việc lập lịch tài nguyên trên ĐTĐM là một thách thức lớn. Lập lịch tài nguyên tối ưu là rất cần thiết trong việc sử dụng hiệu quả tài nguyên trong ĐTĐM IaaS. Bài toán tối ưu dạng này thường thuộc lớp NP-Hard hoặc NP-Complete [1]. Giải pháp cho vấn đề lập lịch thường dựa trên đặc tính cụ thể của từng bài toán từ đó áp dụng các giải thuật như vét cạn (exhaustive algorithm), giải thuật tất định (deterministic algorithm) [2] hoặc giải thuật metaheuristic [3] [4] [5]. Trong thực nghiệm, hầu như các giải thuật tất định tốt hơn các giải thuật vét cạn. Tuy nhiên các giải thuật tất định lại không hiệu quả trong môi trường dữ liệu phân tán từ đó dẫn đến không thích hợp cho các vấn đề lập lịch trong môi trường tính mở rộng (lagre-scale) [6]. Trong khi đó, ĐTĐM là môi trường có dữ liệu phân tán, đòi hỏi có khả năng mở rộng, khả năng đáp ứng yêu cầu người dùng cao do vậy có thể tiếp cận vấn đề lập lịch máy ảo trên ĐTĐM theo hướng metaheuristic là khả thi mặc dù các giải thuật metaheuristic có thể cho kết quả gần tối ưu trong thời gian chấp nhận được. Trong nghiên cứu này, chúng tôi đưa ra giải pháp lập lịch đảm bảo cân bằng các mục tiêu của các bên bên liên quan gồm nhà cung cấp dịch vụ và khách hàng dựa trên lý thuyết trò chơi và dùng giải thuật metaheuristic cụ thể là tối ưu đàn kiến (Ant Colony Optimization- ACO) để tìm ra tìm được giải pháp lập lịch máy ảo tối ưu hoặc gần tối ưu dựa trên cân bằng Nash.
2. Mô hình cấp phát tài nguyên trên điện toán đám mây
Trong cơ sở hạ tầng của điện toán đám mây IaaS, giả sử có m máy vật lý. Nhờ công nghệ ảo hóa, máy vật lý có thể triển khai máy ảo trên chính nó. Tất cả các máy vật lý có thể nhận yêu cầu máy ảo và tạo ra máy ảo đáp ứng yêu cầu của người dùng. Một yêu cầu máy ảo r (cpu, ram, disk) tương ứng với cpu, ram, disk của máy ảo. Việc đảm bảo việc sử dụng tài nguyên hiệu quả cũng như việc sử dụng dịch vụ cơ sở hạ tầng IaaS ổn định, cần phải có chiến lược cấp phát tài máy ảo trong IaaS hợp lý. Giả sử mỗi máy vật lý trong hệ thống phục vụ tài nguyên IaaS được mô hình theo dạng hàng đợi M/M/1
Hình 1. Yêu cầu máy ảo từ người dùng
2.1. Mô hình trò chơi của các bên liên quan
Có thể mô hình hóa bài toán lập lịch trên điện toán đám mây dưới dạng đồ thị có hướng DAG (Directed Acyclic Graph) [7] [8] [9] G(V,E) với trong đó V là tập đỉnh thể hiện các công việc, E là tập các cạnh có hướng thể hiện mối quan hệ phụ thuộc giữa các đỉnh. Các tham số được xem xét trong bài toán gồm: m: số máy ảo được yêu cầu, n: số máy vật lý. Để đảm bảo hệ thống luôn có hiệu suất (performance) tốt, hệ thống cần làm sao tối đa hóa việc sử dụng tài nguyên máy chủ vật lý một cách đồng đều. Hay nói cách khác các máy ảo được phân phối đều trên các má