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

t¼m ki¸m nhị ph¥n trong tøng ma trªn gi£i ph¡p BINARY nA mà
méi ki¸n t¤o ra để so s¡nh và x¡c định gi¡ trị tèt nh§t cõa gi£i ph¡p trong méi l¦n
lặp, Sbest, gi¡ trị cõa gi£i ph¡p được th½nh theo Công thùc (2.7). Gi¡ trị tèt nh§t này
 42
gọi là f(Sbest).
 Mục đích cõa thuªt to¡n là nh¬m tèi thiºu sè lượng m¡y vªt lý, v¼ th¸ c¦n t«ng
lñi ½ch trung b¼nh tài nguy¶n cõa c¡c m¡y vªt lý c¦n dùng. Do vªy, mùi con ki¸n t¼m
ra gi£i ph¡p tèt nh§t cõa l¦n lặp được gûi vào cặp "dịch vụ £o hóa-m¡y vªt lý " được
t½nh b¬ng nghịch đảo cõa gi¡ trị hàm mục ti¶u được ¡p dụng tr¶n gi£i ph¡p tèt nh§t
Sbest cõa l¦n lặp và thº hi»n b¬ng Công thùc (2.12):
 ( 1
 best f(Sbest) ; n¸u eij = 1; 8i 2 VS; 8j 2 PM
 ∆τij = (2.12)
 0; trường hñp kh¡c
 Tuy nhi¶n, ch¿ con ki¸n tèt nh§t cõa l¦n lặp mới được ph²p gûi mùi, n¶n sự t­c
ngh³n (stagnation) trong thuªt to¡n có thº sớm x£y ra, d¨n đến t¼nh huèng mà t§t
c£ con ki¸n sau đó đều chọn cùng mët dịch vụ £o hóa để được cung c§p tài nguy¶n.
Điều này, làm cho kh£ n«ng thuªt to¡n kh¡m ph¡ c¡c gi£i ph¡p tèi ưu kh¡c s³ gi£m.
Để tr¡nh hi»u ùng này, thuªt to¡n H» ki¸n Max-Min sû dụng mi·n giới h¤n cho gi¡
 min max
trị mùi τij trong đoạn [τ ; τ ]. Công thùc (2.13) và (2.14) được sû dụng để t½nh
cho c¡c gi¡ trị này (C¡c công thùc này được chọn tø [105] để ¡p dụng cho đèi tượng
"m¡y vªt lý - dịch vụ £o hóa").
 1
 τ max = (2.13)
 f(Sbest) × (1 − ρ)
  
 τ max × 1 − pN pbest
 τ min = (2.14)
 (avg − 1) × pN pbest
 Trong đó, N là sè lượng dịch vụ £o hóa, avg = N=2 và 0 ≤ pbest ≤ 1 là tham sè
điều ch¿nh bi¶n cõa v»t mùi.
 Tóm l¤i, thuªt to¡n MDRAVS-MMAS để gi£i bài to¡n MDRAVS đưñc tr¼nh bày
như Thuªt to¡n 5. Thuªt to¡n này được tr¼nh bày trong công tr¼nh sè 2.
 - Ho¤t động cõa thuªt to¡n:
 Đầu ti¶n, thuªt to¡n khởi t¤o gi¡ trị ban đầu cho c¡c tham sè và gi¡ trị mùi ban
đầu cõa c¡c cặp "dịch vụ £o hóa-m¡y vªt lý ".
 Ti¸p đến, thuªt to¡n thực hi»n numLoop l¦n lặp để c¡c con ki¸n x¥y dựng gi£i
ph¡p cung c§p tài nguy¶n (tø L»nh 2 đến L»nh 22). Trong đó, tương ùng méi l¦n lặp,
tøng con ki¸n chọn mët m¡y vªt lý j (gọi là m¡y vªt lý hi»n hành) và b­t đầu x¥y
dựng gi£i ph¡p (tø L»nh 3 đến L»nh 12). Để đạt điều này, khởi t¤o ma trªn gi£i ph¡p
 nA
BINARY có c¡c ph¦n tû eij := 0 (L»nh 5).
 43
 Thuªt to¡n 5: Thuªt to¡n MDRAVS-MMAS.
 Đầu vào:
 ∗ ∗∗
 • Tªp dịch vụ £o hóa VS với c¡c vector ri , ri . Tªp c¡c m¡y vªt lý PM.
 • C¡c tham sè: α; β; ρ, pbest; τ max, sè l¦n lặp numLoop và sè ki¸n numAnt.
 Đầu ra : Gi£i ph¡p tèt nh§t, Sbest−toan−cuc, là sè lượng m¡y vªt lý được dùng.
 best max max
 1 Khởi t¤o c¡c tham sè α; β; ρ, p ; τ và thi¸t lªp gi¡ trị mùi τij = τ ;
 2 for nL := 1 ! numLoop do
 3 for nA := 1 ! numAnt do
 4 j := 1 ; /* Sû dụng mët m¡y vªt lý j, j là ch¿ sè lượng m¡y vªt lý. */
 nA
 5 BINARY := [eij := 0]; 8i 2 VS; 8j 2 PM;
 6 while (VS 6= ;) do
 (  )
  M
 temp P ∗ ∗∗
 7 VS = i 2 VS  xij = 0 ^ Loadj + ri + ri ≤ Cj; 8j ;
 j=1
 temp
 8 if (VS 6= ;) then
 temp
 9 Chọn ng¨u nhi¶n mët dịch vụ £o hóa i 2 VS theo x¡c su§t
 α β
 [τij ] ×[ηij ] temp
 pij := P α β ; 8i 2 ;
 temp [τuj ] ×[ηuj ] VS
 u2VS
 ∗ ∗∗
10 eij := 1; VS := VS − fig; Loadj := Loadj + (ri + ri );
11 else
12 j := j + 1 ; /* Sû dụng th¶m mët m¡y vªt lý j. */
 nA
13 So s¡nh c¡c gi£i ph¡p thông qua c¡c ma trªn BINARY cõa méi con ki¸n
 t¤o ra dựa vào gi¡ trị f(Sbest) và lưu gi£i ph¡p tèt nh§t vào bi¸n
 Sbest−vong−lap;
 best−vong−lap
14 if (nL = 1 _ Best − T oan − Cuc(S )) then
 best−toan−cuc best−vong−lap
15 S := S ; /* Chọn gi£i ph¡p tèt nh§t toàn cục mới.
 Trong đó, Hàm Best − T oan − Cuc(Sbest−vong−lap) kiºm tra Sbest−vong−lap có
 ph£i là gi£i ph¡p tèt nh§t đến thời điểm hi»n t¤i hay không. */
 min max
16 T½nh gi¡ trị τ ; τ dựa vào c¡c Công thùc (2.13) và (2.14);
17 foreach (i; j) 2 (VS × PM) do
 best
18 τij := ρ × τij + ∆τij ;
 max
19 if (τij > τ ) then
 max
20 τij := τ ;
 min
21 if (τij < τ ) then
 min
22 τij = τ ;
 best−toan−cuc
23 return Gi£i ph¡p tèt nh§t toàn cục S ;
 44
 Ti¸p đến, con ki¸n chọn c¡c dịch vụ £o hóa để được cung c§p tài nguy¶n tø c¡c
m¡y vªt lý cho đến khi tài nguy¶n cõa m¡y vªt lý được b¢o háa. Điều này đạt được
 temp
b¬ng c¡ch khởi t¤o tªp VS chùa c¡c dịch vụ £o hóa i chưa được cung c§p tài
nguy¶n tø b§t kỳ m¡y vªt lý nào và không vượt qu¡ n«ng lực tài nguy¶n cõa m¡y
vªt lý hi»n hành (L»nh 7). N¸u (VS 6= ;) th¼ ¡p dụng phương ph¡p roulette wheel
(dựa tr¶n gi¡ trị hàm x¡c su§t pij) chọn mët dịch vụ £o hóa i để được cung c§p tài
nguy¶n tø m¡y vªt lý hi»n hành j (L»nh 9). Thi¸t lªp gi¡ trị ph¦n tû eij cõa ma trªn
BINARY nA b¬ng 1, lo¤i bỏ dịch vụ đó ra khỏi tªp (VS và cªp nhªt t£i cõa m¡y vªt
lý (L»nh 10). Ti¸n tr¼nh này thực hi»n cho đến khi n«ng lực tài nguy¶n cõa m¡y vªt
lý hi»n hành cán kh£ n«ng đáp ùng (tø L»nh 6 đến L»nh 11). Sau đó, khi n«ng lực
cõa m¡y chõ được b£o háa (tùc là réng) th¼ chon mët m¡y vªt lý mới và thực hi»n
ti¸n tr¼nh cung c§p tài nguy¶n cho đến khi t§t c£ c¡c dịch vụ £o hóa được được cung
c§p tài nguy¶n (tø L»nh 6 đến L»nh 12).
 Sau khi t§t c£ c¡c con ki¸n đã x¥y dựng gi£i ph¡p cung c§p tài nguy¶n, thuªt
to¡n thực hi»n so s¡nh c¡c gi£i ph¡p để t¼m ra gi£i ph¡p tèt nh§t váng lặp (thông qua
hàm mục ti¶u: tèi thiºu sè m¡y chõ vªt lý), gi£i ph¡p tèt nh§t này được lưu vào bi¸n
Sbest−vong−lap (L»nh 13).
 Ti¸p đến, n¸u ch¿ có mët l¦n lặp th¼ gi£i ph¡p tèt nh§t cõa l¦n lặp này trở thành
gi£i ph¡p tèt nh§t toàn cục. Ngược l¤i, thuªt to¡n so s¡nh với gi£i ph¡p tèt nh§t toàn
cục hi»n hành. N¸u gi¡ trị hàm mục ti¶u cõa gi£i ph¡p tèt nh§t l¦n lặp hi»n hành
được c£i thi»n th¼ gi£i ph¡p này trở thành gi£i ph¡p tèt nh§t toàn cục mới (L»nh 14
đến 15).
 Cuèi cùng, t½nh c¡c gi¡ trị τ min; τ max và cªp nhªt mùi tr¶n t§t c£ c¡c cặp "dịch vụ
£o hóa-m¡y vªt lý ". N¸u mët cặp "dịch vụ £o hóa-m¡y vªt lý " nhªn gi¡ trị mùi cao
hơn τ max th¼ gi¡ trị mùi này được khởi t¤o l¤i ở mùc gi¡ trị τ max. Tương tự, khi gi¡
trị mùi th§p hơn gi¡ trị τ min th¼ gi¡ trị này được cªp nhªt ở mùc τ min. Thuªt to¡n s³
k¸t thúc sau numLoop l¦n lặp và tr£ v· gi£i ph¡p tèt nh§t toàn cục (tø L»nh 16 đ¸n
L»nh 23)
 - Ph¥n t½ch thuªt to¡n:
 + Bài to¡n MDRAVS như đã tr¼nh bày t¤i Mục 2.2.1 là bài to¡n cung c§p tài
nguy¶n tĩnh. V¼ th¸, t¤i thời điểm cung c§p tài nguy¶n, tªp dịch vụ £o hóa VS với c¡c
 ∗ ∗∗
nhu c¦u tài nguy¶n ri , ri , tªp c¡c m¡y vªt lý PM cũng như n«ng lực tài nguy¶n cõa
m¡y vªt lý hoàn toàn x¡c định đưñc.
 + Độ hëi tụ cõa thuªt to¡n MDRAVS-MMAS: gọi P (numLoop) là x¡c su§t t¼m
 45
th§y gi£i ph¡p cõa thuªt to¡n H» ki¸n Max-Min sau numLoop bước lặp, sû dụng mô
h¼nh Markov không đồng nh§t, Stutzle [105] và Dorigo [28] chùng minh r¬ng: 8" > 0
và n¸u numLoop đủ lớn th¼ P (numLoop) > 1−". Do đó, lim P (numLoop) = 1.
 numLoop!1
V¼ th¸, thuªt to¡n MDRAVS-MMAS s³ hëi tụ sau numLoop bước lặp.
 + Độ phùc t¤p cõa thuªt to¡n MDRAVS-MMAS: gọi sè ki¸n là numAnt, sè l¦n
lặp là numLoop, sè lượng dịch vụ £o hóa là N, sè lượng m¡y vªt lý là M và sè lo¤i tài
nguy¶n là D th¼ độ phùc t¤p cõa thuªt to¡n là O(numLoop × numAnt × N × M × D).
N¸u cè định sè lo¤i tài nguy¶n D, độ phùc t¤p cõa thuªt to¡n là O(numLoop ×
numAnt × N × M).
2.3.3. Thực nghi»m và nhªn x²t
2.3.3.1. Phương ph¡p mô phỏng
 Để đánh gi¡ c¡c thuªt to¡n, luªn ¡n sû dụng tªp c¡c m¨u dú li»u thực nghi»m
được t¤o ra theo phương ph¡p ng¨u nhi¶n cõa Stillwell [100], như sau:
 X²t N dịch vụ £o hóa và M m¡y vªt lý với sè lo¤i tài nguy¶n D. Tương ùng với
méi dịch vụ £o hóa, sè nhu c¦u t§t y¸u là D=2 và sè nhu c¦u tùy bi¸n là D=2. T§t c£
c¡c nhu c¦u tài nguy¶n được l§y m¨u tø mët ph¥n bè x¡c su§t với trung b¼nh µN và
độ l»ch chu©n δN . Méi dịch vụ £o hóa có ρN x¡c su§t để có mët y¶u c¦u QoS. Luªn
¡n gi£ định gi¡ trị cõa c¡c tham sè này là:
 - Sè lượng dịch vụ £o hóa N l¦n lượt là: 32; 64; 128; 256 và 512. Sè lo¤i tài nguy¶n
D = 6, trong đó, sè nhu c¦u t§t y¸u b¬ng sè nhu c¦u tùy bi¸n và b¬ng 3.
 - N«ng su§t dịch vụ bij = 0,5 (tùc là, mët nûa nhu c¦u tùy bi¸n cõa dịch vụ £o
hóa ph£i được cung c§p), gi¡ trị cõa y¶u c¦u QoS là 0,5, gi¡ trị tham sè µN = 0,5, gi¡
trị δN l¦n lượt là: 0,25; 0,5 và 1,0 và gi¡ trị ρN l¦n lượt là: 0,25; 0,5; 1,0. Thực nghi»m
với c¡c gi¡ trị kh¡c hoặc với c¡c gi¡ trị ng¨u nhi¶n cũng d¨n đến k¸t qu£ tương tự.
 Như vªy, tê hñp gi¡ trị tø c¡c tham sè ở tr¶n s³ có 5 × 1 × 1 × 3 × 3 × 1 = 45 kịch
b£n. Với méi kịch b£n t¤o ra 100 m¨u ng¨u nhi¶n, v¼ th¸ s³ có 4500 m¨u dú li»u đầu
vào để đ¡nh gi¡ thuªt to¡n. C¡c m¨u thực nghi»m được t¤o ra lưu vào tªp tin có c§u
trúc như H¼nh 2.2.
 Để đánh gi¡ hi»u qu£ c¡c thuªt to¡n, luªn ¡n sû dụng hai thước đo: sè lượng m¡y
vªt lý được sû dụng và thời gian thực hi»n thuªt to¡n t½nh b¬ng gi¥y. Gi¡ trị cõa hai
thước đo được l§y trung b¼nh tø 900 (tùc là, 1 × 1 × 3 × 3 × 1 × 100) m¨u thực nghi»m.
 Chương tr¼nh mô phỏng c¡c thuªt to¡n được thực hi»n b¬ng ngôn ngú C++ và
 46
thời gian thực hi»n được đo tr¶n m¡y t½nh đơn có bë vi xû lý Intel Core Duo 1.86
GHz, RAM 2Gb.
 H¼nh 2.2: C§u trúc tªp tin dú li»u thực nghi»m.
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*
 Sè lượng m¡y vªt lý được dùng tương ùng với sè lượng dịch vụ £o hóa khi thực
hi»n c¡c thuªt to¡n được tr¼nh bày trong B£ng 2.1 và H¼nh 2.3. Thời gian thực hi»n
c¡c thuªt to¡n tương ùng với sè lượng dịch vụ £o hóa được tr¼nh bày trong B£ng 2.2
và H¼nh 2.4.
B£ng 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*.
 T¶n Sè lượng dịch vụ £o hóa
 thuªt to¡n N=32 dịch vụ N=64 dịch vụ N=128 dịch vụ N=256 dịch vụ N=512 dịch vụ
 FirstFitDesMax 24 47 90 174 344
 FirstFitDesLex 24 47 90 174 344
 FirstFitDesSum 24 47 90 174 344
 BestFitDesMax 24 47 90 174 344
 BestFitDesLex 24 47 89 170 327
 BestFitDesSum 24 47 90 174 344
 47
 B£ng 2.2: Thời gian thực hi»n c¡c thuªt to¡n First Fit*, Best Fit*.
 T¶n Sè lượng dịch vụ £o hóa
 thuªt to¡n N=32 dịch vụ N=64 dịch vụ N=128 dịch vụ N=256 dịch vụ N=512 dịch vụ
 FirstFitDesMax 0,00009 0,00107 0,00303 0,01076 0,03193
 FirstFitDesLex 0,00010 0,00114 0,00214 0,00827 0,02529
 FirstFitDesSum 0,00016 0,00113 0,00268 0,00932 0,02791
 BestFitDesMax 0,00121 0,00254 0,00833 0,03741 0,13107
 BestFitDesLex 0,00123 0,00232 0,00783 0,03500 0,12253
 BestFitDesSum 0,00128 0,00234 0,00800 0,03693 0,13380
H¼nh 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*.
 C«n cù k¸t qu£ tr¶n b£ng sè li»u và đồ thị, th§y r¬ng:
 - Thời gian thực hi»n thuªt to¡n và sè lượng m¡y vªt lý được sû dụng tỷ l» thuªn
với sè lượng dịch vụ £o hóa, thời gian thực hi»n thuªt to¡n tương đối nhỏ và có thº
¡p dụng trong thực t¸.
 - Khi sè lượng dịch vụ £o hóa nhỏ th¼ gi¡ trị cõa hai thước đo này không kh¡c
bi»t nhau nhi·u giúa c¡c thuªt to¡n. Ngưñc l¤i, trong trường hñp sè lượng dịch vụ
£o hóa lớn (N ≥ 256) th¼ có sự kh¡c bi»t rã r»t, trong đó thuªt to¡n BestFitDesLex
cho sè lưñng m¡y vªt lý được dùng th§p nh§t cán thời gian thực hi»n thuªt to¡n
FirstFitDesLex có gi¡ trị ng­n nh§t.
 48
 H¼nh 2.4: Đồ thị biºu di¹n thời gian thực hi»n c¡c thuªt to¡n First Fit*, Best Fit*.
 Do đó, khi cung c§p tài nguy¶n cho dịch vụ £o hóa (sè dịch vụ lớn) mà quan t¥m
v· thời gian thực hi»n th¼ thuªt to¡n FirstFitDesLex phù hñp, ngược l¤i khi quan t¥m
v· sè lượng m¡y vªt lý tèi thiºu được dùng th¼ thuªt to¡n BestFitDesLex phù hñp.
 Sự kh¡c nhau cõa k¸t qu£ thực nghi»m có thº lý gi£i như sau:
 V· b£n ch§t c¡c thuªt to¡n này gièng nhau, n¶n qu¡ tr¼nh thực hi»n s³ cho k¸t
qu£ gièng nhau. Tuy nhi¶n, nguy¶n nh¥n có sự kh¡c bi»t trong k¸t qu£ thực nghi»m
là: dú li»u đầu vào cõa c¡c thuªt to¡n được s­p x¸p l¤i theo 03 ti¶u ch½ kh¡c nhau,
điều này t¡c động đến k¸t qu£ đầu ra cõa thuªt to¡n. Vªy n¶n có thº k¸t luªn r¬ng:
gi¡ trị hàm mục ti¶u và thời gian thực hi»n cõa c¡c thuªt to¡n phụ thuëc vào dú li»u
đầu vào, ở đây ch½nh là nhu c¦u tài nguy¶n cõa c¡c dịch vụ £o hóa.
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*
 Lựa chọn gi¡ trị c¡c tham sè cõa thuªt to¡n MDRAVS-MMAS:
 Theo tài li»u [102], Stutzle và c¡c cëng sự cho r¬ng: vi»c lựa chọn gi¡ trị tham sè
th½ch hñp s³ c£i thi»n đáng kº cõa hành vi cõa thuªt to¡n theo thời gian t½nh to¡n mà
không £nh hưởng đến ch§t lượng cõa gi£i ph¡p cuèi cùng.
 Hi»n nay, để x¡c định gi¡ trị c¡c tham sè α; β; ρ cõa thuªt to¡n H» ki¸n Max -
 49
Min c¡c nhà nghi¶n cùu thường sû dụng phương ph¡p Th½ch ùng tham sè (Parameter
Adaptation), đó là thay đổi vi»c thi¸t lªp gi¡ trị c¡c tham sè cõa thuªt to¡n khi gi£i
mët bài to¡n cụ thº.
 Trong ph¤m vi cõa đề tài, luªn ¡n thực hi»n theo phương ph¡p được công bè trong
tài li»u [29]. Tùc là, gi¡ trị c¡c tham sè được x¡c định thông qua vi»c kiºm tra thực
nghi»m tr¶n tê hñp c¡c tham sè: gi¡ trị α l¦n lượt là 0; 0,5; 1; 2 và 5 , gi¡ trị β l¦n
lượt là 0; 1; 2 và 5, gi¡ trị ρ l¦n lượt là 0,3; 0,5; 0,7; 0,9; và 0,999.
 Nhªn th§y, c¡c gi¡ trị tèt nh§t s³ là: α = 1; β = 2; ρ = 0; 9 và c¡c gi¡ trị pbest =
0,05, τ max = 3, numLoop = 5, numAnt = 5.
 K¸t qu£ thực nghi»m:
 K¸t qu£ gi¡ trị sè lượng m¡y vªt lý được dùng (gi¡ trị hàm mục ti¶u) tương ùng
với sè lượng dịch vụ £o hóa khi thực hi»n c¡c thuªt to¡n được tr¼nh bày trong B£ng
2.3 và H¼nh 2.5.
 Thời gian thực hi»n (t½nh b¬ng gi¥y) c¡c thuªt to¡n tương ùng với sè dịch vụ được
tr¼nh bày trong B£ng 2.4 và H¼nh 2.6. C¡c k¸t qu£ thực nghi»m được l§y tø trung
b¼nh cõa 100 l¦n thực thi thuªt to¡n. Trong đó:
 - Gi¡ trị thời gian thực hi»n và sè lượng m¡y vªt lý được dùng cõa thuªt to¡n First
Fit* được l§y tø gi¡ trị trung b¼nh cëng gi¡ trị cõa 03 thuªt to¡n FirstFitDesSum,
FirstFitDesMax, FirstFitDesLex.
 - Gi¡ trị thời gian thực hi»n và sè lưñng m¡y vªt lý được dùng cõa thuªt to¡n Best
Fit* được l§y tø gi¡ trị trung b¼nh cëng gi¡ trị cõa 03 thuªt to¡n BestFitDesSum,
BestFitDesMax, BestFitDesLex như đã tr¼nh bày trong B£ng 2.1 và B£ng 2.2, tương
ùng.
B£ng 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.
 T¶n Sè lượng dịch vụ £o hóa
 thuªt to¡n N=32 dịch vụ N=64 dịch vụ N=128 dịch vụ N=256 dịch vụ N=512 dịch vụ
 First Fit* 24 47 90 174 344
 Best Fit* 24 47 89,7 172,7 338,3
 MDRAVS-MMAS 24 47 88 172 323
 50
B£ng 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.
 T¶n Sè lượng dịch vụ £o hóa
 thuªt to¡n N=32 dịch vụ N=64 dịch vụ N=128 dịch vụ N=256 dịch vụ N=512 dịch vụ
 First Fit* 0,000117 0,001113 0,002617 0,009450 0,028377
 Best Fit* 0,001240 0,002400 0,006553 0,036447 0,129133
 MDRAVS-MMAS 0,001000 0,003000 0,020890 0,040120 0,174100
H¼nh 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.
 Tø k¸t qu£ thực nghi»m, th§y r¬ng:
 - Thời gian thực hi»n thuªt to¡n và sè lượng m¡y vªt lý được dùng tỷ l» thuªn với
sè lượng dịch vụ £o hóa, thời gian thực hi»n thuªt to¡n tương đối nhỏ và có thº ¡p
dụng trong thực t¸.
 - Khi sè lượng dịch vụ £o hóa nhỏ th¼ gi¡ trị cõa hai thước đo này không kh¡c
bi»t nhau nhi·u giúa c¡c thuªt to¡n. Ngưñc l¤i, trong trường hñp sè lượng dịch vụ
£o hóa lớn (N ≥ 256) th¼ có sự kh¡c bi»t, trong đó thuªt to¡n MDRAVS-MMAS cho
gi¡ trị sè lượng m¡y vªt lý được dùng ½t hơn (tùc là, gi¡ trị hàm mục ti¶u tèt hơn)
thuªt to¡n First Fit* và Best Fit*. Tuy nhi¶n, thời gian thực hi»n cõa thuªt to¡n
MDRAVS-MMAS cao hơn thuªt to¡n First Fit* và Best Fit*.
 51
H¼nh 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
 Nguy¶n nh¥n kh¡c bi»t này đưñc lý gi£i như sau:
 Thuªt to¡n MDRAVS-MMAS ho¤t động theo phương ph¡p t¼m ki¸m tèi ưu toàn
cục, sû dụng c¡c tham sè như: sè ki¸n numAnt, sè l¦n lặp numLoop n¶n £nh hưởng
đến thời gian thực thi cõa thuªt to¡n. Hơn núa, đối với c¡c bài to¡n k½ch thước lớn
(trường hñp này là sè lượng dịch vụ £o hóa lớn), sû dụng c¡c thuªt to¡n tèi ưu truy·n
thèng (ở đây là 02 thuªt to¡n First Fit* và Best Fit* ) s³ không đủ v· mặt thời gian
t½nh to¡n, thªm ch½ không t¼m được gi£i ph¡p tèi ưu. Do đó, nhúng thuªt to¡n thuëc
lớp Meta-Heuristic như thuªt to¡n MDRAVS-MMAS phù hñp để gi£i c¡c bài to¡n
k½ch thước lớn và có thº t¼m được gi£i ph¡p tèi ưu hoặc g¦n tèi ưu trong thời gian đa
thùc.
2.4. Tiºu k¸t Chương 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 do Mark
Stillwell và c¡c cëng sự [100] đề xu§t. Tr¶n cơ sở đó, đề xu§t mô h¼nh to¡n học cõa
v§n đề cung c§p tài nguy¶n đa chi·u (x²t nhi·u lo¤i tài nguy¶n, như: CPU, RAM,
Disk,...) 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.
 Đây là bài to¡n cung c§p tài nguy¶n h¤n ch¸ thuëc lớp bài to¡n NP-đầy đủ. Để
ước lượng bài to¡n, luªn ¡n thực hi»n c¡c thuªt to¡n để gi£i, cụ thº:
 52
 - Dựa tr¶n c¡c thuªt to¡n chu©n gi£i bài to¡n Vector Packing, ¡p dụng c¡c thuªt
to¡n First Fit và Best Fit [63], [72] để đưa ra 06 phi¶n b£n kh¡c nhau cõa thuªt to¡n.
C¡c thuªt to¡n này đã công bè trong công tr¼nh sè 1;
 - Đề xu§t thuªt to¡n MDRAVS-MMAS tr¶n cơ sở thuªt ¡p dụng thuªt to¡n tèi
ưu H» ki¸n Max-Min [105]. Thuªt to¡n MDRAVS-MMAS đã công bè trong công tr¼nh
sè 2.
 C¡c thuªt to¡n được đánh gi¡ thông qua mët lo¤t c¡c kịch b£n mô phỏng tr¶n
4500 m¨u dú li»u, c¡c dú li»u thực nghi»m được t¤o ra theo phương ph¡p x¡c su§t
ng¨u nhi¶n, k¸t qu£ so s¡nh giúa c¡c thuªt to¡n dựa tr¶n 02 thước đo: sè lượng m¡y
vªt lý c¦n dùng (hàm mục ti¶u cõa bài to¡n) và thời gian thực hi»n cõa thuªt to¡n.
Chương tr¼nh mô phỏng c¡c thuªt to¡n được thực hi»n b¬ng ngôn ngú C++ và thời
gian thực hi»n thuªt to¡n được đo tr¶n m¡y t½nh đơn có bë vi xû lý Intel Core Duo
1.86 GHz, RAM 2Gb. C¡c k¸t qu£ thực nghi»m cho th§y:
 - Độ phùc t¤p cõa c¡c thuªt to¡n thực hi»n trong thời gian đa thùc;
 - Khi sè lượng (mi·n cõa bài to¡n) dịch vụ £o hóa nhỏ th¼ c¡c thước đo tr¶n c¡c
thuªt to¡n này không kh¡c nhau nhi·u. Trường hñp, sè dịch vụ lớn th¼ k¸t qu£ có sự
kh¡c nhau, đó là: thuªt to¡n MDRAVS-MMAS cho sè lượng m¡y vªt lý c¦n dùng ½t
hơn (tùc là, ti¸t ki»m tài nguy¶n hơn) 02 thuªt to¡n First Fit* và Best Fit*. Hơn núa,
thời gian thực hi»n cõa c¡c thuªt to¡n nhỏ, n¶n phù hñp khi ¡p dụng triºn khai trong
h» thèng t½nh to¡n đám m¥y thực t¸.
 53
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
 N·n t£ng m¡y chõ chia s´ t¤i c¡c trung t¥m dú li»u trong h» thèng t½nh to¡n đám
m¥y có 02 lo¤i: n·n t£ng m¡y chõ chia s´ đồng nh§t và n·n t£ng m¡y chõ chia s´
không đồng nh§t. Hơn núa, nhu c¦u sû dụng c¡c m¡y vªt lý cho dịch vụ £o hóa t¤i c¡c
trung t¥m dú li»u ngày càng t«ng. Điều này, d¨n đến vi»c gia t«ng n«ng lượng ti¶u
thụ trong c¡c trung t¥m dú li»u s³ £nh hưởng đến tuêi thọ, hi»u su§t cõa h» thèng và
gia t«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¸, tr¶n cơ sở mô h¼nh h» thèng được tr¼nh bày t¤i Mục 1.7.1, nëi dung cõa
chương này mở rëng bài to¡n đ¢ tr¼nh bày ở Chương 2 để nghi¶n cùu mô h¼nh tài
nguy¶n và nhu c¦u tài nguy¶n trong n·n t£ng m¡y chõ chia s´ không đồng nh§t. Qua
đó, x¥y dựng mô h¼nh to¡n học cõa 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´ 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. Gi¡ trị
hàm mục ti¶u và thời gian thực hi»n c¡c thuªt to¡n này được so s¡nh với thuªt to¡n
FFD [101] trong môi trường mô phỏng đám m¥y CloudSim, dú li»u thực nghi»m được
thu thªp tø c¡c đám m¥y thực t¸ [33], [6]. Nëi dung chương này đã tr¼nh bày trong
c¡c công tr¼nh sè 3, sè 4, sè 6 và sè 7.
3.1. Mô h¼nh tài nguy¶n và nhu c¦u tài nguy¶n
 Kh¡c với Chương 2 là x²t môi trường đồng nh§t, nëi dung chương này kh£o s¡t mët
n·n t£ng m¡y chõ chia s´ không đồng nh§t (Heterogeneous Shared Hosting Platform),
gồm cụm c¡c m¡y vªt lý có c§u h¼nh tài nguy¶n không gièng nhau, được k¸t nèi qua
thi¸t bị m¤ng để chia s´ tài nguy¶n nh¬m cung c§p cho dịch vụ £o hóa (trường hñp
tĩnh). V¼ th¸, mô h¼nh tài nguy¶n và nhu c¦