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 DHT và đưa ra giải pháp cải tiến hiệu năng của thuật toán Chord

í của các node được xác định bằng prefix của ID. Các ID trong Kademlia được biểu diễn theo cơ sở nhị phân. Mỗi node chia cây nhị phân thành các cây nhị phân con liên tiếp mà không chứa ID của node và lưu ít nhất một contact trong mỗi cây con này. Ví dụ, một node với ID là 3 có biểu diễn nhị phân 0011 trong không gian ID N=16. Do prefix với độ dài 1 là 0 nên nó cần biết một node với chữ số đầu tiên là 1. Tương tự như vậy, do prefix với độ dài 2 là 00 nên node cần biết một node với prefix là 01. Prefix với độ dài 3 là 001, node cần biết một node khác với prefix 000. Cuối cùng, do prefix với độ dài bằng 4 là 0011 nên nó cần biết node có prefix là 0010. Quy tắc này được minh họa trong XHình 1.7X dưới đây: Luận văn tốt nghiệp Ngô Hoàng Giang 31 Hình 1.7.Con trỏ của node 3 (0011) trong Kademlia Kademlia không lưu một danh sách các node gần với nó trong không gian ID như successor list của Chord. Tuy nhiên với mỗi cây con trong không gian ID, node lưu tới k contact thay vì một contact nếu có thể và gọi một nhóm không nhiều hơn k contact trong một cây con là subtree. Mapping items onto nodes Kademlia định nghĩa khái niệm khoảng cách giữa hai ID là kết quả XOR của hai ID. Một item được lưu trên node mà khoảng cách giữa hai ID là nhỏ nhất. Lookup process Để tăng cường khả năng tìm kiếm và giảm thời gian phản hồi, Kademlia thực hiện các lookup đồng thời và theo phương pháp lặp. Khi một node tìm kiếm một ID, nó sẽ kiểm tra cây con nào chứa ID và chuyển yêu cầu lookup đến α node ngẫu nhiên từ được lựa chọn từ k-bucket của cây con đó. Mỗi node lại trả về một k-bucket của cây con nhỏ hơn gần hơn với ID. Từ bucket được Luận văn tốt nghiệp Ngô Hoàng Giang 32 trả về, node lại chọn α node ngẫu nhiên và lặp lại quá trình tương tự cho đến khi ID được tìm thấy. Khi một node muốn chèn một item mới nào đó, nó sẽ lưu item tại k node gần nhất với ID. Do sử dụng so khớp prefix nên một lookup sẽ được thực hiện trong O(log(N)) chặng. Joins, leave and maintenance Một node tìm thấy node gần nó nhất thông qua bất kỳ contact ban đầu nào và khởi tạo bảng định tuyến của nó bằng cách yêu cầu node đó tìm kiếm các node trong các cây con khác nhau. Nếu một k-bucket được bổ xung quá nhiều node từ một cây con nào đó, quy tắc thay thế least-recently-used sẽ được áp dụng. Tuy nhiên Kademlia sử dụng một thống kê từ các nghiên cứu về peer-to-peer cho rằng một node nếu đã kết nối trong một khoảng thời gian dài nhiều khả năng sẽ tiếp tục ở lại mạng trong một thời gian dài nữa. Do đó, Kademlia có thể bỏ qua thông tin về các node mới nếu nó đã biết nhiều node ổn định trong cây con đó. Việc maintenance bảng định tuyến sau khi node join/leave được thực hiện nhờ sử dụng lưu lượng lookup, kỹ thuật này khác với kỹ thuật stabilization của Chord. XOR metric dẫn đến mọi node nhận được truy vấn từ node chứa trong bảng định tuyến của nó. Do đó, nhận được một thông điệp từ một node nào đó trong cây con chính là một cập nhật k-bucket của cây con đó. Cách tiếp cận này rõ ràng là tối thiểu hóa chi phí bảo trì. Một nhiệm vụ bảo trì khác là dựa vào việc nhận được nhiều truy vấn từ một cây con, Kademlia cập nhật latency của các node trong một k-bucket cụ thể. Việc này cải thiện sự lựa chọn node cho quá trình tìm kiếm và có thể nói rằng Kademlia cũng chú ý đến độ trễ và tính vị trí của các node. Luận văn tốt nghiệp Ngô Hoàng Giang 33 Replication and Fault Tolerance Khả năng chịu lỗi của Kademlia phụ thuộc chủ yếu vào liên kết bền vững trong k-bucket bởi vì Kademlia lưu k contact cho mỗi cây con, điều này giúp cho khả năng graph bị đứt liên kết thấp. Kademlia lưu k phiên bản của một item trên k node gần id của item nhất, các node này được republish định kỳ. Chính sách cho việc republish này là bất kỳ node nào thấy nó gần với item ID hơn các node khác mà nó biết sẽ báo cho k-1 node còn lại biết. Applications and Implementation Kademlia được chấp nhận rộng rãi thông qua hai ứng dụng chia sẻ file là Overnet và Emule. 1.3.3. Tapestry Overlay graph Tapestry cũng tổ chức các ID trong không gian vòng tròn N. Các ID được biểu diễn theo base β. Luận văn tốt nghiệp Ngô Hoàng Giang 34 Hình 1.8. Minh họa cách chọn bảng định tuyến của một node Tapestry Hàng thứ nhất trong bảng định tuyến của một node chứa các node có ID khác với ID của node đó ở chữ số thứ nhất. Tương tự như vậy, hàng thứ hai trong bảng định Luận văn tốt nghiệp Ngô Hoàng Giang 35 tuyến chứa các node có ID giống với ID của node đó ở chữ số thứ nhất nhưng khác ở chữ số thứ hai. Các hàng còn lại của bảng định tuyến được tổ chức tương tự như vậy. XHình 1.8X minh họa cách chia không gian ID của Tapestry . Để tăng tính dự phòng, ở mỗi mức, mỗi contact lại được dự phòng bởi c contact cùng nhóm. Một node Tapestry có bảng định tuyến với logβN mức, mỗi mức có c × β contact. Như vậy bảng định tuyến của Tapestry có kích thước c × β × logβN. Mapping items onto nodes Tapestry ánh xạ ID của item tới một node duy nhất gọi là root của ID. Nếu tồn tại node N có ID bằng với ID của item thì node được gọi là root của item đó. Nếu không tồn tại node có ID bằng với ID của item thì item được ánh xạ vào node có ID gần ID của nó nhất. Tapestry không chuyển item đến node nào đó trên mạng mà chỉ thiết lập con trỏ trên các node nằm trên đường đi từ node chứa item tới node root của item trỏ tới item. Lookup process Quá trình định tuyến của Tapestry diễn ra như sau. Để tìm một node gần với một ID x nhất, node sẽ dùng bảng định tuyến kiểm tra từ trên xuống dưới xem x rơi vào khoảng ID nào. Nếu x rơi vào khoảng ID khác với khoảng ID của node, node sẽ chuyển tiếp truy vấn tới contact của nó nằm trong khoảng ID đó. Quá trình cứ diễn ra như vậy cho đến khi đến node root của x. Nếu trong bảng định tuyến của node không tồn tại contact như vậy, node sẽ chuyển tiếp truy vấn tới node có ID gần với x nhất. Luận văn tốt nghiệp Ngô Hoàng Giang 36 Quá trình định tuyến được minh họa trong XHình 1.9 Hình 1.9. Đường đi của thông điệp từ node 5230 tới node 42AD Để thông báo về sự tồn tại của một item I, node n lưu item định kỳ gửi thông điệp đến root của item đó. Mỗi node dọc đường đi của thông điệp sẽ lưu một con trỏ ánh xạ (I,n) thay vì lưu lại bản thân item. Khi có vài bản sao của một item trên một số node, mỗi node sẽ thông báo về bản sao nó lưu. Một node nhận được nhiều thông báo về một item, nó sẽ lưu ánh xạ theo thứ tự latency. Quá trình publishing được minh họa trong XHình 1.10 Luận văn tốt nghiệp Ngô Hoàng Giang 37 Hình 1.10. Ví dụ về Tapestry node publish item Một node muốn truy vấn một item nào đó, nó sẽ gửi truy vấn đến root của item. Mỗi node trên đường đi sẽ kiểm tra xem nó có ánh xạ vị trí của item đó không, nếu có nó sẽ chuyển truy vấn theo hướng đến node lưu item, nếu không có nó sẽ chuyển tiếp truy vấn theo hướng đến root của item. Quá trình truy vấn item được minh họa trong XHình 1.11X dưới đây Hình 1.11. Ví dụ về Tapestry node tìm kiếm item Luận văn tốt nghiệp Ngô Hoàng Giang 38 Join/leave and maintenance Chèn một node N vào mạng bắt đầu bằng việc tìm kiếm node gốc S (có chung prefix độ dài p) của N. Node S sau đó gửi thông điệp tới các node cùng chung prefix, các node này sau khi nhận được thông điệp sẽ chèn N vào trong bảng định tuyến của chúng và chuyển các ánh xạ tham chiếu vị trí nếu cần thiết. Quá trình khởi tạo bảng định tuyến của N diễn ra như sau. N tìm kiếm các neighbour gần nhất bắt đầu với mức định tuyến p, điền các neighbour này vào bảng định tuyến ở mức p dùng k node gần nhất. Sau đó N giảm p và tiếp tục quá trình như vậy cho đến khi các mức trong bảng định tuyến được điền đầy. 1.3.4. Kelips Overlay graph Kelisp băm không gian ID vào k nhóm sử dụng consistent hashing, đánh số từ 0 đến k-1. Do sử dụng thuật toán consistent hashing nên Kelips đảm bảo rằng số node trong mỗi nhóm là n/k với xác xuất cao. Bảng định tuyến của một Kelips node bao gồm ba phần: − Affinity group view: thông tin về một tập các node nằm trong cùng nhóm. − Contact: đối với mỗi nhóm, Kelips lưu thông tin về một tập nhỏ các node trong nhóm đó. − Filetuples: một tập các bộ, mỗi bộ lưu thông tin về một file và node chứa file đó. Một node chỉ lưu thông tin về các file chứa trong các node nằm cùng nhóm với node đó. XHình 1.12X minh họa bảng định tuyến của một node trong hệ thống có 10 nhóm: Luận văn tốt nghiệp Ngô Hoàng Giang 39 Hình 1.12. Mạng Kelips trong đó các node phân tán trong 10 nhóm affinity và trạng thái tại một node cụ thể Mapping items onto nodes Một item được băm vào một trong các nhóm của hệ thống sử dụng cùng thuật toán consistent hashing được dùng để băm các node và được lưu trên một node bất kỳ trong nhóm này. Lookup process Khi một node muốn truy vấn một item, nó sẽ dùng consistent hashing xem item được ánh xạ vào nhóm nào và gửi truy vấn đến contact gần nhất trong nhóm đó. Nếu trong các bộ của node contact có item cần tìm, node sẽ trả kết quả về cho node truy vấn, nếu node contact không có thông tin về item cần tìm, node truy vấn có thể gửi yêu cầu Luận văn tốt nghiệp Ngô Hoàng Giang 40 truy vấn đến nhiều contact, hoặc node contact sẽ gửi yêu cầu truy vấn tới các node khác cùng nhóm với nó, hoặc node truy vấn có thể yêu cầu một node khác cùng nhóm với nó thực hiện truy vấn item. Một node muốn chèn một item mới sẽ sử dụng consistent hashing xem item đó được ánh xạ vào nhóm nào. Sau đó node sẽ gửi yêu cầu chèn dữ liệu tới một contact thuộc nhóm đó, node contact sẽ chọn ngẫu nhiên một node bất kỳ trong nhóm và gửi yêu cầu chèn dữ liệu. Node này sẽ trở thành node lưu item. Nếu yêu cầu chèn dữ liệu không thực hiện được, quá trình gửi lại yêu cầu chèn dữ liệu diễn ra như quá trình gửi lại yêu cầu truy vấn. 1.4. Các phương pháp đánh giá, thử nghiệm mạng P2P Cộng đồng nghiên cứu peer to peer nói chung sử dụng ba phương pháp để đánh giá, kiểm nghiệm các kết quả nghiên cứu là phương pháp phân tích, phương pháp thực nghiệm và phương pháp mô phỏng. Trong phương pháp phân tích, người ta đánh giá mô hình toán học của hệ thống. Tuy nhiên phương pháp này chỉ hiệu quả đối với các mô hình đơn giản trong khi các mô hình p2p thực tế thường phức tạp. Trong phương pháp thực nghiệm, người ta tiến hành thử nghiệm trên hệ thống thật, tuy nhiên các hệ thống p2p có số lượng node rất lớn, nếu thực nghiệm trên hệ thống có quy mô nhỏ thì kết quả sẽ không có ý nghĩa. Đồng thời các thay đổi như thay đổi topology mạng hay thay đổi trong protocol trên các node sẽ khó và tốn nhiều thời gian. Phương pháp mô phỏng cũng có những hạn chế, tuy nhiên nó khắc phục được những hạn chế của phương pháp phân tích và phương pháp thực nghiệm. Tại thời điểm này, phương pháp mô phỏng không hoàn toàn độc lập với hai phương pháp trên. Nếu có thể, nên sử dụng phương pháp phân tích và chứng minh bằng phương pháp mô phỏng. Tương tự, các kết quả mô phỏng nên được chứng minh bằng thực nghiệm trên Luận văn tốt nghiệp Ngô Hoàng Giang 41 các hệ thống thật. Hiện nay, hầu hết các nghiên cứu về p2p được thực hiện sử dụng phương pháp mô phỏng. 1.4.1. Khảo sát các simulator mô phỏng mạng overlay Cộng đồng nghiên cứu sử dụng khá nhiều simulator khác nhau, có simulator đang được phát triển, có simulator không được phát triển tiếp. Simulator Ngôn ngữ Trạng thái License P2PSim C++ Active GPL PeerSim Java Active LGPL Query-Cycle Simulator Java Inactive Apache Narses Java Inactive GPL-like Neurogrid Java Inactive GPL GPS Java Inactive Open-Source, No License Overlay Weaver Java Active Apache DHTSim Java Active GPL PlanetSim Java Active LGPL Bảng 1.1. Trạng thái phát triển của các simulator Đặc điểm của các simulator như sau: Simulator Kiến trúc Tính dễ dùng Tính khả mở (max nodes) P2PSim Discrete-event cho mạng P2P có cấu trúc Rất ít tài liệu 3000 nodes PeerSim Query-Cycle hoặc Discrete-event cho mạng không cấu trúc. Có thể mô phỏng node joining, departing và failing. Chỉ có mô phỏng Query-Cycle là có tài liệu 106 node Narses Discrete-event, flow-based topology có thể điều chỉnh 600 node, tùy thuộc vào topology bên dưới 600 node Overlay Weaver Giả lập phân tán và Tài liệu về API và 4000 node Luận văn tốt nghiệp Ngô Hoàng Giang 42 một số giải thuật cho structured overlay mã nguồn tốt PlanetSim Mô phỏng discrete- event, sử dụng API chung. Có tài liệu về thiết kế và API 100 000 node Neurogrid Discrete-event cho mạng không có cấu trúc, có thể chỉnh sửa để sử dụng cho mạng có cấu trúc Có tài liệu mở rộng trên web 300 000 node Simulator Thống kê Underlying network P2PSim Cung cấp một lượng hữu hạn thống kê. end-to-end time graph, G2 graph, GT-ITM, random, và Euclidean PeerSim Có thể cài đặt các component để thống kê dữ liệu Không được mô hình hóa Narses Có hỗ trợ nhưng phải cài đặt Một số topology Overlay Weaver Không thể thu thập thống kê Không được mô hình hóa PlanetSim Không có cơ chế thu thập thống kê nhưng có thể xem trực quan Một số ít topology Neurogrid Cần sửa mã nguồn Không được mô hình hóa Bảng 1.2. Đặc điểm của các simulator 1.4.2. P2PSim P2PSim là phần mềm mã nguồn mở, đa tiến trình, discrete event để mô phỏng mạng overlay có cấu trúc do một nhóm nghiên cứu mạng p2p tại MIT phát triển. P2PSim được nhiều nhóm nghiên cứu sử dụng để nghiên cứu DHT. P2PSim hỗ trợ đến mô phỏng mạng với số node tối đa là 3000, với nhiều topology khác nhau như end-to-end time graph, G2 graph, GT-ITM, random, và Euclidean. Tuy nhiên tài liệu về P2PSim rất hạn chế. Luận văn này sử dụng P2PSim để mô phỏng và đánh giá, so sánh hiệu năng giữa các DHT. Địa chỉ web site của P2PSim : HU Luận văn tốt nghiệp Ngô Hoàng Giang 43 Chương 2. 1BĐánh giá hiệu năng một số DHT 2.1. Bài toán thực tế Hầu hết các DHT được thiết kế để hoạt động với các peer là máy tính. Đây là môi trường có độ ổn định khá cao, tức là khoảng thời gian từ lúc một node gia nhập cho đến khi rời khỏi mạng tương đối dài. Trong môi trường này, các DHT hoạt động với hiệu năng tương đối cao. Hiệu năng của một DHT được đánh giá thông qua hai tham số chính là tỷ lệ tìm kiếm dữ liệu thành công khi dữ liệu có trên mạng và độ trễ tìm kiếm. Vài năm trở lại đây các sản phẩm cho người sử dụng có thể nối mạng phát triển hết sức mạnh mẽ và đa dạng, các sản phầm không chỉ có máy tính mà còn có các thiết bị như điện thoại, PDA, tivi, …. Cũng giống như người sử dụng máy tính, người sử dụng các thiết bị này cũng có nhu cầu chia sẻ, khai thác nguồn tài nguyên hết sức phong phú trên mạng p2p, đặc biệt là các tài nguyên như video, audio. Tuy nhiên thời gian kết nối mạng của các thiết bị này thường rất ngắn, thậm chí có thể tính bằng giây, dẫn đến sự bất ổn định của mạng. Các DHT vốn được thiết kế để hoạt động với các peer là máy tính lúc này không đáp ứng được yêu cầu về hiệu năng do khoảng thời gian các peer ở trên mạng quá ngắn. Một mạng như vậy người ta gọi là mạng có churn rate cao. Một bài toán mới đặt ra cho cộng đồng nghiên cứu p2p là xây dựng các mạng p2p thích nghi được với môi trường churn rate cao. Một trong những giải pháp được nhiều người quan tâm là cải tiến các DHT hiện có để chúng hoạt động hiệu quả ngay cả trong môi trường có churn rate cao. Việc đưa ra được giải pháp cải tiến hiệu năng cần căn cứ vào một số cơ sở, một trong những cơ sở quan trọng là việc đánh giá hiệu năng của các DHT trong môi trường mới. Luận văn tốt nghiệp Ngô Hoàng Giang 44 Luận văn này đánh giá, so sánh hiệu năng của một số well-known DHT, đặc biệt là trong môi trường churn rate cao. Từ kết quả này kết hợp với phân tích lý thuyết, luận văn đưa ra giải pháp cải tiến hiệu năng cho một DHT tiềm năng (Chord) trong điều kiện churn rate cao. 2.2. Đánh giá hiệu năng một số DHT 2.2.1. Mục tiêu và cơ sở lý luận Phần này của luận văn phân tích, đánh giá hiệu năng của các DHT nhằm tạo cơ sở cho việc đưa ra các giải pháp cải tiến hiệu năng của chúng đồng thời giúp các ứng dụng lựa chọn, sử dụng các DHT hiệu quả hơn. Đánh giá hiệu năng của các DHT bao gồm nhiều khía cạnh: − Xác định ngưỡng churn rate mà các DHT hoạt động tốt − Phân tích ảnh hưởng của tham số thiết kế đến hiệu năng của DHT − So sánh hiệu năng của các DHT khác nhau − Đánh giá tính khả mở của các DHT. Các đánh giá được thực hiện trong dải churn rate rộng từ cao đến thấp, đặc biệt chú trọng đến trường hợp churn rate cao. Khi churn rate càng cao, độ ổn định của mạng càng thấp thì hiệu năng của các DHT càng giảm. Do đó một trong những nhiệm vụ đầu tiên của phần đánh giá hiệu năng là xác định ngưỡng churn rate mà các DHT hoạt động với hiệu năng cao. Đánh giá ảnh hưởng của các tham số thiết kế đến hiệu năng một DHT cho phép xác định các tham số quan trọng đối với hiệu năng của DHT và xác định khoảng giá trị của các tham số trong đó DHT làm việc tốt. So sánh hiệu năng của các DHT khác nhau trong các điều kiện khác nhau cho thấy trong từng điều kiện cụ thê, DHT nào làm việc tốt hơn và tốt hơn ở những khía cạnh nào. Luận văn tốt nghiệp Ngô Hoàng Giang 45 Đánh giá ảnh hưởng của các tham số thiết kế và so sánh hiệu năng của các DHT khác nhau không những có ích trong việc nghiên cứu và cải tiến DHT mà còn cho phép các ứng dụng lựa chọn DHT phù hợp với điều kiện môi trường, điều chỉnh các tham số cần thiết để đạt được hiệu quả tối ưu. Tính khả mở là một đặc tính quan trọng của DHT, một DHT hiệu quả phải có tính khả mở cao. Kết quả đánh giá tính khả mở của các DHT có thể làm cơ sở để lựa chọn, sử dụng DHT. 2.2.2. Quá trình thực nghiệm và phương pháp đánh giá hiệu năng Các DHT được mô phỏng với nhiều bộ tham số khác nhau sử dụng phần mềm mô phỏng P2PSim. Quá trình mô phỏng được thực hiện trong nhiều tháng với số lượng mô phỏng lên đến hơn 20 000 để đảm bảo kết quả mô phỏng ổn định. Ứng với mỗi bộ tham số, kết quả mô phỏng DHT thống kê các thông số hiệu năng của DHT như tỷ lệ tìm kiếm thành công (hoặc tỷ lệ tìm kiếm thất bại), độ trễ tìm kiếm, băng thông trung bình mỗi node sử dụng,…. Các mô phỏng này được biểu diễn trên độ thị hai chiều với trục đứng biểu diễn tỷ lệ tìm kiếm thành công/thất bại, hoặc độ trễ tìm kiếm và trục ngang là băng thông trung bình mỗi node sử dụng. Nói cách khác, trục đứng biểu diễn các thông số hiệu năng và trục ngang biểu diễn chi phí phải bỏ ra để đạt được hiệu năng đó. Rõ ràng, một DHT tốt nếu có tỷ lệ tìm kiếm thành công cao, độ trễ tìm kiếm thấp và băng thông mỗi node sử dụng trung bình thấp. Kết quả mô phỏng DHT với một bộ tham số đầu vào tương ứng với một điểm trên đồ thị. Khi mô phỏng DHT với nhiều bộ tham số khác nhau, ta có nhiều điểm trên đồ thị. Hình 2.1X là một đồ thị biểu diễn kết quả mô phỏng giao thức Chord với trục đứng là tỷ lệ tìm kiếm thất bại và trục ngang là băng thông trung bình mỗi node sử dụng. Luận văn tốt nghiệp Ngô Hoàng Giang 46 Việc đánh giá hiệu năng của một DHT, so sánh hiệu năng giữa các DHT dựa trên đường convex hull. Đường convex hull là đường bao nhỏ nhất của một hợp điểm. Ở đây chúng ta chỉ quan tâm đến đoạn gần với hai trục từ điểm có hoành độ cao nhất đến điểm có tung độ cao nhất. Khi trục đứng là tỷ lệ tìm kiếm thất bại hoặc là độ trễ tìm kiếm thì đường này chính là sự kết hợp tối ưu giữa hiệu năng và chi phí. Có hai loại đường convex hull, đường overall convex hull và đường parameter convex hull. Đường overall convex hull là đường convex hull của tất cả các điểm ứng với tất cả các bộ tham số. P2PSim còn cho phép chỉ biểu diễn các điểm ứng với một giá trị nào đó của một tham số trên đồ thị. Khi đó, đường convex hull của tập điểm này gọi là đường parameter convex hull ứng với tham số đó. Đường overall convex hull được sử dụng để đánh giá hiệu năng tổng quát trong khi đường parameter convex hull được dùng để phân tích ảnh hưởng của các tham số đến hiệu năng của DHT. Hình 2.1. Node join/leave với interval=600 s trong mạng Chord 100 node Luận văn tốt nghiệp Ngô Hoàng Giang 47 2.2.3. Xác định ngưỡng churn rate các DHT làm việc tốt 2.2.3.1. 4BMục tiêu Xác định ngưỡng churn rate mà từng DHT còn làm việc với 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