ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC SÀI GÒN

DỊCH BÀI BÁO SỐ 93
AN AUTO-SCALING VM GAME APPROACH FOR
MULTI-TIER APPLICATION WITH PARTICLE SWARM
OPTIMIZATION ALGORITHM IN CLOUD COMPUTING
(PHƯƠNG PHÁP TỰ ĐỘNG ĐIỀU CHỈNH QUY MÔ MÁY
ẢO DỰA TRÊN LÝ THUYẾT TRÒ CHƠI CHO ỨNG DỤNG
NHIỀU TẦNG VỚI THUẬT TỐN TỐI ƯU HĨA BẦY ĐÀN
TRONG ĐIỆN TỐN ĐÁM MÂY)
CHUN NGÀNH: KHOA HỌC MÁY TÍNH
MƠN : MẠNG VÀ TỐI ƯU HỐ
GIẢNG VIÊN: PGS.TS TRẦN CƠNG HÙNG
HỌC VIÊN: NGUYỄN NGỌC HÂN
KHĨA: 22.1
MSSV: CH 11221002

Thành phố Hồ Chí Minh, năm 2023


ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC SÀI GÒN

DỊCH BÀI BÁO SỐ 93
AN AUTO-SCALING VM GAME APPROACH FOR
MULTI-TIER APPLICATION WITH PARTICLE SWARM
OPTIMIZATION ALGORITHM IN CLOUD COMPUTING
(PHƯƠNG PHÁP TỰ ĐỘNG ĐIỀU CHỈNH QUY MÔ MÁY
ẢO DỰA TRÊN LÝ THUYẾT TRÒ CHƠI CHO ỨNG DỤNG
NHIỀU TẦNG VỚI THUẬT TỐN TỐI ƯU HĨA BẦY ĐÀN

TRONG ĐIỆN TỐN ĐÁM MÂY)
CHUN NGÀNH: KHOA HỌC MÁY TÍNH
MƠN : MẠNG VÀ TỐI ƯU HỐ
GIẢNG VIÊN: PGS.TS TRẦN CƠNG HÙNG
HỌC VIÊN: NGUYỄN NGỌC HÂN
KHĨA: 22.1
MSSV: CH11221002

Thành phố Hồ Chí Minh, năm 2023


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

PHƯƠNG PHÁP TỰ ĐỘNG ĐIỀU CHỈNH QUY MƠ MÁY
ẢO DỰA TRÊN LÝ THUYẾT TRỊ CHƠI CHO ỨNG DỤNG
NHIỀU TẦNG VỚI THUẬT TỐN TỐI ƯU HĨA BẦY ĐÀN
TRONG ĐIỆN TOÁN ĐÁM MÂY
Khiet Bui Thanh

Lam Mai Hoang Xuan

Chien Nguyen Khac

Khoa Khoa học Máy

Học viện Cơng nghệ Bưu

Khoa Tốn – Tin

tính và Kỹ thuật


chính Viễn thơng

Đại học Cảnh sát Nhân dân

Đại học Bách Khoa

Thành phố Hồ Chí Minh, Việt

TP.HCM

TP.Hồ Chí Minh

Nam

Thành phố Hồ Chí Minh, Việt

Thành phố Hồ Chí



Nam

Minh, Việt Nam

m





Hung Ho Dac

Vu Pham Tran

Hung Tran Cong

Khoa Công nghệ Kỹ

Khoa Khoa học Máy tính và

Phịng Khoa học Cơng nghệ và

thuật

Kỹ thuật

Đào tạo

Đại học Thủ Dầu Một

Đại học Bách Khoa TP.Hồ Chí

Học viện Cơng nghệ Bưu chính

Bình Dương, Việt Nam

Minh

Viễn thơng




Thành phố Hồ Chí Minh, Việt

Thành phố Hồ Chí Minh, Việt

Nam

Nam





Tóm tắt — Điện tốn đám mây cho phép khách hàng mở rộng quy mô ứng dụng theo
nhu cầu của họ. Tuy nhiên, bài toán xác định lượng tài nguyên cần thuê mà vẫn đảm bảo
chất lượng dịch vụ, chi phí thấp là một thách thức lớn. Trong nghiên cứu này, chúng tơi
tập trung vào mơ hình hóa vấn đề máy ảo tự động thay đổi quy mô cho các ứng dụng
nhiều tầng dựa trên lý thuyết trò chơi. Chiến lược tự động mở rộng tài nguyên được dựa
3


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

trên định lý cân bằng Nash và tham số QoS của các máy ảo. Trong môi trường điện toán
đám mây cần khả năng mở rộng và đáp ứng người dùng cao, chúng tôi thiết kế thuật toán
PSOVM để giải quyết vấn đề này dựa trên thuật tốn PSO. Các thuật tốn metaheuristic
có khả năng tìm thấy kết quả gần tối ưu trong thời gian chấp nhận được.
Từ khố — tự động điều chỉnh quy mơ; PSO; điện toán đám mây
I. GIỚI THIỆU

Điện toán đám mây là công nghệ ngày càng được ưa chuộng bởi những ưu điểm mà nó
mang lại cho khách hàng như khả năng triển khai ứng dụng một cách linh hoạt, đơn giản hóa
q trình th và giải phóng tài ngun. Các dịch vụ công nghệ ngày nay phần lớn dựa trên tài
nguyên, cơ chế vận hành cũng như lưu trữ, phân phối và xử lý thơng tin trên đám mây. Thay vì
sử dụng một hoặc nhiều máy vật lý (PM), người dùng có thể sử dụng tài ngun ảo hóa thơng
qua mơi trường internet trong mơ hình dịch vụ IaaS, hoặc sử dụng dịch vụ PaaS bao gồm các
API để phát triển ứng dụng trên nền tảng công nghệ cụ thể hoặc dịch vụ phần mềm (SaaS) - hầu
hết trong số đó được cung cấp dưới dạng ứng dụng dựa trên web và được truy cập từ khoảng
cách xa.
Mơi trường điện tốn đám mây cho phép khách hàng tự động tăng/giảm quy mô ứng dụng của
họ [1]. Cụ thể, trong dịch vụ hạ tầng IaaS, đám mây phải có khả năng tự động tăng/giảm quy
mô tài nguyên được gán cho ứng dụng tại các thời điểm khác nhau để cải thiện hiệu suất, duy trì
sự ổn định của hệ thống [2].
Mặc dù điện tốn đám mây cho phép các ứng dụng thích ứng với nhu cầu thay đổi, nhưng để
đưa ra quyết định đúng đắn khơng phải là một bài tốn dễ dàng. Công việc này cần một hệ
thống để chia tỷ lệ tài nguyên theo khối lượng công việc mà ứng dụng xử lý. Theo đó, tự động
mở rộng quy tài nguyên có thể được điều chỉnh theo chiều ngang hoặc chiều dọc. Trong quy mô
chiều ngang, đơn vị tài nguyên là bản sao máy ảo. Ngược lại, quy mô theo chiều dọc liên quan
đến việc thay đổi các tài nguyên được gán cho một máy ảo đang chạy, chẳng hạn như tăng
(hoặc giảm) hiệu năng CPU hoặc bộ nhớ được phân bổ. Các hệ điều hành phổ biến nhất không
cho phép sự thay đổi nhanh chóng (khơng khởi động lại) trên máy mà nó chạy (ngay cả khi đó
4


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018

là máy ảo); vì lý do này, hầu hết các nhà cung cấp đám mây chỉ cung cấp khả năng mở rộng
theo chiều ngang.
Các quyết định của ứng dụng tự động điều chỉnh quy mô phải đảm bảo nhu cầu giữa các bên
liên quan. Đối với khách hàng, họ muốn chi phí dịch vụ thấp, trong khi nhà cung cấp dịch vụ

muốn tối đa hóa lợi nhuận của họ. Các mơ hình định giá tài ngun có thể bao gồm các loại
máy ảo, chi phí trên một đơn vị thời gian ( theo mỗi phút, mỗi giờ). Ứng dụng tự động chia tỷ lệ
cũng phải đảm bảo rằng chức năng của ứng dụng được triển khai đúng yêu cầu bằng cách duy
trì QoS. QoS thường phụ thuộc vào hai loại thỏa thuận cấp độ dịch vụ (SLA): Ứng dụng SLA là
hợp đồng giữa khách hàng (chủ sở hữu ứng dụng) và người dùng cuối; và tài nguyên SLA được
cung cấp bởi nhà cung cấp và khách hàng. Cả hai loại SLA thường được kết hợp để đáp ứng các
ứng dụng SLA, và nhà cung cấp cần tuân thủ các tài nguyên của SLA. Tuy nhiên, việc xác định
lượng tài nguyên phù hợp để cho thuê và đáp ứng mức dịch vụ được yêu cầu trong khi vẫn giữ
mức chi phí tổng thể thấp là một thách thức lớn. Có nhiều thuật tốn tự động điều phối tài
ngun đã được phát triển nhưng khơng có thuật tốn nào có thể thích hợp với mọi ứng dụng
[3-5]. Trong môi trường đám mây, khách hàng và nhà cung cấp dịch vụ thường có các yêu cầu
khác nhau và có thể xung đột với nhau. Do đó, việc tự động thay đổi quy mơ tài ngun trên
điện tốn đám mây là một thử thách khó. Lời giải cho bài tốn này thường dựa trên đặc thù của
từng bài toán, từ các thuật toán như thuật toán vét cạn, thuật toán tất định [6] hay thuật toán
metaheuristic [7-9]. Trong thực tế, hầu như tất cả các thuật toán xác định thuật tốn tồn diện
khá tốt. Tuy nhiên, các thuật tốn tồn diện không hiệu quả trong môi trường dữ liệu phân tán
vì chúng khơng phù hợp với các bài tốn lập lịch trong mơi trường mở rộng [10]. Đồng thời,
điện tốn đám mây là một môi trường dữ liệu phân tán đòi hỏi khả năng mở rộng và khả năng
phản hồi của người dùng cao để có thể giải quyết vấn đề điều chỉnh linh hoạt các máy ảo một
cách nhanh chóng. Phát triển thuật tốn metaheuristic cho điện tốn đám mây là khả thi mặc dù
các thuật tốn 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 đề xuất giải pháp tự động điều chỉnh tài nguyên để đảm bảo
chất lượng mục tiêu và chi phí thuê tài nguyên dựa trên lý thuyết trị chơi và thuật tốn
metaheuristic nói riêng để tối ưu hoá PSO (Particle Swarm Optimization) nhằm tìm ra giải pháp
5


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

tối ưu hoặc gần tối ưu dựa trên cơ sở về cân bằng Nash. Các phần tiếp theo được trình bày như

sau: Phần II là các công việc liên quan; Phương pháp tự động mở rộng máy ảo được trình bày
trong Phần III; Phần IV cho thấy phương pháp tự động thay đổi quy mô máy ảo dựa trên PSO.
Phần V là thực nghiệm để đánh giá phương pháp đề xuất; Cuối cùng, phần kết luận và hướng
phát triển tiếp theo được trình bày trong Phần VI.
II. CÁC CƠNG TRÌNH LIÊN QUAN
Mỗi phương pháp tự động thay đổi quy mô đã được thiết kế với các mục đích cụ thể, tập
trung vào kiến trúc ứng dụng hoặc nhà cung cấp đám mây và cung cấp các khả năng điều chỉnh
khác nhau. Chúng đều có thể căn cứ vào đặc tính kỹ thuật và cơ sở lý thuyết ứng dụng, và có
thể phân chia tự động theo các hướng như: (i) dựa trên ngưỡng, (ii) lý thuyết điều khiển, (iii)
học tăng cường, (iv) lý thuyết hàng đợi và (v) phân tích chuỗi thời gian. Q trình tự động thay
đổi quy mô chủ yếu bao gồm các giai đoạn phân tích và lập kế hoạch của vịng lặp MAPE. Lý
thuyết hàng đợi và phân tích chuỗi thời gian rất hữu ích trong giai đoạn phân tích để ước tính
nhu cầu hiện tại hoặc nhu cầu trong tương lai của ứng dụng. Các quy tắc dựa trên ngưỡng, học
tăng cường và lý thuyết kiểm sốt có thể được sử dụng trong giai đoạn lập kế hoạch để xác định
hành động khắc phục và chúng có thể được kết hợp với một phân tích liên quan trước đó, chẳng
hạn như phân tích chuỗi thời gian.
Ruiqing Chi et al. đề xuất một phương pháp tự động mở rộng quy mô tài nguyên cho các
ứng dụng web nhiều tầng dựa trên lý thuyết trị chơi [11]. Mơ hình đảm bảo u cầu QoS, và
đồng thời giảm thiểu chi phí sử dụng tài nguyên. Dựa trên lý thuyết trò chơi, họ áp dụng định lý
cân bằng Nash, đề xuất một thuật toán tiến hóa và sử dụng Mạng hàng đợi đa lớp (Layer
Queuing Network - LQN) để dự đoán hành vi ứng dụng chính xác trên một phạm vi khối lượng
cơng việc và tài nguyên được phân bổ. Chúng giải quyết các vấn đề phân chia tài nguyên cho
các ứng dụng web nhiều tầng trên đám mây.
Huang et al. đã đề xuất một thuật tốn tự động mở rộng quy mơ [5] mà nó có thể tạo ra các
ứng dụng web khơng chỉ đáp ứng nhu cầu của khách hàng mà còn sử dụng ít tài nguyên hơn, cải
thiện việc sử dụng tài nguyên và giảm chi phí triển khai. Thiết kế cơ chế điều chỉnh máy ảo tự
6


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018


động với mục đích tự động hố quy trình phân bổ tài ngun của ứng dụng là cách tốt nhất để
dự đoán tài nguyên mà ứng dụng cần bằng cách sử dụng lý thuyết hàng đợi. So với các phương
pháp truyền thống sử dụng tải tài nguyên mức cao, phương pháp này có thể cải thiện hiệu quả
sử dụng tài nguyên và đảm bảo chất lượng dịch vụ.
Wei-Hua Ba et al. [3] đã đề xuất phương pháp đánh giá hiệu suất của ứng dụng trên đám
mây. Dựa trên thời gian phản hồi trung bình, thời gian chờ trung bình và các chỉ số hiệu suất
khác, phương pháp có thể truy cập mật độ lưu lượng sử dụng của từng máy chủ, cũng như cấu
hình của chúng, trong một trung tâm dữ liệu không đồng nhất. Sử dụng lý thuyết hàng đợi, họ
xây dựng một mơ hình hàng đợi phức tạp bao gồm hai hệ thống hàng đợi nối tiếp và biểu diễn
dưới dạng mơ hình phân tích để đánh giá hiệu suất của các trung tâm dữ liệu khơng đồng nhất.
Mơ hình hàng đợi phức tạp này cung cấp kết quả có độ chính xác cao cho từng phép đo hiệu
suất và cho phép phân tích tính khơng đồng nhất của một trung tâm dữ liệu không đồng nhất.
Massimo Ficco et al. đã đề xuất một cách tiếp cận siêu thuật toán (meta-heuristic) để phân
bổ tài nguyên đám mây dựa trên các hệ sinh thái mô hình lấy cảm hứng từ sinh học [12]. Theo
đó, lý thuyết trị chơi cổ điển nhằm tối ưu hóa chiến lược phân bổ nguồn lực đảm bảo được mục
tiêu của nhà cung cấp dịch vụ cũng như yêu cầu của khách hàng. Các thuật tốn tiến hóa dựa
trên cấu trúc rạn san hô và sự sinh sản của san hô cho thấy một hành vi rất thú vị để mô phỏng
các yêu cầu liên tục của tài nguyên, kích hoạt q trình quy mơ thay đổi, quy mơ mở rộng, quy
mơ thu nhỏ và quy mơ di cư. Nó cũng khai thác động lực cạnh tranh giữa những người dùng
chiến lược (với SLA của họ) và các nhà cung cấp dịch vụ (với mục tiêu tối đa hóa doanh thu) để
hội tụ các giải pháp tối ưu có thể đáp ứng lợi ích rõ ràng của các bên liên quan. Các thử nghiệm
cho thấy rằng sự kết hợp giữa các phương pháp tiếp cận dựa trên sinh học và dựa trên trị chơi
khơng chỉ đạt được giải pháp thỏa đáng về khả năng thích ứng và tính đàn hồi, mà cịn có thể
dẫn đến những cải tiến đáng kể về hiệu suất. Khi hội tụ đúng lúc, vấn đề về quy mơ dưới những
điện tốn đám mây lớn với nhiều máy và máy ảo sẽ được phân bổ lại.
Yang Guo et al. đã đề xuất thuật toán tự động thay đổi quy mô cho các ứng dụng máy ảo
trên đám mây [4]. Mục tiêu là giảm thiểu số lượng máy vật lý được lưu trữ bằng cách đóng gói
các máy ảo thành máy vật lý, trong khi các máy ảo được tự động điều chỉnh để đáp ứng các yêu
7



Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018

cầu thay đổi. Thuật tốn Shadow sử dụng hệ thống hàng đợi ảo được thiết kế riêng biệt để tự
động tạo giải pháp tối ưu cho việc điều chỉnh máy ảo tự động và đóng gói máy ảo với máy vật
lý. Các thuật toán sẽ được chạy liên tục mà không phải giải quyết lại vấn đề tối ưu hóa cơ bản
"từ đầu", và tự động thay đổi quy mô theo các nhu cầu biến động của ứng dụng.
III. PHƯƠNG PHÁP TỰ ĐỘNG MỞ RỘNG MÁY ẢO
A.

Mơ hình hệ thống
Điện tốn đám mây là một phương thức cung cấp tài nguyên cho các ứng dụng. Mô-đun
giám sát vòng lặp MAPE-K liên tục giám sát việc sử dụng tài nguyên của các ứng dụng. Môđun giám sát sẽ thu thập dữ liệu về trạng thái sử dụng tài nguyên và chuyển dữ liệu đó tới bộ tự
động điều chỉnh quy mơ, sau đó đưa ra các lệnh để tự động chia quy mô - cụ thể là tăng/giảm số
lượng máy ảo được phục vụ. Để có thể truy cập vào QoS cho từng nhân viên của ứng dụng đa
tầng, chúng ta sử dụng Mạng lưới hàng đợi đa lớp (Layer Queuing Network - LQN) [13, 14].
Đây là một mơ hình phân tích dựa trên Mạng lưới hàng đợi (QNs). Mơ hình này rất phù hợp để
mơ hình hóa những ứng dụng phức tạp, có tài nguyên phần cứng mà các thực thể phần mềm
chạy trên đó có thể kết hợp nhiều mức độ chi tiết khác nhau trong mơ hình. Mơ hình hiệu suất
LQN có thể dễ dàng tích hợp với Chu Trình Phát Triển Phần Mềm (Software Development Life
Cycle - SDLC). Các LQN rất lý tưởng để biểu diễn sự tương tác và độ phức tạp của các ứng
dụng nhiều tầng.

8


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018

Hình 1. Kiến trúc hệ thống

Ở nghiên cứu này, mơ hình LQN cung cấp thước đo hiệu suất như thời lượng trạng thái ổn
định và thời gian phản hồi. Đầu vào của mơ hình LQN là tài nguyên phần cứng, cường độ làm
việc của khách hàng, và nhu cầu dịch vụ của khách hàng đối với mơ hình thành phần ở từng giai
đoạn.
B.

Mơ hình trị chơi tự động điều chỉnh quy mô
Giả sử ở cơ sở hạ tầng đám mây, có M máy vật lý (PM). Nhờ có cơng nghệ ảo hóa, các máy
vật lý có thể tự triển khai các máy ảo (VM). Hệ thống điện toán đám mây cung cấp tài nguyên
cho các ứng dụng đa tầng A={ A1 , A 2 ,… A n }. Vectơ phân bổ tài nguyên Φ={Φ 1 , Φ 2 , … , Φn } định
nghĩa số lượng của các bản sao VM được phân bổ cho từng ứng dụng tại tất cả máy chủ sao cho
hợp lý. Chiến lược phân bổ VM cho từng ứng dụng Ai được biểu diễn bởi ma trận không âm Φ i
của hàng k cho từng tầng và cột m cho từng máy vật lý được biểu diễn bên dưới:
v i11 v i12
i
i
Φ i= v 21 v 22
⋮
⋮
i
v k 1 vik 2

(

⋯ vi1 m
⋯ v i2 m ,
⋱ ⋮
⋯ v ikm

)


(1)

trong đó vikm >0 là số lượng máy ảo được phân bổ cho từng ứng dụng i tại hàng k máy vật lý m.
Một ứng dụng đa tầng Ai phục vụ Ti={ti 1 ,t i 2 , … . , t iy }, trong đó y là số lượng tác vụ. Để đảm bảo
chất lượng dịch vụ cho người sử dụng của ứng dụng Ai, chúng ta sẽ xem xét mức độ đáp ứng
nhu cầu của người dùng dựa trên thời gian phản hồi tác vụ như sau:
y

Ri=∑ 1−
j=1

1
r
1+ e

T
ij

−rij

,

(2)

trong đó, thời gian phản hồi r ij của ứng dụng i cho tác vụ j, r Tij là thời gian phản hồi dự kiến của
ứng dụng i cho tác vụ j. Bằng cách áp dụng LQN, ta tính r ij như sau:

9



Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018
k

r ij = ∑

∝=1

y

1−∑
β =1

s ∝ij
w αiβ
m

∑v
δ=1

,
s

α
iβ

(3)

α
iδ


trong đó,
-

s∝ij là thời gian phục vụ trung bình của ứng dụng i cho tác vụ j tại lớp ∝

-

sαiβ là thời gian phục vụ trung bình của ứng dụng i cho tác vụ b tại lớp ∝

- w αiβ là khối lượng công việc ở ứng dụng i tại lớp ∝
-

viδα là số lượng máy ảo của ứng dụng i tại lớp ∝ được phân bổ trên máy vật lý δ

Ở bài nghiên cứu này, chúng ta sẽ tính toán giá thành của dịch vụ dựa trên số lượng CPU được
phân bổ cho ứng dụng. Giả sử rằng, x là số lượng tài nguyên được phân bổ cho máy vật lý i.
Nếu càng nhiều tài nguyên được sử dụng thì khách hàng sẽ phải trả càng nhiều tiền. Giá thành tỉ
lệ thuận với mức độ sử dụng tài nguyên và thời gian để hồn thành tác vụ. Vì thế, giá thành x
được thể hiện như sau:
pi ( x ) =ax +b ( 0< x
(4)

trong đó, a, b là hằng số, c i là tổng số lượng CPU của máy vật lý i.
Các quyết định tự động điều chỉnh quy mô của tài nguyên đều dựa trên việc truy xuất thông
tin từ trung tâm giám sát môi trường đám mây. Chúng ta coi tự động điều chỉnh quy mơ của tài
ngun là một trị chơi và khách hàng là người chơi. Từng người chơi sẽ thử khai thác tối đa tài
nguyên bằng cách điều chỉnh Φ i. Người chơi biết được thông tin chiến lược và điểm quyết định
của nhau, vì thế chúng ta có thể thiết lập một trò chơi phối hợp và thu thập được thơng tin hồn

chỉnh. Từ đó, chúng ta tiếp cận tới khái niệm về trạng thái cân bằng hiệu quả Pareto dựa trên
Nash của trò chơi như một điểm mà khơng người chơi nào có thể thu được kết quả cao hơn
bằng cách thay đổi chiến lược của mình [15]. Để thể hiện sự thay đổi giữa chất lượng, dịch vụ
và giá thành, chức năng đấu loại trực tiếp đưa cho người chơi thứ i khi phục vụ máy ảo được thể
hiện như bên dưới:
i

m

k

F =τ Ri +(1−τ ) ∑ ∑ p x ( viyx ) ∀ τ ∈[0,1]

(5)

x=1 y=1

10


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

Giả sử rằng, từng người chơi có thể thay đổi chiến lược phân bố của họ bằng cách thực hiện
một trong ba hành động sau đây:
v iyx +1
a i=
,
v iyx −1
v iyx +1, v izx−1

{

(6)

trong đó, viyx+ 1 là hành động thêm một máy ảo vào ứng dụng i tại tầng y ở trên máy vật lý x, mặt
khác viyx −1 là hành động sửa đổi một máy ảo và viyx + 1, vizx −1 là hành động di chuyển máy ảo từ
máy vật lý y đến máy vật lý z.
Ở trò chơi này, hàm lợi ích của trị chơi có ảnh hưởng quan trọng đến quyết định chiến lược của
một người chơi và kết quả của trò chơi. Mỗi người chơi sẽ chọn một chiến lược để tối đa hóa
kết quả của họ, vì vậy hàm mục tiêu được xác định như sau:
n

(7)

Min ∑ F i ( ϕ )
i=1

n

m

k

Subject ¿ ∑ ∑ ∑ ( viyx ) ≤ c x .
i=1 x=1 y=1

Trạng thái cân bằng Nash của trị chơi là một chiến lược trong đó khơng một người chơi nào
có thể tăng lợi nhuận khi các người chơi khác đã cố định chiến lược của họ. Sau đó, nếu chiến
¿
lược của người chơi i là chiến lược tối ưu được biểu thị là pi , thì các chiến lược tối ưu của người

¿
¿
chơi khác được biểu thị là p−i thì cân bằng Nash của chiến lược pi sẽ phải tuân theo các điều

kiện [16] sau:
¿
F i ( p¿−i , p ¿i ) ≥ F i ( p−i
, pi )

(8)

Trong một hệ thống đa tác nhân, điểm cân bằng có thể khơng ổn định [17]. Hơn nữa, sẽ rất
khó khăn để tìm ra Pareto hiệu quả của cân bằng Nash. Để giải quyết vấn đề này, hầu hết các
thuật toán đều dựa trên thuật toán metaheuristic. Các lựa chọn cho việc gán máy ảo cho máy vật
lý đều có căn cứ dựa trên thuật tốn tối ưu. Từ tập các lựa chọn khả thi dựa trên điều kiện cân
bằng Nash, ta sẽ chọn lựa chọn tốt nhất. Điều kiện dừng của thuật toán sẽ theo [15]:

11


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018
n

∑ (F itrj −F itrj −1)2 <ε

(9)

i=1

IV. ĐIỀU CHỈNH QUY MÔ MÁY ẢO TỰ ĐỘNG DỰA THEO PHƯƠNG PHÁP PSO

Phương pháp tối ưu bầy đàn (PSO) là một kỹ thuật tối ưu hóa ngẫu nhiên dựa trên một quần
thể được phát triển bởi Eberhart và Kennedy dựa trên mô phỏng hành vi của chim hoặc cá [18].
Trong PSO, mỗi giải pháp đơn lẻ là một phần tử của kịch bản trên. Mỗi phần tử được đặc trưng
bởi hai thơng số là vị trí hiện tại của phần tử present và vận tốc v. Có hai vectơ trên trường số Rn
với n là kích thước của phần tử được xác định bởi các vấn đề cụ thể. Mỗi phần tử có một giá trị
thích ứng fitness value, được đánh giá bởi hàm đo lường thích ứng fitness function. Vào thời điểm
bắt đầu, bầy đàn, hay chính xác là vị trí của từng phần tử, được tạo ra một cách ngẫu nhiên
(hoặc theo một số cách dựa trên kiến thức trước đó của vấn đề). Trong q trình chuyển động,
từng phần tử chịu ảnh hưởng bởi hai giá trị: pBest là vị trí tốt nhất mà phần tử đó đã đạt được
trong quá khứ, g Best là vị trí tốt nhất của đàn đó đã đạt được trong quá khứ. Trong bản gốc của
Eberhart và Kennedy, các phần tử trong PSO sẽ duyệt các khoảng vấn đề bằng cách theo dõi
các phần tử có điều kiện hiện tại tốt nhất - đồng nghĩa với sự thích nghi lớn nhất. Cụ thể, sau
mỗi khoảng thời gian rời rạc, vận tốc và vị trí của mỗi phần tử được cập nhật theo các công thức
sau:
v=v + c 1. rand ()∗( pBest − present ) + c 2. rand ()∗( g Best − present )
present=present +v

(10)

(11)

trong đó, rand ( ) là một số ngẫu nhiên trong khoảng (0,1); c 1, c 2là các hệ số học tập.
A. Sơ đồ mã hoá
Để có thể áp dụng PSO cho xử lý vấn đề tự động mở động quy mô, máy ảo cần được thiết kế
lại sơ đồ mã hóa và các chức năng lợi ích. Lấy ví dụ, giả sử hệ thống có 5 máy vật lý đang phục
vụ cho 3 ứng dụng A={ A1 , A 2 , A3 }, mỗi ứng dụng có 3 lớp được triển khai như Hình 2, bao gồm:
- Ứng dụng 1 được triển khai trên 6 máy ảo, bao gồm: Tầng 1 có 2 máy ảo tại máy vật lý 1
và máy vật lý 2; Tầng 2 có 2 máy ảo trong máy vật lý 2 và máy vật lý 4, Tầng 3 có 2 máy ảo
trong máy vật lý 3 và máy vật lý 5.
12

Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

- Ứng dụng 2 được triển khai trên 5 máy ảo bao gồm: Tầng 1 có 2 máy ảo tại máy vật lý 3 và
máy vật lý 5; Tầng 2 có 2 máy ảo trong máy vật lý 3 và máy vật lý 5, Tầng 3 có 1 máy ảo tại
máy vật lý 2.
- Ứng dụng 3 được triển khai trên 4 máy ảo bao gồm: Tầng 1 có 1 máy ảo tại máy vật lý 4;
Tầng 2 có 1 máy ảo tại máy vật lý 1, Tầng 3 có 2 máy ảo tại máy vật lý 1 và máy vật lý 4.
Với mơ hình triển khai máy ảo cho ứng dụng đa tầng như Hình 2, ta có thể biểu diễn chiến
lược triển khai máy ảo được mô tả trong (1) cho từng ứng dụng:
1 1 0 0 0
ϕ =0 1 0 1 0
1 0 0 1 0
1

0 0 1 0 1
ϕ =0 0 1 0 1
0 1 0 0 0
2

0 0 0 1 0
ϕ =1 0 0 0 0
1 0 0 1 0
3

B. Thuật toán

13

Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018

Hình 2. Sơ đồ triển khai hệ thống
Thơng qua đó, mỗi thuật tốn tương tác của PSOVM có thể tìm ra các chiến lược có thể
được phân bổ máy ảo cho các ứng dụng như sau:
Chiến thuật 1
0
ϕ 1= 1
1
0
2
ϕ =1
2
0
ϕ 3= 1
2

2
0
0
0
1
2
0
1
2

0
1

0
0
0
1
0
0
0

1
0
3
1
1
1
1
1
1

1
2
0
1
1
1
1
1
1

Chiến thuật 2
1

ϕ 1= 1
0
0
2
ϕ =0
0
1
ϕ 3= 0
0

2
1
0
2
1
0
2
1
0

4
1
0
4
1
1
4
1
0

1
0
3
0
1
0
1
1
1

2
1
0
2
1
0
2
1
0

V. THÍ NGHIỆM
A.

Giới thiệu

Ở thí nghiệm này, chúng ta quan tâm tới chất lượng của ứng dụng và giá thành của dịch vụ.
Với phương pháp tối PSOVM, kết quả xấp xỉ phụ thuộc vào tham số ℇ, số lượng cá thể trong 1, số lượng cá thể trong 1
bể chứa swarm¿ ¿30 ¿, sự đánh đổi giữa chất lượng dịch vụ và tiền thuê máy ảo t. Vì thế, ở thí
nghiệm sau đây, chúng ta sẽ tìm thấy các thơng số thích hợp cho hệ thống cũng như đánh giá
khả năng mở rộng tài nguyên cho ứng dụng thông qua chất lượng dịch vụ trong công thức (4)

14


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

và giá thành của việc thuê tài nguyên theo công thức (5). Chúng ta xây dựng thuật tốn và thí
nghiệm dựa trên bộ cơng cụ CloudSim 3.0 và xây dựng trung tâm dữ liệu có 10 máy vật lý.
C.

Kết quả
Lựa chọn ℇ, số lượng cá thể trong 1 trong trường hợp xử lý theo hướng người dùng, theo hướng của lưu trữ dữ liệu
và cả hai. Thí nghiệm được thực hiện trên 10 máy vật lý và 70 ứng dụng. Duyệt lần lượt từng ℇ, số lượng cá thể trong 1
từ 0.001 đến 0.01 vàđo số chu kỳ được thiết lập bởi thuật tốn.

Hình 3. Độ hiệu quả của ℇ
Chọn epsilon = 0.03, tăng số lượng hiển thị từ 5 lên 50 cá thể

15


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018

Hình 4. Độ ảnh hưởng của số lượng cá thể trong đàn
Hình 4 cho thấy rằng khi tăng số lượng cá thể trong đàn thì thời gian tăng theo gần như
tuyến tính. Tuy nhiên, số lượng cá thể trong đàn ban đầu dao động từ 10 đến 20 cá thể, nhưng
giá trị mục tiêu đã tăng lên, và trong quần thể có số lượng cá thể là 30, hàm mục tiêu đã giảm
xuống tới giá trị tối thiểu. Tiếp tục tăng số lượng cá thể lên 35, giá trị hàm mục tiêu tăng lên.
Khi số lượng cá thể tăng lên 50, giá trị mục tiêu giảm. Từ đó, có thể thấy rằng số lượng cá thể
trong đàn quá ít hoặc quá nhiều dẫn đến sự bất lợi trong việc tìm giá trị tối ưu và thời gian thực
thi của máy ảo. Trong Hình 4 ở trên, giá trị tối thiểu của hàm mục tiêu được đạt khi số lượng cá

thể là 30 và giá trị tối đa được đạt là khi số lượng cá thể là 35.
Trong thử nghiệm tiếp theo, chúng ta đã chọn số đàn là 30 và 35 để so sánh hiệu quả trong
Hình 5 - 8. Chúng ta phân tích tác động của ứng dụng đến kích thước đàn.

Hình 5: Thời gian phản hồi của ứng dụng.

16


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018

Hình 6. Giá thành của ứng dụng.

Hình 7. Số lượng máy ảo được triển khai trên các máy vật lý.

17


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thơng (ATC) năm 2018

Hình 8. So sánh kết quả của thuật tốn.
Hình 8 cho thấy so sánh tổng thể giữa bầy đàn 30 và bầy đàn 35. Bầy đàn #35 cung cấp độ
trễ ít hơn so với bầy đàn #30 nhưng lại tốn chi phí cao hơn. Tỷ lệ khác biệt của chi phí nhỏ hơn
tỷ lệ khác biệt của thời gian phản hồi, vì vậy chúng ta có thể chọn tham số đàn phù hợp để tối
ưu hóa thời gian phản hồi và chi phí.
VI. KẾT LUẬN
Bài báo này đã giới thiệu một mơ hình tự động điều chỉnh quy mô tài nguyên máy ảo cho
ứng dụng đa tầng dựa trên lý thuyết trị chơi trên điện tốn đám mây. Chiến lược mở rộng tài
nguyên được tìm thấy ở thuật toán PSOVM được dựa trên thuật toán PSO. Trong thí nghiệm
phần trước, bài báo đã giới thiệu các tham số ảnh hưởng tới hiệu quả của thuật toán bằng cách

điều chỉnh các tham số ví dụ như ℇ, số lượng cá thể trong 1, kích thước đàn, ... Ở phần nghiên cứu tới đây, chúng ta sẽ
cải thiện độ hiệu quả của thuật toán bằng cách kết hợp với khả năng tìm hiểu thơng số cấu hình.
TÀI LIỆU THAM KHẢO
[1]. Lorido-Botran, T., Miguel-Alonso, J., and Lozano, J.A.: ‘A review of autoscaling
techniques for elastic applications in cloud environments’, Journal of grid computing, 2014, 12,
(4), pp. 559-592
[2]. Kumar, Y.R., Madhu Priya, M., and Shahu Chatrapati, K.: ‘Effective distributed dynamic
load balancing for the clouds’, International Journal of Engineering Research & Technology
(IJERT), 2013, 2, (2), pp. 1-6
18


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

[3]. Bai, W.-H., Xi, J.-Q., Zhu, J.-X., and Huang, S.-W.: ‘Performance analysis of
heterogeneous data centers in cloud computing using a complex queuing model’, Mathematical
Problems in Engineering, 2015, 2015
[4]. Guo, Y., Stolyar, A., and Walid, A.: ‘Online VM Auto-Scaling Algorithms for Application
Hosting in a Cloud’, IEEE Transactions on Cloud Computing, 2018
[5]. Huang, G., Wang, S., Zhang, M., Li, Y., Qian, Z., Chen, Y., and Zhang, S.: ‘Auto scaling
virtual machines for web applications with queueing theory’, in Editor: ‘Book Auto scaling
virtual machines for web applications with queueing theory’ (IEEE, 2016, edn.), pp. 433-438
[6]. Morton, T., and Pentico, D.W.: ‘Heuristic scheduling systems: with applications to
production systems and project management’ (John Wiley & Sons, 1993. 1993)
[7]. Van Laarhoven, P.J., Aarts, E.H., and Lenstra, J.K.: ‘Job shop scheduling by simulated
annealing’, Operations research, 1992, 40, (1), pp. 113-125
[8]. Colorni, A., Dorigo, M., Maniezzo, V., and Trubian, M.: ‘Ant system for job-shop
scheduling’, Belgian Journal of Operations Research, Statistics and Computer Science, 1994,
34, (1), pp. 39-53
[9]. Ghumman, N.S., and Kaur, R.: ‘Dynamic combination of improved maxmin 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, 2015, edn.), pp. 1- 5
[10]. Tsai, C.-W., and Rodrigues, J.J.: ‘Metaheuristic scheduling for cloud: A survey’, IEEE
Systems Journal, 2014, 8, (1), pp. 279-291
[11]. Chi, R., Qian, Z., and Lu, S.: ‘A game theoretical method for auto-scaling of multi-tiers
web applications in cloud’, in Editor: ‘Book A game theoretical method for auto-scaling of
multi-tiers web applications in cloud’ (ACM, 2012, edn.), pp. 3
[12]. Ficco, M., Esposito, C., Palmieri, F., and Castiglione, A.: ‘A coral-reefs and game theorybased approach for optimizing elastic cloud resource allocation’, Future Generation Computer
Systems, 2018, 78, pp. 343-352
19


Hội nghị quốc tế về công nghệ tiên tiến cho truyền thông (ATC) năm 2018

[13]. Franks, G., Maly, P., Woodside, M., Petriu, D., and Hubbard, A.: ‘Layered Queueing
Network Solver and Simulator User Manual (2005)’, Carleton Univ
[14]. Jung, G., Joshi, K.R., Hiltunen, M.A., Schlichting, R.D., and Pu, C.: ‘Generating
adaptation policies for multi-tier applications in consolidated server environments’, in Editor:
‘Book Generating adaptation policies for multi-tier applications in consolidated server
environments’ (IEEE, 2008, edn.), pp. 23-32
[15]. Xu, X., and Yu, H.: ‘A game theory approach to fair and efficient resource allocation in
cloud computing’, Mathematical Problems in Engineering, 2014, 2014
[16]. Osborne, M.J., and Rubinstein, A.: ‘A course in game theory’ (MIT press, 1994. 1994)
[17]. Pendharkar, P.C.: ‘Game theoretical applications for multi-agent systems’, Expert Systems
with Applications, 2012, 39, (1), pp. 273-279
[18]. Kennedy, J.: ‘Particle swarm optimization’: ‘Encyclopedia of machine learning’ (Springer,
2011), pp. 760-766

MỤC LỤC

I.

GIỚI THIỆU............................................................................................................................. 4

II. CÁC CƠNG TRÌNH LIÊN QUAN.........................................................................................6
III. PHƯƠNG PHÁP TỰ ĐỘNG MỞ RỘNG MÁY ẢO.............................................................8
A.

Mơ hình hệ thống................................................................................................................... 8

B.

Mơ hình trị chơi tự động điều chỉnh quy mơ......................................................................9

IV. ĐIỀU CHỈNH QUY MƠ MÁY ẢO TỰ ĐỘNG DỰA THEO PHƯƠNG PHÁP PSO......11
A.

Sơ đồ mã hố........................................................................................................................ 12

B.

Thuật tốn............................................................................................................................ 13

V.

THÍ NGHIỆM......................................................................................................................... 14

A.

Giới thiệu.............................................................................................................................. 14

B.

Kết quả................................................................................................................................. 14
20