Hình 2.8. Đồ 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 interval=5s (trái) và 10s (phải).
XHình 2.8X biểu diễn tỷ lệ tìm kiếm thành công của Kelips và Tapestry trong mạng 100 node và 1000 node và RTT lần lượt là 1s và 10s. Từ hình này và các kết quả mô phỏng khác, chúng tôi nhận tháy Tapestry có tính khả mở cao hơn Kelips với RTT thấp (RTT=1s,2s).
Dưới đây là bảng so sánh rút ra từ các kết quả mô phỏng
Chord | Kelips | Tapestry | Ghi chú | |
Tỷ lệ thành công | Worse (0 %) | Poor (< 50 %) | Best (<80 %) | Với mọi kịch bản mô phỏng |
Độ trễ | High | Low | ||
Tính khả mở | Poor | Good với mạng có RTT thấp | ||
Băng thông sử dụng | Less | Much |
Có thể bạn quan tâm!
-
Minh Họa Cách Chọn Bảng Định Tuyến Của Một Node Tapestry -
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 -
Ả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 -
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
Xem toàn bộ 98 trang tài liệu này.
Bảng 2.10. So sánh giữa Chord, Kelips và Tapestry
2.2.4.2. T9B rường hợp churn rate cao
Mục tiêu
So sánh hiệu năng của các DHT: Chord, Kelips, Tapestry trong điều kiện churn rate cao (120s – 600s) và rất cao (5-10s). Đánh giá ảnh hưởng của churn rate đến tỷ lệ tìm kiếm thành công và độ trễ tìm kiếm. Đánh giá tính khả mở của các DHT này.
Kịch bản mô phỏng
Topology của mạng mô phỏng: Euclidean
RTT trung bình giữa các node: 2s
Số node mạng : 100, 250, 500, 700 và 1000 node.
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 |
Bảng 2.11. 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.12. 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.13. Giá trị tham số của Tapestry
Kết quả và phân tích
Hình 2.9. Đồ 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 trong mạng Chord 1000 node với interval=120s (trái) và interval=600s (phải).
XHình 2.9X biểu điễn đường overall convex hull của Chord, Kelips và Tapestry trong mạng 1000 node với churn rate lần lượt là 120s và 600s. Các đường convex hull cho ta thấy tỷ lệ tìm kiếm thất bại của Tapestry nhỏ hơn so với Kelips và Chord trong điều kiện churn rate tương đối cao (120s). Nhưng tại churn rate thấp hơn (600s), tỷ lệ tìm kiếm thất bại của Chord lại nhỏ hơn Kelips và Tapestry. Trong cả hai trường hợp, hiệu năng của Kelips đều nằm giữa Tapestry và Chord.
Từ kết quả mô phỏng trên, một tập nhỏ các giá trị tham số của Chord, Kelips và Tapestry được lựa chọn làm đầu vào trong kịch bản mô phỏng thứ 2 ( liệt kê trong các bảng ). Trong kịch bản này, giá trị trung bình của các kết quả mô phỏng được sử dụng để đánh giá ảnh hưởng của churn rate và kích thước mạng nên hiệu năng của các giao thức trên.
Failed lookup vs. churn rate
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Node join/leave interval (s)
Chord100 Kelips100 Tapestry100 Chord500 Kelips500 Tapestry500 Chord1000 Kelips1000
Tapestry1000
1500
Med. successful lookup latency vs. churn rates
1400
1300
1200
1100
1000
900
800
700
Node join/leave interval (s)
Chord500 Kelips500 Tapestry500 Chord100 Kelips100 Tapestry100 Chord1000 Kelips1000 Tapestry1000
Fraction of lookup failed
Med. successful lookup latency (ms)
0
100
200
300
400
500
600
0
100
200
300
400
500
600
Hình 2.10. Tác động của churn rate đối với tỷ lệ tìm kiếm thất bại (hình trên) và độ trễ tìm kiếm trung bình (hình dưới) trong các mạng có kích thước khác nhau.
XHình 2.10X biểu diễn tác động của churn rate đối với tỷ lệ tìm kiếm không thành công (hình trên) và độ trễ tìm kiếm trung bình (hình dưới) trong mạng 100, 500 và 1000 node. Trong các hình trên, ChordN, KelipsN và TapestryN biểu diễn các mạng Chord, Kelips và Tapestry với kích thước N.
Khi churn rate cao, node join/leave với interval < 120s), Tapestry có tỷ lệ tìm kiếm không thành công thấp nhất, tức là có tỷ lệ tìm kiếm thành công cao nhất, trong khi Chord có tỷ lệ tìm kiếm không thành công cao nhất. Nhưng khi churn rate giảm, Chord cho thấy hiệu năng cao hơn so với Kelips và Tapestry. Khi node join/leave với interval > 300s, tỷ lệ tìm kiếm thất bại của Chord thấp nhất trong khi tỷ lệ này của Kelips cao nhất.
1
Failed lookup vs. node numbers
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Node numbers
Chord60 Kelips60 Tapestry60 Chord120
Kelips120
Tapestry120 Chord600
Kelips600
Tapestry600
Fraction of failed lookup
0
100
200
300
400
500
600
700
800
900
1000
Hình dưới cho thấy độ trễ tìm kiếm trung bình của Chord nhỏ hơn so với Kelips và Tapestry trong điều kiện churn rate thấp.
Med. successful lookup latency vs. node numbers
1500
1400 Chord60
Kelips60
1300 tapestry60
Chord120
1200 Kelips120
1100
1000
Tapestry120 Chord600 Kelips600
Tapestry600
900
800
700
Node numbers
Med. successful lookup latency (ms)
0
100
200
300
400
500
600
700
800
900
1000
Hình 2.11. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công (hình trên) và độ trễ tìm kiếm trung bình (hình dưới) theo băng thông trung bình một node sử dụng trong các mạng có kích thước khác nhau với các node join/leave với interval=600s
HX ình 2.11X biểu diễn tác động của kích thước mạng nên tỷ lệ tìm kiếm thất bại
(hình trên) và độ trễ tìm kiếm trung bình (hình dưới) trong mạng với churn rate xấp xỷ 60s, 120s và 600s.
Từ XHình 2.11X ta có thể thấy cả tỷ lệ tìm kiếm thất bại và độ trễ tìm kiếm trung bình của Chord là nhỏ nhất trong khi các chỉ số này của Kelips là lớn nhất. Hình trên cho thấy, khi kích thước mạng tăng lên, cả tỷ lệ tìm kiếm thất bại và độ trễ tìm kiếm trung bình của cả ba DHT đều tăng, nhưng các chỉ số này của Chord và Tapestry tăng chậm hơn nhiều so với Tapestry. Điều này chứng minh rằng tính khả mở của Chord và Tapestry cao hơn Kelips. Dưới đây là bảng tóm tắt kết quả đạt được.
Chord | Kelips | Tapestry | Ghi chú | |
Chỉ số hiệu năng: (1/ Churn rate rất cao 2/ Churn rate cao và trung bình) Tỷ lệ tìm kiếm thất bại | Poor Best | 1- Chord < and < Tapestry 2- Chord < and < Tapestry | Best Worse | |
Độ trễ tìm kiếm trung bình | Best Best | Worse Worse | Medium Medium | |
Tính khả mở (1/ Churn rate rất cao 2/ Churn rate cao và trung bình) | 1- N/A 2- Good | 1- Medium 2- Medium | 1- Good 2- Good | Trong trường hợp 1 đối với Chord, phần lớn lookup không thành công |
Khả năng điều chỉnh đến trạng thái tối ưu | Hard | Easy | Easy | |
Tác động của RTT đến hiệu năng | Low | Low | High | RTT thấp tăng hiệu năng của Tapestry |
Bảng 2.14. Bảng tóm tắt kết quả
2.2.5. Đánh giá ảnh hưởng của các tham số thiết kế đến hiệu năng các DHT
2.2.5.1. 10BMục tiêu
Đánh giá ảnh hưởng của các tham số thiết kế đến hiệu năng của DHT. Xác định các tham số quan trọng và khoảng giá trị tốt nhất của các tham số này.
2.2.5.2. 1BKịch bản mô phỏng
Mô phỏng này được thực hiện với kịch bản giống như kịch bản trong trường hợp churn rate cao (mục X2.2.4.2X )
Topology của mạng mô phỏng: Euclidean
RTT trung bình giữa các node: 2s
Số node mạng : 100, 250, 500, 700 và 1000 node.