Luận văn Đánh giá hiệu năng của một số thuật toán bảng băm phân tán DTH và đưa ra giải pháp cải tiến hiệu năng của thuật toán chord

hiệu quả cao, cụ thể là: − Xác định churn rate mà tỷ lệ tìm kiếm dữ liệu thành công của DHT đạt 90% trở lên cho một số trường hợp tốt. − Xác định khoảng giá trị của các tham số của DHT trong những trường hợp này 2.2.3.2. 5BPhương pháp xác định ngưỡng Quá trình tìm ra churn rate cho tỷ lệ tìm kiếm thành công trên 90% trong các trường hợp tốt bao gồm hai quá trình đan xen: quá trình chọn ra churn rate cho hiệu năng cao và quá trình chọn ra dải giá trị tốt của từng tham số. Việc chọn các trường hợp tốt được thực hiện bằng cách mô phỏng với các tham số nhận giá trị biến thiên trong một dải rộng. Dựa trên các kết quả đạt được, chúng tôi chọn ra các dải giá trị tham số cho kết quả tốt, các giải giá trị này hẹp hơn giải giá trị trong mô phỏng đầu tiên. DHT lại được mô phỏng với giải giá trị này. Quá trình chọn churn rate bắt đầu bằng mô phỏng DHT với churn rate cao, hiệu năng của DHT trong trường hợp này thấp, tỷ lệ tìm kiếm thành công < 90 % kể cả những trường hợp tốt. Sau đó, DHT lại được mô phỏng với churn rate rất thấp, hiệu năng của DHT trong trường hợp này tốt hơn cả yêu cầu, tỷ lệ tìm kiếm thành công > 90 % cho hầu hết nhiều trường hợp. Dựa trên hai mô phỏng trên, chúng tôi chọn ra churn rate nằm giữa hai churn rate trên và thực hiện mô phỏng. Quá trình chọn churn rate diễn ra như vậy cho đến khi chọn được churn rate cho kết quả > 90 % trong các trường hợp tốt. Quá trình lựa chọn trên được biểu diễn trong đồ thị Luận văn tốt nghiệp Ngô Hoàng Giang 48 Hình 2.2. Lưu đồ thuật toán quá trình xác định churn rate 2.2.3.3. 6BKịch bản mô phỏng Kịch bản mô phỏng như sau − DHT được mô phỏng: Chord, Kademlia, Tapestry, Kelips − Topology của mạng: Euclidean − Số node trong mạng: 100, 1000 node − Round Trip Time trung bình giữa các node trong mạng: 2s − Tốc độ sinh tìm kiếm trung bình: 10s/lookup/node Luận văn tốt nghiệp Ngô Hoàng Giang 49 2.2.3.4. 7BKết quả và phân tích Kademlia Kademlia đạt được tỷ lệ tìm kiếm thành công trên 90% với churn rate 180s đối với cả mạng 100 node và mạng 1000 node XHình 2.3X biểu diễn tỷ lệ tìm kiếm thành công của Kademlia trong mạng 100 và 1000 nodem, tương ứng với churn rate 180s Hình 2.3. Đồ 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 Kademlia 100 node (trái) và 1000 node (phải). XBảng 2.1X cho thấy khoảng giá trị tham số tốt nhất của Kademlia tại các churn rate trên. 100 nodes 1000 nodes Parameters Values Values Alpha 16 8 K 8,16 8,16 K_tell = k = k Stabilize_timer (sec) 60 Æ 960 120 Æ 960 Stablearn_only 0 0 Bảng 2.1. Bảng tham số của Kademlia Luận văn tốt nghiệp Ngô Hoàng Giang 50 Chord Chord đạt được tỷ lệ tìm kiếm thành công trên 90% với churn rate 1800s đối với mạng 100 node và 4200s đối với mạng 1000 node. XHình 2.4X biểu diễn tỷ lệ tìm kiếm thành công của Chord trong mạng 100 và 1000 nodem, tương ứng với churn rate 1800s và 4200s. Hình 2.4. Đồ 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 100 node (trái) và 1000 node (phải). XBảng 2.2X cho thấy khoảng giá trị tham số tốt nhất của Chord tại các churn rate trên. 100 nodes 1000 nodes Parameters Values Values Base 4, 8, 16 64 number of successors 16 16 finger stabilization interval (sec) 0.5 Æ 9 (0.5, 1, 3, 6, 9) 9 Æ 72 (9, 18, 36, 72) Pnstimer (sec) 0.5 Æ 9 (0.5, 1, 3, 6, 9) 9 Æ 72 (9, 18, 36, 72) Succlisttimer (sec) = pnstimer = pnstimer Bảng 2.2. Bảng tham số của Chord Luận văn tốt nghiệp Ngô Hoàng Giang 51 Kelips Kelips đạt được tỷ lệ tìm kiếm thành công trên 90% với churn rate 2400s đối với mạng 100 node và 7200s đối với mạng 1000 node. XHình 2.5 X biểu diễn tỷ lệ tìm kiếm thành công của Kelips trong mạng 100 và 1000 nodem, tương ứng với churn rate 2400s và 7200s. Hình 2.5. Đồ 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 Kelips 100 node (trái) và 1000 node (phải). XBảng 2.3X cho thấy khoảng giá trị tham số tốt nhất của Kelips tại các churn rate trên. 100 nodes 1000 nodes Parameters Values Values K 10 32 Gossip interval (sec) 0.5 Æ 9 (0.5, 1, 3, 6, 9) 0.5 Æ 6 (0.5, 1, 3, 6) Group ration 5, 10 16,32 Contact ration 5, 10 16,32 N_contacts 5, 10 16 Item_rounds 5 8 Bảng 2.3. Bảng tham số của Kelips Luận văn tốt nghiệp Ngô Hoàng Giang 52 Tapestry Tapestry đạt được tỷ lệ tìm kiếm thành công trên 90% với churn rate lên đến hơn 7200s trong cả hai mạng 100 node và 1000 node. XHình 2.6X biểu diễn tỷ lệ tìm kiếm thành công của Tapestry trong mạng 100 và 1000 nodem, tương ứng với churn rate 7200s Hình 2.6. Đồ 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 Tapestry 100 node (trái) và 1000 node (phải). XBảng 2.4X cho thấy khoảng giá trị tham số tốt nhất của Kelips tại các churn rate trên. 100 nodes 1000 nodes Parameters Values Values Base 128 8,16,32 Stabilization interval (sec) 9 Æ 36 9 Æ 36 Number of backup nodes 4 4 Number of nodes contacted during repair 10 10 direct_reply 0 0 Bảng 2.4. Bảng tham số của Tapestry Luận văn tốt nghiệp Ngô Hoàng Giang 53 Phân tích Kết quả thu được trong các mô phỏng được tổng hợp trong bảng sau: Kích thước mạng DHTs 100 node 1000 node Kademlia 180 180 Chord 1800 4200 Kelips 2400 7200 Tapestry > 7200 > 7200 Bảng 2.5. Giá trị churn rate để các DHT đạt được tỷ lệ tìm kiếm thành công 90% trong mạng 100 và 1000 node Bảng so sánh trên cho thấy Kademlia là DHT tốt nhất trong điều kiện churn rate cao. Kademlia không chỉ đạt được tỷ lệ tìm kiếm thành công 90% trong điều kiện churn rate cao nhất mà còn có tính khả mở cao nhất, hiệu năng trong mạng 1000 node không thấp hơn quá nhiều so với hiệu năng trong mạng 100 node. Chord, Kelips và cuối cùng là Tapestry, chỉ đạt được tỷ lệ tìm kiếm thành công với churn rate > 7200s. 2.2.4. So sánh hiệu năng của các DHT 2.2.4.1. 8BTrường hợp churn rate rất cao Mục tiêu So sánh hiệu năng của các DHT trong trường hợp churn rate rất cao (5-10s). Luận văn tốt nghiệp Ngô Hoàng Giang 54 Kịch bản mô phỏng Điều kiện mô phỏng được biểu diễn trong bảng sau Network size (nodes) RTT (s) Churn rate (s) 100, 1000 1, 2, 5, 10 5, 10 Bảng 2.6. Điều kiện mô phỏng Bảng giá trị tham số của Chord Parameters Values Base 2, 4, 8, 16, 32, 64, 128 Successors 16 Pnstimer (s) 0.5, 1, 3, 9, 18, 36, 72, 144 Basictimer (s) 0.5, 1, 3, 9, 18, 36, 72, 144 Succlisttimer (s) 0.5, 1, 3, 9, 18, 36, 72, 144 Bảng 2.7. Giá trị tham số của Chord Bảng giá trị tham số của Tapestry Parameters Values Base 2, 4, 8, 16, 32, 64, 128 Redundancy 2, 4 Redundant_lookup_num 2, 4 Stabtimer 0.5, 1, 3, 9, 18, 36, 72, 144 Max_repair_num 5, 10 Bảng 2.8. Giá trị tham số của Tapestry Luận văn tốt nghiệp Ngô Hoàng Giang 55 Bảng giá trị tham số của Kelips 100 nodes 1000 nodes Parameters Values Values K 10 32 Round_interval (s) 0.5, 1, 3, 9, 18, 36, 72, 144 0.5, 1, 3, 9, 18, 36, 72, 144 Group_ration 5,10 16,32 Contact_ration 5,10 16,32 N_contacts 5,10 16, 32 Item_rounds 2, 5 2, 8 Bảng 2.9. Giá trị tham số của Kelips Kết quả và đánh giá Hình 2.7. Đồ 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 với interval=5s (trái) và interval=10s (phải). XHình 2.7X cho thấy Chord không thể hoạt động được trong điều kiện churn rate rất cao. Tỷ lệ tìm kiếm thành công của Chord tại churn rate này hầu như bằng 0. Luận văn tốt nghiệp Ngô Hoàng Giang 56 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 Bảng 2.10. So sánh giữa Chord, Kelips và Tapestry Luận văn tốt nghiệp Ngô Hoàng Giang 57 2.2.4.2. 9BTrườ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 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 Bảng 2.11. Giá trị tham số của Chord Luận văn tốt nghiệp Ngô Hoàng Giang 58 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.12. 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.13. Giá trị tham số của Tapestry Luận văn tốt nghiệp Ngô Hoàng Giang 59 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. Luận văn tốt nghiệp Ngô Hoàng Giang 60 Failed lookup vs. churn rate 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 10 0 20 0 30 0 40 0 50 0 60 0 Node join/leave interval (s) Fr ac tio n of lo ok up fa ile d Chord100 Kelips100 Tapestry100 Chord500 Kelips500 Tapestry500 Chord1000 Kelips1000 Tapestry1000 Med. successful lookup latency vs. churn rates 700 800 900 1000 1100 1200 1300 1400 1500 0 10 0 20 0 30 0 40 0 50 0 60 0 Node join/leave interval (s) M ed . s uc ce ss fu l l oo ku p la te nc y (m s) Chord500 Kelips500 Tapestry500 Chord100 Kelips100 Tapestry100 Chord1000 Kelips1000 Tapestry1000 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. Luận văn tốt nghiệp Ngô Hoàng Giang 61 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. 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. Failed lookup vs. node numbers 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 10 0 20 0 30 0 40 0 50 0 60 0 70 0 80 0 90 0 10 00 Node numbers Fr ac tio n of fa ile d lo ok up Chord60 Kelips60 Tapestry60 Chord120 Kelips120 Tapestry120 Chord600 Kelips600 Tapestry600 Luận văn tốt nghiệp Ngô Hoàng Giang 62 Med. successful lookup latency vs. node numbers 700 800 900 1000 1100 1200 1300 1400 1500 0 10 0 20 0 30 0 40 0 50 0 60 0 70 0 80 0 90 0 10 00 Node numbers M ed . s uc ce ss fu l l oo ku p la te nc y (m s) Chord60 Kelips60 tapestry60 Chord120 Kelips120 Tapestry120 Chord600 Kelips600 Tapestry600 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 XHì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. Luận văn tốt nghiệp Ngô Hoàng Giang 63 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. 11BKị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. Luận văn tốt nghiệp Ngô Hoàng Giang 64 − 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 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 Luận văn tốt nghiệp Ngô Hoàng Giang 65 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 Luận văn tốt nghiệp Ngô Hoàng Giang 66 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.12 X (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 Luận văn tốt nghiệp Ngô Hoàng Giang 67 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. Luận văn tốt nghiệp Ngô Hoàng Giang 68 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 Luận văn tốt nghiệp Ngô Hoàng Giang 69 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 Luận văn tốt nghiệp Ngô Hoàng Giang 70 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 XHì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 Luận văn tốt nghiệp Ngô Hoàng Giang 71 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 Luận văn tốt nghiệp Ngô Hoàng Giang 72 status := joinreq sendto e.JoinReq(n) end if end event event n.JoinReq(d) from m if JoinForward and m = oldpred then sendto pred.JoinReq(d) ⊲ Join Forwarding else if LeaveForward then sendto succ.JoinReq(d) ⊲ Leave Forwarding else if pred 6= nil and d  (n, pred] then sendto succ.JoinReq(d) else if lock 6= free or pred = nil then sendto m.RetryJoin() else JoinForward := true lock := taken sendto m.JoinPoint(pred) oldpred := pred pred := m end if end if end event event n.JoinPoint(p) from m status :=joining pred := p succ := m sendto pred.NewSucc() end event event n.NewSucc() from m sendto succ.NewSuccAck(m) succ := m end event event n.NewSuccAck(q) from m lock := free JoinForward := false sendto q.JoinDone() end event Luận văn tốt nghiệp Ngô Hoàng Giang 73 event n.JoinDone() from m lock := free status := inside end event Thuật toán 3.1. Thuật toán join tối ưu hóa 3.3.2.3. 15BQuá trình rời mạng của một node Cơ chế leave của một node khỏi vòng Chord được biểu diễn trong XHình 3.3X, giả sử node q muốn rời khỏi mạng, node q là successor của p và predecessor của r. Quá trình leave như sau: Khi node q muốn rời khỏi mạng, nó phải lấy lock của bản thân, nếu lock của q đang ở trạng thái taken thì q phải đợi đến khi lock chuyển sang trạng thái free. Khi lock của q ở trạng thái free, nó lấy lock và gửi thông điệp yêu cầu rời khỏi mạng đến node r. Nếu lock của r không free thì node q phải đợi, khi lock của r free, r sẽ gửi thông điệp cho phép q rời khỏi mạng. Lúc này Luận văn tốt nghiệp Ngô Hoàng Giang 74 Hình 3.3. Biểu đồ thời gian biểu diễn quá trình một node rời khỏi mạng Luận văn tốt nghiệp Ngô Hoàng Giang 75 event n.Leave() from app if lock 6= free then ⊲ Application should try again later else if succ = pred and succ = n then ⊲ Last node, can quit else status := leavereq lock := true sendto succ.LeaveReq() end if end event event n.LeaveReq() from m if lock = free then lock := taken sendto m.GrantLeave() state :=predleavereq else if lock 6= free then sendto m.RetryLeave() end if end event event n.RetryLeave() from m status := inside lock := free ⊲ Retry leaving later end event event n.GrantLeave() from m LeaveForward := true status := leaving sendto m.LeavePoint(pred) end event event n.LeavePoint(q) from m status :=predleaving pred := q sendto pred.UpdateSucc() end event event n.UpdateSucc() from m sendto succ.UpdateSuccAck() succ := m Luận văn tốt nghiệp Ngô Hoàng Giang 76 end event event n.UpdateSuccAck() from m sendto succ.LeaveDone() ⊲ Leave the system end event event n.LeaveDone() from m lock := free status := inside end event Thuật toán 3.2. Thuật toán leave tối ưu hóa 3.3.2.4. 16BXử lý trường hợp node bị lỗi − Các hàm FixSucc, FixPred (chạy định kỳ) và cơ chế timer được sử dụng để xử lý trường hợp node bị lỗi. Periodic stabilization có hai mục đích: gộp các node mới vào vòng và xóa các node lỗi khỏi vòng. + Cơ chế timer Mỗi khi lock của node i chuyển sang trạng thái busy, node khởi tạo timer. Timer sẽ tắt ngay khi lock của node chuyển sang trạng thái free. Nếu quá thời gian định trước (timeout), lock chưa chuyển sang trạng thái free, node sẽ chuyển trạng thái của lock sang free và thiết lập các biến JoinForward và LeaveForward sang false. Nếu timeout xuất hiện tại node đang join vào mạng, có 2 trường hợp xảy ra. Nếu succ = nil, nó sẽ khởi động lại quá trình join cho đến khi nó lấy được con trỏ successor. Nếu succ ≠ nil, các lock sẽ được giải phóng và quá trình stabilization sẽ đưa node này vào vòng. Nếu timeout xảy ra tại node đang rời khỏi mạng, node đó sẽ rời khỏi hệ thống không đưa ra thông báo. Luận văn tốt nghiệp Ngô Hoàng Giang 77 Nếu timeout xảy ra tại successor của node đang trong quá trình gia nhập hoặc rời khỏi mạng, node sẽ thiết lập biến lock của nó sang trạng thái free và khởi tạo quá trình stabilization. Nếu predecessor thực sự bị fail, quá trình stabilization sẽ tự động khôi phục hệ thống và các lock tương ứng được giải phóng, khi đó hệ thống sẽ trở về trạng thái đúng. FixSucc, FixPred tương tự như các thuật toán manintenance của Chord. Hai cơ chế này đảm bảo p.succ.pred = p đối với bất kỳ node p nào. Cơ chế FixSucc định kỳ chuyển con trỏ successor của một node tới node còn trên mạng gần nó nhất theo chiều kim đồng hồ. Nếu một node phát hiện successor của nó không còn tồn tại nữa, node sẽ thay thế successor bằng node đầu tiên f còn trên mạng trong successor list. Ngay cả khi f kông phải là successor của node này thì có chế FixSucc sẽ cập nhật con trỏ succ trỏ đến successor gần nhất. Cơ chế FixPred định kỳ chuyển con trỏ predecessor của một node tới node gần nhất còn trên mạng theo hướng ngược chiều kim đồng hồ và thiết lập con trỏ pred thành nil nếu nó phát hiện node predecessor không còn tồn tại trên mạng nữa. Điều kiện trong thủ tục Notify được đổi lại để con trỏ pred luôn cập nhật mỗi khi nó có giá trị nil. Successor-list tại mỗi node được duy trì định kỳ. Mỗi node định kỳ cập nhật successor-list của nó bằng cách copy successor-list của successor, đặt successor vào đầu của successor-list và chặt successor-list tới một kích thước cố định. Thuật toán join được xửa để successor của node đang trong quá trình join vào mạng gửi successor-list cùng với thông điệp JoinPont, như vậy các node có thể khởi tạo successor list của mình. procedure n.CheckPredecessor(p) //Locally called periodically if IsAlive(pred) = false then pred := nil Luận văn tốt nghiệp Ngô Hoàng Giang 78 end if end procedure procedure n.Stabilize() // Locally called periodically try p := succ.GetPredecessor() if p=nil and p ∈ (n, succ] then succ := p end if slist := succ.GetSuccList() succlist := succ + slist //Prepend succ to slist succlist := trunc(succlist, k) //Right-truncate //to fixed size k succ.Notify(n) end try catch(RemoteException) succ := getFirstAliveNode(succlist) //Get closest alive //node end catch end procedure procedure n.GetPredecessor() return pred end procedure procedure n.GetSuccList() return succlist end procedure procedure n.Notify(p) if pred = nil or p ∈ (pred, n] then pred := p end if end procedure Thuật toán 3.3. Quá trình stabilization định kỳ để xử lý failure Luận văn tốt nghiệp Ngô Hoàng Giang 79 3.3.2.5. 17B ảng finger Bảng finger được xây dựng như trong thuật toán Chord 3.3.2.6. 18BQuá trình lookup Có thể tìm kiếm sử dụng proxy, dựa trên quá trình tìm kiếm thông thường của Chord hoặc sử dụng tìm kiếm song song (phần nhân bản) 3.4. Giải pháp caching proxy 3.4.1. Mục tiêu Giải pháp caching proxy nhằm làm giảm độ trễ tìm kiếm và góp phần cải tiến cơ chế replication. 3.4.2. Cơ chế làm việc 3.4.2.1. 19BSơ đồ mạng overlay Mạng peer-to-peer được chia thành hai vòng Chord, một vòng là các nút mạng thông thường, vòng kia bao gồm các proxies. Không gian ID của hai vòng giống nhau. Các proxy được chia thành hai loại: main proxy và normal proxy: Mỗi main proxy chịu trách nhiệm cho các normal proxy theo sau nó và main proxy đứng ngay trước nó. Mỗi normal proxy chịu trách nhiệm cho các node có ID đứng trước ID của nó và đứng sau ID của proxy trước nó. Luận văn tốt nghiệp Ngô Hoàng Giang 80 Hình 3.4. Kiến trúc của giải pháp caching proxy 3.4.2.2. 20BQuá trình caching Xét một ví dụ như sau, node A tìm kiếm dữ liệu K, dữ liệu K được lưu trên node C. Node B nằm ngay trước node C. Khi nhận được yêu cầu tìm dữ liệu K từ node A, node B trả kết quả tìm kiếm là node C về cho node A và đồng thời trả kết quả (keyed, nodeid, ipaddress) này cho main proxy chịu trách nhiệm cho node C. Main proxy chuyển tiếp thông tin về node C tới normal proxy chịu trách nhiệm cho node C. Normal proxy cache lại thông tin này. event n.CacheReq sendto p.cache () end event event p.cache from n forwardto pi.cache() end event Normal node ring Proxy ring Main proxy Normal proxy Luận văn tốt nghiệp Ngô Hoàng Giang 81 event pi.cache from p if KeyID exists in cache then if associated nodeid is in cache then ⊲ Ignore request else if associated nodeid is in replication groups then ⊲Add to cache else ⊲Replicate associated nodeID in cache end if else ⊲Add to cache end if end event. Thuật toán 3.4. Quá trình caching Hình 3.5. Biểu đồ thời gian biểu diễn quá trình caching thành công Node A Main proxy keyid, nodeid, nodeip nodeid, nodeip {Add to cache} Normal proxy Luận văn tốt nghiệp Ngô Hoàng Giang 82 3.4.2.3. 21BQuá trình tìm kiếm Khi một node tìm kiếm một key, nó sẽ gửi đồng thời hai request, request thứ nhất tới main proxy tương ứng, request thứ hai được gửi tới node đứng trước gần key nhất trong bảng finger như trong thuật toán Chord Request được gửi tới main proxy sẽ được chuyển tới proxy chịu trách nhiệm cho key cần tìm. Nếu thông tin về key đó đã được cache, proxy sẽ gửi thông tin này tới node tìm kiếm và node tìm kiếm sẽ bỏ qua các thông điệp từ các quá trình tìm kiếm khác. Nếu key đó chưa được cache, proxy sẽ trả về hệ số replication của key đó. Trong trường hợp này, node có thể tìm kiếm key tại các node có ID được tính ra từ hệ số replication. Request gửi tới node trong bảng finger sẽ được xử lý như trong thuật toán Chord. 3.4.2.4. 22BQuá trình duy trì Duy trì vòng proxy Proxy không phải là các node Chord thông thường trên mạng, chúng là các server được dành riêng làm nhiệm vụ proxy. Các server này có tính sẵn sang cao, tần suất gia nhập, rời khỏi mạng hay lỗi của các server này thấp. Cấu trúc overlay, quá trình duy trì (join/leave/failure) tương tự như với vòng Chord. Các proxy có chung danh sách main proxy. Nếu proxy đang join vào vòng proxy là main proxy, nó sẽ thông báo với các proxy khác cập nhật nó trong danh sách main proxy. Nếu main proxy leave khỏi mạng, nó sẽ thông báo với các proxy khác để các proxy này xóa nó khỏi danh sách main proxy. Nếu main proxy bị fail, successor và predecessor của nó sẽ thông báo với các proxy khác để cập nhật danh sách main proxy. Luận văn tốt nghiệp Ngô Hoàng Giang 83 Nếu node đang join hoặc leave là normal proxy, nó sẽ thông báo với main proxy tương ứng để main proxy cập nhật danh sách proxy của nó. Nếu normal proxy bị fail, successor và predecessor của nó sẽ thông báo với main proxy để cập nhật danh sách proxy. Sao lưu: một proxy sao lưu cache của nó trong k proxy liên tiếp sau nó. Khi một proxy phát hiện successor của nó bị fail, nó sẽ thay thế proxy đó bởi proxy đầu tiên còn online trong danh sách proxy của nó. Đồng bộ giữa vòng proxy và vòng các node thông thường Đồng bộ khi node thông thường thay đổi. Khi một node join vào mạng, nó sẽ lấy một bản sao danh sách main proxy từ successor của nó. Khi một node leave khỏi mạng, nó thông báo với caching proxy tương ứng với nó và gửi successor của nó tới proxy. Proxy sẽ kiểm tra xem node đang leave khỏi mạng có trong cache của nó không. Nếu node đã được cache, proxy sẽ chuyển các key mà node chịu trách nhiệm sang successor của node đó và xóa node khỏi danh sách cache. Khi một node join vào mạng, nó sẽ gửi thông tin về successor của nó tới proxy tương ứng. Proxy sẽ kiểm tra xem successor đó đã được cache chưa. Nếu successor đã được cache, các key có ID < ID của node đang join vào mạng sẽ được chuyển tới node này. Khi một node phát hiện successor của nó bị fail, nó sẽ thông báo với proxy tương ứng. Nếu node đã được cache trong proxy, proxy sẽ xóa node đó khỏi cache. event n.Leave from app sendto p.NotifyLeave() end event Luận văn tốt nghiệp Ngô Hoàng Giang 84 event p.NotifyLeave from n sendto pi.NotifyLeave() end event event pi.NotifyLeave from p If n is not in cache then ⊲Ignore leaving node else If succ(n) is in cache then ⊲Merge cache of n to cache of succ(n) else ⊲Add succ(n) to cache end if endif end event event n.Join from app sendto p.NotifyJoin() end event event p.NotifyJoin from n sendto pi.NotifyJoin() end event event pi. NotifyJoin from p If succ(n) is not in cache then ⊲Ignore joining node else If some cached keys of succ(n) belong to n then ⊲Add n to cache and move keys to n else ⊲Ignore joining node end if end if end event event p.NotifyFailure from successor of n sendto p.NotifyFailure() end event event pi.NotifyFailure from p sendto p.NotifyFailure() Luận văn tốt nghiệp Ngô Hoàng Giang 85 end event event pi.NotifyFailure if n is not in cache then ⊲Ignore failure node else ⊲Remove n from cache (or replicate by associate node) end if end event Thuật toán 3.5. Đồng bộ hóa vòng proxy và vòng node Chord thông thường Đồng bộ khi vòng proxy thay đổi Khi một proxy join vào mạng, successor của proxy này sẽ chuyển các key tương ứng với proxy mới join vào mạng sang cho proxy này. Nếu proxy đang join vào mạng là normal proxy, nó sẽ thông báo với main proxy tương ứng cập nhật lại danh sách proxy. Nếu node đang join vào mạng là main proxy, nó sẽ thông báo với main proxy đứng trước nó để lấy về danh sách proxy list và cập nhật danh sách main proxy trong tất cả proxy. Main proxy cũng thông báo cập nhật danh sách main proxy trong các node được cache. Khi một proxy leave khỏi hệ thống, successor của proxy đó sẽ chịu trách nhiệm cho các key được cache trong proxy đang leave. Nếu proxy đang leave là normal proxy, nó sẽ thông báo với main proxy tương ứng để cập nhật danh sách proxy. Nếu proxy đang leave là main proxy, nó sẽ chuyển danh sách proxy sang main proxy ngay sau nó và thông báo với các proxy cập nhật lại danh sách main proxy. Các proxy cũng thông báo với các node thông thường để các node này cập nhật lại danh sách main proxy. Khi một proxy phát hiện successor của nó fail, nó sẽ thay thế proxy đó bởi proxy đầu tiên còn hoạt động trong danh sách successor của nó. Nếu proxy fail là normal proxy, successor hoạt predecessor của nó sẽ thông báo với main proxy tương ứng để main proxy này cập nhật lại proxy list. Nếu proxy bị fail là main proxy, Luận văn tốt nghiệp Ngô Hoàng Giang 86 successor hoặc predecessor của nó sẽ thông báo với các proxy khác và các node thông thường cập nhật lại danh sách main proxy. Để cập nhật danh sách main proxy trong các node thông thường, mỗi proxy thông báo danh sách main proxy mới cho các node mà nó đang cache. Node thông thường sẽ thông báo danh sách main proxy mới cho successor và predecessor của nó cho đến khi các node trong vòng có cùng danh sách main proxy (version giống nhau). Một node dừng việc thông báo danh sách main proxy mới cho successor và predecessor của nó khi danh sách main proxy của nó giống với danh sách main proxy nó nhận được từ successor hoặc predecessor. Quá trình cập nhật này là quá trình lan tỏa nên kết thúc rất nhanh. Quá trình xử lý join/leave/failure của các proxy tương tự như node Chord thông thường Giả mã xử lý thay đổi trong vòng proxy event p.MainProxyListChanged for node n in cache do sendto n.NotifyMainProxyListChanged() end for end event event Notify MainProxyListChanged from p If vn is less than received from proxy or predecessor then # vn: version number of proxy list ⊲Replace its proxy list ⊲Forward proxy list to it successor and predecessor else ⊲Ignore received proxy list end if end event Thuật toán 3.6. Xử lý thay đổi trong vòng proxy Luận văn tốt nghiệp Ngô Hoàng Giang 87 3.5. Giải pháp dùng nhân bản đối xứng cải tiến 3.5.1. Mục tiêu Nhân bản đối xứng nhằm tăng cường tính sẵn sàng của dữ liệu và tránh bottle-neck. 3.5.2. Cơ chế làm việc Giải pháp này dựa trên cơ chế nhân bản đối xứng 3.5.2.1. 23BNhân bản đối xứng Ý tưởng chính của nhân bản đối xứng là mỗi ID i trong hệ thống cần có liên kết với ID f khác. Nếu ID i liên kết với ID f thì node chịu trách nhiệm cho item i cũng chịu trách nhiệm cho cả item i và item j. Tương tự, node chịu trách nhiệm cho item j cũng sẽ chịu trách nhiệm cho item i. Mỗi ID trong hệ thống liên kết với một tập f các ID khác thỏa mãn: nếu ID i liên kết với tập ID r1, ...,rf , thì ID rx, với 1 ≤ x ≤ f , cũng liên kết với các ID r1, ...,rf. Nói cách khác, không gian ID được chia thành N/f lớp tương được sao cho ID trong mỗi lớp này liên kết với nhau. Để đơn giản, người ta thường sử dụng các lớp với module m với m = N/f với N là kích thước của không gian ID. Cho F = {1, ..., f }, khi đó ID i sẽ liên kết với các ID f được xác định bởi công thức r : I x F → I: r(i, x) = i ⊕ (x − 1) + N/f 3.5.2.2. 24BCơ chế nhân bản đối xứng cải tiến Ý tưởng cải tiến ở đây là các key được tìm kiếm với tần suất khác nhau sẽ được nhân bản với hệ số nhân bản khác nhau. Các item trong hệ thống được nhân bản ở các mức khác nhau. Mọi node trong hệ thống đều được nhân bản với hệ số cơ bản (giống nhân bản đối xứng). Các node được tìm kiếm nhiều hơn sẽ được nhân bản với hệ số bổ xung, các node này sẽ được Luận văn tốt nghiệp Ngô Hoàng Giang 88 nhân bản trong một số lớp khác. Đối với các node được nhân bản them thì nhân bản là không đối xứng, node này không nhân bản các item của các node trong các lớp nó được nhân bản bổ xung. Các node trong các lớp liên kết với ID i được xác định như sau: fk: rk(i, x) = i ⊕ (x − 1) + N/f + (k-1).N/f Với N/f k k = 1 là mức nhân bản cơ sở. k > 1 nhân bản bổ xung trong đó k được tính từ proxy dựa trên tần suất tìm kiếm Quá trình duy trì Thuật toán join Khi một node n join vào hệ thống, nó sẽ kích hoạt sự kiện JoinReplication, sự kiện này gửi thông điệp RetrieveItems tới successor để lấy về các item n cần lưu. Thông điệp bao gồm các thông tin về các item nằm trong giải (pred,n], trong đó pred là ID của predecessor và n là ID của nó. Khi successor nhận được thông điệp RetrieveItems, nó khởi tạo một mạng hai chiều rỗng ( f , N). Sau đó, các item liên kết với một ID trong giải xác định được sao từ bảng HashTable cục bộ tới mảng vừa tạo và được gửi trở lại trong thông điệp Replicate tới node vừa join vào mạng. Khi nhận được thông điệp Replicate, node mới join vào mạng sẽ sao các item trong mảng vào bảng HashTable cục bộ. Node mới lúc này sẽ sẵn sàng nhận truy vấn tìm kiếm từ các node khác trong hệ thống. Thuật toán leave Thuật toán leave làm việc tương tự như thuật toán join. Khi một node muốn leave khỏi hệ thống, nó sẽ kích hoạt sự kiện LeaveReplication, sự kiện này sử dụng sự kiện RetrieveItems để sao các item mà nó chịu trách nhiệm và gửi chúng trong thông điệp Replicate tới node successor. Thuật toán chèn Luận văn tốt nghiệp Ngô Hoàng Giang 89 Để chèn một item, node muốn chèn thực hiện quá trình chèn song song tới các node chịu trách nhiệm cho item. event n.JoinReplication() from m sendto succ.RetrieveItems(pred, n, n) end event event n.LeaveReplication() from m sendto n.RetrieveItems(pred, n, succ) end event event n.RetrieveItems(start, end, p) from m for r := 1 to f do items[r] := Æ i := start while i 6= end do i := i ⊕ 1 items[r][i] := localHashTable[r][i] end while end for sendto p.Replicate(items, start, end) end event event n.Replicate(items, start, end) from m for r := 1 to f do i := start while i 6= end do i := i ⊕ 1 localHashTable[r][i] := items[r][i] end while end for end event Thuật toán 3.7. Quá trình tìm kiếm và chèn trong giải pháp nhân bản đối xứng event n.InsertItem(key, value) from app for r := 1 to f do replicaKey := key ⊕ (r − 1)Nf n.Lookup(replicaKey,AddItem(replicaKey, value, r)) Luận văn tốt nghiệp Ngô Hoàng Giang 90 end for end event procedure n.AddItem(key, value, r) localHashTable[key][r] := value end procedure event n.LookupItem(key, r) from app replicaKey := key ⊕ (r − 1)Nf Lookup(replicaKey,GetItem(replicaKey, r)) end event procedure n.GetItem(key, r) return localHashTable[r][key] end procedure Thuật toán 3.8. Join và leave trong trường hợp nhân bản đối xứng Thuật toán xử lý failure event n.FailureReplication( f ailed, predFailed, r) from m s := predFailed ⊕ (r − 1)Nf e := f ailed ⊕ (r − 1)Nf sendto n.StartBulkOwn((s, e], RetrieveItems(s, e, succ)) end event Thuật toán 3.9. Xử lý failure trong nhân bản đối xứng event n.StartBulkOwn(I, msg) from m sendto n.BulkOwn(I, I, n, msg) ⊲ Local message to itself end event event n.BulkOwn(I, R, next, msg) from m MS := R ∩ (u(M), n] ⊲ u(M) is same as pred if MS 6= Æ then Deliver(msg, MS) ⊲ App is responsible for ids in MS Luận văn tốt nghiệp Ngô Hoàng Giang 91 end if limit := n lnext := next sentsucc :=false for i := M downto 1 do ⊲ Node has M unique pointers J := (u(i), limit] if I ∩ J 6= Æ then K := (u(i − 1), u(i)] sendto u(i).BulkOwn(I ∩ J, I ∩ K, lnext, msg) I := I − J ⊲ Same as I := I − (I ∩ J) limit := u(i) lnext := u(i) if i = 1 then sentsucc :=true end if end if end for J := (n, u(1)] if I ∩ J 6= Æ and sentsucc = false and next 6= u(1) then sendto u(1).BulkOwn(Æ, I ∩ J, limit, msg) end if end event Thuật toán 3.10. Thuật toán bulk owner operation Luận văn tốt nghiệp Ngô Hoàng Giang 92 Kết luận Sự phát triển mạnh mẽ và đa dạng của các thiết bị truy cập mạng như điện thoại, PDA, TV,… là một thách thức đối với mạng structured overlay hiện nay. Với sự xuất hiện của các thiết bị này, mạng trở nên bất ổn và kéo theo sự sụt giảm nghiêm trọng hiệu năng của mạng. Cải tiến hiệu năng của mạng trong điều kiện làm việc mới là bài toán đặt ra cho cộng đồng nghiên cứu peer-to-peer hiện nay. Sau khi tóm tắt lý thuyết tổng quan về peer-to-peer, luận văn đánh giá, phân tích và so sánh hiệu năng của các DHT như Chord, Kademlia, Kelips và Tapestry trong điều kiện churn rate cao sử dụng phương pháp mô phỏng. Dựa trên cơ chế hoạt động của Chord, kết hợp với kết quả mô phỏng, luận văn đã chỉ ra hạn chế của giao thức Chord trong điều kiện churn rate cao và đưa ra các giải pháp nâng cao hiệu năng của giao thức này. Trong giai đoạn tiếp theo, tác giả sẽ cài đặt các giải pháp nâng cao hiệu năng của Chord và đánh giá kết quả đạt được, trên cơ sở đó tác giả tiếp tục cải tiến hơn nữa các giải pháp để Chord đạt được hiệu suất cao trong môi trường truyền thông không dây. Trong quá trình nghiên cứu, một số kết quả nghiên cứu đã được công bố trên các bài báo quốc tế và trong nước [ 15, 16, 17, 18]. Luận văn tốt nghiệp Ngô Hoàng Giang 93 Tài liệu tham khảo [1]. Jinyang Li, Jeremy Stribling, Robert Morris, M. Frans Kaashoek and Thomer M. Gil. “A performance vs. cost framework for evaluating DHT design tradeoffs under churn” [2]. Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan. “Chord: A scalable Peer-To-Peer lookup service for internet applications”. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149–160, 2001. [3]. Ali Ghodsi. “Distributed k-ary System: Algorithms for Distributed Hash Tables”, PhD dissertation, KTH-Royal Institute of Technology, October 2006. [4]. Ali Ghodsi, Luc Onana Alima, Seif Haridi. Symmetric Replication for Structured Peer-to-Peer Systems, DBISP2P2005, The 3rd International Workshop on Databases, Information Systems and Peer-to-Peer Computing, August 28-29, 2005, Trondheim, Norway [4]. Ruud van Kessel. “Peer-to-peer storage: a survey on the common used techniques”, 2006 [5]. S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, “Handling churn in a DHT,” in roceedings of the 2004 USENIX Technical Conference, June 2004. [6] J. Li, J. Stribling, T. Gil, R. Morris, and M. F. Kaashoek, “Comparing the performance of distributed hash tables under churn,” in Proceedings of the 3rd International Workshop on Peer-to- Peer Systems, Feb. 2004. [7]. P. Maymounkov and D. Mazieres, “Kademlia: A peer-to-peer information system based on the XOR metric,” in Proceedings of the 1st IPTPS, Mar. 2002. [8]. I. Gupta, K. Birman, P. Linga, A. Demers, and R. van Renesse, “Kelips: Building an efficient and stable P2P DHT through increased memory and background overhead,” in Proceedings of the 2nd IPTPS, 2003. [9]. B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, “Tapestry: A resilient global-scale overlay for service deployment,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 41–53, Jan. 2004. [10]. K.P.Gummadi, R.Gummadi, S.Gribble, S.Ratnasamy , S.Shenker, and I. Stoica, “The impact of DHT routing geometry on resilience and proximity,” in Proceedings of the 2003 ACM SIGCOMM, Aug. 2003. [11]. F. Dabek, M. F. Kaashoek, J. Li, R. Morris, J. Robertson, and E. Sit, “Designing a DHT for low latency and high throughput,” in Proceedings of the 1st NSDI, March 2004. [12]. A. Gupta, B. Liskov, and R. Rodrigues, “Efficient routing for peer-to-peer overlays,” in Proceedings of the 1st NSDI, Mar. 2004. [13]. Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma and Steven Lim, “A Survey and Comparison of Peer-to-Peer Overlay Network Schemes” IEEE COMMUNICATIONS SURVEY AND TUTORIAL, MARCH 2004 [14]. P2PSIM home page, HU [15]. Giang Ngo Hoang, Hung Nguyen Chan, Thang Le Quang, “Performance study of distributed hash table mechanisms on p2p overlay network under extreme conditions”, International Symposium on Electrical-Electronics Engineering – ISEE 2007, Hochiminh, Vietnam. Luận văn tốt nghiệp Ngô Hoàng Giang 94 [16]. Nguyen Chan Hung, Ngo Hoang Giang, Le Quang Thang, “Comparative study on Distributed Hash Table algorithms of P2P network”, Proceeding NOC2007 12th European Conference on Networks & Optical Communications. [17]. “Performance Evaluation of Distributed Hash Table (DHT) Chord algorithm”, MCSE 2007, Proceeding of Modeling of Complex System and Environment MCSE 2007 by ISSAT (IEEE - International Society of Science and Applied Technologies Conference), Hochiminh, Vietnam [18]. Hung Nguyen Chan, Giang Ngo Hoang, Thang Le Quang, Tan Pek Yew, “Performance study of Chord, Kelips and Tapestry protocols on structured Peer-to-Peer Overlay networks”, in press, Special issues of Post & Telecommunications & Information Technology Journal, 2008