Trang chủ / Bảng Băm Phân Tán

Ảnh Hưởng Của Tham Số “Base” Đối Với Hiệu Năng Của Tapestry (Trái) Và Tham Số “Gossip Interval” Đối Với Hiệu Năng Của Mạng Kelips Trong Mạng


Giá trị churn rate biến thiên từ 10 – 600 s

Tần số lookup: 60s/request/node.

Các DHT được mô phỏng với các tham số biến thiên trong dải giá trị rất rộng để có thể thấy hết các trường hợp. Giá trị của các tham số của từng DHT được cho thấy trong các bảng sau:

Bảng giá trị tham số của Chord



Tham số

Giá trị

Base

2,4,8, 16,32, 64,128

Finger stabilization interval (sec)

1, 3, 6, 9, 18, 36, 72, 144

Pnstimer (sec)

1, 3, 6, 9, 18, 36, 72, 144

Number of successors

16

Có thể bạn quan tâm!

Xem toàn bộ 98 trang tài liệu này.


Bảng 2.15. Giá trị tham số của Chord


Bảng giá trị tham số của Kelips


Tham số

Giá trị

Gossip interval (sec)

1, 3, 6, 9, 18, 36, 72, 144

Group ration

8,16,32

Contact ration

8,16,32

Times a new item is gossiped

2,8

Routing entry timeout (sec)

5, 30, 60, 150, 300


Bảng 2.16. Giá trị tham số của Kelips


Bảng giá trị tham số của Tapestry


Tham số

Giá trị

Base

2,4,8, 16,32, 64,128

Stabilization interval (sec)

1, 3, 6, 9, 18, 36, 72, 144

Number of backup nodes

2,3,4

Number of nodes contacted during repair

1,3,5,10


Bảng 2.17. Giá trị tham số của Tapestry


2.2.5.3. 12BKết quả và phân tích


Hình 2.12. Ảnh hưởng của tham số “base” đối với hiệu năng của Tapestry (trái) và tham số “gossip interval” đối với hiệu năng của mạng Kelips trong mạng 1000 nodes khi các node join/leave với interval=600s




Hình 2.13. Biểu diễn convex hull của successor stabilization interval (trái) và finger stabilization interval (phải ) trong mạng Chord 1000 node khi các node join/leave với interval=600s


XHình 2.12X và XHình 2.13X biểu diễn đường overall convex hull của các giao thức Chord, Kelips và Tapestry trên cùng đồ thị với đường convex hull của các tham số quan trọng. Tham số được coi là quan trọng nếu sự thay đổi giá trị của chúng ảnh hưởng nhiều đến sự thay đổi hiệu năng của DHT.

Các kết quả mô phỏng cho thấy base chính là tham số quan trọng nhất của Tapestry, các tham số khác có ảnh hưởng rất ít. XHình 2.12X (trái) cho thấy đường convex hull ứng với tham số base = 2 thấp hơn các đường convex hull khác và nằm sát với đường overall convex hull trên đồ thị biểu diễn độ trễ tìm kiếm trung bình theo băng thông trung bình mỗi node sinh ra. Điều này chứng tỏ 2 là giá trị tốt nhất của tham số base.

Tương tự như vậy, mô phỏng chứng tỏ sự thay đổi của tham số gossip_interval ảnh hưởng lớn đến sự thay đổi của Kelips trong khi các tham số khác ảnh hưởng không nhiều. XHình 2.12X (phải) cho thấy đường convex hull ứng với tham số gossip_interval = 144s thấp hơn các đường convex hull khác và nằm sát với đường overall convex hull trên đồ thị biểu diễn độ trễ tìm kiếm trung bình theo băng thông trung bình mỗi node


sinh ra. Trong điều kiện churn rate cao, ta nên điều chỉnh tham số gossip_interval đến xấp xỉ 144s để Kelips đạt hiệu suất cao.

Đối với Chord, basictimer và pnstimer là các tham số quan trọng nhất. Không giống với Kelips và Tapestry, XHình 2.13X cho thấy không có giá trị tốt nhất cho hai tham số trên. Các đường convex hull ứng với basictimer nhận giá trị 3s, 9s, 18s, 36s tạo nên đường overall convex hull của Chord. Đối với tham số pnstimer, kết quả cũng tương tự.

Kết quả mô phỏng cho thấy, đối với một số DHT như Kelips hay Tapestry, ứng dụng có thể thiết lập một số tham số đến xấp xỉ một giá trị nhất định để DHT đạt được hiệu năng tối ưu. Trong khi đó, một số DHT cần phải điều chỉnh vài tham số cùng nhau để đạt được hiệu năng tối ưu.


Chương 3. 2BCải tiến hiệu năng của Chord


Mô phỏng, đánh giá hiệu năng của các DHT trong điều kiện churn rate cao cho thấy, nhìn chung các DHT đều làm việc với hiệu năng thấp trong điều kiện churn rate cao.

Mục tiêu của luận văn là cải tiến hiệu năng của các DHT. Trong đó Chord là giao thức được cải tiến đầu tiên. Chord được cải tiến đầu tiên bởi vì Chord là một giao thức đơn giản, có tính chất kinh điển.

3.1. Hạn chế của giao thức Chord

Các mô phỏng đã cho chúng ta thấy hiệu năng của Chord rất thấp trong điều kiện churn rate cao (5-600s), đặc biệt khi churn rate rất cao, tỷ lệ thành công trong việc tìm kiếm dữ liệu của Chord hầu như bằng 0%.

Đó là do thiết kế của Chord. Độ chính xác tìm kiếm của Chord phụ thuộc vào bảng successor list. Trong điều kiện churn rate cao, các node join/leave liên tục, bảng successor list của Chord bị sai giữa các lần cập nhật (chạy giao thức stabilization).


3.2. Giải pháp cải tiến giao thức Chord

Căn cứ vào các nhược điểm của Chord trong điều kiện churn rate cao, luận văn trình bày ba giải pháp cải tiến hiệu năng của Chord.

Giải pháp thứ nhất sử dụng cơ chế lock để quản lý vòng Chord nhằm nâng cao độ chính xác trong bảng successor list của Chord từ đó nâng cao tỷ lệ tìm kiếm dữ liệu thành công.

Giải pháp thứ hai sử dụng cơ chế caching proxy nhằm giảm độ trễ tìm kiếm dữ

liệu


Giải pháp cuối cùng sử dụng cơ chế nhân bản để nâng cao tính dự phòng của dữ liệu, qua đó nâng cao tỷ lệ tìm kiếm thành công cũng như giảm độ trễ tìm kiếm.

3.3. Giải pháp duy trì vòng dùng cơ chế lock


3.3.1. Mục tiêu

Đảm bảo độ chính xác của danh sách successor và predecessor của mỗi node trong điều kiện các node join/leave với tốc độ cao đồng thời giảm sai sót trong trường hợp các xảy ra lỗi.

3.3.2. 3BCơ chế làm việc

Ý tưởng của giải pháp này là sử dụng biến lock tại mỗi node để quản lý sự join/leave của node đó và node sau nó, đảm bảo vòng Chord cập nhật tức thời khi xảy ra join/leave trừ trường hợp lỗi.

Mỗi node có một biến lock, muốn join/leave, node đó phải lấy được lock của chính nó và lock của node ngay sau nó, khi đó lock của node đó và node ngay sau được thiết lập giá trị busy. Ngay sau khi hoàn thành join/leave, lock của các node này được thiết lập giá trị free.

Các trạng thái của node, quá trình join/leave và quá trình xử lý lỗi của giao thức Chord được trình bày trong phần còn lại của mục này.

3.3.2.1. 13BCác trạng thái của node

Các trạng thái của một node được biểu diễn trong XHình 3.1X



Hình 3 1 Biểu đồ chuyển đổi trạng thái của node Chord 3 3 2 2 14B Cơ chế join 1

Hình 3.1. Biểu đồ chuyển đổi trạng thái của node Chord


3.3.2.2. 14BCơ chế join của vòng Chord

Cơ chế join của vòng Chord được biểu diễn trong HX


ình 3.2X, giả sử node q join

vào giữa node p và node r, trước đó node r là successor của node p. Quá trình join như sau.

Đầu tiên, node q lấy lock của nó và gửi thông điệp yêu cầu lock của node r, nếu node r đang bận, lock của nó không không free thì q sẽ phải đợi. Nếu lock của node r đang free, nó sẽ thiếp lập lock = taken, rồi gửi thông điệp thông báo predecessor của q (node p). Nhận được thông điệp, q trỏ con trỏ pred vào p và con trỏ succ vào r rồi gửi thông điệp báo cho node p biết để p cập nhật successor mới. Nhận được thông điệp p


trỏ con trỏ succ vào p và gửi thông điệp tới node r để r giải phóng lock. Node r tiếp tục gửi thông điệp để q giải phóng lock, đến đây quá trình join kết thúc.


Hình 3 2 Biểu đồ thời gian biểu diễn quá trình một node jon vào mạng thành 2

Hình 3.2. Biểu đồ thời gian biểu diễn quá trình một node jon vào mạng thành công


Mã giả của quá trình xử lý node join vào mạng được trình bày trong XThuật toán 3.1X :


event n.Join(e) from app

if e = nil then

lock := free pred := n succ := n

else


lock := taken pred := nil succ := nil

..... Xem trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 26/04/2022