Tài liệu Tìm kiếm thông tin theo các giá trị thuộc tính trên mạng ngang hàng có cấu trúc

Lời cam đoan Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của riêng cá nhân tôi, không sao chép lại của người khác. Trong toàn bộ nội dung luận văn, những điều được trình bày hoặc là của cá nhân tôi, hoặc do tôi tổng hợp được từ các nguồn tài liệu khác nhau. Tất cả các tài liệu được tham khảo điều có xuất xứ rõ ràng, được trích dẫn hợp pháp và được liệt kê đầy đủ trong mục tài liệu tham khảo của luận văn. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, ngày 03 tháng 11 năm 2008 Phạm Thị Huế Lời cảm ơn Tôi xin bày tỏ lời cảm ơn chân thành tới các thầy cô giáo trong khoa Công nghệ thông tin – Đại học Công nghệ - ĐHQG Hà Nội, đặc biệt là các thầy cô giáo trong bộ môn Mạng và truyền dữ liệu, đã tạo điều kiện thuận lợi và giúp đỡ tôi trong thời gian tôi học tập. Tôi xin bày tỏ lòng biết ơn chân thành, lời cảm ơn sâu sắc đối với thầy giáo TS. Nguyễn Hoài Sơn đã tận tình hướng dẫn, định hướng cho tôi giải quyết các vấn đề trong luận văn. Tôi cũng xin bày tỏ lời cảm ơn đối với cha mẹ, gia đình, các đồng nghiệp và bạn học viên lớp Cao học K12T3 đã động viên, giúp đỡ, góp ý cho tôi rất nhiều trong quá trình hoàn thành luận văn. Hà Nội, ngày 3 tháng 11 năm 2008 Phạm Thị Huế 1 MỤC LỤC Trang phụ bìa Lời cam đoan Lời cảm ơn Mục lục ............................................................................................................... 1 Danh mục các thuật ngữ và các từ viết tắt ...................................................... 3 Danh mục bảng biểu .......................................................................................... 4 Danh mục hình vẽ .............................................................................................. 5 MỞ ĐẦU............................................................................................................. 6 CHƢƠNG 1 TỔNG QUAN VỀ MẠNG NGANG HÀNG ................................... 10 1.1 Khái niệm mạng ngang hàng ............................................................... 10 1.2 1.3 Ưu, nhược điểm của mạng ngang hàng ............................................... 15 Kết luận................................................................................................ 16 CHƢƠNG 2 MẠNG NGANG HÀNG CÓ CẤU TRÚC ...................................... 18 2.1 Mạng ngang hàng có cấu trúc dựa trên DHT ...................................... 18 2.1.1 Khái niệm mạng ngang hàng có cấu trúc ...................................... 18 2.1.2 Các tính chất của mạng DHT. ....................................................... 19 2.2 Mạng ngang hàng có cấu trúc CHORD ............................................... 20 2.2.1 Mô hình mạng Chord ..................................................................... 20 2.2.2 Ánh xạ khóa vào một node trong Chord........................................ 21 2.2.3 Tìm kiếm trong mạng Chord ......................................................... 22 2.2.4 Tham gia và ổn định mạng ............................................................ 22 2.3 Kết luận................................................................................................ 23 CHƢƠNG 3 MỘT SỐ GIẢI PHÁP PHÂN PHỐI VÀ TÌM KIẾM THÔNG TIN TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC. .................................... 24 3.1 INS/Twine ........................................................................................... 24 3.1.1 Giải pháp ........................................................................................ 24 3.1.2 Nhận xét ......................................................................................... 28 3.2 CDS ..................................................................................................... 29 3.2.1 Giải pháp ........................................................................................ 29 3.2.2 Nhận xét ......................................................................................... 34 3.3 Data Indexing ...................................................................................... 35 3.3.1 Giải pháp ........................................................................................ 35 3.3.2 Nhận xét ......................................................................................... 41 3.4 Kết luận................................................................................................ 41 2 CHƢƠNG 4 GIẢI PHÁP TÌM KIẾM THÔNG TIN THEO CÁC THUỘC TÍNH/GIÁ TRỊ TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC ........ 42 4.1 Ý tưởng ................................................................................................ 42 4.2 Mô hình giải pháp SMAV ................................................................... 44 4.2.1 Khái quát ........................................................................................ 44 4.2.2 Ánh xạ tên miền-khóa và phân bổ nội dung .................................. 45 4.2.3 Truy vấn thông tin ......................................................................... 51 4.2.4 Quản lý khi trạng thái mạng thay đổi ............................................ 54 CHƢƠNG 5 ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI PHÁP “TÌM KIẾM THÔNG TIN THEO CÁC THUỘC TÍNH/GIÁ TRỊ TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC” ............................................................................. 55 5.1 Đánh giá định tính ............................................................................... 55 Đánh giá dựa trên mô phỏng ............................................................... 56 5.2.1 Các tham số mô phỏng .................................................................. 56 5.2.2 Kết quả ........................................................................................... 58 5.3 Mở rộng hệ thống cho phù hợp với các yếu tố thực tế ........................ 64 5.2 CHƢƠNG 6 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ....................................... 66 3 DANH MỤC CÁC THUẬT NGỮ VÀ CÁC TỪ VIẾT TẮT AV (Attribute/Value) Based -DHT Bibliographic database Broadcast CAN (ContentAddressable Network) CDS (Content discovery System) Thuộc tính/giá trị Dựa trên bảng băm phân tán Chord Một giao thức mạng ngang hàng dựa trên DHT thực hiện việc phân bổ và quản lý khóa theo dạng vòng (ring) Máy khách/ Máy chủ Client/Server DHT (Distributed Hash Table ) Entry Identify JXTA Key LBM (Load Balancing Matrix) Load-balancing Node Node Rendezvous Points P2P (Peer to Peer network) Cây thư mục Gửi phát tràn (quảng bá) Một giao thức mạng ngang hàng dựa trên DHT thực hiện việc phân bổ và quản lý khóa trên không gian n chiều Hệ thống phát hiện nội dung Bảng băm phân tán Một bản ghi trong bảng dùng để lưu thông tin về các đặc tả tài nguyên tại mỗi node Định danh Một cơ sở hạ tầng mạng ngang hàng dựa trên mã nguồn mở Khóa Ma trận cân bằng tải Cân bằng tải Thực thể có khả năng thực hiện một công việc hữu ích nào đó và trao đổi kết quả với các thực thể khác qua mạng một cách trực tiếp hoặc gián tiếp Điểm nút môi giới Mạng ngang hàng Partial query Truy vấn từng phần Partition Query Replication Phần, vùng Truy vấn Bản sao (thứ bản) 4 Trade-off Sự thỏa hiệp hay việc cân bằng giữa các yếu tố khác nhau để đạt được 1 sự kết hợp tốt nhất. XML (Extensible Markup Language) Ngôn ngữ đánh dấu mở rộng 5 DANH MỤC BẢNG BIỂU Bảng 2-1 Bảng định nghĩa các trường trong Finger Table ............................................21 Bảng 4-1 Bảng ánh xạ khóa phân bổ - nội dung thông tin ............................................49 Bảng 4-2 Bảng ánh xạ khóa thứ cấp ..............................................................................50 Bảng 4-3 Bảng ánh xạ khóa không phổ biến.................................................................50 Bảng 4-4 Bảng ánh xạ khóa đặc biệt .............................................................................50 6 DANH MỤC HÌNH VẼ Hình 1.1-1 Mô hình client/Server .................................................................................10 Hình 1.1-2 Mô hình P2P ...............................................................................................11 Hình 1.1-3 Mô hình mạng Napster ...............................................................................12 Hình 1.1-4 Mô hình xử lý truy vấn trên mạng Gnutella ...............................................12 Hình 2.2-1 Một mạng Chord với 3 node 0, 1, 3 và các bảng Finger Table ứng với mỗi node. N = 3 bit nên Finger Table có 3 entry..........................................................21 Hình 2.2-2 Lưu giữ key trong mạng Chord: node 0 lưu key 6, node 1 lưu key 1 và node 3 lưu key 2. ...................................................................................................22 Hình 3.1-1 Một ví dụ về đặc tả tài nguyên và cây AVTree .........................................24 Hình 3.1-2 Mô hình hoạt động của hệ thống INS/Twine. ............................................25 Hình Hình Hình Hình 3.1-3 Trích rút 1 AVTree thành các strand .........................................................26 3.1-4 Việc quản lý trạng thái trong hệ thông INS/Twine. ...................................28 3.2-1 Kiến trúc 1 node sử dụng CDS ..................................................................29 3.2-2 Ví dụ về việc đăng ký tên miền và xử lý truy vấn với 1 tập các điểm môi giới RPs. ................................................................................................................30 Hình 3.2-3 Ma trận cân bằng tải cho cặp thuộc tính aivi ..............................................31 Hình 3.3-1 Ví dụ về đặc tả file .....................................................................................36 Hình 3.3-2 Ví dụ về cấu trúc các câu truy vấn. ............................................................37 Hình 3.3-3 Đồ thị biểu diễn các câu truy vấn được đưa ra trong hình 3.3-2................37 Hình 3.3-4 Lược đồ chỉ mục cho dữ liệu cây thư mục (bibliographic database) .........38 Hình 3.3-5 Ví dụ về chỉ mục phân tán cho 3 tài liệu được đưa ra trong hình 3.3-1 và lược đồ chỉ mục trong hình 3.3-4 ..........................................................................39 Hình 3.3-6 Việc ánh xạ giữa các câu truy vấn cho hình 3.3-5 .....................................39 4.2-1 Lược đồ phân bổ tên nội dung thông tin theo giải thuật SMAV ...............46 4.2-2 Ánh xạ khóa thứ cấp ..................................................................................49 4.2-3 Lược đồ truy vấn thông tin theo giải thuật SMAV ....................................52 5.2-1-A: Tỷ lệ phần trăm tần số xuất hiện 1 thuộc tính/giá trị ............................59 5.2-2-B Tần số xuất hiện các AV trên các node ..................................................59 5.2-3 So sánh tải nội dung giữa 2 phương pháp phân bổ tên nội dung: Phân phối bình thường dựa trên DHT-Chord và phân phối theo SMAV ...............................60 Hình 5.2-4 So sánh tải truy vấn giữa 2 phương pháp phân bổ tên nội dung: Phân phối Hình Hình Hình Hình Hình Hình bình thường dựa trên DHT-Chord và phân phối theo SMAV. ..............................61 Hình 5.2-5 Số ánh xạ sinh ra bởi mỗi tên nội dung khi sử dụng giải thuật SMAV .....61 Hình 5.2-6 Thời gian truy vấn ......................................................................................63 7 MỞ ĐẦU Công nghệ mạng ngang hàng (peer-to-peer network) đã phát triển nhanh chóng trên mạng Internet trong thời gian gần đây với sự xuất hiện của hàng loạt các ứng chia xẻ file ngang hàng như Napster, Gnutella, Freenet, BitTorrent, Edonkey,… Qua các ứng dụng nói trên, việc chia sẻ và tìm kiếm các tài nguyên mạng trở lên dễ dàng và nhanh chóng hơn bao giờ hết, ngoài ra, người sử dụng có thể chia sẻ file trực tiếp cho nhau mà không cần thông qua bất cứ máy chủ dịch vụ nào. Sở dĩ mô hình mạng P2P phát triển như vậy là vì mô hình này rất phù hợp với tính phân tán của dữ liệu, đồng thời nó đảm bảo quyền quản lý dữ liệu của người dùng nên khuyến khích được việc chia sẻ dữ liệu, làm tăng nguồn tài nguyên trên mạng. Mô hình P2P cũng được sử dụng để xử lý các bài toán phức tạp do tận dụng được khả năng tính toán phân tán và tích hợp dữ liệu từ các peer tham gia mạng. Trong mô hình P2P, mỗi peer vừa có thể đóng vai trò là Client, vừa có thể đóng vai trò là Server. Tổng sức mạnh xử lý của các peer này có khi lớn hơn nhiều lần khả năng xử lý của 1 Server lớn. Như vậy, mô hình P2P không chỉ làm tăng lượng tài nguyên mạng, mà còn làm tăng sức mạnh xử lý đáp ứng yêu cầu dịch vụ, nâng cao tính sẵn sàng phục vụ của mạng. Tuy nhiên, trong thời kỳ đầu mới phát triển, việc tìm kiếm trong mạng ngang hàng thường được thực hiện theo kiểu phát tràn thông báo, gây tốn kém băng thông mạng. Các ứng dụng sau này đã từng bước cải tiến giao thức định tuyến thông báo, làm mạng hoạt động hiệu quả hơn, nhưng vẫn chưa đảm bảo việc tìm kiếm thông tin sẽ thành công. Mạng ngang hàng có cấu trúc sử dụng giải thuật Bảng băm phân tán (Distributed Hash Table – DHT) khắc phục nhược điểm trên bằng cách tổ chức các node mạng theo một cấu trúc không gian khóa nhất định như mạch vòng (giải thuật Chord[7]) hay không gian n-chiều (giải thuật CAN[10]) và định tuyến thông báo dựa trên cấu trúc này. Nội dung thông tin được gắn với một khóa k là giá trị băm của một đặc tả đặc trưng nào đó của nội dung thông tin (gọi là tên nội dung) và sẽ được phân bổ đến node phụ trách khóa k. Mỗi node trong mạng sẽ chịu trách nhiệm quản lý 1 tập các khóa trong không gian khóa, và lưu giữ thông tin về 1 số các node khác trong mạng. Việc tìm kiếm thông tin qua câu truy vấn q được thực hiện bằng cách băm q để được khóa kq, rồi chuyển q đến node quản lý khóa kq, node đó sẽ thực hiện việc tìm kiếm địa phương và trả về kết quả cho câu truy vấn. Bằng phương pháp này, giải thuật DHT cho phép xây dựng một mạng ngang hàng với khả năng mở rộng cao, định tuyến hiệu quả các gói tin thông báo tới đích và kháng lỗi tốt. 8 Tuy nhiên, giải thuật DHT chỉ hỗ trợ tìm kiếm chính xác, tức là tìm kiếm nội dung thông tin gắn với một khóa k nào đó. Trong thực tế, không phải lúc nào người tìm kiếm cũng biết chính xác về các đặc tả của thông tin mình cần tìm, do đó, rất nhiều giải pháp hỗ trợ tìm kiếm nâng cao đã và đang được rất nhiều tổ chức, cá nhân trên thế giới nghiên cứu và ứng dụng. Một số giải pháp điển hình như tìm kiếm theo khoảng, tìm kiếm theo các thuộc tính/giá trị, tìm kiếm gần đúng, … Trong số các kiểu tìm kiếm nâng cao trên P2P, tìm kiếm theo các thuộc tính/giá trị gần đây đang được quan tâm nghiên cứu bởi sự phù hợp của việc biểu diễn đặc tả thông tin thông qua các cặp thuộc tính/giá trị. Qua phương pháp này, 1 tên nội dung không còn được băm thành 1 giá trị khóa duy nhất nữa, mà sẽ được ánh xạ vào 1 tập các khóa tương ứng với giá trị băm của các cặp thuộc tính/giá trị có mặt trong tên nội dung. Sau đó, tập khóa này sẽ được chuyển đến 1 tập các node sẽ quản lý chúng dựa trên giao thức DHT nào đó. Bằng cách này, 1 nội dung thông tin sẽ được lưu trữ ở nhiều node hơn, làm tăng tính sẵn sàng sử dụng và khắc phục lỗi của mạng khi có sự vào ra của các node. Đồng thời, thông tin được tìm kiếm cũng dễ dàng hơn, do chỉ cần biết 1 phần đặc tả của thông tin (ứng với 1 cặp thuộc tính/giá trị trong tên nội dung thông tin). Có nhiều giải pháp tìm kiếm theo các thuộc tính/giá trị khác nhau được đưa ra, chủ yếu nhấn mạnh vào việc sẽ phân bổ các thuộc tính/giá trị đến các node, và tiến hành xử lý truy vấn như thế nào. Có giải pháp thì đưa ra cách xây dựng cây AVTree từ các cặp thuộc tính/giá trị (trong INS/Twine), rồi tính khóa phân bổ bằng cách băm các nhánh của cây này. Có giải pháp thì đưa ra cách xây dựng các Xpath từ các đặc tả kiểu XML của tên nội dung, rồi dùng nó để tạo cây truy vấn,…Mỗi giải pháp đều có điểm mạnh riêng, song vẫn còn nhiều hạn chế cần khắc phục để mạng cân bằng hơn về tải và tìm kiếm hiệu quả hơn. Việc nghiên cứu các giải pháp này để từ đó, tìm ra được 1 giải pháp tìm kiếm tốt hơn trên P2P có cấu trúc là việc làm hết sức cần thiết để phát triển các ứng dụng P2P phù hợp với thực tế. Luận văn Tìm kiếm thông tin theo các giá trị thuộc tính trên mạng ngang hàng có cấu trúc đi vào nghiên cứu và đánh giá các giải pháp tìm kiếm theo các thuộc tính/giá trị đã có, từ đó tìm cách cải tiến để đưa ra 1 giải pháp mới. Giải pháp mới được triển khai trong luận văn này không nằm ngoài xu hướng nghiên cứu chung, đồng thời cũng được đánh giá qua chương trình mô phỏng và cho kết quả khá tốt. Về bố cục, nội dung của luận văn bao gồm 6 chương: Chương 1: Giới thiệu tổng quan về mạng ngang hàng, những khái niệm cơ bản cũng như sơ lược về lịch sử phát triển của mạng ngang hàng. 9 Chương 2: Trình bày sâu thêm về 1 nhánh của mạng ngang hàng: mạng ngang hàng có cấu trúc. Đồng thời giới thiệu chi tiết về giao thức Chord, giao thức sẽ được sử dụng để triển khai mạng phủ DHT khi xây dựng chương trình mô phỏng. Chương 3: Trình bày các nghiên cứu liên quan, cụ thể là 1 số giải pháp phân bổ và tìm kiếm thông tin theo các thuộc tính/giá trị trên mạng ngang hàng có cấu trúc tiêu biểu. Chương 4: Trình bày chi tiết về giải pháp “Tìm kiếm thông tin theo các thuộc tính/giá trị trên mạng ngang hàng có cấu trúc” Chương 5: Đánh giá hiệu quả của giải pháp “Tìm kiếm thông tin theo các thuộc tính/giá trị trên mạng ngang hàng có cấu trúc” trên lý thuyết và qua chương trình mô phỏng. Chương 6: Cuối cùng là phần kết luận nêu tóm tắt các vấn đề đã trình bày trong luận văn, rút ra những điểm đã đạt được cũng như chưa đạt được, đồng thời đưa ra một số hướng nghiên cứu, phát triển tiếp theo. Ngoài ra, luận văn còn có thêm các danh mục các thuật ngữ, các từ viết tắt, danh mục bảng biểu, hình vẽ và danh mục các tài liệu tham khảo để thuận tiện cho việc tìm hiểu và tra cứu nội dung của luận văn. 10 CHƢƠNG 1 TỔNG QUAN VỀ MẠNG NGANG HÀNG Trong chương này, báo cáo luận văn sẽ giới thiệu khái quát về công nghệ mạng ngang hàng: khái niệm mạng ngang hàng là gì? Mô hình ra sao? Và những ưu nhược điểm của mạng ngang hàng. 1.1 Khái niệm mạng ngang hàng Như chúng ta đã biết, hầu như mọi dịch vụ Internet ngày nay đều dựa trên mô hình client/Server (hình 1.1-1). Theo mô hình này thì một máy khách (client) sẽ kết nối với một máy chủ thông qua một giao thức nhất định như WWW, FTP, Telnet, email ... Nói chung, mô hình client/Server có nhiều ưu điểm, một trong số đó là việc mọi xử lý đều nằm trên Server do đó sẽ tránh cho clients những tính toán nặng nề, và do đó các máy Client không cần có cấu hình mạnh Hình 1.1-1: Mô hình client/Server Tuy nhiên, với chế độ hoạt động theo kiểu: Client đóng vai trò thụ động, chỉ yêu cầu dịch vụ từ Server chứ không thể cung cấp dịch vụ cho các client khác, thì chính ưu điểm trên lại trở thành nhược điểm của mô hình này. Với tốc độ phát triển Internet như hiện nay, số lượng client tăng nhanh liên tục gây ra sự quá tải và tắc nghẽn tại các Server. Khi số lượng clients tăng đến một mức độ nào đó mà nhu cầu về tải và băng thông tăng lên tới mức máy chủ không còn đủ khả năng để đáp ứng được dịch vụ cho các máy khách thì Server bị sập và mạng sẽ bị sập theo. Việc tăng số lượng Server để tăng khả năng chịu tải cho các Server là cần thiết. Tuy nhiên, chi phí cho 1 Server thường là rất lớn. Bởi vậy, ý tưởng về một kiến trúc mạng mà ở đó, không cần thêm chi phí cho việc lắp đặt thêm Server, ta vẫn đảm bảo 11 mạng hoạt động tốt bằng cách tận dụng những tài nguyên mạng có sẵn từ chính các máy tham gia mạng, đã dẫn đến sự ra đời của mạng ngang hàng (peer to peer - P2P) . Vậy P2P là gì? Hình 1.1-2: Mô hình P2P Hình 1.1-2 cho ta thấy một cách trực quan mô hình P2P. Có thể nói: Công nghệ P2P là công nghệ mạng cho phép mọi thiết bị nối mạng cung cấp dịch vụ cho nhau, đồng thời mọi loại tài nguyên trên các thiết bị nối mạng đều có thể được chia sẻ cho nhau. Như vậy, trên P2P, không còn có khái niệm Client hay Server nữa. Tất các máy đều có thể yêu cầu dịch vụ, cũng như đáp ứng yêu cầu dịch vụ của các máy khác. Mọi máy tính đều có thể lưu trữ và chia sẻ tài nguyên, cũng như kết nối trực tiếp với nhau. Thực chất kiến trúc mạng P2P không phải là mới. Hoạt động của mạng LAN chính là hoạt động kiểu P2P: các Client trong 1 mạng LAN hoàn toàn có thể chia sẻ và sử dụng tài nguyên của nhau. Những ứng dụng P2P cũng xuất hiện từ lâu, ví dụ như Usenet được xây dựng từ năm 1979 [2]. Tuy nhiên cho tới gần đây, khi có sự xuất hiện của các dịch vụ chia xẻ files như Napster, Gnutella, Bittorent, …, những chương trình tin nhắn tức thời như ICQ, YIM, …, thì P2P mới được nhận ra là một công nghệ quan trọng cho Internet. Ta có thể khái quát về các bước phát triển của P2P qua tổng hợp trong[2,13], theo đó thì P2P đã trải qua 3 thế hệ: Thế hệ 1: Đó là thế hệ phát triển của kiến trúc P2P đơn giản nhằm mục đích chia sẻ file. Hai đại diện cho P2P giai đoạn này là 2 mạng Napster (1999) [2] and Gnutella (1999) chia sẻ file MP3. 12 Hoạt động của Napster khá đơn giản: Người sở hữu file đặt tên cho file là x và chia sẻ file Mọi người thì tìm kiếm x, sau đó copy hoặc down về. Hình 1.1-3: Mô hình mạng Napster Mô hình này là mô hình P2P lai ghép vì vẫn còn tồn tại 1 Server quản lý tập trung các danh sách ánh xạ user-file. Người muốn chia sẻ file thì gửi thông tin user-file lên Server để đăng ký. Người muốn down file thì truy vấn đến Server để tìm thông tin về file mình cần, Server tìm và trả về thông tin user có file đó, sau đó, người muốn down kết nối trực tiếp với user có file để down file về. Hình 1.1-4: Mô hình xử lý truy vấn trên mạng Gnutella 13 Khi 1 node muốn tham gia vào mạng, nó liên hệ với 1 node bootstrap hoặc 1 node nào đó mà địa chỉ nằm trong danh sách địa chỉ được cài đặt sẵn. Sau khi việc kết nối thành công, client sẽ thực hiện tìm kiếm các client đang làm việc. Client cố gắng kết nối tới các node mà nó biết địa chỉ (đã được cài sẵn hoặc thông qua các node khác) cho đến khi nhận được 1 số lượng nhất định các node. Client sẽ chỉ kết nối đến các node này, cache lại những địa chỉ mà nó chưa có trong bộ nhớ nội bộ và bỏ qua những địa chỉ mà nó không kết nối được đến. Hình 1.2-2 mô tả hoạt động tìm kiếm của Gnutella: Khi người dùng tại 1 node muốn tìm kiếm tài nguyên, node sẽ gửi yêu cầu đến mỗi node mà nó đang kết nối đến. Sau đó, mỗi node nhận được yêu cầu lại tiếp tục forward yêu cầu tới các node mà node này biết. Việc forward tiếp diễn cho đến khi gói tin đạt đến số hop được đĩnh nghĩa trước bởi node tìm kiếm ban đầu (ở phiên bản 0.4 số hop lớn nhất là 7).Nếu câu truy vấn tìm được kết quả, node có kết quả sẽ liên lạc với node tìm kiếm. Trong phiên bản ban đầu, thông điệp trả lời được gửi cho node tìm kiếm bằng cách đi ngược lại con đường mà truy vấn đã được truyền đi. Nhưng việc này đã được xem lại và cải tiến trong giao thức hiện nay, node có kết quả sẽ cung cấp kết quả trực tiếp đến node tìm kiếm thông qua giao thức UDP. Vì vậy, mỗi câu truy vấn bao giờ cũng gồm thông tin về địa chỉ IP và cổng của node khác. Nhờ đó mà yêu cầu về băng thông cũng được giảm xuống và tăng khả năng mở rộng của mạng. Khi 1 node ngắt kết nối, nó sẽ lưu lại danh sách các node nó đã kết nối và các tài nguyên chia sẻ để dùng cho lần kết nối tiếp theo. Trong thực tế, phương pháp tìm kiếm của Gnutella thường không tin cậy. Các node là các máy tính bình thường, do đó có thể gia nhập hoặc rời mạng bất cứ lúc nào, và do đó mạng không bao giờ ở trạng thái cân bằng hoàn toàn cả. Hơn nữa, nếu số lượng các node tăng lên thì băng thông dùng cho việc tìm kiếm và duy trì các kết nối cũng tăng lên làm cho hoạt động của mạng trở nên nặng nề, các yêu cầu tìm kiếm thường xuyên bị bỏ qua (dropped). Các nghiên cứu thực tế cho thấy, Gnutella không phải là 1 mạng có khả năng mở rộng và hoạt động hiệu quả. Theo [15], để giải quyết vấn đề thắt nút cổ chai (bottlenecks), Gnutella đã được cài đặt thành hệ thống nhiều tầng. Thay vì tất cả các node đều có vai trò như nhau, giờ đây, các node gia nhập vào mạng chỉ được giữ ở cạnh mạng giống như các node lá và không chịu trách nhiệm định tuyến. Các node ultrapeers mới có khả năng định tuyến thông điệp tìm kiếm và lưu thông điệp đó. Điều này cho phép việc tìm kiếm trong 1 không gian mạng rộng hơn và cũng làm tăng hiệu quả hoạt động của mạng. Do không phụ thuộc vào 1 Server duy nhất nên Gnutella cũng khó bị đánh sập hơn so với Napster. 14 Thế hệ 2: Thế hệ thứ 2 của P2P với các đại diện như Freenet ,eDonkey, hay KaZaA nhấn mạnh tính nặc danh (Freenet) và khả năng tương tác giữa các hệ thống ngang hàng khác nhau (eDonkey)[13]. Sau những tranh chấp về pháp lý dẫn đến sự đóng cửa của 1 số mạng P2P trước đó, các mạng sau này hoặc phải thêm tính năng giấu thông tin của các file được chia sẻ, hoặc tìm cách thương mại hóa, hợp pháp hóa các ứng dụng P2P (Audiogalaxy)[13]. Trong hệ thống Freenet, file không được lưu trữ trên đĩa cứng của các peer cung cấp chúng mà được lưu trữ ở các vị trí khác trong mạng. Mục đích của việc phát triển mạng Freenet là làm cho thông tin được lưu trữ và truy cập mà không cần biết định danh. Với cách tổ chức như vậy, chủ sở hữu của một node mạng cũng không biết được tài liệu gì được lưu trữ trên đĩa cứng của máy anh ta. Vì lý do này mà các Peer và các file được cung cấp các số định danh khác nhau. Khi một file được tạo, nó được truyền qua các peer láng giềng tới các peer có số định danh gần với số định danh của file nhất và được lưu trữ ở đó. Cũng trong giai đoạn này, các nghiên cứu về việc cải tiến kiến trúc và giao thức hoạt động của P2P đã dẫn đến sự ra đời của nhiều mô hình P2P như Chord, CAN, Pastry, …Với các mô hình kiến trúc mới này, hiệu suất của mạng được cải tiến đáng kể so với thế hệ trước đây. Thế hệ 3: Thế hệ thứ 3 hay chính là thế hệ tương lai của P2P, vượt ra ngoài mục đích sơ khai là chia sẻ và tìm kiếm tài nguyên theo tên để hướng đến nhiều mục đích hơn như: Tìm kiếm so khớp 1 phần, tìm kiếm theo từ khóa Công cụ tìm kiếm Web Công việc có tính tương tác cộng đồng Công việc cần tính toán phân tán (data mining) P2P hiện tại và tương lai sẽ phải đối mặt với nhiều thách thức hơn khi mà yêu cầu về khả năng mở rộng với mạng lên tới hàng triệu node tham gia và vẫn phải đảm bảo mạng hoạt động hiệu quả. Khả năng chịu lỗi, tính sẵn sàng sử dụng và khả năng tự ổn định Việc phân phối dữ liệu, định tuyến, cân bằng tải trong các mạng phủ Về mặt an ninh: khả năng chống được các cuộc tấn công Tính tin cậy trong việc tính toán và chia sẻ dữ liệu Những kỹ thuật nhằm đảm bảo sự công bằng trong khi sử dụng mạng (cân bằng giữa tính ích kỷ cá nhân và mục tiêu toàn cục) Nhiều hệ thống đã được đề xuất và kết quả mô phỏng cho thấy chúng hoạt động khá hiệu quả (EDUTELLA[9], INS/Twine[4]). Bên cạnh đó, công nghệ ngang hàng 15 còn được tích hợp vào các trình duyệt Web (AllPeers - Firefox plug-in [17]) và công cụ tìm kiếm trên mạng. 1.2 Ưu, nhược điểm của mạng ngang hàng Mô hình P2P rất phù hợp với tính phi tập trung của Internet, bởi bản chất của tài nguyên là phân tán, các thông tin lưu trữ không chỉ trên các Server mà ở cả các máy Client. Việc cá nhân hóa quyền quản lý tài nguyên làm tăng lượng tài nguyên mạng, từ đó nâng cao mức độ sẵn sàng phục vụ cũng như hiệu suất khai thác. Xét về khía cạnh sức mạnh xử lý, mạng P2P có tiềm năng cao hơn cả những máy chủ lớn nhất hiện nay, và do đó, sử dụng mạng P2P có thể cải thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu, giải các bài toán phức tạp (đây đều là những vấn đề vượt ra ngoài tầm xử lý của những máy chủ tập trung khi số lượng truy vấn, tính toán lên đến hàng trăm triệu mỗi ngày). Sỡ dĩ như vậy là vì, P2P đã tận dụng được tiềm năng từ “cạnh” của Internet, tận dụng khả năng xử lý, khả năng lưu trữ còn thừa của các máy tính tham gia mạng với những thuật toán phân tán hợp lý. Công nghệ này đã chia việc xử lý lớn ra thành những xử lý nhỏ có thể phân tán giữa các máy tính trong một mạng. Mỗi một PC đồng thời xử lý các dữ liệu và trả về kết quả cho máy tính trung tâm ráp nối các kết quả thành phần lại. Bằng cách đó, ta có thể giải quyết những bài toán phức tạp mà không cần chi phí nào cho việc trang bị thêm máy móc. Bên cạnh đó, việc phân tán trách nhiệm cung cấp dịch vụ đến tất cả các nút trên mạng sẽ giúp loại bỏ vấn đề ngừng trệ dịch vụ do nơi cung cấp duy nhất bị sự cố. Khi có nhiều máy cùng cung cấp 1 dịch vụ, ta có nhiều giải pháp khả biến trong việc cung cấp dịch vụ đó. P2P cũng tận dụng được băng thông trên toàn bộ mạng, vì việc tăng số giao tiếp giữa các thiết bị mạng qua các đường truyền khác nhau sẽ làm giảm khả năng tắc nghẽn mạng. Ngoài ra, khi càng nhiều máy tính tham gia vào P2P thì tổng sức mạnh xử lý, khả năng lưu trữ và chia sẻ tài nguyên, băng thông lại càng tăng. Điều đó cho thấy một cách rõ ràng khả năng mở rộng của mạng P2P. Tuy nhiên, mạng ngang hàng cũng có nhiều nhược điểm. Với mô hình P2P thuần túy, tức là mô hình mà ở đó, mọi máy đều có vài trò như nhau và không tuân theo bất cứ 1 qui luật định tuyến hay kết nối nào, thì mạng P2P cũng bộc lộ khá nhiều nhược điểm: 16 Đầu tiên, chính vì yêu cầu dịch vụ được đáp ứng một cách tùy biến nên máy yêu cầu dịch vụ có thể nhận được nhiều kết quả khác nhau khi nó kết nối đến các máy khác nhau cung cấp cùng 1 dịch vụ. Tiếp theo, các yêu cầu gửi đi có thể không nhận được kết quả trả về, vì chẳng có gì đảm bảo sẽ tồn tại 1 máy nào đó có khả năng đáp ứng yêu cầu đó. Ngoài ra, các tài nguyên có thể biến mất do node cung cấp tài nguyên có thể ngắt kết nối bất cứ lúc nào. Tuy nhiên, những nhược điểm trên đều có thể khắc phục được bằng cách cải tiến mô hình P2P thuần túy. Và đó chính là nguyên nhân dẫn đến sự ra đời của mạng ngang hàng có cấu trúc mà ta sẽ nghiên cứu tiếp ở chương 2. 1.3 Kết luận Ngày nay, do mọi sự chú ý đều tập trung vào vấn đề cộng tác, các hệ thống P2P cho phép các ứng dụng phần mềm tương tác với nhau đem lại nhiều hứa hẹn cho các ứng dụng kết hợp các dữ liệu phân tán cho thương mại điện tử, thiết kế sản phẩm hoặc quản lý tri thức. Các chương trình đó dùng P2P như một phương thức gửi dữ liệu vào ra từ trình ứng dụng này tới trình ứng dụng khác hoặc liên kết một số lượng vô hạn các máy tính thành một cơ sở dữ liệu khổng lồ. Công nghệ tương tác phần mềm cho phép các công ty chia nhỏ các vấn đề phức tạp cho dễ quản lý hơn. Các hệ thống cho phép đối chiếu dữ liệu và đảm bảo rằng chúng đang được điều khiển bởi chính những người tạo ra chúng, đảm bảo rằng hoạt động chính xác và kịp thời rất lý tưởng cho các ứng dụng trực tuyến và kinh doanh chứng khoán. Một số các công ty đang tiếp tục phát triển thế hệ tiếp theo của các máy tìm kiếm trên công nghệ P2P để phân phối thông tin đúng lúc và toàn diện hơn cho các công ty truyền thông lớn. Một loạt các hãng mới thành lập đang tạo ra những chương trình tận dụng tài nguyên triển khai khả nǎng của P2P để lưu trữ các file, phân phối nội dung và chia sẻ sức mạnh xử lý của các máy khác. Mục đích ở đây một phần là cắt giảm giá thành phần cứng chẳng hạn như thiết bị lưu trữ, Server và các thiết bị khác, nhưng cũng giúp cho việc quản lý thông lượng trên mạng. Mặc dù có tiềm nǎng dịch vụ lớn, nhưng những vấn đề liên quan đến an toàn bảo mật và sự phức tạp liên quan đến việc quản lý bản quyền khiến cho việc áp dụng các dịch vụ P2P trở nên khó khăn. Một số lượng lớn các ứng dụng của P2P đã phải ngừng hoạt động, nhưng các công ty lớn như Microsoft , Sun Microsystems và nhiều công ty khác lại bắt đầu áp dụng P2P. Những hãng khổng lồ này đang nghiên cứu để ứng dụng công nghệ P2P trong các sản phẩm của họ. Intel là công ty lớn đầu tiên dùng P2P và đang đầu tư để phát triển tiếp và đồng thời giúp đỡ 17 các nhóm làm việc về P2P nhằm đưa ra các chuẩn công nghệ ban đầu. Trong khi đó, Microsoft đã tuyên bố công khai dự án Hailstorm của họ và đã đưa ra một số nét nổi bật của các dịch vụ P2P. Không chịu đứng ngoài cuộc Sun Microsystems đã đưa ra một loạt chuẩn cho một nền P2P mã nguồn mở gọi là JXTA. Việc nghiên cứu về lịch sử phát triển P2P cũng như những thông tin liên quan cho thấy P2P là 1 công nghệ mạnh và có khả năng được sử dụng rộng rãi trong tương lai. Đây sẽ là nền tảng quan trọng để chúng ta có thể phát triển được các ứng dụng mạng phù hợp với tốc tốc độ phát triển công nghệ thông tin như hiện nay. 18 CHƢƠNG 2 MẠNG NGANG HÀNG CÓ CẤU TRÚC Trong chương này, báo cáo luận văn sẽ giới thiệu khái quát về mạng ngang hàng có cấu trúc và hoạt động của giao thức Chord, 1 giao thức DHT sẽ được sử dụng để cài đặt mạng phủ DHT trong phần sau. 2.1 Mạng ngang hàng có cấu trúc dựa trên DHT 2.1.1 Khái niệm mạng ngang hàng có cấu trúc Mô hình mạng P2P mà trong đó, các node được tổ chức lại theo 1 cấu trúc nhất định và việc định tuyến thông báo sẽ dựa trên cấu trúc đó, được gọi là mô hình mạng ngang hàng có cấu trúc. Như đã nói trong chương 1, mạng P2P thuần túy hoạt động không hiệu quả do các node tham gia mạng không tuân theo 1 quy luật nào, các kết nối xảy ra ngẫu nhiên, thông báo được gửi kiểu phát tràn, …Mạng ngang hàng có cấu trúc dựa trên DHT khắc phục nhược điểm của mạng không cấu trúc bằng cách sử dụng hệ thống bảng băm phân tán. Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với phần dữ liệu nào được chia sẻ trong mạng. Với cấu trúc này, khi một máy 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 về dữ liệu đó và liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Mạng P2P có cấu trúc sử dụng một giao thức đảm bảo tính toàn cục để chắc chắn rằng mọi peer tham gia mạng đều có thể định tuyến truy vấn tới các peer khác chứa dữ liệu mong muốn, ngay cả khi dữ liệu đó không phổ biến. Sự đảm bảo này yêu cầu một mạng phủ (overlay) được liên kết theo một cấu trúc nhất định. Hầu hết những mạng P2P có cấu trúc hiện này đều thuộc kiểu DHT, với kiểu này một kỹ thuật băm phù hợp được sử dụng để gán quyền quản lý dữ liệu cho những peer tham gia cụ thể, cũng như bảng băm truyền thống, mỗi khóa sẽ được gán cho những ô cụ thể. Một số mạng based-DHT phổ biến có thể kể là: Chord, Pastry, CAN,…. Bảng băm là một cặp (tên, giá trị) hay thường gọi là cặp (khóa, giá trị). Mỗi một node khi tham gia vào mạng có thể dễ dàng tìm thấy giá trị mong muốn dựa vào khóa của giá trị đó. Việc hình thành khóa và gắn các khóa đó với giá trị tương ứng được thực hiện trực tiếp tại các node trong mạng, chính vì vậy khả năng sập mạng được giảm tối thiểu khi các node tham gia hoặc dời bỏ mạng. Chính lý do này khiến khả năng mở rộng của mạng DHT là cực lớn, quá trình kiểm soát việc tham gia, dời bỏ mạng của các node cũng trở nên dễ dàng hơn.