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áy vật lý, lúc này hệ thống sẽ đạt trạng thái cân bằng. Để đo hiệu suất sử dụng tài nguyên của một máy vật lý, dùng công thức:
 	(1)
	Trong đó: là tài nguyên đã được sử dụng trong máy vật lý thứ i được tính theo công thức 	(2)
	 tài nguyên của máy vậy lý thứ i, được tính là: 	(3)
	 là hiệu suất sử dụng tài nguyên của máy vật lý thứ i. 
	Độ cân bằng tải của hệ thống được đo bằng công thức: 	(4)
	Trong đó là giá trị trung bình của hiệu suất. 
	Đối với nhà cung cấp dịch vụ, để đạt lợi nhuận cao thường họ khai thác tối đa khả năng phục vụ của máy vật lý, tránh tình trạng lãng phí tài nguyên của máy vật lý. Lãng phí tài nguyên của máy vật lý thứ i trong hệ thống được tính: 	(5)
	Trong đó: là tài nguyên sẵn sàng phục vụ yêu cầu máy ảo của máy vật lý thứ i, được tính 	(6)
	 tài nguyên của máy vậy lý thứ i; mức độ lãng phí tài nguyên máy vật lý thư i. 
	Tổng mức độ khai thác hệ thống được tính: 	(7)
	Cho tham số để biểu diễn sự đánh đổi giữa cân bằng tải và tối đa hóa lợi nhuận của thiết kế hệ thống ĐTĐM. Lợi nhuận (payoff) đem lại cho người chơi thứ j khi được phục vụ yêu cầu máy ảo, được biểu diễn bằng sự kết hợp tuyến tính của 
	 	(8)
2.2. Điểm cân bằng Nash
Điểm cân bằng Nash của trò chơi là chiến lược mà ở đó không một người chơi nào có thể tăng lợi nhuận khi những người chơi khác đã cố định chiến lược. Khi đó, nếu chiến lược của người chơi thứ i là chiến lược tối ưu được kí hiệu , chiến lược tối ưu của những người chơi khác được ký hiệu là thì cân bằng Nash của chiến lược sẽ tuân thủ theo điều kiện [10]: 	(9)
Trong môi trường multi agent system, có thể điểm cân bằng sẽ không ổn định (stable)[11]. Ngoài ra, khó có thể tìm được Pareto-efficiency của cân bằng Nash. Để giải quyết vấn đề này đa phần các giải thuật được dựa trên các giải thuật metaheuristic. Các phương án gán máy ảo vào các máy vật lý khả thi được tìm dựa trên giải thuật tối ưu đàn kiến. Từ tập phương án khả thi đó dựa vào điều kiện cân bằng Nash sẽ chọn ra phương án tốt nhất.
	2.3. Thuật toán cấp phát tài nguyên trên điện toán đám mây
Giải thuật tối ưu đàn kiến được đề xuất dựa trên thí nghiệm về đàn kiến. Do đặc tính tự nhiên và đặc tính hóa học, mỗi con kiến khi di chuyển luôn để lại vệt mùi (pheromone trail) trên đường đi và thường thì chúng sẽ đi theo con đường có lượng mùi đậm đặc hơn. Các vết mùi này là những loại hóa chất bay hơi theo thời gian, ban đầu thì lượng mùi ở hai nhánh là xấp xỉ như nhau, sau một khoảng thời gian nhất định nhánh ngắn hơn sẽ có lượng mùi đậm đặc hơn so với nhánh dài hơn; lượng mùi gần xấp xỉ như nhau khi phân bố ở nhánh dài hơn mật độ phân bố mùi ở nhánh này sẽ không dày bằng nhánh ngắn hơn; cũng do lượng mùi trên nhánh dài hơn sẽ bị bay hơi nhanh hơn trong cùng một khoảng thời gian.
Quá trình học tăng cường có tác dụng nâng cao hiệu quả của thuật toán trong quá trình các con kiến tìm lời giải. Một trong những điều quan trọng đầu tiên trong việc áp dụng các thuật toán ACO là công việc xác định thông tin học tăng cường qua các vệt mùi, nói cách khác là xác định thông tin mà vệt mùi biểu diễn. Ở đây vệt mùi là khả năng một máy chủ được lựa chọn để cấp phát máy ảo theo yêu cầu, khả năng này phụ thuộc vào cấu hình hiện tại và thông tin heuristic của máy chủ. Thông tin heuristic sẽ được tính lại sau mỗi lần cấp phát bởi thông tin cấu hình của máy chủ sẽ thay đổi sau mỗi lần cấp phát thành công máy ảo. Việc tính toán lại sẽ giúp các thông tin heuristic chính xác hơn cho các lần cấp phát tiếp theo.
Điều kiện dừng của thuật toán theo [15]: 	(10)
3. Thực nghiệm
Trong bài báo này, chúng tôi quan tâm với vấn đề cân bằng tải của hệ thống và vấn đề khai thác tài nguyên hệ thống. Với lớp giải thuật tối ưu đàn kiến, kết quả xấp xỉ phụ thuộc vào các tham số epsilon, anpha, beta. Do vậy, trong các thực nghiệm dưới đây, chúng tôi tìm những thông số thích hợp cho hệ thống cũng như đánh giá việc cấp phát tài nguyên máy ảo cho khách hàng thông qua mức độ cân bằng tải của hệ thống trong công thức (4) và mức độ lãng phí tài nguyên hệ thống theo công thức (5).
Chọn epsilon trong trường hợp theo yêu cầu người dùng hướng xử lý, hướng lưu trữ dữ liệu, và cả hai. Thực nghiệm trên 100 host và 50 user không đồng nhất đang có tải. Với alpha = beta = nguy = lamda = 0.5; pro= 0.2; p0 = 0.9. Cho epsilon từ 0.1 đến 0.03, đo số vòng lập của thuật toán. 
Hình 2. Mối tương quan giữa epsilon và iterator
	Trong hình 2 khi thay đổi epsilon từ 0.03 đến 0.1 ta có thể thấy thuật toán ACS có số lần lập ít và luôn ổn định. Khi tăng epsilon, thuật toán MMAS và AS đều có số lần lập giảm và gần bằng với số lần lập của ACS. Mặc dù ở giá trị epsilon lớn nhưng MMAS vẫn cho ra một số lần lặp cao hơn ACS và AS. Điều này cho thấy thuật toán MMAS có giải pháp phong phú hơn. 
Hình 3. Epsilon và L và W
Hình 4. alpha = 0.1, beta = 0.9 	Hình 5. alpha = 0.9, beta = 0.1.
Với epsilon = 0.05, mức độ cân bằng tải và mức độ lãng phí tài nguyên ở mức trung bình. Khi epsilon tăng lên số lượng vòng lập giảm xuống nhưng kéo theo mức độ cân bằng tải và lãnh phí tài nguyên có xu hướng tăng lên. Do vậy, trong giới hạn của bài báo chúng tôi chọn epsilon = 0.05 cho các thực nghiệm tiếp theo. Chọn thông số khác epsilon = 0.05, nguy = lamda = 0.5; pro= 0.2; p0 = 0.9. Cho số lượng khách hàng từ 10 đến 60, Cho số lượng khách hàng từ 10 đến 50, điều chỉnh alpha, beta như hình 4, 5. Với kết quả của hình trên, mức độ lãng phí tài nguyên của các thuật toán gần như không phụ thuộc vào alpha và beta. Mức độ cân bằng tải của hệ thống đối khi alpha = 0.9, beta = 0.1 của 3 thuật toán có mức dao động tương đối ít.
Hình 6. alpha = 0.7, beta = 0.3 
4. Kết luận
	Dựa trên việc nghiên cứu cơ sở lý thuyết và các công nghệ liên quan bài báo đã xây dựng mô hình cấp phát tài nguyên cho điện toán đám mây và xây dựng giải thuật cấp phát tài nguyên dựa trên metaheuristic. Trong môi trường Điện toán đám mây thường có dữ liệu lớn, 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 điện toán đám mây 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. Giải pháp lập lịch đề xuất đả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. Sắp tới, tiếp tục nghiên cứu sâu hơn về các thuật toán Metaheuristic, xây dựng thực nghiệm trên các bộ dữ liệu lớn để đánh giá hiệu quả của thuật toán chính xác hơn. Nghiên cứu một số thuật toán thuộc họ Metaheuristic và song song hóa để so sánh và đánh giá tính chính xác và mức độ hiệu quả giữa các thuật toán.
TÀI LIỆU THAM KHẢO
Gary, M.R., and Johnson, D.S. (1979), ‘Computers and Intractability: A Guide to the Theory of NP-completeness’, in Editor (Ed.)^(Eds.): ‘Book Computers and Intractability: A Guide to the Theory of NP-completeness’ (WH Freeman and Company, New York, edn.). 
Morton, T., and Pentico, D.W. (1993), ‘Heuristic scheduling systems: with applications to production systems and project management’, John Wiley & Sons.
Van Laarhoven, P.J., Aarts, E.H., and Lenstra, J.K. (1992), ‘Job shop scheduling by simulated annealing’, Operations research, 40, (1), pp. 113-125.
Colorni, A., Dorigo, M., Maniezzo, V., and Trubian, M. (1994), ‘Ant system for job-shop scheduling’, Belgian Journal of Operations Research, Statistics and Computer Science, 34, (1), pp. 39-53
Ghumman, N.S., and Kaur, R. (2015), ‘Dynamic combination of improved max-min and ant colony algorithm for load balancing in cloud system’, in Editor (Ed.)^(Eds.): ‘Book Dynamic combination of improved max-min and ant colony algorithm for load balancing in cloud system’ (IEEE, edn.), pp. 1-5.
Tsai, C.-W., and Rodrigues, J.J. (2014), ‘Metaheuristic scheduling for cloud: A survey’, IEEE Systems Journal, 8, (1), pp. 279-291.
Li, J., Qiu, M., Ming, Z., Quan, G., Qin, X., and Gu, Z. (2012), ‘Online optimization for scheduling preemptable tasks on IaaS cloud systems’, Journal of Parallel and Distributed Computing, 72, (5), pp. 666-677.
Rahman, M., Li, X., and Palit, H. (2011), ‘Hybrid heuristic for scheduling data analytics workflow applications in hybrid cloud environment’, in Editor (Ed.)^(Eds.): ‘Book Hybrid heuristic for scheduling data analytics workflow applications in hybrid cloud environment’ (IEEE, edn.), pp. 966-974.
Saovapakhiran, B., Michailidis, G., and Devetsikiotis, M. (2011), ‘Aggregated-DAG scheduling for job flow maximization in heterogeneous cloud computing’, in Editor (Ed.)^(Eds.): ‘Book Aggregated-DAG scheduling for job flow maximization in heterogeneous cloud computing’ (IEEE, edn.), pp. 1-6
Osborne, M.J., and Rubinstein, A. (1994), ‘A course in game theory’ (MIT press).
Pendharkar, P.C. (2012), ‘Game theoretical applications for multi-agent systems’, Expert Systems with Applications, 39, (1), pp. 273-279
Dorigo, M., Maniezzo, V., and Colorni, A. (1996), ‘Ant system: optimization by a colony of cooperating agents’, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26, (1), pp. 29-41
Stützle, T., and Hoos, H.H. (2000), ‘MAX–MIN ant system’, Future generation computer systems, 16, (8), pp. 889-914
Dorigo, M., and Gambardella, L.M. (1997), 'Ant colony system: a cooperative learning approach to the traveling salesman problem’, IEEE Transactions on evolutionary computation, 1, (1), pp. 53-66.