Download miễn phí 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
Mục lục
LỜI CAM ĐOAN .1
LỜI CẢM ƠN .2
Mục lục .3
Danh mục thuật ngữ .5
Danh mục hình vẽ .6
Danh mục thuật toán .8
Danh mục bảng .9
Lời mở đầu .10
Chương 1.Lý thuyết tổng quan .11
1.1.U ULý thuyết chung vềvềmạng P2P .11
1.1.1.U UKhái niệm mạng P2PU .11
1.1.2.U UQuá trình phát triển của các hệthống P2P .12
1.1.3.U UỨng dụng p2pU .16
1.1.4.U UCác vấn đề đối với mạng p2p hiện nay .16
1.2.U ULý thuyết vềDistributed Hash Table (DHT) .18
1.2.1.U UHash Table (bảng băm) .18
1.2.2.U UDistributed Hash Table .18
1.3.U UGiới thiệu một sốDHT .20
1.3.1.Chord .21
1.3.2.Kademlia .30
1.3.3.UTapestry .33
1.3.4.Kelips .38
1.4.Các phương pháp đánh giá, thửnghiệm mạng P2P .40
1.4.1.Khảo sát các simulator mô phỏng mạng overlay .41
1.4.2.P2PSim .42
Chương 2.Đánh giá hiệu năng một sốDHT .43
2.1.Bài toán thực tế .43
2.2.Đánh giá hiệu năng một sốDHT .44
2.2.1.Mục tiêu và cơsởlý luận .44
2.2.2.Quá trình thực nghiệm và phương pháp đánh giá hiệu năng .45
2.2.3.Xác định ngưỡng churn rate các DHT làm việc tốt .47
2.2.4.So sánh hiệu năng của các DHTU .53
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 .63
Chương 3.Cải tiến hiệu năng của Chord .68
3.1.Hạn chếcủa giao thức Chord .68
3.2.Giải pháp cải tiến giao thức Chord .68
3.3.Giải pháp duy trì vòng dùng cơchếlock .69
3.3.1.Mục tiêu .69
3.3.2.Cơchếlàm việc .69
3.4.Giải pháp caching proxy.79
3.4.1.Mục tiêu .79
3.4.2.Cơchếlàm việc .79
3.5.Giải pháp dùng nhân bản đối xứng cải tiến .87
3.5.1.Mục tiêu .87
3.5.2.Cơchếlàm việc .87
Kết luận .92
UTài liệu tham khảoU .
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-30-luan_van_danh_gia_hieu_nang_cua_mot_so_thuat_toan.XqOeLPMdBU.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42781/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
í 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...
