Tham gia: 31/07/2015
Mô tả:
ệ„
Điều kiện cần trong (2.7): có thể thu được dễ dàng từ những phát biểu ở quan hệ 2.3
Điều kiện đủ ớ (2.7): sự đáo ngược có thể được chi ra bằng mâu thuẫn (ví dụ, giả
thiết rằng với vài giá trị của i, p, > 0 khi f,(0) > oc + g(Ằ,). Như vậy từ những điều
10
kiện ở trên, chúng ta thấy rằng với i. a + g(X) > f,(0), điều này mâu thuẫn với giả
thiết đặt ra).
Lưu V các định nghĩa sau trong giải pháp tối ưu
Rj = {iiPi = 0} (nguồn rỗi)
Ra = Ị iio < (3, < (ị), Ị (nguồn hoạt động)
N = Ịilp, = ộ, í (trung lập)
s = {iip, > (Ị),} (chìm)
Trườnu hop 2 : nếu [3 là nghiệm tối ưu cho phương trình (2.1) thì chúng ta có:
Pi = 0,
i e R d,
(3, = f, '(a+g(À))
i e R a,
Pi = 4 i
>
ie N ,
3, = IV‘
(a)
i eS.
Chứng minh: Điều này là rõ ràng từ định lý Tantawi-Towsley.
Trườnu hơn 3: Nếu p là nghiệm tối ưu của phương trình (2.1) thì chúng ta có:
Ằ = A = Ằr,
-s
lrong đó:
„1
,
I
A, = £ ! / , - ' ( « ) - 4
ẢR =
ieĩit/
I€R
ữ
(2.8)
+ 2 (4 )) J
Chứng minh: Chúng ta thấy rằng phương trình (2.4) tương đương với Ằs = Â nếu
.R
chúng ta sử dụng định nghĩa đưa ra bời phương trình (2.8) và (2.9) và lưu ý rằng:
ieRj
ieR
a
leN
ieS
Sử dụng các định nghĩa về các thành phần node [2] và lưu ý rằng:
0.
±
l =\
/ =l
chúng ta có:
•i = ị ấ k , - A l = 2 > - A )
^
/= l
Từ đó, sử dụng trường họp 2 ta thấy rằng x=xs .
Lưu ý các định nghĩa được liệt kê theo trình tự dưới đây cho giá trị a tuỳ ý (> 0 ):
S{a) = { i \ a > f \ ệ , ) ị
(2.10)
Ằs ( a ) =
(2 .1 1 )
R, (a) = { / | / ( 0 ) > a + g(Ảs ( a) )ị
(2.12)
Rtl(a) = {/ \ /,(>,)> a + g(Ăs(a)) > /(0)},
(2.13)
I
*,+ Y M , - /,■ '( « + ^ ( 4 («)))!
I€lị/(a)
N(a) = { i \ a <
(2-14)
/€/?„(a)
/;
(ự>,),) và a . Ngoài ra, với giá trị oc tối ưu chúng ta có:
A —A —X —Ả(ị(ơ.) —Xị^(ct)
.
.s - -R “
Trên cơ sở các trường hợp ], 2 và 3 ở trên, rút ra thuật toán cân bằng
tảidưới đây,
trong đó đề cập tới các yêu cầu về tính toán.
[Thuật toán 11
1. Sắp xếp các node
0 ( n logn)
Sắp xếp các node sao cho f|(ội) < f2(< 2) - •• ^ fni^n)t>
Nếu f|((Ị)|) + g(0) >
2. Xác định a O(n)
khi đó không cần cân bằng tải.
(Xem các lưu ý dưới đây)
Tìm a sao cho Ảs(a)=ẰK
(a) (ví dụ tìm bằng phương pháp tìm kiếm nhị phân).
Các biếu thức dưới đây được tính lần lượt với giá trị a nói trên.
S(a) = ị i ị a > f,(0,),}
Ãs ( a ) =
RJ («) = { If, (°) ^ a + g(J*(a ))ị
'
Ra{a ) = {/'!./; ( a + g(Ãỵ ịa)) > f ' (0)},
'L a )=
A
ieKj(a)
+ I W “ / l' ' ( fl + ẵ ( 4 ( fl)))]
ieRa{a)
12
3. Xác định tải tối ưu 0(n)
fìỊ - 0.
với
i e Rd (a),
/3' =f'~'(a + g{Ả)),
với
j3,=f,~'{ocị
ieS(a),
[ỉ = ộ .
với
với
i e R a(a),
ieN(a),
với, N( a) = { i \ a < f \ ộ l ) < a + g(Ảs (a))}
Lưu ý : Quá trình xử lý chính của thuật toán là xác định a (trong bước 2). Thuật toán
đơn điếm của Tantawi và Towsley xác định các thành phần của node trước khi tính
a một cách chính xác. Thuật toán của chúng tôi khống đòi hỏi quá trình phàn chia
node riêng rẽ và có thê thay vào đó là xác định phân chia các node trong quá trình
xác định a. Các yêu cầu tính toán ở trên tưưng ứng với số node là n. Trong bước 2,
tuy vậy, các yêu cầu tính toán tãng lên khi sai số cho phép của a giảm. Nếu phương
pháp tìm kiếm nhị phàn được sử dụng thì các yêu cầu tính toán là 0 ( n log 1/s) trong
đó s biếu diễn sai số cho phép.
Chúng ta tiếp tục xem xét một số trường hợp sau:
Trường hơn 4 : hàm số Ằ ) tăng (từ 0) và Ằ (a ) giảm (từ 0 ) một cách đơn điệu
.s(a
.K
khi a tăng.
Chứng minli: trường hợp này có thể chứng minh đơn giản từ định nghĩa (2.11) và
(2.14) và giả thiết của f,(a) và g(A.).
Chú ý: trường hợp này đảm bảo rằng thuật toán có thể xác định a thoả mãn Ằs(a)
=ẢR(ct).
Trường hơp 5 : với giá trị a bất kỳ thoả mãn a , < a < a 2,
R j(a) = Rd(a ,) nêu Rd(a ,) = R j(a 2),
R,(a) = Ra(a,) nếu Ra(a ,) = Ra( a 2),
N(a) = N (a,) nếu N (aị) = N (a 2),
S(a) = S(a,) nếu S(a,) = S(a2)
13
Chứng minh: ta có R,|(a) = R^otị)
với giá trị bất kỳ của a (a, < a < a 2) nếu R,i(a,)
= R j(a 2). Sắp xếp các node sao cho:
f , ( 0 ) > f 2( 0 ) > f \ ( 0 ) > ..... >f„(0)
Rti(a,) = Rd( a 2) hàm ý rằng f,(0) > a , + g(Às(a,)) > f1+
l(0) và f,(0) > a 2 + g(Ằ.s( a 2))
> f,+i(0) với cùng giá trị của i. Từ trường hợp 4 và giả thiết trên g(A.) chúng ta thấy
rằng:
c
a , + g(Às(a,)) < a + g(Ầ.s(a)) < a 2 + g(Às( a 2))
Do vậy:
f,(0) > a + g(Ầs(a)) > fI+|(0),
điều đó có nghĩa là : R j(a) = Rt|(a,) = R j(a 2)
Các biếu thức còn lại cũng được chứng minh tương tự.
Trên cơ sớ của các vấn đề nêu ở trên, chúng ta có phiên bản khác của thuật toán có
thế hoàn chinh hơn và yêu cầu ít thời gian tính toán hơn.
2.2.4 So sánh đặc tính thuật toán cân bằng tải.
Chương trình FOTRAN dược viết để áp dụng thuật toán Tantawi và Towsley (T&T),
thuật toán 1 (K & K 1) như ở trên và thuật toán r (K&K1’) được xây dựng lại từ thuật
toán 1 kết hợp với trường hợp 5. Số bước chương trình của thuật toán 1 và r bằng
khoáng 1/3 hoặc 2/3 số bước của thuật toán Tantawi và Towsley.
Bang 2 .1 so sánh đặc tính của các thuật toán với mô hình phân tán bao gồm 10 node
nối với nhau bởi mạng đơn kênh. Các kênh được mỏ hình hoá như hệ thống hàng đợi
M/M/I 1111 Mỗi node được mô hình như là mô hình máy chủ trung tâm. Cách
.
phân chia tối ưu các node là: một chim (S), hai trung lập (N), 5 nguồn hoạt động
(Ra) và 2 nguồn rỗi (Rj). Thời gian biên dịch và thời gian tính toán của các thuật
toán đã được liệt kê ở trên, 8 là sai số cho phép của a.
Bảng 2.1 : Thời gian biên dịch và thời gian tính toán của các thuật toán.
Thuật toán
T&T
K & KI
K & K I’
Thời gian biên
dịch (giây)
2,11
0.78
0,92
e = 102
3,07
1,88
1,82
14
Thời gian tính toán (mili giây)
10'
104
10'5
3,66
3,24
3,80
2,10
2,65
2,86
1,98
2,53
2,39
10'6
4,17
3,30
2,87
99 6981 14
97 4225 0
68 3214 5
96 2616 0
92 2538 1
81 2521 1
74 2449 9
104 2338 2
139 2117 7
69 2040 0
58 1986 1
63 1752 2
87 1720 0
62 1581 7
82 1554 0