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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- LUẬN VĂN THẠC SĨ KHOA HỌC N G Ô H O À N G G IA N G NGÀNH: CÔNG NGHỆ THÔNG TIN C Ô N G N G H Ệ TH Ô N G TIN ĐÁ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 NGÔ HOÀNG GIANG 2006 - 2008 Hà Nội 2008 HÀ NỘI 2008 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- LUẬN VĂN THẠC SĨ KHOA HỌC NGÀNH: CÔNG NGHỆ THÔNG TIN 3898 ĐÁ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 NGÔ HOÀNG GIANG Người hướng dẫn khoa học: TS. 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 *** Cộng hoà xã hội chủ nghĩa Việt Nam Độc lập – Tự do – Hạnh phúc LỜI CAM ĐOAN Luận văn thạc sỹ này do tôi nghiên cứu và thực hiện dưới sự hướng dẫn của Thầy giáo TS. Nguyễn Chấn Hùng. Để hoàn thành bản luận văn này, ngoài các tài liệu tham khảo đã liệt kê, tôi cam đoan không sao chép các công trình hoặc thiết kế tốt nghiệp của người khác. 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. Nguyễn Chấn Hùng – người đã trực tiếp dành nhiều thời gian tận tình hướng dẫn, cung cấp những thông tin quý báu giúp đỡ tôi hoàn thành bản luận văn này. Tôi xin chân thành cảm ơn Ban lãnh đạo Trung tâm mạng thông tin – Trường Đại học Bách khoa Hà Nội, nơi tôi đang công tác đã tạo nhiều điều kiện động viên khích lệ để tôi có thể hoàn thành bản luận văn này. Sau cùng tôi xin bày tỏ lòng biết ơn đến người thân cùng bạn bè đồng nghiệp, những người luôn cổ vũ động viên tôi hoàn thiện bản luận văn này. Hà Nội, ngày 28 tháng 10 năm 2008 Ngô Hoàng Giang Luận văn tốt nghiệp Ngô Hoàng Giang 3 Mục lục ULỜI CAM ĐOANU ............................................................................................................1 ULỜI CẢM ƠNU ..................................................................................................................2 UMục lụcU.............................................................................................................................3 UDanh mục thuật ngữU .........................................................................................................5 UDanh mục hình vẽU ............................................................................................................6 UDanh mục thuật toán U ........................................................................................................8 UDanh mục bảngU ................................................................................................................9 ULời mở đầuU .....................................................................................................................10 UChương 1.U ULý thuyết tổng quanU .................................................................................11 U1.1.U ULý thuyết chung về về mạng P2PU ....................................................................11 U1.1.1.U UKhái niệm mạng P2PU ...............................................................................11 U1.1.2.U UQuá trình phát triển của các hệ thống P2PU ...............................................12 U1.1.3.U UỨng dụng p2p U ..........................................................................................16 U1.1.4.U UCác vấn đề đối với mạng p2p hiện nayU ....................................................16 U1.2.U ULý thuyết về Distributed Hash Table (DHT)U ..................................................18 U1.2.1.U UHash Table (bảng băm)U ............................................................................18 U1.2.2.U UDistributed Hash TableU ............................................................................18 U1.3.U UGiới thiệu một số DHTU....................................................................................20 U1.3.1.U UChordU........................................................................................................21 U1.3.2.U UKademliaU ..................................................................................................30 U1.3.3.U UTapestryU....................................................................................................33 U1.3.4.U UKelipsU .......................................................................................................38 U1.4.U UCác phương pháp đánh giá, thử nghiệm mạng P2PU ........................................40 U1.4.1.U UKhảo sát các simulator mô phỏng mạng overlayU .....................................41 U1.4.2.U UP2PSimU.....................................................................................................42 Luận văn tốt nghiệp Ngô Hoàng Giang 4 UChương 2.U UĐánh giá hiệu năng một số DHTU .............................................................43 U2.1.U UBài toán thực tếU................................................................................................43 U2.2.U UĐánh giá hiệu năng một số DHTU.....................................................................44 U2.2.1.U UMục tiêu và cơ sở lý luậnU .........................................................................44 U2.2.2.U UQuá trình thực nghiệm và phương pháp đánh giá hiệu năngU ...................45 U2.2.3.U UXác định ngưỡng churn rate các DHT làm việc tốtU .................................47 U2.2.4.U USo sánh hiệu năng của các DHTU ..............................................................53 U2.2.5.U UĐánh giá ảnh hưởng của các tham số thiết kế đến hiệu năng các DHTU ..63 UChương 3.U UCải tiến hiệu năng của ChordU...................................................................68 U3.1.U UHạn chế của giao thức ChordU ..........................................................................68 U3.2.U UGiải pháp cải tiến giao thức ChordU..................................................................68 U3.3.U UGiải pháp duy trì vòng dùng cơ chế lockU ........................................................69 U3.3.1.U UMục tiêuU ...................................................................................................69 U3.3.2.U UCơ chế làm việcU........................................................................................69 U3.4.U UGiải pháp caching proxyU..................................................................................79 U3.4.1.U UMục tiêuU ...................................................................................................79 U3.4.2.U UCơ chế làm việcU........................................................................................79 U3.5.U UGiải pháp dùng nhân bản đối xứng cải tiến U.....................................................87 U3.5.1.U UMục tiêuU ...................................................................................................87 U3.5.2.U UCơ chế làm việcU........................................................................................87 UKết luậnU ..........................................................................................................................92 UTài liệu tham khảoU..........................................................................................................93 Luận văn tốt nghiệp Ngô Hoàng Giang 5 Danh mục thuật ngữ Tiếng Anh Tiếng Việt Peer-to-peer Mạng ngang hàng Peer Đồng đẳng trong mạng ngang hàng Node Một thiết bị nối mạng (một peer) Item Một đơn vị dữ liệu Structured Có cấu trúc Overlay Mạng được xây dựng trên các mạng khác Hash table Bảng băm Distributed hash table Bảng băm phân tán Join Gia nhập (mạng ngang hàng) Leave Rời khỏi (mạng ngang hàng) Failure Lỗi Churn rate Số lượng peer rời khỏi/gia nhập mạng trong một khoảng thời gian. Luận văn tốt nghiệp Ngô Hoàng Giang 6 Danh mục hình vẽ UHình 1.1. Mô hình centralized directory U .......................................................................13 UHình 1.2. Mô hình flooding request U ...............................................................................14 UHình 1.3. Distributed Hash Table U ..................................................................................20 UHình 1.4. (a) Một mạng Chord với 6 node, 5 item và N=16. (b) Nguyên tắc chung của bảng routing table. (c) Bảng routing table của node 3 và node 11 U ................................23 UHình 1.5. Quá trình một node join vào mạngU.................................................................28 UHình 1.6. (a) Bảng finger và vị trí của key sau khi node 6 join. (b)Bảng finger và vị trí của key sau khi node 3 leave.U.........................................................................................29 UHình 1.7.Con trỏ của node 3 (0011) trong KademliaU....................................................31 UHình 1.8. Minh họa cách chọn bảng định tuyến của một node Tapestry U.......................34 UHình 1.9. Đường đi của thông điệp từ node 5230 tới node 42ADU .................................36 UHình 1.10. Ví dụ về Tapestry node publish itemU ...........................................................37 UHình 1.11. Ví dụ về Tapestry node tìm kiếm itemU.........................................................37 UHì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ểU ..................................................................................................39 UHình 2.1. Node join/leave với interval=600 s trong mạng Chord 100 nodeU..................46 UHình 2.2. Lưu đồ thuật toán quá trình xác định churn rateU ............................................48 UHì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).U .............................................................49 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 .........................50 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 ........................51 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 ...................52 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 ............55 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 của Kelisp và Tapestry với RTT=1s, 10s và node join/leave với interval=5s (trái) và 10s (phải).U ......................................................................................56 UHì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).U .............................................................................................................................59 UHì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.U..................60 UHì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=600sU ..................................62 UHì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=600sU .....................................................................65 UHì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=600sU ..................................................................................................................66 UHình 3.1. Biểu đồ chuyển đổi trạng thái của node ChordU ..............................................70 UHì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ôngU ...71 UHình 3.3. Biểu đồ thời gian biểu diễn quá trình một node rời khỏi mạngU .....................74 UHình 3.4. Kiến trúc của giải pháp caching proxyU...........................................................80 UHình 3.5. Biểu đồ thời gian biểu diễn quá trình caching thành côngU.............................81 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. Giả mã tìm node successor của ID nU.....................................................25 UThuật toán 1.2. Giả mã cho hoạt động join vào mạng của một nodeU.............................26 UThuật toán 1.3. Giả mã cho quá trình stabilizationU ........................................................27 UThuật toán 3.1. Thuật toán join tối ưu hóaU .....................................................................73 UThuật toán 3.2. Thuật toán leave tối ưu hóaU...................................................................76 UThuật toán 3.3. Quá trình stabilization định kỳ để xử lý failureU ....................................78 UThuật toán 3.4. Quá trình caching U ..................................................................................81 UThuật toán 3.5. Đồng bộ hóa vòng proxy và vòng node Chord thông thườngU ..............85 UThuật toán 3.6. Xử lý thay đổi trong vòng proxyU ..........................................................86 UThuậ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ứngU ..........89 UThuật toán 3.8. Join và leave trong trường hợp nhân bản đối xứngU ..............................90 UThuật toán 3.9. Xử lý failure trong nhân bản đối xứngU..................................................90 UThuật toán 3.10. Thuật toán bulk owner operationU ........................................................91 Luận văn tốt nghiệp Ngô Hoàng Giang 9 Danh mục bảng UBảng 1.1. Trạng thái phát triển của các simulatorU .........................................................41 UBảng 1.2. Đặc điểm của các simulatorU ...........................................................................42 UBảng 2.1. Bảng tham số của KademliaU ..........................................................................49 UBảng 2.2. Bảng tham số của ChordU................................................................................50 UBảng 2.3. Bảng tham số của KelipsU ...............................................................................51 UBảng 2.4. Bảng tham số của Tapestry U............................................................................52 UBả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 nodeU .................................................................................................53 UBảng 2.6. Điều kiện mô phỏngU.......................................................................................54 UBảng 2.7. Giá trị tham số của ChordU ..............................................................................54 UBảng 2.8. Giá trị tham số của Tapestry U ..........................................................................54 UBảng 2.9. Giá trị tham số của KelipsU .............................................................................55 UBảng 2.10. So sánh giữa Chord, Kelips và Tapestry U .....................................................56 UBảng 2.11. Giá trị tham số của ChordU ...........................................................................57 UBảng 2.12. Giá trị tham số của KelipsU ...........................................................................58 UBảng 2.13. Giá trị tham số của Tapestry U ........................................................................58 UBảng 2.14. Bảng tóm tắt kết quảU ....................................................................................63 UBảng 2.15. Giá trị tham số của ChordU ............................................................................64 UBảng 2.16. Giá trị tham số của KelipsU ...........................................................................64 UBảng 2.17. Giá trị tham số của Tapestry U ........................................................................65 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. Với nhiều ưu điểm hứa hẹn như tính hiệu quả, linh hoạt và khả năng mở rộng cao, các mạng peer-to-peer overlay đã và đang thu hút được nhiều sự quan tâm từ cộng đồng nghiên cứu. Các mạng peer-to-peer overlay đã phát triển qua ba thế hệ, thế hệ hiện nay là mạng structured overlay dựa trên khả năng lưu trữ và tìm kiếm dữ liệu hiệu quả của cơ chế bảng băm phân tán (Distributed Hash Table hay DHT). Các DHT được thiết kế để làm trong môi trường tương đối ổn định với các peer là máy tính. Tuy nhiên, vài năm gần đây, các thiết bị nối mạng ngày càng phong phú, đa dạng như tivi hay các thiết bị wireless như điện thoại, PDA, …. Các thiết bị này kết nối và rời khỏi mạng sau một thời gian ngắn (churn rate cao) khiến cho thông tin về các peer trên mạng liên tục thay đổi dẫn đến hiệu năng của các DHT giảm sút rõ rệt. Đánh giá và cải thiện hiệu năng của các DHT trong điều kiện mạng churn rate cao là bài toán đang rất được quan tâm hiện nay. Luận văn bao gồm ba phần. Phần thứ nhất tóm tắt lý thuyết chung về mạng peer-to-peer. 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. Các kết quả nghiên cứu trong luận văn đã được công bố trên một số 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 11 Chương 1. 0BLý thuyết tổng quan 1.1. Lý thuyết chung về về mạng P2P 1.1.1. Khái niệm mạng P2P Trong khoảng 10 năm trở lại đây, lĩnh vực P2P nhận được sự quan tâm của rất nhiều nhóm nghiên cứu, của các công ty, trường đại học và đã có những bước phát triển mạnh mẽ. Ngày nay các ứng dụng peer-to-peer được sử dụng rộng rãi cho nhiều mục đích khác nhau như chia sẻ tài nguyên và nội dung, chat, chơi game, … Cũng giống như các xu hướng đang trong quá trình phát triển khác, hiện nay chưa có một định nghĩa chính xác về mạng P2P. Dưới đây là một số định nghĩa về P2P: Theo Oram, P2P là một lớp các ứng dụng tận dụng các tài nguyên như bộ nhớ, năng lực xử lý, nội dung, … tại các điểm cuối trong mạng Internet. Bởi vì truy cập vào các tài nguyên phân tán này cũng có nghĩa là hoạt động trong một môi trường liên kết không ổn định và với địa chỉ IP có thể thay đổi, các node P2P phải hoạt động ngoài hệ thống DNS và có quyền tự trị cao hoặc hoàn toàn tự trị. Theo Miller, P2P là một kiến trúc trong đó các máy tính có vai trò và trách nhiệm như nhau. Mô hình này đối lập với mô hình client/server truyền thống, trong đó một số máy tính được dành riêng để phục vụ các máy tính khác. P2P có năm đặc điểm: − Việc truyền dữ liệu và thông tin giữa các peer trong mạng dễ dàng − Các peer vừa có thể hoạt động như client vừa có thể hoạt động như server − Nội dung chính trong mạng được cung cấp bởi các peer − Mạng trao quyền điều khiển và tự trị cho các peer − Mạng hỗ trợ các peer không kết nối thường xuyên và các peer không có địa chỉ IP cố định Theo P2P Working Group: P2P computing là sự chia sẻ tài nguyên và dịch vụ bằng cách trao đổi trực tiếp giữa các hệ thống. 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ữ. Peer-to-peer computing tận dụng sức mạnh tính toán của các máy tính cá nhân và kết nối mạng, cho phép doanh nghiệp tận dụng sức mạnh tổng hợp của các client. Các định nghĩa về P2P thống nhất ở một số khái niệm: chia sẻ tài nguyên, tự trị/phân tán, địa chỉ IP động, vai trò vừa là client vừa là server. 1.1.2. Quá trình phát triển của các hệ thống P2P Peer-to-Peer là thuật ngữ tương đối mới trong lĩnh vực mạng và các hệ thống phân tán. Theo Oram, P2P computing bắt đầu trở thành đề tài được nhiều người quan tâm từ giữa những năm 2000. Trong khoảng thời gian từ đó đến nay, P2P trải qua vài thế hệ, mỗi thế hệ được phát triển với những động cơ, mục đích của mình. Thế hệ thứ nhất Thế hệ P2P đầu tiên bắt đầu với sự xuất hiện của ứng dụng chia sẻ file Napster. Napster và các ứng dụng khác trong thế hệ thứ nhất sử dụng mô hình centralized directory. Đây là mô hình hybrid P2P trong đó hầu hết các peer trong hệ thống có vai trò như nhau, một số peer có vai trò lớn hơn và được gọi là các server. XHình 1.1X cho thấy một ví dụ về mô hình centralized directory. Trong mô hình này, các peer muốn chia sẻ file với các peer khác sẽ thông báo với server về các file này. Khi một peer muốn tìm một file nào đó, nó sẽ gửi yêu cầu đến server, dựa trên các thông tin đã thu thập được, server sẽ tìm ra các peer chứa file đó và trả kết quả tìm kiếm cho peer yêu cầu. Kết quả trả về là peer phù hợp dựa trên một số thông số như tốc độ kết nối, kích thước file, …. Sau khi nhận được kết quả, peer tìm kiếm sẽ trao đổi file trực tiếp với peer chứa file mà không thông qua server nữa. Luận văn tốt nghiệp Ngô Hoàng Giang 13 Hình 1.1. Mô hình centralized directory Đóng góp chính của thế hệ thứ nhất là đã đưa ra kiến trúc mạng không xem các máy tính như client và server mà xem chúng như các máy cung cấp và sử dụng tài nguyên với vai trò tương đương nhau. Mô hình centralized directory cho phép tìm kiếm thông tin trong không gian lưu trữ một cách nhanh chóng, tuy nhiên, điểm yếu của của mô hình này là tính khả mở vì tải trên index server sẽ tăng tuyến tính với số lượng peer. Đồng thời các hệ thống sử dụng mô hình này, điển hình là Napster còn gặp vấn đề về bản quyền các tài nguyên. Thế hệ thứ hai Thế hệ thứ hai bắt đầu với các ứng dụng như Gnutella, Freenet làm việc mô hình flooded requests. Mô hình này không có bất kỳ server nào, các peer bình đẳng như nhau. Các hệ thống peer to peer thế hệ thứ hai là các hệ thống peer to peer thuần túy. Không giống thế hệ thứ nhất, các peer không thông báo về các nội dung chúng chia sẻ, khi một peer muốn tìm kiếm một file, nó gửi yêu cầu tới các peer kết nối trực tiếp với nó, nếu các peer đó không tìm thấy file, mỗi peer sẽ gửi yêu cầu tìm kiếm đến Luận văn tốt nghiệp Ngô Hoàng Giang 14 các peer kết nối trực tiếp với nó, quá trình cứ diễn ra như vậy cho đến khi request bị timeout. Quá trình gửi yêu cầu tìm kiếm đi như vậy gọi là flooding. XHình 1.2 X biểu diễn một mô hình flooding request. Hình 1.2. Mô hình flooding request Thế hệ thứ hai xóa bỏ được một số điểm xử lý tập trung trong mạng nhưng tính khả mở còn kém hơn do mạng sử dụng thuật toán flooding sinh ra quá nhiều traffic. Thêm nữa, các mạng làm việc theo mô hình này không đảm bảo sẽ tìm được dữ liệu có trên mạng do phạm vi tìm kiếm bị giới hạn. Một số mạng trong thế hệ thứ hai đưa ra một số cải tiến. Freenet đưa ra mô hình document routing, trong đó dữ liệu được lưu trên trên node có id tương tự với id của dữ liệu và các query được chuyển tiếp dựa trên id của dữ liệu tìm kiếm. Kazza, Gnutella sử dụng khái niệm super peer trong đó một số node hoạt động như directory service, giảm lượng flooding trong mạng. Luận văn tốt nghiệp Ngô Hoàng Giang 15 Thế hệ thứ ba Sự đơn giản trong giải pháp và khả năng xóa bỏ điểm tập trung, chuyển trách nhiệm pháp lý về phía người sử dụng cũng như hạn chế về tính khả mở do lưu lượng quá lớn đã thu hút cộng đồng nghiên cứu về mạng và các hệ thống mở. Bài toán đặt ra cho cộng đồng nghiên cứu là xây dựng một mạng P2P overlay khả mở không có điểm điều khiển tập trung. Nỗ lực giải quyết bài toán này là sự xuất hiện của “structured P2P overlay networks”. Thế hệ thứ ba được khởi đầu với các dự án nghiên cứu như Chord, CAN, Pastry, Tapestry và P-Grid. Các dự án này đưa ra khái niệm Distributed Hash Table (DHT). Mỗi peer trong hệ thống có một ID thu được từ việc băm các đặc thuộc tính đặc trưng của peer đó như địa chỉ IP hay public key. Mỗi data item cũng có một ID thu được theo cách tương tự với các peer. Hash table lưu data dưới dạng cặp key-value. Như vậy, node ID và cặp key-value được băm vào cùng một không gian ID. Các node sau đó được nối với nhau theo một topology nào đó. Quá trình tìm kiếm dữ liệu trở thành quá trình định tuyến với kích thước bảng định tuyến nhỏ và chiều dài đường đi cực đại. Thế hệ thứ ba đảm bảo xác xuất tìm thấy thông tin cao. Các DHT được xây dựng nhằm mục đích cho phép các peer hoạt động như một cấu trúc dữ liệu phân tán với hai hàm chính Put(key,value) và Get(Key). Hàm Put lưu dữ liệu tại một peer nào đó sao cho bất kỳ peer nào cũng có thể tìm được bằng hàm Get. Các hàm này hoàn thành sau khi đi qua một số nhỏ các chặng. Giải pháp DHT đảm bảo cho mạng có tính khả mở và khả năng tìm thấy thông tin cao trong khi vẫn hoàn toàn phân tán. DHT đang được xem như là cách tiếp cận hợp lý cho vấn đề định vị và định tuyến trong các hệ thống P2P. Cộng đồng nghiên cứu đã đưa ra nhiều DHT khác nhau. Mỗi DHT hoạt động theo nguyên lý chung và có ưu điểm riêng, Chord với thiết kế đơn giản, Tapestry và Pastry giải quyết được vấn đề proximity routing, … Luận văn tốt nghiệp Ngô Hoàng Giang 16 1.1.3. Ứng dụng p2p Các ứng dụng p2p có thể chia vào bốn nhóm: Chia sẻ file (file sharing): lưu trữ và chia sẻ nội dung là ứng dụng thành công nhất của công nghệ p2p. Các ứng dụng chia sẻ file tập trung vào việc lưu trữ thông tin trên các peer khác nhau trên mạng và lấy thông tin từ các peer đó. Các ứng dụng thuộc nhóm này bao gồm Napster, Gnutella, Freenet, Kazaa, Chord, …. Tính toán phân tán (distributed computing): các ứng dụng thuộc nhóm này sử dụng tài nguyên từ các máy tính được nối mạng. Ý tưởng chính của các ứng dụng tính toán phân tán là các chu kỳ xử lý nhàn rỗi trên bất kỳ máy tính nối mạng nào đều có thể được sử dụng cho việc giải quyết bài toán trên các máy yêu cầu nhiều năng lực tính toán. SETI (Search for Ex-traterrestrial Intelligence) là một dự án nghiên cứu khoa học nhằm mục đích xây dựng một máy tính ảo khổng lồ từ sức mạnh của các máy tính nối mạng trong chù kỳ nhàn rỗi của chúng. Cộng tác (collaboration): các ứng dụng cộng tác p2p cho phép người sử dụng cộng tác với nhau ở mức ứng dụng. Các ứng dụng này rất đa dạng, từ instant messaging, chat đến game online hay các ứng dụng chia sẻ sử dụng trong thương mại, giáo dục hay môi trường gia đình. Platform (nền): các platform p2p cung cấp hạ tầng hỗ trợ các ứng dụng sử dụng cơ chế p2p. Các thành phần p2p được sử dụng bao gồm naming, discovery, communication, security và resource aggregation. JXTA là một p2p platform cung cấp hạ tầng tính toán và lập trình mạng. 1.1.4. Các vấn đề đối với mạng p2p hiện nay Các hệ thống p2p có nhiều ưu điểm so với các hệ thống client-server truyền thống như tính khả mở, khả năng chịu lỗi, hiệu năng. 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. Bởi vì trong hệ thống p2p các peer là động và không tin tưởng lẫn nhau nên để đạt được mức bảo mật cao trong các hệ thống p2p sẽ khó hơn trong các hệ thống client-server. Các cơ chế bảo mật truyền thống để bảo vệ dữ liệu và hệ thống khỏi tấn công, xâm nhập như firewall không thể bảo vệ thống p2p bởi vì các hệ thống này phân tán và các cơ chế bảo mật có thể ngăn chặn, hạn chế quá trình truyền thông p2p. Do đó cần đưa ra các khái niệm bảo mật mới cho phép tương tác và xử lý phân tán trong các hệ thống p2p. Tính tin cậy (reliability): một hệ thống tin cậy là một hệ thống có khả năng hồi phục sau khi xuất hiện lỗi. Các cơ chế đảm bảo độ tin cậy trong mạng p2p bao gồm nhân bản dữ liệu, phát hiện và khôi phục node bị lỗi, xây dựng nhiều cơ chế đảm bảo thông tin định vị, tránh “single point of failure” và đảm bảo nhiều đường đi tới dữ liệu. Tính linh hoạt (flexibility): một trong những tính chất quan trọng nhất trong các hệ thống p2p là các peer tự chủ, chúng có thể join/leave bất kỳ lúc nào. Các hệ thống p2p gần đây có quy mô lớn, điều khiển phân tán và hoạt động trong môi trường động. Để giải quyết vấn đề quy mô và tính động của các hệ thống p2p, khi xây dựng các hệ thống p2p cần chú ý đến khả năng điều chỉnh và tự tổ chức. Cân bằng tải (load balancing) : vấn đề phân tán dữ liệu và tính toán rất quan trọng đối với hiệu quả hoạt động của các mạng p2p. Một trong những giải pháp cho vấn đề phân tán này là distributed hash table (DHT). Trong cách tiếp cận này, cân bằng tải được xem xét trên hai khía cạnh: cân bằng không gian địa chỉ tức là cân bằng phân phối của không gian key address trên các node và cân bằng item trong trường hợp phân phối của các item trong không gian địa chỉ không thể là ngẫu nhiên. Cân bằng tải giữa các node tính toán trong hệ thống p2p cũng có thể được cài đặt sử dụng mô hình tự tổ chức dựa trên agent. Luận văn tốt nghiệp Ngô Hoàng Giang 18 1.2. Lý thuyết về Distributed Hash Table (DHT) 1.2.1. Hash Table (bảng băm) Một hash table là một cấu trúc dữ liệu ánh xạ giữa key và value. Tức là tương ứng với một key, hash table sẽ trả về một value. Để thực hiện việc ánh xạ, hash table sử dụng hash function tính toán vị trí lưu value dựa trên key. Hash function phải đảm bảo: tránh xung đột và dễ dàng thực hiện. Tránh xung đột nghĩa là ánh xạ giữa không gian key và không gian địa chỉ phải đều và ngẫu nhiên đến mức có thể. 1.2.2. Distributed Hash Table Distributed Hash Table (DHT) là thuật toán được sử dụng trong các ứng dụng p2p, DHT cho phép quản lý mạng p2p theo đúng nghĩa với độ tin cậy cao, khả mở, hiệu quả và có khả năng chịu lỗi. DHT là một hash table được cài đặt như một hệ thống phân tán. Cũng như một hash table thông thường, DHT cung cấp ánh xạ từ key đến value. Nhưng không giống như hash table thông thường, các value trong một DHT được lưu trên các node khác nhau trong mạng chứ không phải lưu trong một cấu trúc dữ liệu cục bộ. Thông qua một key, value tương ứng được lưu tại một node phù hợp trên mạng hoặc được lấy về từ node tương ứng trên mạng. Trong một DHT, key được tính ra từ value. Tất cả các key đều nằm trên cùng một không gian địa chỉ. Các ứng dụng file sharing thường sử dụng không gian địa chỉ 160 bit. Để xác định node nào lưu value nào, mỗi node phải có một ID trong không gian địa chỉ giống như không gian địa chỉ của key. Các DHT đưa ra khái niệm khoảng cách giữa hai ID (một key có thể xem như ID của value). Khi đó value được lưu trên node có ID gần với ID của value nhất. Để 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. Quá trình cứ tiếp tục như vậy, thông điệp được chuyển tiếp trên mạng cho đến khi nó gặp node có ID gần với ID của dữ liệu nhất và value được lưu trên node này. Để tìm một value, thủ tục cũng tương tự, node cần tìm dữ liệu sẽ gửi đi thông điệp tìm kiếm dữ liệu. Sau quá trình chuyển tiếp thông điệp giống như quá trình chuyển tiếp thông điệp lưu dữ liệu, node lưu dữ liệu sẽ được tìm ra và node này sẽ trả dữ liệu cho node tìm kiếm. Distributed Hash Tables có các ưu điểm khác biệt so với dịch vụ hướng Client- Server truyền thống: − DHT cho phép hoạt động phân tán, không cần duy trì một server trung tâm để điều khiển hoạt động của mạng p2p. Cũng vì vậy, các ứng dụng p2p sử dụng DHT là các ứng dụng p2p thuần túy. − Hệ thống có tính khả mở, nghĩa là hệ thống vẫn hoạt động tốt ngay cả với số lượng node và lưu lượng trên mạng lớn. − Tải được cân bằng giữa các peer trong mạng − Hệ thống dựa trên giả định rằng mạng không tĩnh và các thay đổi xuất hiện thường xuyên với các node join vào mạng và leave khỏi mạng (còn gọi là churn) − Việc định tuyến và lấy dữ liệu nhanh và có thể hoàn thành trong thời gian tỷ lệ loga − Hệ thống mạnh mẽ, nghĩa là nó có thể đứng vững ngay cả khi bị tấn công trên diện rộng DHT cung cấp dịch vụ lưu trữ, tìm kiếm dữ liệu thông qua hai hàm insert và lookup. Luận văn tốt nghiệp Ngô Hoàng Giang 20 Hình 1.3. Distributed Hash Table 1.3. Giới thiệu một số DHT Trong phần này chúng ta sẽ xem xét một số well-known DHT như Chord, Kelips, Tapestry, Kademlia. Ta phân tích các DHT này dựa trên một số khía cạnh như sau: Overlay Graph (sơ đồ mạng overlay): đây là tiêu chuẩn chính để phân biệt các hệ thống với nhau. Đối với mỗi overlay graph, chúng ta sẽ xem xét graph và bảng định tuyến của mỗi node trong graph. Mapping Items Onto Nodes (ánh xạ giữa item và node): đối với mỗi overlay graph, chúng ta quan tâm đến mối quan hệ giữa ID của node và ID của các item lưu trên node đó, tức là một item cụ thể sẽ được lưu trên node nào. Lookup process (tiến trình tìm kiếm): tiến trình tìm kiếm trên một mạng diễn ra như thế nào và hiệu năng của quá trình tìm kiếm liên quan chặt chẽ đến loại overlay graph của mạng đó. Joins, Leaves và Maintenance (gia nhập, rời khỏi mạng và duy trì) : chúng ta sẽ xem một node mới được thêm vào graph như thế nào và một node rời graph như thế nào. 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. Replication và fault tolerance (nhân bản và chịu lỗi): bên cạnh các node rời khỏi mạng có báo trước, một số node có thể đột ngột rời khỏi mạng do một số nguyên nhân như mất điện, đường truyền hỏng, …, trường hợp này khó xử lý hơn trường hợp các node thông báo đến các node khác trước khi rời khỏi mạng. Replication là một giải pháp cho trường hợp các node rời khỏi mạng mà không báo trước. Upper services và applications (ứng dụng và dịch vụ bên trên): một số ứng dụng và dịch vụ đã được phát triển sử dụng DHT. Implementation (cài đặt): liệt kê một số cài đặt của các DHT. 1.3.1. Chord Overlay graph Chord sử dụng một không gian ID vòng tròn kích thước N. Một node Chord với ID là u có một con trỏ tới node đầu tiên đứng sau nó trong không gian ID theo chiều kim đồng hồ, ký hiệu là Succ(u) và một con trỏ tới node đứng trước nó trong không gian ID, ký hiệu là Pred(u). Các node tạo thành một danh sách liên kết hai chiều. Bên cạnh đó, một node Chord lưu M = log2(N) con trỏ gọi là các finger. Tập các finger của node Chord u được xác định như sau Fu = {(u, Succ(u + 2i−1))}, 1 ≤ i ≤ M. Với cách lựa chọn finger thế này, tong mạng Chord, các node quan sát không gian ID vòng như là không gian này bắt đầu từ ID của chúng. Đồng thời với cách lựa chọn finger của Chord, không gian ID sẽ được chia đôi, nửa thứ nhất cũng được chia đôi, rồi phần tư thứ nhất lại được chia đôi, … XHình 1.4X cho thấy một mạng với không gian ID N = 16, mỗi node có M=log2(N)= 4 finger. Mạng có các node với ID lần lượt là 0, 3, 5, 9, 11, 12. 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) . Node n chọn các finger của nó bằng cách xem nó như là điểm khởi đầu của không gian ID, rồi chọn finger là successor của các ID n + 20, n + 21, n + 22, và n + 23. ID cuối cùng n + 23 chia không gian ID thành hai phần bằng nhau, ID trước đó n + 22 chia nửa thứ nhất thành hai phần bằng nhau, ID n + 21 chia phần tư đầu tiên thành hai phần bằng nhau, tương tự ID n + 20 chia phần tám thứ nhất thành hai phần bằng nhau. Tuy nhiên, có thể không có node có ID giống với ID tại điểm chia, khi đó successor của ID tại điểm chia được chọn làm finger. XHình 1.4X(c) cho thấy bảng định tuyến của node 3 và node 11. Luận văn tốt nghiệp Ngô Hoàng Giang 23 Hình 1.4. (a) Một mạng Chord với 6 node, 5 item và N=16. (b) Nguyên tắc chung của bảng routing table. (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. Như chúng ta thấy trên XHình 1.4X, một item được lưu trên node đầu tiên mà theo sau nó theo chiều kim đồng hồ trong không gian ID. Các item với ID tương ứng 2, 3, 6, 10,13 được lưu trong các node trên mạng như sau: {2,3} được lưu tại node 3; {6} được lưu tại node 9; {10} được lưu tại node 11; và {13} được lưu tại node 0 Lookup Process Quá trình tìm kiếm là kết quả tự nhiên của cách chia không gian ID. Cả việc chèn và tìm kiếm dữ liệu đều dựa trên việc tìm ID successor của một ID. Ví dụ, khi node 11 muốn chèn một item mới với ID là 8, lookup được chuyển tiếp tới node 3 là node đứng trước gần node 8 nhất trong bảng finger của node 11. Node lại thực hiện quá trình tương tự, nó chuyển tiếp yêu cầu tới node 5 là node đứng trước gần 8 nhất trong bảng finger của nó. Node 5 thấy rằng 8 nằm giữa nó và successor của nó (node 9), do đó nó trả về kết quả 9 theo đường đi ngược lại. Sau khi nhận được câu trả lời, tầng ứng dụng trên node 11 sẽ liên lạc với tầng ứng dụng trên node 9 và yêu cầu lưu một số giá trị với key là 8. Bất kỳ node nào muốn tìm kiếm key 8 đều thực hiện quá trình tương tự và trong không quá M chặng, một node sẽ tìm ra node lưu các dữ liệu ứng với key 8. Nói chung, trong điều kiện thông thường, một tìm kiếm sẽ hoàn thành trong O(log2(N)) chặng. Joins, Leaves and Maintenance Khi node n muốn join vào mạng, nó phải tìm ID của mình thông qua một số contact trong mạng và chèn bản thân nó vào vòng giữa successor s của nó và predecessor của s sử dụng một thuật toán stabilization chạy định kỳ. Bảng định tuyến của n được khởi tạo bằng cách copy bảng định tuyến của s hoặc yêu cầu s tìm các finger của n. Tập các node cần điều chỉnh bảng định tuyến sau khi n join vào mạng nhờ các node này đều chạy thuật toán stabilization định kỳ. 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. Việc di chuyển dữ liệu này được thực hiện bởi tầng ứng dụng của n và s. Giả mã của các quá trình tìm kiếm successor của node n, khởi tạo bảng định tuyến của n, cập nhật bảng finger của các node liên quan và quá trình stabilization như sau: //yêu cầu node n tìm successor của id n.find_successor(id); n’=find_predecessor(id); return n’.successor; // yêu cầu node n tìm predecessor của id n.find_predecessor(id); n’=n; while (id ∉ (n’, n’.successor]) n’=n’.closest_preceding_finger(id); return n’; // trả về finger gần nhất đứng trước id n.closest_preceding_finger(id); for i = m downto 1 if (finger[i].node ∈ (n; id)) return finger[i].node; return n; Thuật toán 1.1. Giả mã tìm node successor của ID n #define successor finger[1].node // node n join vào mạng; // n’ là một node tùy ý trong mạng n.join(n’) if (n’) init_finger_table(n’); update_others(); // chuyển key trong khoảng (predecessor,n] từ successor else // n là node duy nhất trên mạng for i = 1 to m finger[i].node = n; Luận văn tốt nghiệp Ngô Hoàng Giang 26 predecessor = n ; // khởi tạo bảng finger table của node // n’ là một node bất kỳ trên mạng n.init_finger_table(n’) finger[1].node = n’.fin_successor(finger[1].start); predecessor = successor.predecessor; successor.predecessor = n; for i = 1 to m-1 if (finger[i+1].start ∈ [n, finger[i].node)) finger[i+1].node = finger[i].node; else finger[i+1].node = n’.find_successor(finger[i+1].start); // cập nhật n vào các node có finger table that đổi n.update_others() for i = 1 to m //tìm node p cuối cùng có finger thứ i là n p = find_predecessor(n-2i-1); p.update_finger_table(n.,i); //nếu s là finger thứ i của n, cập nhật s vào bảng finger của n n.update_finger_table(s,i) if (s ∈ [n, finger[i].node)) finger[i].node = s; p = predecessor; // lấy node đầu tiên đứng trước n p.update_finger_table(s,i); Thuật toán 1.2. Giả mã cho hoạt động join vào mạng của một node n.join(n’) predecessor = nil; successor = n’.find_successor(n); // định kỳ kiểm tra successor đứng ngay n và báo cho successor //biết về n n.stabilize() x = successor.predecessor; if ( x ∈ (n, successor)) successor = x; successor.notify(n); Luận văn tốt nghiệp Ngô Hoàng Giang 27 // n’ nghĩ n’ là predecessor của n n.notify(n’) if (predecessor is nil or n’ ∈ (predecessor,n)) predecessor = n’ ; // định kỳ cập nhật các finger trong bảng finger table n.fix_finger() i = random index > 1 into finger [] finger[i].node = find_successor(finger[i].start); Thuật toán 1.3. Giả mã cho quá trình stabilization XHình 1.5X cho chúng ta thấy một ví dụ về quá trình join vào mạng của một node. Giả sử node 21 có successor là node 32, trên node 32 đang lưu các key 24 và 30. Node 26 join vào mạng, sau quá trình tìm kiếm, node 26 biết node 32 là successor của mình, nó trỏ con trỏ successor của mình vào node 32 và báo cho node 32 biết. Node 32 sau khi được báo thì trỏ con trỏ predecessor vào node 26. Node 26 copy các key tương ứng với nó (key 24) từ node 32. Đến định kỳ, N21 chạy quá trình stabilize, lúc này con trỏ successor vẫn trỏ vào node 32. Node 21 hỏi node 32 về predecessor của node 32, lúc này predecessor của 32 là 26. Sau khi nhận được câu trả lời, N21 trỏ con trỏ successor vào node 26 và báo cho node 26 biết nó là predecessor của node 26. 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. Quá trình một node join vào mạng Quá trình rời khỏi mạng có báo trược được thực hiện như sau: node sắp rời khỏi mạng chuyển các key nó đang lưu sang successor của nó rồi báo cho các node predecessor và successor. Bảng định tuyến của các node liên quan sẽ được cập nhật khi các node này chạy thuật toán stabilization. XHình 1.6X dưới đây cho chúng ta một ví dụ về bảng định tuyến của các node khi có sự join/leave. Ban đầu mạng có 3 node với ID là 0, 1, 3, bảng định tuyến của chúng được cho thấy trên hình vẽ. 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. Hình 1.6. (a) Bảng finger và vị trí của key sau khi node 6 join. (b)Bảng finger và vị trí của key sau khi node 3 leave. Replication and Fault Tolerance Các node rời khỏi mạng đột ngột có hai tác động tiêu cực. Thứ nhất là dẫn đến mất dữ liệu lưu trên các node này, thứ hai một phần của vòng bị mấtl liên kết dẫn đến một số ID sẽ không được tìm thấy. Có thể xảy ra tình huống một dãy các node liền nhau cùng rời khỏi mạng đột ngột. Chord giải quyết vấn đề này bằng cách cho mỗi node lưu một danh sách log2(N) node theo sau nó trong không gian ID. Danh sách này có hai mục đích, thứ nhất là nếu một node phát hiện successor của nó không hoạt động, nó sẽ thay thế bằng node ngay cạnh trong successor list, thứ hai, mọi dữ liệu được lưu trên một node nào đó cũng được lưu trên các node trong successor list. Dữ liệu chỉ bị mất hay vòng chỉ bị đứt khi có log2(N) + 1 node liên tiếp fail đồng thời. 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. Đồng thời, một thuật toán broadcast cũng được phát triển cho Chord Implementation Cài đặt chính của Chord được thực hiện bằng nghôn ngữ C++. Thêm nữa, một C++ discrete-event simulator cũng đã được xây dựng. Naanou là một cài đặt C# của Chord với một ứng dụng chia sẻ file được xây dựng dựa trên nó. 1.3.2. Kademlia Overlay graph Kademlia graph tổ chức các ID trong không gian vòng tròn trong đó ID của các node là lá của cây nhị phân, vị trí 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 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 t