Đánh giá hiệu năng của một số 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

- NGUYỄN CHẤN HÙNG HÀ NỘI 2008 Luận văn tốt nghiệp Ngô Hoàng Giang 1 BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- Hà Nội, ngày 28 tháng 10 năm 2008 (Ký và ghi rõ họ tên) Ngô Hoàng Giang Luận văn tốt nghiệp Ngô Hoàng Giang 2 LỜI CẢM ƠN Trước hết tôi vô cùng biết ơn sâu sắc đến Thầy giáo TS.
- Luận văn tốt nghiệp Ngô Hoàng Giang 6 Danh mục hình vẽ UHình 1.1.
- Đồ 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).U UHì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).U UHì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).U Luận văn tốt nghiệp Ngô Hoàng Giang 7 UHì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).U UHì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).U UHì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 trong mạng Chord 1000 node với interval=120s (trái) và interval=600s (phải).U UHình 2.10.
- Đồ 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=600sU UHình 2.12.
- Biểu đồ thời gian biểu diễn quá trình caching thành côngU Luận văn tốt nghiệp Ngô Hoàng Giang 8 Danh mục thuật toán UThuật toán 1.1.
- Quá trình tìm kiếm và chèn trong giải pháp nhân bản đối xứngU UThuật toán 3.8.
- Thuật toán bulk owner operationU Luận văn tốt nghiệp Ngô Hoàng Giang 9 Danh mục bảng UBảng 1.1.
- 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 nodeU UBảng 2.6.
- Giá trị tham số của TapestryU Luận văn tốt nghiệp Ngô Hoàng Giang 10 Lời mở đầu Khoảng mười năm trở lại đây, thế giới đã chứng kiến sự bùng nổ của Internet băng thông rộng, cùng với nó là sự phát triển mạnh mẽ của các ứng dụng peer-to-peer.
- Luận văn bao gồm ba phần.
- Phần thứ hai, luận văn phân tích, đánh giá hiệu năng của một số DHT nổi tiếng như Chord, Kademlia, Tapestry, Kelips trong điều kiện mạng churn rate cao.
- Dựa trên kết quả đạt được, luận văn phân tích hạn chế của giao thức Chord và đưa ra giải pháp cải tiến hiệu năng của giao thức này trong điều kiện churn rate cao.
- Luận văn tốt nghiệp Ngô Hoàng Giang 11 Chương 1.
- Tài nguyên và dịch vụ ở đây bao gồm Luận văn tốt nghiệp Ngô Hoàng Giang 12 thông tin, chu kỳ xử lý, không gian lưu trữ.
- Luận văn tốt nghiệp Ngô Hoàng Giang 13 Hình 1.1.
- Luận văn tốt nghiệp Ngô Hoàng Giang 16 1.1.3.
- Tuy nhiên các hệ thống p2p đang phải đối mặt với một số vấn đề: Luận văn tốt nghiệp Ngô Hoàng Giang 17 Bảo mật (security): các cài đặt phân tán phát sinh thêm một số vấn đề bảo mật so với kiến trúc client-server truyền thống.
- Luận văn tốt nghiệp Ngô Hoàng Giang 18 1.2.
- Để lưu một value trên mạng, một node gửi thông điệp yêu cầu lưu dữ liệu tới một contact phù hợp được chọn ra từ bảng routing table, trong bảng routing table, Luận văn tốt nghiệp Ngô Hoàng Giang 19 contact này có ID gần với ID của dữ liệu cần lưu nhất.
- Luận văn tốt nghiệp Ngô Hoàng Giang 20 Hình 1.3.
- Do các node trong mạng thường xuyên join, leave nên cần có một số tiến trình Luận văn tốt nghiệp Ngô Hoàng Giang 21 maintenance để xử lý các thay đổi trong mạng, chúng ta quan tâm đến các tiến trình này diễn ra như thế nào và chi phí thực hiện các tiến trình này.
- Cách xây Luận văn tốt nghiệp Ngô Hoàng Giang 22 dựng bảng finger table được thể hiện trong XHình 1.4X(b.
- Luận văn tốt nghiệp Ngô Hoàng Giang 23 Hình 1.4.
- (c) Bảng routing table của node 3 và node 11 Luận văn tốt nghiệp Ngô Hoàng Giang 24 Mapping Items Onto Nodes.
- Nhiệm vụ cuối cùng là chuyển Luận văn tốt nghiệp Ngô Hoàng Giang 25 một phần các item đang lưu trên node s có ID nhỏ hơn hoặc bằng n sao node n.
- Luận văn tốt nghiệp Ngô Hoàng Giang 26 predecessor = n.
- Luận văn tốt nghiệp Ngô Hoàng Giang 27.
- Node 26 trỏ con trỏ predecessor vào node 21 Luận văn tốt nghiệp Ngô Hoàng Giang 28 Hình 1.5.
- Luận văn tốt nghiệp Ngô Hoàng Giang 29 Sau đó node 6 join vào mạng rồi node 3 rời khỏi mạng, bảng định tuyến của các node và sự thây đổi bảng định tuyến được thể hiện trong hình vẽ với những phần thay đổi có màu đen, những phần không đổi có màu xám.
- Luận văn tốt nghiệp Ngô Hoàng Giang 30 Upper Services and Applications Một số ứng dụng như cooperative file-system [14], một ứng dụng đọc/ghi hệ thống file và một DNS đã được xây dựng dựa trên Chord.
- 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.
- 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.
- Luận văn tốt nghiệp Ngô Hoàng Giang 34 Hình 1.8.
- 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.
- 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.
- 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 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.
- 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.
- 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.
- 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 : HUhttp://pdos.csail.mit.edu/p2psim/U Luận văn tốt nghiệp Ngô Hoàng Giang 43 Chương 2.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 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.
- Đồ 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).
- 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.
- Đồ 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).
- 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.5X 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.
- Đồ 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).
- 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).
- 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 Bảng 2.5.
- 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 Bảng 2.6.
- 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 Group_ration Contact_ration N_contacts Item_rounds 2, 5 2, 8 Bảng 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 với interval=5s (trái) và interval=10s (phải).
- 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.
- node numbers Node numbersFraction of failed lookup Chord60Kelips60Tapestry60Chord120Kelips120Tapestry120Chord600Kelips600Tapestry600 Luận văn tốt nghiệp Ngô Hoàng Giang 62 Med.
- 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.
- 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 Stabilization interval (sec Number of backup nodes 2,3,4 Number of nodes contacted during repair 1,3,5,10 Bảng 2.17.
- Ả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.
- 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.
- Luận văn tốt nghiệp Ngô Hoàng Giang 68 Chương 3.
- Mục tiêu của luận văn là cải tiến hiệu năng của các DHT.
- 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.
- 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.
- 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.
- nil Luận văn tốt nghiệp Ngô Hoàng Giang 72 status.
- 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.
- 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.
- m Luận văn tốt nghiệp Ngô Hoàng Giang 76 end event event n.UpdateSuccAck() from m sendto succ.LeaveDone.
- 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.
- nil Luận văn tốt nghiệp Ngô Hoàng Giang 78 end if end procedure procedure n.Stabilize.
- 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.
- Luận văn tốt nghiệp Ngô Hoàng Giang 80 Hình 3.4.
- 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.
- 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 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.
- Xử lý thay đổi trong vòng proxy Luận văn tốt nghiệp Ngô Hoàng Giang 87 3.5.
- 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.
- 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.
- 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.
- App is responsible for ids in MS Luận văn tốt nghiệp Ngô Hoàng Giang 91 end if limit.
- 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.
- 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.
- Luận văn tốt nghiệp Ngô Hoàng Giang 93 Tài liệu tham khảo [1].
- Luận văn tốt nghiệp Ngô Hoàng Giang 94 [16]

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt