1

MỞ ĐẦU
Môi trường đám mây [1] là mô hình ảo hóa những máy chủ vật lý (tài nguyên phần
cứng) thành những máy ảo (VMs). Sự di trú máy ảo [2], [3] trong khi vận hành hệ thống
điện toán đám mây cần phải được thực hiện sao cho hiệu suất tốt [4], giá thành hợp lý [5]
và khả năng chịu lỗi cao [6] (fault tolerance). Các máy ảo cần phải di trú một cách linh hoạt
trong suốt quá trình hoạt động của hệ thống để đáp ứng yêu cầu di chuyển của khách hàng,
dữ liệu của hệ thống phải được cân bằng tải, và các server không phải chịu tải cao. Nói
cách khác, khi một khách hàng di chuyển từ một vùng này đến vùng khác thì phải sử dụng
hai slot cho việc di trú máy ảo của khách hàng đó, một slot cho host gốc và một slot cho
host đến (slot mục tiêu) trong một khoảng thời gian cần thiết để di trú máy ảo hoàn thành.
Do đó, nếu số lượng di trú nhiều thì phải cần nhiều nguồn slot dự phòng trong suốt thời
gian di trú. Vì vậy, số lượng slot trống giành cho yêu cầu dịch vụ của khách hàng mới sẻ
giảm. Nếu hệ thống không có đủ slot cho yêu cầu dịch vụ của khách hàng mới thì hệ thống
sẽ từ chối yêu cầu. Khả năng từ chối yêu cầu dịch vụ của khách hàng mới được đánh giá
bởi xác suất từ chối [7]. Xác suất từ chối phụ thuộc số lượng máy ảo đang di trú của khách
hàng trong hệ thống và số lượng yêu cầu dịch vụ của khách hàng mới.
Một hệ thống có nhiều sự di trú của máy ảo [8] đòi hỏi phải có nhiều slot trống vì
số máy ảo giữ hai slot cho việc chuyển vùng tăng cao. Trong trường hợp này, Nếu số lượng
slot giành riêng cho việc di trú ít hơn số lượng máy ảo cần di trú thì sẽ làm tăng thời gian
chờ của các máy ảo đang di trú. Một hệ thống có số lượng slot ít, xác suất từ chối yêu cầu
dịch vụ mới của khách hàng cũng như thời gian chờ của việc di trú máy ảo tăng, và chất
lượng dịch vụ giảm. Một hệ thống kinh doanh cần phải bảo đảm kỹ thuật theo những yêu
cầu của khách hàng, xác suất từ chối phải được duy trì dưới ngưỡng đặt ra để bảo đảm chất
lượng dịch vụ.
Bài toán được đặt ra ở đây là phải xác định số slot mục tiêu (số lượng slot tối đa
giành cho các tiến trình di trú máy ảo) để duy trì xác suất từ chối yêu cầu khách hàng mới
và thời gian chờ của di trú máy ảo dưới ngưỡng được xác định trước. Nếu xác suất từ chối
yêu cầu của khách hàng mới cao thì khả năng từ chối yêu cầu của khách hàng càng cao dẫn
đến lợi nhuận thấp (trường hợp slot mục tiêu lớn). Ngược lại nếu xác xuất từ chối thấp thì

2
thời gian chờ của di trú máy ảo trong hệ thống sẽ tăng (trường hợp slot mục tiêu nhỏ). Vậy
số lượng slot mục tiêu cho di trú máy ảo bao nhiêu là phù hợp. Luận văn “Nghiên cứu tìm
thuật toán tốt nhất trong việc tìm kiếm slot mục tiêu ứng với xác suất từ chối và thời gian
chờ” nhằm tìm phương pháp làm giảm thời gian chờ và xác suất từ chối của hệ thống đối
với sự di chuyển của khách hàng sao cho hệ thống có thể sử dụng ít tài nguyên hơn trong
khi vẫn đảm bảo chất lượng của dịch vụ.


3

CHƢƠNG 1 - TỔNG

1.1.

QUAN ĐIỆN TOÁN ĐÁM MÂY

Giới thiệu
Điện toán đám mây là một giải pháp toàn diện cung cấp công nghệ thông tin như một

dịch vụ và là một giải pháp điện toán dựa trên Internet ở đó cung cấp tài nguyên chia sẻ
giống như dòng điện được phân phối trên lưới điện. Các máy tính trong các đám mây được
cấu hình để làm việc cùng nhau và các ứng dụng khác nhau sử dụng sức mạnh điện toán tập
hợp cứ như thể là chúng đang chạy trên một hệ thống duy nhất. Nói cách khác, ở mô hình
tính toán này, mọi khả năng liên quan đến công nghệ thông tin đều được cung cấp dưới dạng
các dịch vụ, cho phép người sử dụng truy cập các dịch vụ công nghệ thông tin từ một nhà
cung cấp nào đó trong đám mây mà không cần phải biết về công nghệ đó, cũng như không
cần quan tâm đến các cơ sở hạ tầng phục vụ công nghệ đó.


1.2.

Các thành phần của điện toán đám mây
Mô hình điện toán đám mây được xây dựng bởi vài đối tượng: các máy khách, các

máy chủ phân tán và trung tâm dữ liệu …. Mô hình điện toán đám mây được tạo bởi ba
thành phần chính (các máy client, trung tâm dữ liệu và máy chủ phân tán). Mỗi phần có mục
đích và đóng vai trò riêng trong việc cung cấp những chức năng ứng dụng cơ bản của đám
mây.

1.2.1. Các máy khách (clients)
Client là một chương trình (hay máy tính) yêu cầu thông tin từ máy khác trong mạng
lưới. Ví dụ, khi một trình duyệt web như Internet Explore yêu cầu web server mở ra một
trang web. Client thông thường là những máy tính để bàn. Nó cũng có thể là máy tính xách
tay, máy tính bảng, điện thoại. Nói chung clients được xếp vào ba loại (Mobile, Thin,
Thick).

1.2.2. Trung tâm dữ liệu (data center)


4
Data center là nơi tập trung nhiều thành phần tài nguyên mật độ cao (hardware,
software...) làm chức năng lưu trữ, xử lý toàn bộ dữ liệu hệ thống với khả năng sẵn sàng và
độ ổn định cao. Data center có thể là một phòng lớn phụ thuộc vào hệ thống của doanh
nghiệp.

1.2.3. Các máy chủ phân tán (distributed servers)
Distributed server là tất cả các server không đặt cùng một vị trí mà được đặt ở khắp
nơi trên thế giới và chúng được liên kết với nhau. Các server được thêm và bớt linh động

hơn. Ví dụ, Amazon có rất nhiều các server trong đám mây của họ trên thế giới. Nếu vì lý do
nào đó mà một trong những server đó bị lỗi thì dịch vụ đang được truy cập sẽ tự động
chuyển qua một server khác.

1.3.

Các tầng kiến trúc của điện toán đám mây
Điện toán đám mây cung cấp các dịch vụ ở tất cả các tầng, từ phần cứng tới các phần

mềm. Các dịch vụ có thể chia thành 3 lớp chính: Phần mềm dịch vụ (software as a service),
nền dịch vụ (platform as a service), và cơ sở hạ tầng dịch vụ (infrastructure as a service).
Các lớp này có thể tập hợp thành các tầng kiến trúc khác nhau, có thể chồng chéo.

1.4.

Mô hình dịch vụ trong điện toán đám mây
Dịch vụ điện toán đám mây bao gồm tất cả các lớp dịch vụ điện toán như cung cấp

năng lực tính toán trên máy chủ hay các máy chủ ảo, không gian lưu trữ dữ liệu, hay một hệ
điều hành, một công cụ lập trình, hay một ứng dụng kế toán … Các dịch vụ cũng được phân
loại khá da dạng, nhưng các mô hình dịch vụ điện toán đám mây phổ biến nhất có thể được
phân thành 3 nhóm: Dịch vụ hạ tầng (IaaS), Dịch vụ nền tảng (PaaS) và Dịch vụ phần mềm
(SaaS).

1.4.1. Phần mềm như là dịch vụ (SaaS)
SaaS (Sofware as a Service) được hiểu là phần mềm như một dịch vụ. SaaS là một
ứng dụng trực tuyến có thể sử dụng thay vì cài đặt trên một server hoặc máy PC. Một trong
những ví dụ cổ nhất là webmail. Những người đã sử dụng Hotmail, Yahoo! Mail, và những
dịch vụ khác từ những thập niên 1990. Nhiều người sử dụng của các dịch vụ này không cần



5
cài đặt một ứng dụng email thay vào đó, người sử dụng chỉ cần duyệt đến trang web của nhà
cung cấp dịch vụ, đăng nhập.

1.4.2. Nền tảng hướng dịch vụ (PaaS – Platform as a Service)
Một nền tảng điện toán dưới dạng đơn giản nhất, đề cập đến một nơi mà phần mềm
có thể được khởi chạy một cách nhất quán miễn là mã đáp ứng được các tiêu chuẩn của nền
tảng đó. Các ví dụ phổ biến của các nền tảng gồm có Windows™, Apple Mac OS X, và
Linux® cho các hệ điều hành; Google Android, Windows Mobile®, và Apple iOS cho điện
toán di động; và Adobe® AIR™ hay Microsoft® .NET Framework. Điều quan trọng của
dịch vụ này không phải là phần mềm mà là về nền tảng mà phần mềm được xây dựng để
chạy trên đó.

1.4.3. Hạ tầng hướng dịch vụ (Infrastructure as a Service)
Infrastructure as a service (IaaS) bao gồm sự kết hợp của các tài nguyên phần cứng
và phần mềm. Phần mềm IaaS là mã mức thấp chạy độc lập với hệ điều hành, được gọi
là trình siêu giám sát, và chịu trách nhiệm kiểm kê tài nguyên phần cứng và phân phối tài
nguyên. Quá trình này được gọi là phân nhóm tài nguyên (resource pooling). Phân nhóm tài
nguyên bằng trình siêu giám sát làm cho có thể ảo hóa, và ảo hóa làm cho tăng khả năng số
lượng máy khách. Một khái niệm để chỉ một cơ sở hạ tầng được chia sẻ bởi một vài tổ chức
có các mối quan tâm giống nhau về các yêu cầu an toàn và tuân thủ quy định về dữ liệu.

1.4.4. Một số dịch vụ khác
Network as a service (NaaS) , Storage as a service (STaaS), ...

1.5.






Mô hình triển khai điện toán đám mây
Đám mây công cộng (Public cloud )
Đám mây riêng (Private cloud)
Đám mây lai (Hybrid cloud )
Đám mây cộng đồng


6

CHƢƠNG 2 - GIẢI

THUẬT TÌM SỐ LƢỢNG TỐI ĐA SLOT

MỤC TIÊU ĐỂ DI TRÚ MÁY ẢO TRONG ĐÁM MÂY
2.1. Giới thiệu
Luận văn nghiên cứu thuật toán tìm số lượng tối đa của các slot mục tiêu
(tổng số lượng slot khách hàng có thể di trú tối đa tại một thời điểm ) trong hệ
thống dịch vụ đám mây, đảm bảo xác suất từ chối và thời gian chờ thỏa ngưỡng
được cho trước. Thuật toán áp dụng cho những doanh nghiệp cung cấp dịch vụ
đám mây, dựa trên xác suất từ chối yêu cầu khách hàng mới muốn tham gia dịch
vụ đám mây và thời gian chờ của các máy ảo đang sử dụng dịch vụ đám mây
muốn di trú đi nơi khác. Từ đó giúp cho doanh nghiệp tổng quan về tình hình tài
nguyên trong hệ thống dịch vụ đám mây của doanh nghiệp và điều chỉnh các
ngưỡng xác suất từ chối cũng như thời gian chờ phù hợp với từng hệ thống dịch
vụ.

2.1.1 Mô tả bài toán
Giả sử trong hệ thống, có một khách hàng yêu cầu một dịch vụ nào đó thì

nhà cung cấp phải tạo ra một máy ảo cho họ. Trong thời gian giao dịch, máy ảo
có thể di trú đến nơi khác trong hệ thống để đáp ứng với sự thay đổi về vị trí của
khách hàng hoặc để cải thiện hiệu suất của hệ thống. Bài toán giả sử rằng tổng số
các slot vật lý mà các máy chủ trong hệ thống có thể cung cấp là N. Số lượng tối
đa của slot có thể được chiếm giữ trong quá trình di trú được ký hiệu là K (K ≤
N) (K là số lượng tối đa của slot mục tiêu có thể di trú cùng một lúc). Số lượng
khách hàng mới tham gia dịch vụ của hệ thống trung bình trong một giây và Số
lượng máy ảo di trú trung bình trong một giây được thể hiện theo quy trình
Poisson[16], tương ứng với λs và λm. Thời gian trung bình để xử lý giữa hai dịch


7

vụ của khách hàng và thời gian trung bình để xử lý giữa hai quá trình di trú của
máy ảo theo phân phối mũ tương ứng với 1 / µs và 1 / µm.

Hình 2.1: Tổng số lƣợng slot N và số lƣợng slot tối đa sử dụng cho xử lý di trú K.
(a) m ≤ K; (b) m > K [18]

Hình 2.1 có hai trường hợp có thể xảy ra trong hệ thống, m ≤ K và m > K, với m
là số lượng máy ảo cần được di trú và K là số lượng các slot mục tiêu bị chiếm
giữ trong di trú hiện hành. Trong trường hợp m ≤ K (hình 2.1a), m máy ảo sẽ
được di trú cùng một lúc. Trong trường hợp m > K (hình 2.1b), chỉ có K máy ảo
được chuyển và m-K máy ảo phải chờ đợi cho đến khi một trong các máy ảo đang
được di trú hoàn tất quá trình di trú. Lưu ý rằng nếu chỉ k slot (k ≤ K) được sử
dụng cho việc di trú (hình 2.1a) thì (K - k) slot mục tiêu dành cho quá trình di trú
có thể được sử dụng để phục vụ sự tham gia của khách hàng mới. Sử dụng quy
tắc hàng đợi tức là đến trước được phục vụ trước.
Vấn đề cần giải quyết là phải xác định số slot tối đa sử dụng cho xử lý di
trú để duy trì xác suất từ chối và thời gian chờ dưới ngưỡng được xác định trước.



8

Nếu xác suất từ chối cao thì khả năng từ chối khách hàng mới càng cao dẫn đến
lợi nhuận thấp. Ngược lại nếu xác xuất từ chối thấp thì thời gian chờ sẽ tăng (thời
gian chờ là thời gian khách hàng chờ đến khi nào có slot trống trong hệ thống).

2.1.2. Đầu vào
N

: Tổng số slot vật lý của server trong hệ thống doanh nghiệp giành cho
khách hàng mới muốn tham gia dịch vụ và khách hàng di trú trong hệ
thống.

λs

: Số lượng khách hàng tham gia dịch vụ của hệ thống trung bình trong một
giây theo phân phối Poisson [16].

λm

: Số lượng máy ảo di trú trung bình trong một giây, trong hệ thống theo
phân phối Poisson .

1/µs : Thời gian trung bình để xử lý giữa hai dịch vụ của khách hàng theo phân
phối mũ (exponential distribution) [17].
1/µm : Thời gian trung bình để xử lý giữa hai quá trình di trú của máy ảo theo
phân phối mũ.
ThR : Ngưỡng xác suất từ chối (xác suất từ chối của khách hàng phải nhỏ hơn

hoặc bằng ngưỡng được cho trước này).
ThW : Ngưỡng thời gian chờ (thời gian chờ của khách hàng phải nhỏ hơn hoặc
bằng ngưỡng được cho trước này).

2.1.3. Đầu ra
Giải thuật trả về slot mục tiêu tối đa (K), K đảm bảo xác suất từ
chối của khách hàng mới và thời gian chờ của khách hàng di trú trong đám
mây không vượt quá ngưỡng đã được cho trước. Nếu không tìm được K
thỏa xác suất từ chối và thời gian chờ thì giá trị trả về là 0, ngược lại là giá
trị K.


9

2.1.4. Sơ đồ tuần tự
2.2. Giải thu t kết hợp giải thu t K với ngƣỡng thời gian
1

Require: N,  m,  s,  m,  s, ThR, ThW

2

Find Range Of K from constraint

3

for k




K

i 0

PN , i ≤

ThR ;

Range of K do



 j 0 PN , j TND, j ;
K 1

4

Find E[TD] =

5

If E[TD] is minimum && E[TD] ≤ ThW then

P T

K* = k;

6
7


N
D
i  2 K 1 i , K i , K

endif

8

endfor

9

return K* ;

2.2.1. Sơ đồ chuyển dịch trạng thái

Hình 2.3: Sơ đồ chuyển dịch trạng thái [18]


10

Hình 2.4: Sơ đồ cân bằng tải hệ thống [18]

Sơ đồ chuyển trạng thái được sử dụng để tính toán xác suất bị từ chối và thời gian
chờ được đưa ra trong hình 2.4. Trong sơ đồ chuyển trạng thái này, mỗi trạng thái
trong hệ thống được thể hiện ở hai tham số (i, j), i là tổng số slot bị chiếm giữ
trong hệ thống (i ≤ N), và j là số slot bị chiếm của các tiến trình di trú hiện tại (j ≤
K). Ví dụ, trạng thái (3, 1) là tổng số slot chiếm giữ là 3, trong đó có 1 slot bị
chiếm cho việc di trú. Điều đó có nghĩa, có hai khách hàng trong hệ thống, và
một trong số hai người đó đang di trú. Bởi vì i là tổng của các slot đang được sử

dụng bởi khách hàng mới và các slot mục tiêu sử dụng cho di trú, cho nên i ≥ 2j
(vì mỗi người đang di trú cần 2 slot).
Hệ thống bắt đầu với trạng thái (0, 0) tức là chưa có khách hàng nào tham
gia hệ thống, trạng thái này chỉ có thể đi đến trạng thái (1, 0) tức là có một người
tham gia hệ thốngvới một tỷ lệ tham gia của khách hàng mới là λs. Nếu một
khách hàng mới muốn tham gia hệ thống trong khi thời điểm đó hệ thống không
có bất kỳ khách hàng nào di trú thì trạng thái (i, 0) sẽ được chuyển sang trạng thái


11

(i + 1, 0) với cùng tỷ lệ tham gia λs . Ngoài ra, nếu hệ thống ở trạng thái (i, 0) và
một khách hàng rời hệ thống, các slot cắm dành riêng cho khách hàng đó được
giải phóng và hệ thống sẽ chyển sang trạng thái (i-1, 0). Thời gian để xảy ra trạng
thái (i-1, 0) là được phân bố theo cấp số nhân với tỷ lệ iμs , và phụ thuộc vào số
lượng khách hàng đang sử dụng dịch vụ. Trong trường hợp tại trạng thái (i, j) với
j là các slot mục tiêu bị chiếm giữ cho di trú, λs là tỷ lệ mà hệ thống chuyển từ
trạng thái (i, j) đến trạng thái (i + 1, j ) và (i - 2j)us là tỷ lệ mà hệ thống chuyển từ
trạng thái (i, j) đến trạng thái (i - 1, j). Ngoài ra, iλm là tỷ lệ hệ thống chuyển từ
trạng thái (i, j) sang trạng thái (i + 1, j + 1) và jμm là tỷ lệ mà hệ thống chuyển từ
trạng thái (i, j) qua trạng thái (i-1, j-1).
Bảng 2.1: Cân bằng tải hệ thống [18]

Trạng thái

Tỷ lệ rời hệ thống = tỷ lệ tham gia hệ thống

Loại

(0, 0)


λsP0, 0 = μsP1, 0

1

(N, 0)

NμsPN, 0 = λsPN-1, 0

2

(i, 0); 0 < i < N

(iμs + λs + iλm)Pi, 0 = λsPi-1, 0 + (i + 1)μsPi+1, 0 +
μmPi+1, 1

(2K, K); 2K = N

KμmPN, K = λmPN-1, K-1

(N, j); 0 < j < N/2

((N − 2j)μs + jμm)PN, j = λsPN-1, j + (N − 2j +
1)λmPN-1, j-1

(i, j); i # N, 0 < j < i/2,

((i − 2j)μs + jμm + λs + (i − 2j)λm)Pi, j = (i − 2j

j

+ 1)λmPi-1, j-1 +λsPi-1, j + (i − 2j + 1)μsPi+1,j + (j

3
4
5

6

+ 1)μmPi+1, j+1
(i, K); 0 < K < i/2

((i − 2K)μs + Kμm + λs)Pi, K = (i − 2K +
1)λmPi-1, K-1 + λsPi-1, K + (i − 2K + 1)μsPi+1, K

7

Xác suất Pi, j là xác suất để trạng thái (i, j) xảy ra có thể được xác định bằng cách
thiết lập các phương trình cân bằng (tại một trạng thái mà có các tham số đi vào
bằng với các tham số đi ra). Nói chung, chúng ta có thể phân chia thành bảy loại


12

bằng cách sử dụng hệ phương trình cân bằng tương ứng được hiển thị trong bảng
1. Mỗi loại trong bảng 1 được trình bày trong hình 2.4. Hơn nữa, xác suất Pi, j
phải thỏa.
N

K

 P
i 0 j 0

i, j

1

(1)

Hình 2.5: Sơ đồ chuyển trạng thái của trƣờng hợp N = 3 và K = 1 [18]

Từ những phương trình cân bằng trong bảng 1 và công thức (1), chúng ta dễ dàng
tính được xác suất của mỗi trạng thái trong sơ đồ trạng thái hình 2.5.
Giả sử N = 3 và K = 1, sơ đồ trạng thái sẽ là như hình 2.5. Chúng ta dễ
dàng suy ra các phương trình cân bằng theo sau dựa vào bảng 1.
(0, 0)

λsP0, 0 = μsP1, 0

(1, 0)

(μs + λs + λm)P1, 0 = λsP0, 0 + 2μsP2, 0 + μmP2, 1

(2, 0)

(2μs +λs +2λm)P2, 0 =λsP1, 0 +3μsP3, 0 +μmP3, 1

(3, 0)

3μs P3, 0 = λsP2, 0

(2, 1)

(μm + λs)P2, 1 = λmP1, 0 + μsP3, 1

(3, 1)

(μs + μm)P3, 1 = λsP2, 1 + 2λmP2, 0

P0, 0 + P1, 0 + P2, 0 + P3, 0 + P2, 1 + P3, 1 = 1.
Ví dụ:
 s = 0.5;  m = 1;  s = 0.2;  m = 0.1.


13

Chúng ta có thể tính sác xuất của mỗi trạng thái trong hình 2.5:
P0, 0 = 0.0103; P1, 0 = 0.0258; P2, 0 = 0.0323; P3, 0 = 0.0269; P2, 1 = 0.2585; P3, 1 =
0.6461.

2.2.2. Xác suất từ chối
Khi có một từ chối xảy ra nếu tại thời điểm đó có một yêu cầu tham gia
của khách hàng mới trong khi không có slot nào còn trống trong hệ thống, vì vậy
xác suất bị từ chối bằng tổng của các xác suất có trạng thái (N, j), ∀ j ≤ K. Xác
suất bị từ chối được mô tả theo phương trình sau:
K

Pr(R)   PN , j

(2)

j 0

Từ ví dụ trong phần trước, chúng ta có xác suất từ chối là Pr (R) = P3, 0 + P3, 1 =
0,673.

2.2.3. Thời gian chờ
Hàng đợi là danh sách các máy ảo yêu cầu di trú nhưng không có slot
trống trong hệ thống tại thời điểm đó. Hàng đợi xảy xa trong hai trường hợp sau:
(i) Trường hợp đầu tiên là khi số lượng các slot mục tiêu đạt giá trị tối đa (K) (tức
là k = K). Trường hợp này tương ứng với trạng thái (2K + 1, K), (2K + 2, K), ...,
(N, K). Mặc dù còn nhiều slot trống chưa được sử dụng nhưng hệ thống chỉ cho
phép sử dụng slot cho việc di trú tối đa là K slot. Do đó, hàng đợi chỉ được phục
vụ nếu có bất kỳ quá trình di trú hiện tại hoàn thành. (ii) Trường hợp thứ hai là
không còn slot nào còn trống trong hệ thống. Trường hợp này tương ứng với các
trạng thái (N, 0), (N, 1), ..., (N, K-1). Trong trường hợp này, hoặc là có một
khách hàng bất kỳ rời hệ thống (giao dịch của khách hàng hoàn tất) hoặc có bất
kỳ quá trình di trú hoàn tất thì hàng đợi sẽ được thực thi. T i,D j là kí hiệu thời gian
mà hệ thống vẫn ở trạng thái (i, j). Từ đó ta có thời gian chờ dự kiến được tính
như sau:


14

N

D

[T ] =

P

i  2 K 1

D
i, K i, K

T

Sffằè
Case 1(i)



K 1

P
j 0

D
N, j N, j

T

(3)

Case 2(ii)

Hình 2.6: Thời gian chờ của tiến trình di trú trƣờng hợp K = 1 [18]

Hình 2.6 là ví dụ về thời gian chờ của trường hợp (i) với số lượng tối đa slot mục
tiêu K = 1. S is kí hiệu thời gian từ thời điểm bắt đầu cho đến khi khách hàng i
tham gia hệ thống và S im kí hiệu thời gian từ thời điểm bắt đầu cho đến khi quá
trình di trú i bắt đầu. tm là thời gian phục vụ trung bình cho tất cả khách hàng và ts
và thời gian di trú trung bình cho tất cả khách hàng. Trong Hình 2.6, có bốn
khách hàng sử dụng trong hệ thống, và máy ảo của khách hàng 3 đang được di
trú. Nếu máy ảo của khách hàng 4 cần được di trú tại thời điểm t0 thì máy ảo đó
phải chờ cho đến khi máy ảo của khách hàng 3 kết thúc di trú (vì K = 1). Trong ví
dụ này, số lượng các slot bị chiếm giữ trong các hệ thống là năm (bốn slot dành
cho bốn khách hàng sử dụng và một slot dành cho việc di trú của khách hàng 3).
Như vậy, trạng thái của hệ thống là (5,1). Thời gian chờ khi hệ thống chuyển từ
trạng thái (5,1) sang trạng thái (x, 0), trong đó x là bất kỳ, có thể được tính như
sau:


15

T5D,1 = E[ S1m ] + E[tm] – E[ S 2m ]

(4)

Thời gian chờ của tiến trình di trú ( Ti ,DK ) trong trường hợp (i) có thể được
tính như sau:
Ti ,DK = E[ S1m ] + E[tm] − E[ S Km1 ], 2K
(5)

E[x] là kỳ vọng của x và được tính như sau:

E[ S is ] 

1

s

m
, E[ Si ] 

1

m

(6)

Do đó, phương trình (5) tương đương :
Ti ,DK 

1

s



1

m



K 1

m



m  K m
m  m

(7)

Vì thời gian chờ của tiến trình di trú được xác định nên phương trình (7)
có thể được viết lại:

D
i ,K

T

 m  K m
,

  m  m
0,


0  K  m

(8)

m  K  N

ρm = λm /μm là tỷ số thời gian mà trung tâm dữ liệu phục vụ cho quá trình di trú.


16

Hình 2.7: Thời gian chờ của tiến trình di trú trƣờng hợp N = 5 và K = 2 [18]

Bây giờ chúng ta xác định TND, j trong trường hợp thứ hai (ii). Ví dụ hình 2.6, với
N = 5 and K = 2. Hiện tại có bốn khách hàng, và máy ảo của khách hàng 3 đang
được di trú. Vì vậy, không có slot cắm có sẵn trong hệ thống. Ym kí hiệu trường
hợp máy ảo của khách hàng 3 kết thúc di trú (hình 2.7a) và Ys kí hiệu trường hợp
khách hàng 1 rời khỏi hệ thống (hình 2.7b). Máy ảo của khách hàng 4 sẽ được di
trú vào thời điểm t0, phải đợi cho đến khi một trong hai trường hợp Ym hoặc Ys
xảy ra .
TND, j được tính bởi công thức sau:


17

TND, j  Pr(Ym ).( E[ S1m ]  t m  E[ S mj1 ]  Pr(Ys ).( E[ S1s ]  t s  E[ S mj1 ]
                     
(a)

(b)

 1
1
j 1


 P(t s  t m  E[ S1m ]  E[ S mj1 ]).


m 
 m  m
1
1
j 1

 P(t s  t m  E[ S1m ]  E[ S mj1 ]). 




s
m 
 s

   j m 

 e s ( m m ) / m m  m


 m m 
 (1  e

  s ( m  m ) / m m

 1

1 j 1

)
 



s
m 
 s

(9)

Thay thế phương trình (8) và (9) vào phương trình (3), chúng ta có được
giá trị kỳ vọng của thời gian chờ cho quá trình di trú. Sử dụng kết quả này để tính
toán thời gian chờ của ví dụ được đề cập trong phần trước, chúng ta có được E
[TD] = 10,264.

2.2.4. Số lượng tối đa của slot mục tiêu (K)
Từ phương trình (2), xác suất bị từ chối sẽ cao nếu K là lớn. Do đó hiệu
suất của hệ thống được giảm. Trong thực tế để đảm bảo chất lượng dịch vụ thì
xác suất từ chối phải được duy trì dưới ngưỡng chấp nhận được, kí hiệu ThR.
Điều kiện này được viết lại như sau :
Pr(R) ≤ ThR

(10)

Mục tiêu để xác định giá trị của K như sau:
min Cost ( N , K , E[T D ])
K

s.t

Pr(R)  ThR ,
E[T D ] 

(11)
K 1

N

P

i  2 K 1

D
i, K i, K

T

  PN , jTND, j
j 0


18

Tổng số slot trong các hệ thống là N. Ω là đơn vị chi phí cho một slot.
Như vậy, tổng chi phí mà hệ thống phải mất là N Ω. Khi tổng chi phí của các hệ
thống vượt quá một giá trị nhất định ((N + δ) Ω) thì các máy ảo sẽ được cấp phát
lại (hoặc được di trú) để giảm chi phí tổng. Hệ thống phải tốn rất nhiều tiền cho

chi phí δΩ cho đến khi hoàn thành tiến trình cấp phát lại máy ảo. Xử lý di trú
càng lâu thì chi phí cho hệ thống tốn càng nhiều. Vì vậy, để giảm chi phí của hệ
thống, chúng ta phải giảm thời gian chờ của các tiến trình di trú. Hàm mục tiêu có
thể được viết lại như sau:
E[Cost(N, K, E[TD])] = E[TD] Ω
Để có được thời gian chờ nhỏ nhất hàm mục tiêu được viết lại như sau:
N

min
K

s.t

P

i  2 K 1

K 1

D
D
i , K Ti , K   PN , j TN , j

Pr(R)  ThR ,

j 0

(12)

Để giải quyết hàm mục tiêu (12), một giải thuật được đưa ra để xác định

giá trị của K thỏa các ràng buộc về thời gian chờ và xác suất từ chối. Từ thuật
toán 1 ta tìm được một khoảng giá trị của K thỏa mãn các ràng buộc, với mỗi giá
trị của K trong khoảng đó sẽ làm giảm thiểu thời gian chờ đợi trung bình E[TD],
ta gọi đó là mục tiêu biến K*. Giá trị thời gian chờ tối thiểu là tối ưu giá trị
E*(TD) của phương trình (12).


19

CHƢƠNG 3 - MÔ

PHỎNG VÀ THỰC NGHIỆM

3.1. Giới thiệu
Luận văn nghiên cứu giải pháp giả lập một hệ thống điện toán đám mây
để triển khai giải thuật ở chương hai và giao diện người dùng thể hiện một cách
trực quan thân thiện với người quản lý. Từ đó doanh nghiệp có thể dễ dàng hơn
trong việc điều chỉnh và xem kết quả điều chỉnh một cách trực quan. Mô phỏng
được thực hiện bằng ngôn ngữ: C#, CPU : core i3, RAM : 2GB.

3.2. Phần mềm thực hiện mô phỏng
Để mô phỏng bài toán cần các tham số đầu vào ứng với các giá trị theo
sau là : tổng số slot trong hệ thống là 100 (N = 100), tỷ lệ tham gia của khách
hàng mới là 0,1 (λs = 0,1), tỷ lệ xuất hiện của sự kiện di trú là 0,05 (λm = 0,05),
thời gian phục vụ trung bình khoảng 17 phút (μs = 0,001), thời gian di trú trung
bình khoảng 40 giây (μm = 0,025, xác suất bị từ chối là lớn hơn hoặc bằng 15%
(ThR ≥ 15%) và thời gian chờ đợi là nhỏ hơn hoặc bằng 1 giây (ThW ≤ 1s). Sử
dụng các thông số đầu vào trên kết hợp với 7 quy tắc trong bảng 1 cùng với giải
thuật ở giải thuật ở chương 2 (2.2.3).
3.3. 1 Các bƣớc thực hiện mô phỏng

Bước 1: Nhập các tham số đầu vào
Bước 2 : thực thi giải thuật để tìm tập các giá trị slot mục tiêu K.


20

Hình 3.1: ác su t t chối với thời gian chờ [18]

Hình 3.1 cho thấy, trong khi số lượng tối đa slot mục tiêu (K) tăng, giá trị của
xác suất từ chối tăng và thời gian chờ giảm dần khi chạy giải thuật quyết định
giá trị K với các tham số đầu vào N,  m,  s,  m,  s, ThR, ThW. Từ hình 3.3 ta
thấy giá trị K thỏa ngưỡng xác suất từ chối và thời gian chờ là :


K  [1, 5]
Pr(R)  15%

 min K [3, 4, 5]  K  3


D
E
[
T
]

1
K

3




3.3.2. Ngoài ra còn có một số đánh giá


21

Hình 3.2: Ảnh hƣởng của xác su t t chối đối với tốc đ đến [18]

Hình 3.3: Ảnh hƣởng của thời gian chờ đối với tốc đ đến [18]


22

Từ hình 3.2 và hình 3.3, ta thấy rằng tập giá trị K thỏa mãn xác suất từ chối và
thời gian chờ là trong khoảng từ 4 đến 5. Hai biểu đồ này cũng thể hiện sự ảnh
hưởng của tốc độ đến đối với xác suất từ chối và thời gian chờ. Trong mô phỏng
này, chúng ta xét 4 trường hợp khác nhau của những cặp tỉ lệ khách hàng đến và
tỉ lệ khách hàng di chuyển là :
(λs, λm) = {(0.1, 0.05), (0.3, 0.15), (0.4, 0.2), (0.7, 0.35)}
Trong đó tỷ lệ xuất hiện yêu cầu khách hàng mới là gấp đôi tỷ lệ khách
hàng di trú. Hình 3.2 và hình 3.3 minh họa sự tăng đáng kể của xác suất từ chối
và thời gian chờ trong khi tỷ lệ tham gia của khách hàng mới và tỉ lệ di trú giảm.
Xác suất từ chối tăng khoảng 85% khi thời gian chờ là 60 giây tại K = 10 trong
trường hợp (λs = 0,7, λm = 0,35).

Hình 3.4: Ảnh hƣởng xác su t t chối đối với tổng số slot [18]

23

Hình 3.5: Ảnh hƣởng của thời gian chờ đối với tổng số slot [18]

Hình 3.4 và hình 3.5 cho thấy sự ảnh hưởng khi tăng N đối với xác suất từ chối
và thời gian chờ. Bằng hình vẽ ta thấy cả xác suất từ chối và thời gian chờ giảm
trong khi N tăng. Đặc biệt hơn, khi N tăng tỉ lệ xác suất từ chối giảm mạnh trong
khi thời gian chờ giảm chậm.


24

KẾT LUẬN
Luận văn nghiên cứu tìm thuật toán tốt nhất trong việc tìm kiếm slot mục
tiêu ứng với xác suất từ chối và thời gian chờ. Giải thuật xác định K (chương 2)
được cải tiến từ giải thuật xác đinh K [18]. Bằng cách kết hợp giải thuật xác
định K với ngưỡng thời gian chờ đã làm giảm thời gian chờ và xác suất từ chối
dịch vụ của hệ thống. Ngoài ra, giải thuật K cải tiến còn làm tăng hiệu suất phân
bổ tài nguyên của doanh nghiệp trong điện toán đám mây.
Các giải pháp áp dụng trong giải thuật xác định số lượng tối đa của slot
mục tiêu (K) dựa trên các ngưỡng nhất định để giới hạn số lượng các slot mục
tiêu sử dụng trong quá trình di trú đã được phân tích. Đó là sơ đồ chuyển dịch
trạng thái, giải thuật Gauss Jodan, công thức để tính xác suất bị từ chối đối với
khách hàng mới và thời gian chờ của những tiến trình di trú.
Giải thuật xác định K được đề xuất đã được phân tích và đánh giá dựa
trên chương trình được mô phỏng. Ứng dụng này có thể giúp các quản trị viên
quản lý hệ thống hiệu quả hơn bằng cách loại bỏ slot dư thừa, tiết kiệm công sức
và giảm chi phí. Cụ thể là trong điện toán đám mây cho di động: khách hàng
thường xuyên di trú và cũng cần thiết cho việc thiết lập định kỳ di trú các máy
ảo trong hệ thống để cải thiện hiệu suất của hệ thống. Vì vậy, giải thuật xác định

K trong luận văn sẽ mang lại những cải tiến đáng kể trong khi vẫn đảm bảo chất
lượng dịch vụ.
Trong thực tế, giải thuật xác định K còn có thể được tiếp tục nghiên cứu
để xác định tổng số lượng slot (N) trong hệ thống tự động ứng với xác xuất từ
chối và thời gian chờ.