Tài liệu 213149999 cai thien chord full docx

Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 MỤC LỤC MỞ ĐẦU..........................................................................................................................................4 DANH MỤC HÌNH VẼ...................................................................................................................6 DANH MỤC BẢNG BIỂU..............................................................................................................7 CHƯƠNG I: TỔNG QUAN VỀ MẠNG NGANG HÀNG.............................................................8 1.1 Tổng quan về mạng ngang hàng............................................................................................8 1.1.1 Khái niệm........................................................................................................................8 1.1.2 Ưu nhược điểm của mạng ngang hàng...........................................................................8 1.2 Phân loại mạng ngang hàng...................................................................................................9 1.2.1 Theo mức độ phân quyền................................................................................................9 a. Mạng ngang hàng tập trung.............................................................................................9 b. Mạng ngang hàng thuần nhất........................................................................................10 c. Mạng ngang hàng lai ghép.............................................................................................11 1.2.2 Phân loại theo cấu trúc liên kết.....................................................................................13 a. Mạng ngang hàng không cấu trúc..................................................................................13 b. Mạng ngang hàng có cấu trúc........................................................................................13 1.2.3 Phân loại theo cơ chế tìm kiếm.....................................................................................14 a. Cơ chế danh mục tập trung............................................................................................14 b. Cơ chế yêu cầu liên tục..................................................................................................15 c. Cơ chế bảng băm phân tán.............................................................................................15 1.3 Ứng dụng của mạng ngang hàng..........................................................................................16 1.3.1 Chia sẻ tài liệu...............................................................................................................16 1.3.2 Phân tán tính toán.........................................................................................................16 1.3.3 Hợp tác..........................................................................................................................16 1.3.4 Lớp nền.........................................................................................................................16 1.4 Các vấn đề với mạng ngang hàng........................................................................................17 1.4.1 Tính bảo mật.................................................................................................................17 1.4.2 Độ tin cậy......................................................................................................................17 1.4.3 Độ linh động.................................................................................................................17 1.4.4 Cân bằng tải..................................................................................................................17 1.5 Một số ví dụ về mạng ngang hàng.......................................................................................17 Đếề tài nghiến cứu khoa học sinh viến 1 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 1.5.1 Mạng Edonkey..............................................................................................................17 1.5.2 Mạng Gnutella..............................................................................................................18 1.5.3 Mạng Napster................................................................................................................19 CHƯƠNG II: CÁC GIAO THỨC ĐỊNH TUYẾN DHT-P2P........................................................20 2.1 Khái niệm về Distributed Hash Table (DHT)......................................................................20 2.2 Các giao thức định tuyến sử dụng DHT...............................................................................21 2.2.1 Chord............................................................................................................................21 a. Mạng phủ.......................................................................................................................21 b. Định tuyến.....................................................................................................................23 2.2.2 Kademlia.......................................................................................................................24 a. Mạng phủ.......................................................................................................................24 b. Định tuyến.....................................................................................................................24 2.2.3 Tapestry.........................................................................................................................25 a. Mạng phủ.......................................................................................................................25 b. Định tuyến.....................................................................................................................26 2.2.4 Kelips............................................................................................................................28 a. Mạng phủ.......................................................................................................................28 b. Định tuyến.....................................................................................................................29 CHƯƠNG III: CẢI THIỆN HIỆU NĂNG ĐỊNH TUYẾN TRONG CHORD..............................30 3.1 Thuật toán Chord hai chiều..................................................................................................31 3.2 Thuật toán NN-Chord và BNN-Chord.................................................................................33 3.2.1 Thuật toán NN-Chord...................................................................................................33 3.2.2 Thuật toán BNN-Chord................................................................................................34 3.2.3 Thuật toán cụ thể...........................................................................................................35 3.4 Cải thiện Chord có xem xét trễ trên mạng vật lý.................................................................38 3.4.1 Vấn đề...........................................................................................................................38 3.4.2 Đề xuất cải thiện...........................................................................................................38 a. Các định nghĩa và định lý..............................................................................................38 b. Bảng finger mới.............................................................................................................39 c. Thuật toán định tuyến....................................................................................................39 CHƯƠNG IV: MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG........................................................41 Đếề tài nghiến cứu khoa học sinh viến 2 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 4.1 Cài đặt kịch bản mô phỏng...................................................................................................41 4.2 Đánh giá phân tích tích kết quả............................................................................................42 4.2.1 Giao diện tiến trình mô phỏng......................................................................................42 4.2.2 Phân tích kết quả...........................................................................................................43 KẾT LUẬN....................................................................................................................................44 TÀI LIỆU THAM KHẢO..............................................................................................................45 Đếề tài nghiến cứu khoa học sinh viến 3 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 MỞ ĐẦẦU Trong nhiều 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 P2P. 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 P2P đã và đang thu hút được nhiều sự quan tâm từ cộng đồng nghiên cứu. Mạng P2P đã phát triển qua nhiều thế hệ, thế hệ hiện nay là mạng có cấu trúc dựa trên khả năng lưu trữ và tìm kiếm dữ liệu hiệu quả theo cơ chế Bảng băm phân tán (DHT). Vấn đề cốt lõi của các mạng ngang hàng P2P là các thuật toán định tuyến, nó đóng vai trò quyết định hiệu quả hoạt động khi thiết lập các dịch vụ hệ thống nền tảng của mạng ngang hàng nói riêng và mạng ảo trên Internet nói chung. Chord là giao thức đang được sử dụng rộng rãi trong các mạng ngang hàng có cấu trúc. Điểm khác biệt của giao thức Chord với các giao thức khác là sự đơn giản của nó và khả năng chịu lỗi cao. Tuy nhiên giao thức này vẫn còn nhiều vấn đề cần xem xét và hướng cải thiện hiệu năng định tuyến cho Chord chính là vấn đề chính mà đề tài này đề cập đến. Nội dung của đề tài bao gồm ba phần chính: Chương I: Lý thuyết chung về mạng ngang hàng Chương II: Các giao thức định tuyến DHT-P2P Chương III: Cải thiện hiệu năng định tuyến trong Chord Chương IV: Mô phỏng và đánh giá hiệu năng Do trình độ và thời gian có hạn nên đề tài không tránh khỏi những sai sót. Kính mong được sự góp ý từ quý thầy cô và các bạn để đề tài được hoàn thiện hơn. Xin kính chúc thầy cô và các bạn có sức khỏe dồi dào và thật nhiều niềm vui trong cuộc sống. Xin chân thành cám ơn! Nhóm sinh viên Đếề tài nghiến cứu khoa học sinh viến 4 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 THUẬT NGỮ VIẾT TẮT Từ Viết Tắt Tiếng Anh Tiếng Việt BNN-Chord Bidirectional Neighbor’s Neighbor Chord NN-Chord hai chiều DHT Distributed Hash Table Bảng băm phân tán NN-Chord Neighbor’s Neighbor Chord Giao thức Chord cải tiến P2P Peer – to – Peer Mạng ngang hàng RTT Round Trip Time Thời gian đi hết một vòng SETI Search for Extraterrestrial Intelligence Tìm kiếm nền văn minh ngoài trái đất TTL Time To Live Thời gian sống ID Identifier Số nhận dạng SHA Secure Hash Algorithm Thuật toán băm bảo mật IP Internet Protocol Giao thức mạng Internet MIT Massachusetts Institute of Technology Viện công nghệ Massachusetts Đếề tài nghiến cứu khoa học sinh viến 5 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 DANH MỤC HÌNH VẼẼ Hình 1.1: Mạng ngang hàng...................................................................................................8 Hình 1.2: Mạng ngang hàng thuần nhất..............................................................................10 Hình 1.3: Mạng ngang hàng lai ghép...................................................................................12 Hình 1.4: Mạng lai ghép với chỉ số hóa tập trung...............................................................12 Hình 1.5: Mạng lai ghép với chỉ số hóa phân tán................................................................13 Hình 1.6: Chức năng chính của DHT..................................................................................14 Hình 1.7: Cơ chế danh mục tập trung..................................................................................14 Hình 1.8: Cơ chế yêu cầu liên tục........................................................................................15 Hình 1.9: Cơ chế bảng băm phân tán...................................................................................16 Hình 1.10: Mô hình mạng Edonkey....................................................................................18 Hình 1.11: Mô hình mạng Gnutella.....................................................................................19 Hình 1.12: Mô hình mạng Napster......................................................................................19 Hình 2.1: Mô tả quá trình tạo key của DHT........................................................................20 Hình 2.2: Vòng không gian địa chỉ Chord...........................................................................22 Hình 2.3: Không gian ID của mạng Chord (N=64).............................................................22 Hình 2.4: Các item lưu trên mạng Chord............................................................................23 Hình 2.5: Không gian ID của mạng Kademlia (N=8).........................................................24 Hình 2.6: Các k-bucket của một node.................................................................................25 Hình 2.7: Minh họa bảng định tuyến của một node............................................................26 Hình 2.8: Các mức liên kết của node 4227..........................................................................27 Hình 2.9: Đường đi của một bản tin từ node 5230 đến node 42AD...................................27 Hình 2.10: Quá trình truy vấn item......................................................................................28 Hình 2.11: Bảng định tuyến của node 110...........................................................................29 Hình 3.1: Quá trình N9 tra cứu khóa k53............................................................................32 Hình 3.2: Tìm kiếm k54.......................................................................................................37 Hình 3.3: Bảng finger mới sau khi được loại bỏ dư thừa và thêm vào các nút mới...........37 Hình 3.4: Bảng finger của nút 8 đã bổ sung delay[i]..........................................................40 Đếề tài nghiến cứu khoa học sinh viến 6 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 DANH MỤC BẢNG BIỂU Bảng 3.1: Cấu trúc bảng W_finger của node n...................................................................32 Bảng 3.2: Bảng W_finger của node N9...............................................................................33 Bảng 3.3: Bảng learn của node n.........................................................................................33 Bảng 3.4: Learn table của node N9.....................................................................................33 Bảng 3.5: Bảng W_learn của node n...................................................................................34 Bảng 3.6: bảng W_finger của node N9...............................................................................35 Bảng 3.7: bảng W_learn của node N9.................................................................................35 Bảng 3.8: Bảng Finger và W_finger cải tiến của node N9.................................................35 Bảng 3.9: Định nghĩa delay[i]..............................................................................................39 Đếề tài nghiến cứu khoa học sinh viến 7 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 CHƯƠNG 1: TỔNG QUAN VỀẦ MẠNG NGANG HÀNG 1.1 Tổng quan về mạng ngang hàng 1.1.1 Khái niệm Mạng ngang hàng là mạng mà trong đó hai hay nhiều máy tính chia sẻ các tập tin và truy nhập các thiết bị như máy in mà không cần đến máy chủ hay các phần mềm máy chủ. Ở dạng đơn giản nhất mạng ngang hàng được tạo ra bởi hai hay nhiều máy tính kết nối với nhau và chia sẻ tài nguyên mà không phải thông qua một máy chủ dành riêng. Mạng ngang hàng dựa vào khả năng và băng tần của các máy tính tham gia vào mạng hơn là tập trung vào một số các máy tính gọi là server. Nó được sử dụng cho kết nối các node thông qua các kết nối đặc biệt và được dùng cho nhiều mục đích như chia sẻ tài liệu, chia sẻ âm nhạc, hình ảnh, dữ liệu, lưu lượng điện thoại… Mô hình của mạng ngang hàng được thể hiện trên Hình 1.1. Hình 1.1: Mạng ngang hàng 1.1.2 Ưu nhược điểm của mạng ngang hàng  Ưu điểm  Không phải đầu tư thêm về phần cứng và phần mềm máy chủ.  Dễ cài đặt, giá thành rẻ.  Không cần người quản trị mạng Đếề tài nghiến cứu khoa học sinh viến 8 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012  Người sử dụng có thể kiểm soát việc dùng chung tài nguyên.  Tăng cường khả năng cân bằng tải trong mạng.  Nhược điểm của mạng ngang hàng  Máy trạm phải gánh thêm việc phục vụ chia sẻ tài nguyên.  Máy trạm không có khả năng kiểm soát nhiều liên kết như một máy chủ  Thiếu tính tập trung, rất khó tìm kiếm dữ liệu  Không có khả năng lưu trữ tập trung  Mỗi người sử dụng trên máy trạm phải có khả năng quản trị trên chính hệ thống của mình  Khả năng bảo mật kém, khó kiểm soát  Quản lý thiếu tập trung, các mạng ngang hàng rất khó làm việc với nhau. 1.2 Phân loại mạng ngang hàng 1.2.1 Theo mức độ phân quyền a. Mạng ngang hàng tập trung Mạng ngang hàng tập trung là một trong những thế hệ mạng ngang hàng đầu tiên, đặc trưng của mạng này vẫn dựa vào một máy chủ tìm kiếm trung tâm. Tô pô xếp chồng của một mạng ngang hàng tập trung do đó có thể được miêu tả như là một mạng hình sao. Trong mô hình mạng này, mỗi điểm nút kết nối tới máy chủ tìm kiếm trung tâm để có thể gửi truy vấn tìm kiếm tài nguyên, sau khi gửi yêu cầu tới máy chủ tìm kiếm trung tâm, máy chủ tìm kiếm trung tâm trả về thông tin phản hồi tương ứng với từ khóa được quy định trong truy vấn. Tức là tại máy chủ tìm kiếm trung tâm, từ khóa trong thông báo truy vấn sẽ được ánh xạ với bảng danh sách tài nguyên mà máy chủ có. Nếu máy chủ tìm kiếm trung tâm có thông tin mà điểm nút đó yêu cầu thì nó sẽ trả về thông tin vị trí truy cập tới các điểm nút chia sẻ (đa phần là trả về các địa chỉ IP và các cổng). Sau khi điểm nút đã nhận được thông tin từ máy chủ tìm kiếm trung tâm thì lúc này quá trình trao đổi thông tin cần tìm được thực hiện theo đúng cơ chế của mạng ngang hàng, tức là trao đổi trực tiếp giữa các nút mạng với nhau mà không cần qua máy chủ tìm kiếm trung tâm.  Hoạt động giữa nút  máy chủ tìm kiếm trung tâm: - Tìm kiếm tài nguyên - Đăng nhập vào mạng xếp chồng - Đăng ký - Cập nhật thông tin các bảng định tuyến - Cập nhật thông tin tài nguyên được chia sẻ  Hoạt động giữa điểm nút điểm nút - Trao đổi dữ liệu  Ứng dụng cho mô hình mạng kiểu này là: Napster, hỗ trợ việc chia sẻ file và nhạc miễn phí giữa người dùng mạng Internet.  Ưu điểm: Đếề tài nghiến cứu khoa học sinh viến 9 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 - Tìm kiếm nhanh và hiệu quả - Quản lý tập trung/quản trị tin cậy - Dễ xây dựng  Nhược điểm: - Dễ dàng bị tấn công - Nút cổ chai - Khả năng tắc nghẽn - Khó mở rộng - Cần quản trị b. Mạng ngang hàng thuần nhất Đặc trưng nổi bật của mô hình này là không có máy chủ tìm kiếm tập trung như trong mô hình mạng ngang hàng tập trung, do đó không gặp phải vấn đề nút cổ chai. Các điểm nút giao tiếp trực tiếp với các điểm nút khác trong mạng mà không cần tới máy chủ trung tâm riêng biệt nào, các điểm nút thiết lập kết nối với nhau ngẫu nhiên. Hình 1.2: Mạng ngang hàng thuần nhất Trong mô hình mạng ngang hàng này, việc tìm kiếm file sử dụng phương pháp phát tràn(phương pháp này có sử dụng giá trị giới hạn phạm vi tìm kiếm là TTL và sử dụng GUID để trao đổi). Khi muốn tìm kiếm một file nào đó thì yêu cầu tìm kiếm được gửi từ điểm nút nguồn tới tất cả điểm nút mạng là hàng xóm của nó. Nếu tài nguyên được tìm thấy thì khi đó điểm nút có tài nguyên chia sẻ sẽ trao đổi với điểm nút yêu cầu dựa vào GUID của điểm nút yêu cầu. Ứng dụng phần mềm điển hình cho mô hình mạng này là: Gnutella 0.4, FreeNet, GnuNet …  Ưu điểm: Đếề tài nghiến cứu khoa học sinh viến 10 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 - Không có điểm duy nhất chịu lỗi khó bị tấn công - Có thể thích nghi với mạng vật lý - Cho phép nặc danh - Dễ xây dựng - Các điểm nút tham gia và rời khỏi mạng một cách tùy mà không ảnh hưởng đến cấu trúc toàn mạng  Nhược điểm: - Tốn tài nguyên băng thông - Tìm kiếm phức tạp - Các điểm nút có khả năng khác nhau (sức mạnh xử lý CPU, băng thông, không gian lưu trữ…) đều có thể phải chịu tải như nhau. c. Mạng ngang hàng lai ghép Được phát triển để khắc phục nhược điểm của các mô hình mạng ngang hàng trước đó. Mô hình mạng ngang hàng lai bao gồm: các siêu điểm nút, các điểm nút thông thường (client). Trong các siêu điểm nút tạo thành một mạng không có cấu trúc, và mỗi siêu điểm nút kết nối đến nhiều điểm nút thông thường, mỗi siêu điểm nút quản lý vùng của nó, vai trò siêu điểm nút giống như một máy chủ trong mô hình mạng ngang hàng tập trung. Có một máy chủ trung tâm để lưu trữ thông tin của các máy trạm và trả lời các truy vấn thông tin này. Các máy trạm có vai trò lưu trữ thông tin, tài nguyên được chia sẻ, cung cấp các thông tin về chia sẻ tài nguyên của nó cho máy chủ.Sử dụng các trạm định tuyến để xác định địa chỉ IP của các máy trạm Ứng dụng điển hình cho mô hình này: Gnutella 0.6, Kazaa/FastTrack. Ngoài ra còn có: Edonkey, Emule, OpenNap, JXTA, Skype….  Ưu điểm: - Không có điểm duy nhất chịu lỗi vì có nhiều siêu điểm nút - Cho phép nặc danh - Phù hợp với các nhóm lợi ích đặc biệt - Khả năng mở rộng quy mô tốt - Hiệu quả thỏa mãn các truy vấn - Hạn chế phát tràn các truy vấn và tránh được hiện tượng nút cổ chai.  Nhược điểm: - Phân chịu tải không cân bằng: các siêu điểm nút chịu tải cao hơn Đếề tài nghiến cứu khoa học sinh viến 11 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 Hình 1.3: Mạng ngang hàng lai ghép Có hai kiểu mạng lai ghép: mạng lai ghép chỉ số hóa tập trung và mạng lai ghép chỉ số hóa phân tán. Hình 1.4: Mạng lai ghép với chỉ số hóa tập trung Trong mạng lai ghép chỉ số hoá tập trung có một máy chủ trung tâm bảo trì các chỉ số của dữ liệu hoặc tài nguyên hiện tại đang được chia sẻ bởi các máy khách tích cực, mỗi máy khách giữ gìn một kết nối tới máy chủ trung tâm để gửi các yêu cầu. Hệ thống này với một server trung tâm đơn giản nhưng xử lí nhanh, có thể tìm kiếm phát hiện thông tin hiệu quả đảm bảo trên toàn bộ hệ thống. Tuy vậy khả năng mở rộng không cao mô hình này rất dễ bị lỗi và sụp đổ khi máy chủ trung tâm bị lỗi hoặc bị tấn công, kích thước cơ sở dữ liệu và khả năng đáp ứng yêu cầu của nó là có giới hạn. Kiến trúc này được sử dụng trong mạng Napster. Trong hệ thống mạng lai ghép với chỉ số phân tán, tồn tại một số siêu node lưu chỉ mục thông tin về các peer cục bộ. Truy vấn thông tin được gửi tới siêu node, nó là proxy cho các peer cục bộ. Do đó truy vấn thông tin nhanh hơn và lưu lượng trao đổi thông tin giữa các node ít hơn so với hệ thống P2P thuần nhất. So với hệ thống chỉ số tập trung nó có ưu điểm là giảm tải đáng kể cho server tránh lỗi cho toàn hệ thống nhưng phát hiện thông tin chậm hơn. Ví dụ: mạng Kazaa, Morpheus. Đếề tài nghiến cứu khoa học sinh viến 12 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 Hình 1.5: Mạng lai ghép với chỉ số hóa phân tán 1.2.2 Phân loại theo cấu trúc liên kết Dựa vào cấu trúc liên kết giữa các mạng ta có thể phân loại mạng ngang hàng thành 2 loại: có cấu trúc và không có cấu trúc a. Mạng ngang hàng không cấu trúc Một mạng ngang hàng không cấu trúc khi các liên kết giữa các nút mạng trong mạng phủ được thiết lập ngẫu nhiên. Những mạng như thế này dễ dàng được xây dựng vì một máy mới khi muốn tham gia mạng có thể lấy các liên kết có sẵn của máy khác đang ở trong mạng và sau đó dần dần tự bản thân nó sẽ thêm vào các liên kết mới của riêng mình. Một nhược điểm của mô hình hệ thống này là do không định hướng, một yêu cầu tìm kiếm thường được chuyển cho một số lượng lớn máy trong mạng làm tiêu tốn một lượng lớn băng thông của mạng, dẫn đến hiệu quả tìm kiếm chung của mạng thấp. Hầu hết các mạng ngang hàng không cấu trúc phổ biến như Napster, Gnutella, Fasttrack và eDonkey2000. b. Mạng ngang hàng có cấu trúc Khắc phục nhược điểm của mạng ngang hàng không cấu trúc bằng cách sử dụng hệ thống DHT (Distributed Hash Table: bảng băm phân tán). Với cấu trúc này, khi một máy tính cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Một số ứng dụng cho mạng này như: Chord, CAN, Kademlia, Pastry và Tapestry. Hash Table (bảng băm) là một cấu trúc dữ liệu ánh xạ giữa key (khóa) và value (giá trị) 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, DHT cung cấp ánh xạ từ key đến value. Đếề tài nghiến cứu khoa học sinh viến 13 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 Hình 1.6: Chức năng chính của DHT 1.2.3 Phân loại theo cơ chế tìm kiếm Cơ chế định vị thông tin trong hệ thống là đặc điểm căn bản trong hệ thống P2P. Cơ chế tìm kiếm trong mạng ngang hàng được phát triển từ thế hệ thứ nhất với cấu trúc danh mục tập trung tới thế hệ thứ hai với cơ chế yêu cầu liên tục và thế hệ thứ ba dựa vào bảng băm phân tán. a. Cơ chế danh mục tập trung Hình 1.7: Cơ chế danh mục tập trung Cơ chế này được sử dụng trong mạng lai ghép, các máy khách kết nối tới máy chủ chứa trung tâm thư mục, là nơi lưu trữ tất cả các thông tin về vị trí và cách sử dụng tài nguyên. Dựa trên yêu cầu từ máy khách trung tâm chỉ số sẽ đưa yêu cầu tới máy khách tốt nhất mà có thư mục phù hợp với yêu cầu. Máy khách tốt nhất có thể là rẻ nhất, nhanh nhất, gần nhất, hoặc sẵn sàng nhất, phụ thuộc vào người sử dụng cần. Sau đó dữ liệu sẽ được trực tiếp trao đổi giữa hai máy khách. Mạng Napster sử dụng phương pháp này, một máy chủ trung tâm sẽ giữ gìn chỉ số của dữ liệu với các trường tiêu đề của tất cả các file trên mạng, một bảng các thông tin đăng kí kết nối của người dùng như địa chỉ IP, tốc độ kết nối…, một bảng danh sách các file mà người sử dụng giữ và chia sẻ trong mạng. Khi bắt đầu, máy khách sẽ tiếp xúc với máy chủ trung tâm và đưa ra một danh sách với các Đếề tài nghiến cứu khoa học sinh viến 14 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 file mà nó giữ. Khi máy chủ thu được một yêu cầu từ người dùng. Nó sẽ tìm kiếm cho chỉ số phù hợp file cần tìm, trả lại danh sách những người dùng đang giữ file phù hợp. Người dùng sẽ thiết lập một kết nối trực tiếp tới máy đang giữ file và lấy nó về. Mô hình này có nhược điểm là khả năng mở rộng không cao, dễ bị lỗi toàn hệ thống. b. Cơ chế yêu cầu liên tục Hình 1.8: Cơ chế yêu cầu liên tục Đây là mô hình mạng ngang hàng hoàn toàn trong đó mỗi điểm (peer) không lưu giữ bất kỳ trung tâm thư mục nào và mỗi điểm sẽ công bố thông tin về nội dung chia sẻ trong mạng ngang hàng. Vì vậy không một điểm đơn nào biết về tất cả các tài nguyên, một điểm khi cần tìm kiếm tài nguyên nó sẽ gửi yêu cầu tới tất cả các điểm đang kết nối với nó, cứ như thế yêu cầu được gửi đi cho tới khi được trả lời hoặc khi số bước gửi yêu cầu là cực đại. Khi số điểm trên mạng lớn thì lưu lượng trên mạng sẽ rất lớn, đây là nhược điểm của mô hình tìm kiếm này. Hệ thống này chỉ làm việc hiệu quả với mạng nhỏ như Gnutella. Mô hình cải tiến đưa vào khái niệm super peer giảm tiêu thụ băng thông và cho khả năng mở rộng cao hơn ví dụ Kazaa. c. Cơ chế bảng băm phân tán Đây là là mô hình tiên tiến nhất và được sử dụng trong mạng ngang hàng hoàn toàn. Mô hình định tuyến thêm vào cấu trúc thông tin về những tài nguyên được lưu trữ sử dụng bảng băm phân tán. Giao thức này cung cấp một ánh xạ giữa số nhận dạng của tài nguyên (ID) và vị trí lưu trữ. Trong cấu trúc của bảng định tuyến một truy vấn có thể được định tuyến hiệu quả tới node có tài nguyên mong muốn. Giao thức này làm giảm bớt số bước mà node trong mạng cần thiết để định vị tài nguyên tìm kiếm. Mỗi node được gắn một giá trị ID và nó biết một vài các node khác. Khi một node muốn chia sẻ tài liệu, tên và nội dung của tài liệu đó được băm tạo ra một ID gắn với tài liệu đó. Tài liệu được định tuyến tới node có ID gần với ID của tài liệu nhất. Khi một node muốn lấy một tài liệu nào đó nó gửi yêu cầu chứa ID của tài liệu. Yêu cầu được chuyển tới node có ID gần với ID của tài liệu nhất, sau đó tài liệu được chuyển tới node yêu cầu. Các mạng ngang hàng thế hệ mới đều sử dụng phương pháp tìm kiếm này như: Freenet, Chord, Kademlia… Đếề tài nghiến cứu khoa học sinh viến 15 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 Hình 1.9: Cơ chế bảng băm phân tán Mô hình này được chứng minh là có hiệu quả với mạng có số peer lớn. Tuy vậy nó vẫn tồn tại các nhược điểm đó là khó cài đặt tính năng tìm kiếm do phải biết trước ID của file trước khi gửi yêu cầu. Băm tên file hoặc nội dung khác nhau tạo ra ID khác dẫn đến không tìm thấy file. Các node khi chia vào các nhóm khác nhau không có sự liên hệ dẫn đến vấn đề ‘’islanding’’(cô lập). 1.3 Ứng dụng của mạng ngang hàng Có thể chia ứng dụng của P2P thành 4 loại: 1.3.1 Chia sẻ tài liệu Lưu trữ và trao đổi tài nguyên là một trong những mặt thành công nhất của công nghệ mạng ngang hàng. Ứng dụng chia sẻ tài liệu tập trung vào sự lưu trữ thông tin và khôi phục thông tin từ nhiều máy khác trên mạng. Một trong những ví dụ tốt nhất của mạng ngang hàng là Napster, nó trở thành hệ thống chia sẻ ca nhạc nổi tiếng . 1.3.2 Phân tán tính toán Ứng dụng này sử dụng tài nguyên từ một số các máy tính trên mạng (năng lực xử lí của các máy tính rỗi trên mạng). Ý tưởng đằng sau ứng dụng này là bất kỳ máy tính nào kết nối vào mạng có thể được sử dụng để giải quyết vấn đề của những máy khác đang yêu cầu tính toán thêm. Ví dụ dự án SETI (Search for Extraterrestrial Intelligence: Tìm kiếm nền văn minh ngoài trái đất). 1.3.3 Hợp tác Mục đích của ứng dụng hợp tác trong mạng ngang hàng là cho phép cộng tác ở mức ứng dụng giữa các người dùng ví dụ như chat, instant messaging, online game đến các ứng dụng chia sẻ có thể sử dụng trong kinh doanh, giáo dục … 1.3.4 Lớp nền P2P platform cung cấp hạ tầng cho các ứng dụng phân tán sử dụng cơ chế P2P. Các phần tử P2P sử dụng ngữ cảnh để phát hiện, kết nối, bảo mật, tập hợp tài nguyên…Ví dụ JXTA là một P2P platform cung cấp một nền cơ bản cho việc lập trình và xử lí trên mạng. Đếề tài nghiến cứu khoa học sinh viến 16 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 1.4 Các vấn đề với mạng ngang hàng Hệ thống P2P có một số ưu điểm hơn so với hệ thống client-server truyền thống như khả năng mở rộng, khả năng chịu lỗi, hiệu năng cao. Tuy nhiên còn nhiều vấn đề mà các hệ thống P2P hiện nay đang phải giải quyết: 1.4.1 Tính bảo mật Bảo mật cho hệ thống P2P khó khăn hơn các hệ thống khác, các node trong hệ thống là động, phân tán khắp nơi, các node không chứng thực lẫn nhau. Các cơ chế bảo mật truyền thống như tường lửa, xác thực… không thể bảo vệ hệ thống P2P ngược lại có thể ngăn cản quá trình truyền thông trong hệ thống. Bởi vậy những khái niệm bảo mật mới được đặt ra đối với hệ thống P2P. 1.4.2 Độ tin cậy Một hệ thống đáng tin cậy là hệ thống có thể phục hồi khi lỗi xảy ra. Những nhân tố cần phải quan tâm khi tính toán cho sự tin cậy là: nhân bản dữ liệu, phát hiện node lỗi, phục hồi… đảm bảo cho thông tin định vị tránh lỗi đơn và khả năng sẵn sàng nhiều đường dẫn tới dữ liệu. Nhân bản dữ liệu tăng sự tin cậy bằng việc tăng sự dư thừa và định vị. Có hai chiến lược cho nhân bản: nhân bản nguyên gốc và nhân bản đường dẫn. Trong nhân bản nguyên gốc, khi tìm kiếm thành công dữ liệu được lưu trữ chỉ tại node yêu cầu. Trong nhân bản đường dẫn khi tìm kiếm thành công dữ liệu được lưu trữ tại tất cả các node dọc theo đường dẫn từ node yêu cầu tới node cung cấp. 1.4.3 Độ linh động Chính là khả năng tự chủ của các node trong việc gia nhập hoặc rời bỏ hệ thống. Để giải quyết vấn đề quy mô lớn, phân tán và linh độ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. 1.4.4 Cân bằng tải Phân phối dữ liệu để lưu trữ hoặc tính toán trên các node là vấn đề rất quan trọng trong các hệ thống mạng ngang hàng, một giải pháp đặc biệt cho sự phân phối này là Bảng băm phân tán (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. 1.5 Một số ví dụ về mạng ngang hàng 1.5.1 Mạng Edonkey Hay còn gọi là mạng Edonkey2000 là một chương trình chia sẻ tệp trên mạng ngang hàng, được phát triển bởi MetaMachine, sử dụng giao thức truyền tệp đa nguồn (tiếng Anh: Multisource File Transfer Protocol). Chương trình eDonkey hỗ trợ cả hai mạng eDonkey và mạng Overnet. Đếề tài nghiến cứu khoa học sinh viến 17 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 Người dùng eDonkey2000 chủ yếu chia sẻ những tệp rất lớn, hàng trăm mêgabyte, như đĩa CD, phim, trò chơi, và phần mềm. Không như các phần mềm chia sẻ tệp ngang hàng khác, tệp chia sẻ trong mạng eDonkey được cung cấp dưới dạng một liên kết ed2k, chương trình eDonkey2000 sẽ tự khởi động và tải tệp khi liên kết ed2k được kích hoạt. Hình 1.10: Mô hình mạng Edonkey Edonkey là mạng ngang hàng phân quyền, tài nguyên không được lưu trữ ở một máy chủ trung tâm mà được chia sẻ trực tiếp giữa những người sử dụng. Phần mềm của mạng Edonkey cài đặt trên máy khách kết nối vào mạng để chia sẻ tài nguyên. Các máy chủ đóng vai trò như những hub truyền thông cho các khách hàng, cho phép người sử dụng định vị tài liệu trong mạng. Bằng việc chạy phần mềm máy chủ Edonkey trên một máy tính kết nối vào Internet, bất kỳ người sử dụng nào cũng có thể kết nối tới máy chủ để vào mạng. Số máy chủ và địa chỉ của nó thường xuyên thay đổi, chương trình chạy trên các máy khách sẽ thường xuyên cập nhật danh sách các server. 1.5.2 Mạng Gnutella Đây là mô hình mạng ngang hàng hoàn toàn trong chia sẻ tài nguyên và cả trong giao thức, ở đó các máy kết nối vào mạng bằng cách kết nối với những máy đã tồn tại trong mạng. Hình thức này hình thành ứng dụng trên mạng vật lý. Tất cả các node trong mạng có thể quản lý tài nguyên và khôi phục tài nguyên từ node khác. Để tạo điều kiện cho việc chia sẻ tài liệu một thông báo được gửi giữa các node, truy vấn về tài liệu cần tìm được phát quảng bá toàn mạng và được lặp lại định tuyến ngược trở lại node đầu tiên đã đưa ra yêu cầu trong mạng. Thông báo tìm kiếm sẽ được sử dụng để tìm kiếm các node. Đếề tài nghiến cứu khoa học sinh viến 18 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 Hình 1.11: Mô hình mạng Gnutella 1.5.3 Mạng Napster Đây là mạng chia sẻ tài nguyên phân tán với máy chủ cơ sở, máy chủ không giống như truyền thống, trong nó chỉ chứa danh sách các thư mục. Các máy khách sẽ tải về và quản lý tài nguyên, trong khi đó máy chủ sẽ giữ chỉ số của tài liệu điều khiển yêu cầu tìm kiếm của máy khách. Một máy khách gửi yêu cầu tìm kiếm của nó tới máy chủ, máy chủ sẽ tìm kiếm trong các chỉ mục nó lưu trữ và gửi danh sách phù hợp trở lại cho máy khách. Hình 1.12: Mô hình mạng Napster Máy khách sẽ sử dụng danh sách đó để kết nối tới máy khách có chứa tài nguyên và tải về tài nguyên từ những máy khách đó. Khi máy khách kết nối với máy chủ lần đầu tiên, chúng sẽ gửi danh sách các tài nguyên mà nó đang muốn chia sẻ lên cho máy chủ, những tài nguyên này sẽ được thêm vào danh sách chỉ mục của máy chủ. Napster là hệ thống chia sẻ tài nguyên ngang hàng tập trung, có nghĩa là Napster cung cấp một máy chủ cho các máy khách để tổ chức và cho phép truy nhập tới bất kỳ hoặc tất cả các file tồn tại trên các máy khách. Đếề tài nghiến cứu khoa học sinh viến 19 Cải thiện hiệu năng giao thức định tuyếến trong mạng ngang hàng 12/2012 CHƯƠNG II: CÁC GIAO THỨC ĐỊNH TUYỀẾN DHT-P2P 2.1 Khái niệm về Distributed Hash Table (DHT) Bảng hàm băm phân tán (Distributed Hash Table) là một lớp của hệ thống phân tán cung cấp dịch vụ tra cứu tương tự như bảng hàm băm (hash table). Một bảng băm là một cấu trúc dữ liệu được ánh xạ giữa khóa (key) và giá trị (value). Tức là tương ứng với một khóa sẽ có một giá trị. Để thực hiện việc ánh xạ, hash table sử dụng hàm băm (hash function) tính toán vị trí lưu giá trị dựa trên khóa. Bảng hàm băm phân tán hiểu đơn giản chính là một bảng băm được cài đặt như một hệ thống phân tán, các tài nguyên được ràng buộc với các khóa (ví dụ được tạo ra bằng cách băm các tên hoặc nội dung file) và việc duy trì sự ánh xạ từ khóa đến tài nguyên sẽ được phân tán đều trong mạng. Mỗi node trong hệ thống sẽ có trách nhiệm lưu giữ một dải các khóa nào đó. Khi muốn tìm kiếm một tài nguyên (giá trị) nào đó, ta sử dụng một toán tử trong DHT đó là tìm kiếm – lookup(key), nó sẽ trả lại nhận dạng của node lưu trữ object ứng với key đó. Toán tử này cho phép các node đưa và lấy các tài nguyên trên cơ sở khóa của chúng. Hình 2.1: Mô tả quá trình tạo key của DHT DHT có các ưu điểm khác biệt so với dịch vụ hướng Client – Sever truyền thống:  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.  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 trong mạng lớn.  Tải được cân bằng giữa các peer trong mạng. Đếề tài nghiến cứu khoa học sinh viến 20