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