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
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!
-
Quá Trình Thực Nghiệm Và Phương Pháp Đánh Giá Hiệu Năng -
Đồ Thị Biểu Diễn Tỷ Lệ Tìm Kiếm Thành Công (Fration Of Successful Lookups) Theo Băng Thông Trung Bình Một Node Sử Dụng (Average Live Bandwidth) Trong Mạng -
Đồ Thị Biểu Diễn Tỷ Lệ Tìm Kiếm Thành Công Theo Băng Thông Trung Bình Một Node Sử Dụng Của Kelisp Và Tapestry Với Rtt=1S, 10S Và Node Join/leave Với -
Biểu Đồ Thời Gian Biểu Diễn Quá Trình Một Node Rời Khỏi Mạng -
Đánh giá hiệu năng của một số thuật toán bảng băm phân tán DHT và đưa ra giải pháp cải tiến hiệu năng của thuật toán CHORD - 11 -
Đánh giá hiệu năng của một số thuật toán bảng băm phân tán DHT và đưa ra giải pháp cải tiến hiệu năng của thuật toán CHORD - 12
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
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
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. 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 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