Luận văn thạc sĩ: Đánh giá các phương pháp tìm kiếm thông tin trong hệ thống mạng ngang hàng

Luận văn thạc sĩ nghiên cứu đánh giá các phương pháp tìm kiếm thông tin trong hệ thống mạng ngang hàng có cấu trúc, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn

• Tác giả: Đỗ Thị Luân
• Người hướng dẫn: TS. Nguyễn Hoài Sơn
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Đánh Giá Phương Pháp Tìm Kiếm Thông Tin Trong Mạng Ngang Hàng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. CHƯƠNG 1: TÌM HIỂU MẠNG NGANG HÀNG VÀ CÁC ỨNG DỤNG
• 1.1. TỔNG QUAN MẠNG NGANG HÀNG
• 1.2. PHÂN LOẠI MẠNG NGANG HÀNG
• 2. MẠNG NGANG HÀNG CÓ CẤU TRÚC. GIAO THỨC CHORD
• 3. GIẢI PHÁP INS/TWINE
• 4. TỔNG QUAN VỀ ĐÁNH GIÁ HIỆU NĂNG MẠNG
• PHỤ LỤC CÁC BẢNG SỐ LIỆU MÔ PHỎNG
• LỜI MỞ ĐẦU
• KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN TIẾP THEO

Tóm tắt

I. Tổng quan về mạng ngang hàng

Mạng ngang hàng (P2P) là một mô hình mạng cho phép các máy tính kết nối và chia sẻ tài nguyên mà không cần thông qua máy chủ trung tâm. Mô hình này đã phát triển mạnh mẽ từ năm 1999 với sự ra đời của phần mềm Napster, cho phép người dùng chia sẻ file âm nhạc. Mạng P2P có thể được phân loại thành hai loại chính: mạng ngang hàng không cấu trúc và mạng ngang hàng có cấu trúc. Mạng không cấu trúc thường sử dụng phương pháp tìm kiếm flooding, trong khi mạng có cấu trúc sử dụng các thuật toán như Bảng băm phân tán (DHT) để tổ chức và tìm kiếm tài nguyên hiệu quả hơn. Việc tìm kiếm thông tin trong mạng ngang hàng là một thách thức lớn do tính phân tán của tài nguyên. Do đó, việc phát triển các phương pháp tìm kiếm hiệu quả là rất cần thiết.

1.1 Định nghĩa và lịch sử phát triển

Mạng ngang hàng (P2P) được định nghĩa là một mạng mà trong đó các máy tính (nodes) có thể chia sẻ tài nguyên mà không cần một máy chủ trung tâm. Lịch sử phát triển của P2P bắt đầu với Napster, phần mềm cho phép người dùng chia sẻ file âm nhạc. Sau Napster, nhiều ứng dụng khác như Gnutella và KaZaa đã xuất hiện, mở rộng khả năng chia sẻ không chỉ cho file âm nhạc mà còn cho nhiều loại tài nguyên khác. Sự phát triển của P2P đã dẫn đến việc sử dụng rộng rãi trong nhiều lĩnh vực, từ chia sẻ file đến điện thoại VoIP và streaming video.

1.2 Phân loại mạng ngang hàng

Mạng ngang hàng có thể được phân loại theo mục đích sử dụng hoặc mức độ tập trung. Mạng ngang hàng không cấu trúc thường không có cấu trúc rõ ràng và sử dụng phương pháp tìm kiếm flooding, trong khi mạng ngang hàng có cấu trúc sử dụng các thuật toán như DHT để tổ chức và tìm kiếm tài nguyên. Mạng ngang hàng tập trung, như Napster, dựa vào một máy chủ trung tâm để tìm kiếm tài nguyên, trong khi mạng ngang hàng thuần túy không có máy chủ trung tâm và sử dụng cơ chế flooding để tìm kiếm. Mạng ngang hàng lai kết hợp các yếu tố của cả hai loại trên để cải thiện hiệu suất.

II. Phương pháp tìm kiếm thông tin trong mạng ngang hàng

Việc tìm kiếm thông tin trong mạng ngang hàng là một thách thức lớn do tính phân tán của tài nguyên. Các phương pháp tìm kiếm chính bao gồm tìm kiếm chính xác, tìm kiếm theo thuộc tính - giá trị và tìm kiếm theo khoảng. Tìm kiếm chính xác yêu cầu người dùng biết chính xác tên tài nguyên cần tìm, trong khi tìm kiếm theo thuộc tính - giá trị cho phép người dùng tìm kiếm dựa trên các thuộc tính cụ thể của tài nguyên. Tìm kiếm theo khoảng cho phép người dùng tìm kiếm trong một khoảng giá trị nhất định, điều này rất hữu ích khi người dùng không biết chính xác thông tin cần tìm.

2.1 Tìm kiếm chính xác

Tìm kiếm chính xác là phương pháp yêu cầu người dùng nhập chính xác tên tài nguyên cần tìm. Phương pháp này thường được sử dụng trong các mạng ngang hàng có cấu trúc, nơi mà các tài nguyên được tổ chức theo một cách có hệ thống. Tuy nhiên, nhược điểm của phương pháp này là người dùng thường không biết chính xác tên tài nguyên, dẫn đến việc tìm kiếm không thành công. Do đó, cần phát triển các phương pháp tìm kiếm linh hoạt hơn để đáp ứng nhu cầu của người dùng.

2.2 Tìm kiếm theo thuộc tính giá trị

Tìm kiếm theo thuộc tính - giá trị cho phép người dùng tìm kiếm tài nguyên dựa trên các thuộc tính cụ thể. Phương pháp này rất hữu ích trong các trường hợp mà người dùng chỉ biết một số thông tin cơ bản về tài nguyên. Các giải pháp như INS/Twine và CDS đã được phát triển để hỗ trợ phương pháp tìm kiếm này, giúp cải thiện khả năng tìm kiếm và tăng cường hiệu suất của mạng ngang hàng. Việc áp dụng các thuật toán tối ưu trong tìm kiếm theo thuộc tính - giá trị có thể giúp giảm thiểu thời gian tìm kiếm và tăng tỷ lệ thành công.

III. Đánh giá hiệu năng của các phương pháp tìm kiếm

Đánh giá hiệu năng của các phương pháp tìm kiếm trong mạng ngang hàng là rất quan trọng để xác định tính khả thi và hiệu quả của từng giải pháp. Các tiêu chí đánh giá bao gồm độ chính xác của tìm kiếm, thời gian phản hồi và khả năng cân bằng tải. Việc mô phỏng các phương pháp tìm kiếm giúp xác định các yếu điểm và ưu điểm của từng giải pháp, từ đó đưa ra các đề xuất cải tiến. Các giải pháp như D-AVTree và CDS đã cho thấy hiệu suất tốt trong việc tìm kiếm và quản lý tài nguyên trong mạng ngang hàng.

3.1 Tiêu chí đánh giá hiệu năng

Các tiêu chí đánh giá hiệu năng của các phương pháp tìm kiếm trong mạng ngang hàng bao gồm độ chính xác, thời gian phản hồi và khả năng cân bằng tải. Độ chính xác của tìm kiếm phản ánh khả năng tìm thấy tài nguyên đúng theo yêu cầu của người dùng. Thời gian phản hồi là khoảng thời gian từ khi người dùng gửi yêu cầu đến khi nhận được kết quả. Khả năng cân bằng tải đảm bảo rằng không có node nào trong mạng bị quá tải, giúp duy trì hiệu suất ổn định cho toàn bộ hệ thống.

3.2 Kết quả mô phỏng và phân tích

Kết quả mô phỏng cho thấy rằng các giải pháp như INS/Twine và CDS có khả năng tìm kiếm hiệu quả hơn so với các phương pháp truyền thống. Mô phỏng cũng chỉ ra rằng việc sử dụng các thuật toán tối ưu trong tìm kiếm có thể giảm thiểu thời gian phản hồi và tăng cường độ chính xác. Phân tích kết quả mô phỏng giúp xác định các yếu điểm của từng giải pháp, từ đó đưa ra các đề xuất cải tiến nhằm nâng cao hiệu suất tìm kiếm trong mạng ngang hàng.

Nội dung chính

Tổng quan nghiên cứu

Mạng ngang hàng (Peer-to-Peer - P2P) đã trở thành một mô hình mạng phổ biến từ cuối những năm 1990, với ứng dụng rộng rãi trong chia sẻ file, video streaming và nhiều dịch vụ phân tán khác. Theo ước tính, các ứng dụng P2P chiếm khoảng 50-75% băng thông Internet hiện nay, cho thấy tầm quan trọng và quy mô phát triển của mô hình này. Tuy nhiên, việc tìm kiếm thông tin hiệu quả trong mạng ngang hàng, đặc biệt là mạng ngang hàng có cấu trúc, vẫn là một thách thức lớn do tính phân tán và đa dạng của tài nguyên.

Luận văn tập trung nghiên cứu và đánh giá các phương pháp tìm kiếm thông tin theo cặp thuộc tính - giá trị trong hệ thống mạng ngang hàng có cấu trúc, với phạm vi nghiên cứu chủ yếu dựa trên giao thức Chord và các giải pháp INS/Twine, Content Discovery System (CDS), D-AVTree. Mục tiêu chính là phân tích hiệu năng tìm kiếm, khả năng cân bằng tải và tỷ lệ truy vấn thành công của các giải pháp này thông qua mô phỏng trên mạng có quy mô lớn, với số lượng nút lên đến 200.000 và số lượng truy vấn đa dạng.

Nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả tìm kiếm thông tin trong các hệ thống phân tán, góp phần cải thiện trải nghiệm người dùng và tối ưu hóa tài nguyên mạng. Kết quả đánh giá sẽ cung cấp cơ sở khoa học để lựa chọn và phát triển các giải pháp tìm kiếm phù hợp với yêu cầu thực tế của các hệ thống mạng ngang hàng hiện đại.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Mạng ngang hàng có cấu trúc (Structured P2P Networks): Sử dụng kỹ thuật Bảng băm phân tán (Distributed Hash Table - DHT) để tổ chức các nút mạng theo cấu trúc không gian khóa, điển hình là giao thức Chord. Mạng Chord định danh các nút và tài nguyên bằng các khóa băm, cho phép định tuyến và tìm kiếm hiệu quả với độ phức tạp logarithmic.

• Phương pháp tìm kiếm theo cặp thuộc tính - giá trị (Attribute-Value Search): Thay vì tìm kiếm chính xác theo khóa, phương pháp này cho phép truy vấn dựa trên các cặp thuộc tính và giá trị, phù hợp với thực tế người dùng thường không biết chính xác tên tài nguyên cần tìm.

• Mô hình phân phối tải và cân bằng tải trong mạng phân tán: Luận văn áp dụng các mô hình cân bằng tải như ma trận cân bằng tải (Load Balancing Matrix - LBM) trong CDS để phân phối đều tải lưu trữ và truy vấn trên các nút mạng, tránh hiện tượng quá tải cục bộ.

Các khái niệm chính bao gồm: bảng Finger trong Chord, cây thuộc tính - giá trị (AVTree), khoảng truy vấn trong không gian khóa DHT, luật phân bố Zipf cho phân phối tài nguyên và truy vấn.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp mô phỏng để đánh giá hiệu năng các giải pháp tìm kiếm thông tin trên mạng ngang hàng có cấu trúc. Cụ thể:

• Nguồn dữ liệu: Mô phỏng mạng với số lượng nút lên đến 200.000, số lượng tài nguyên và truy vấn đa dạng, phân phối theo luật Zipf với các tham số alpha = 0.6 và 1.0 để phản ánh tính không đồng đều trong phân phối tài nguyên và truy vấn.

• Phương pháp phân tích: Sử dụng chương trình mô phỏng viết bằng C++ trên nền tảng CodeBlock, mô phỏng các giải pháp INS/Twine, CDS, D-AVTree và các cải tiến như D-AVTree+ và thuật toán truy vấn two-pass trong CDS. Mạng được xây dựng dựa trên giao thức Chord làm lớp phủ DHT để định tuyến và phân bổ tài nguyên.

• Timeline nghiên cứu: Quá trình mô phỏng và đánh giá được thực hiện theo các bước: tạo mạng, phân bổ tài nguyên, thực hiện truy vấn, thu thập và phân tích kết quả về độ trễ truy vấn, tỷ lệ truy vấn thành công, số bản sao tài nguyên và khả năng cân bằng tải.

Phương pháp mô phỏng được lựa chọn nhằm giảm chi phí và tăng tính linh hoạt so với đo thực tế, đồng thời cho phép kiểm soát các tham số đầu vào để đánh giá chi tiết các yếu tố ảnh hưởng đến hiệu năng hệ thống.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Số bản sao tài nguyên trên mỗi tài nguyên:

   • Khi số lượng tài nguyên tăng từ 10.000 đến 200.000, số bản sao tài nguyên của mỗi giải pháp duy trì ổn định.
   • D-AVTree và D-AVTree+ có số bản sao thấp nhất và gần như không đổi, thể hiện hiệu quả trong việc giảm chi phí lưu trữ.
   • INS/Twine có số bản sao cao nhất, do mỗi nhánh AV được ánh xạ thành nhiều khóa riêng biệt.

2. Số nút cần truy vấn cho một truy vấn:

   • D-AVTree và D-AVTree+ yêu cầu truy vấn số nút ít hơn so với INS/Twine và CDS, nhờ khả năng xác định khoảng truy vấn nhỏ hơn.
   • Thuật toán truy vấn two-pass trong CDS giúp giảm số nút truy vấn so với truy vấn đơn giản, cải thiện hiệu quả truy vấn.

3. Độ trễ truy vấn (số hop trung bình):

   • Độ trễ truy vấn của D-AVTree và D-AVTree+ thấp hơn đáng kể so với INS/Twine và CDS, đặc biệt khi tham số Zipf alpha = 1.0.
   • Độ trễ tăng khi số lượng truy vấn tăng, nhưng các giải pháp D-AVTree duy trì độ trễ ổn định hơn.

4. Khả năng cân bằng tải:

   • CDS với ma trận cân bằng tải LBM thể hiện khả năng phân phối tải lưu trữ và truy vấn tốt hơn, giảm thiểu hiện tượng quá tải tại các nút.
   • INS/Twine và D-AVTree có xu hướng tập trung tải tại một số nút do phân phối khóa không đồng đều theo luật Zipf.
   • Cải tiến D-AVTree+ với cơ chế cân bằng tải giúp cải thiện phân phối tải truy vấn.

Thảo luận kết quả

Kết quả mô phỏng cho thấy các giải pháp tìm kiếm theo cặp thuộc tính - giá trị trên mạng ngang hàng có cấu trúc đều có ưu nhược điểm riêng. D-AVTree và D-AVTree+ nổi bật với chi phí lưu trữ thấp và độ trễ truy vấn thấp, phù hợp với các hệ thống yêu cầu hiệu năng cao và cân bằng tải tương đối. CDS với ma trận LBM có ưu thế trong cân bằng tải nhưng phải đánh đổi bằng chi phí lưu trữ và độ trễ truy vấn cao hơn.

Biểu đồ số bản sao tài nguyên và số nút truy vấn minh họa rõ sự khác biệt về hiệu quả phân bổ tài nguyên và truy vấn giữa các giải pháp. Bảng so sánh các tham số h và α trong D-AVTree cho thấy việc điều chỉnh tham số có thể cân bằng giữa hiệu quả truy vấn và cân bằng tải.

So với các nghiên cứu trước đây, luận văn đã mở rộng phạm vi mô phỏng với quy mô mạng lớn hơn và đa dạng tham số hơn, cung cấp cái nhìn toàn diện hơn về hiệu năng các giải pháp. Kết quả này có ý nghĩa thực tiễn trong việc lựa chọn giải pháp tìm kiếm phù hợp với đặc điểm và yêu cầu của từng hệ thống mạng ngang hàng.

Đề xuất và khuyến nghị

1. Áp dụng giải pháp D-AVTree+ cho các hệ thống yêu cầu hiệu năng cao:

   • Động từ hành động: Triển khai
   • Target metric: Giảm độ trễ truy vấn và chi phí lưu trữ
   • Timeline: 6-12 tháng
   • Chủ thể thực hiện: Các nhà phát triển hệ thống mạng phân tán

2. Sử dụng ma trận cân bằng tải LBM trong CDS để cải thiện cân bằng tải:

   • Động từ hành động: Tích hợp
   • Target metric: Giảm tải quá tải tại các nút
   • Timeline: 3-6 tháng
   • Chủ thể thực hiện: Nhóm nghiên cứu và vận hành mạng

3. Điều chỉnh tham số h và α trong D-AVTree để tối ưu hóa hiệu quả truy vấn và cân bằng tải:

   • Động từ hành động: Tinh chỉnh
   • Target metric: Tối ưu số nút truy vấn và phân phối tải
   • Timeline: Liên tục theo dõi và điều chỉnh
   • Chủ thể thực hiện: Kỹ sư mạng và nhà nghiên cứu

4. Phát triển thuật toán truy vấn two-pass trong CDS để giảm số nút truy vấn:

   • Động từ hành động: Phát triển và áp dụng
   • Target metric: Giảm độ trễ và tăng tỷ lệ truy vấn thành công
   • Timeline: 6 tháng
   • Chủ thể thực hiện: Nhóm phát triển phần mềm

Các đề xuất trên nhằm nâng cao hiệu quả tìm kiếm thông tin trong mạng ngang hàng có cấu trúc, đồng thời đảm bảo cân bằng tải và khả năng mở rộng của hệ thống.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Công nghệ Thông tin, Truyền dữ liệu và Mạng máy tính:

   • Lợi ích: Hiểu sâu về các giải pháp tìm kiếm thông tin trong mạng ngang hàng có cấu trúc, áp dụng vào nghiên cứu và phát triển đề tài.

2. Kỹ sư phát triển hệ thống phân tán và mạng P2P:

   • Lợi ích: Áp dụng các giải pháp tìm kiếm hiệu quả, cân bằng tải trong thiết kế và triển khai hệ thống mạng phân tán thực tế.

3. Quản trị viên mạng và chuyên gia vận hành hệ thống:

   • Lợi ích: Nắm bắt các phương pháp đánh giá hiệu năng mạng, lựa chọn giải pháp phù hợp để tối ưu hóa hoạt động mạng.

4. Các tổ chức và doanh nghiệp phát triển ứng dụng chia sẻ tài nguyên phân tán:

   • Lợi ích: Tăng cường hiệu quả tìm kiếm và phân phối tài nguyên, nâng cao trải nghiệm người dùng và giảm chi phí vận hành.

Luận văn cung cấp kiến thức chuyên sâu và các kết quả mô phỏng thực tiễn, hỗ trợ các đối tượng trên trong việc nghiên cứu, phát triển và vận hành các hệ thống mạng ngang hàng hiện đại.

Câu hỏi thường gặp

1. Tại sao cần tìm kiếm theo cặp thuộc tính - giá trị trong mạng ngang hàng?
   Tìm kiếm theo cặp thuộc tính - giá trị phản ánh thực tế người dùng thường không biết chính xác tên tài nguyên mà chỉ có một số thông tin cơ bản. Phương pháp này giúp tìm kiếm linh hoạt và chính xác hơn, phù hợp với các hệ thống phân tán.

2. Giải pháp nào có hiệu quả nhất về chi phí lưu trữ tài nguyên?
   D-AVTree và D-AVTree+ có chi phí lưu trữ thấp nhất do số bản sao tài nguyên bằng số nhánh AV của cây mô tả, ít hơn so với INS/Twine và CDS.

3. Làm thế nào để cân bằng tải trong mạng ngang hàng có cấu trúc?
   CDS sử dụng ma trận cân bằng tải LBM để phân phối đều tải lưu trữ và truy vấn trên các nút, tránh quá tải cục bộ. D-AVTree+ cũng có cơ chế cân bằng tải cải tiến giúp phân phối tải truy vấn hiệu quả hơn.

4. Độ trễ truy vấn được đo như thế nào trong nghiên cứu này?
   Độ trễ truy vấn được tính bằng số hop trung bình từ nút truy vấn đến nút chứa tài nguyên cần tìm, phản ánh thời gian phản hồi của hệ thống.

5. Phương pháp mô phỏng có ưu điểm gì so với đo thực tế?
   Mô phỏng giúp kiểm soát các tham số đầu vào, giảm chi phí và thời gian so với đo thực tế, đồng thời cho phép đánh giá hiệu năng trên quy mô lớn và nhiều kịch bản khác nhau.

Kết luận

• Luận văn đã phân tích và đánh giá chi tiết các giải pháp tìm kiếm thông tin theo cặp thuộc tính - giá trị trong mạng ngang hàng có cấu trúc, bao gồm INS/Twine, CDS và D-AVTree.
• Kết quả mô phỏng cho thấy D-AVTree và D-AVTree+ có hiệu quả cao về chi phí lưu trữ và độ trễ truy vấn, trong khi CDS nổi bật về khả năng cân bằng tải.
• Việc điều chỉnh tham số và áp dụng các thuật toán truy vấn tối ưu giúp cân bằng giữa hiệu quả tìm kiếm và phân phối tải trong mạng.
• Nghiên cứu cung cấp cơ sở khoa học để lựa chọn giải pháp phù hợp với yêu cầu thực tế của hệ thống mạng ngang hàng.
• Các bước tiếp theo bao gồm triển khai thực nghiệm trên môi trường thực tế và phát triển các thuật toán cân bằng tải nâng cao.

Các nhà nghiên cứu và kỹ sư phát triển hệ thống mạng ngang hàng nên áp dụng và tiếp tục cải tiến các giải pháp được đề xuất để nâng cao hiệu quả tìm kiếm và vận hành mạng phân tán trong tương lai.

Trích đoạn nội dung tài liệu

LỜI MỞ ĐẦU Mô hình mạng ngang hàng bắt đầu xuất hiện trên thế giới từ năm 1999 và đƣợc sử dụng rộng rãi trong nhiều ứng dụng, đặc biệt nhƣ các ứng dụng chia sẻ file, video streaming, …. Trong mô hình mạng ngang hàng, các node tham gia mạng có thể chia sẻ tài nguyên nhƣ các file, dữ liệu cho nhau. Điều đó làm tăng tài nguyên của mạng. Tuy nhiên, do các tài nguyên này đƣợc lƣu trữ một cách phân tán, việc tìm kiếm thông tin về tài nguyên một cách hiệu quả là một vấn đề hết sức quan trọng trong các mạng ngang hàng.

Trong thời kỳ đầu mới phát triển, việc tìm kiếm trong mạng ngang hàng hoặc là sử dụng máy chủ lƣu trữ thông tin tài nguyên, hoặc đƣợ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 [10]) 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 (giao thức Chord [6]) hay không gian n-chiều (giao thức CAN[5]) và định tuyến thông báo dựa trên cấu trúc này. Tuy nhiên, mạng ngang hàng có cấu trúc chỉ hỗ trợ phƣơng pháp tìm kiếm chính xác, tức là tìm kiếm các tài nguyên có tên trùng với từ khoá tìm kiếm.

Tuy nhiên, trên thực tế ngƣời dùng thƣờng không thể biết chính xác thông tin cần tìm kiếm mà chỉ biết một số thông tin cơ bản. Vì vậy, việc tìm kiếm theo khoảng hoặc theo các cặp thuộc tính giá trị là hết sức cần thiết. Luận văn này tập trung tìm hiểu các giải pháp tìm kiếm thông tin theo cặp thuộc tính - giá trị đã đƣợc đề xuất nhƣ INS/Twine [9], Contens Distribution System [8], D-AVTree [4], … và đánh giá hiệu năng tìm kiếm, khả năng cân bằng tải của các giải pháp này thông qua mô phỏng. Luận văn gồm có 4 chƣơng, trong đó 2 chƣơng đầu giới thiệu tổng quan về mạng ngang hàng, mạng ngang hàng có cấu trúc và các giải pháp tìm kiếm thông tin cơ bản trong hệ thống mạng ngang hàng có cấu trúc.

Chƣơng 3 đi sâu tìm hiểu các giải pháp tìm kiếm thông tin theo cặp thuộc tính - giá trị nhƣ INS/Twine, CDS, D-AVTree và so sánh các giải pháp. Chƣơng cuối cùng, luận văn tập trung đánh giá mô phỏng các giải pháp tìm kiếm nêu trên, đƣa ra những đánh giá chi tiết về hiệu năng của hệ thống, khả năng cân bằng tải, … của từng giải pháp và những đề xuất lựa chọn giải pháp tùy theo yêu cầu của hệ thống. TÌM HIỂU MẠNG NGANG HÀNG VÀ CÁC ỨNG DỤNG 1.1 TỔNG QUAN MẠNG NGANG HÀNG Chƣơng này sẽ trình bày tổng quan về mạng ngang hàng, về khái niệm, phân loại và nêu rõ ƣu, nhƣợc điểm của mạng ngang hàng so với mạng dựa trên mô hình client/ server.1 Định nghĩa mạng ngang hàng: Quá trình trao đổi thông tin giữa hai máy tính trên hệ thống mạng có thể diễn ra theo 2 mô hình: mô hình khách hàng/ ngƣời phục vụ (client/ server) (hình 1.) hay mô hình mạng ngang hàng peer to peer (hình 1. Mô hình Client/Server Mạng ngang hàng (còn gọi là mạng peer to peer, viết tắt là P2P) là mạng đƣợc tạo ra bởi 2 hay nhiều máy tính đƣợc kết nối với nhau và chia sẻ tài nguyên (nhƣ tệp tin, máy in, .) mà không phải thông qua một máy chủ riêng nào.

Mô hình mạng ngang hàng P2P Trong hệ thống mạng ngang hàng, các máy tính có thể kết nối với nhau qua cổng USB để truyền tệp tin (file) (2 máy tính), cũng có thể kết nối nhiều máy tính trong một văn phòng nhỏ bằng cáp đồng, hoặc kết nối số lƣợng lớn máy tính với nhau bằng các giao thức, ứng dụng đặc biệt. Có thể hiểu, mạng ngang hàng là một kiểu mạng đƣợc thiết kế cho các thiết bị trong đó có chức năng và khả năng của các thiết bị đó là nhƣ nhau. Mạng ngang hàng P2P không có khái niệm máy trạm (client) hay máy chủ (server), mà chỉ có khái niệm các nốt (peers) đóng vai trò nhƣ cả client và server.2 So sánh mô hình mạng ngang hàng p2p với mô hình client/ server P2P Client/Server Đặc điểm: Một mạng ngang hàng cho Đặc điểm: Dữ liệu đƣợc lƣu trữ ở một phép các node đóng góp, chia sẻ tài Server trung tâm, tốc độ cao (Tốc độ nguyên với nhau. Tài nguyên riêng rẽ truy cập thƣờng lớn hơn so với mạng của các node nhƣ: ổ cứng, CD-ROM, P2P).

Các nguồn tài nguyên này có Khi một máy client yêu cầu lấy thông thể đƣợc truy cập từ bất cứ node nào tin nó sẽ phải gửi một yêu cầu theo trong mạng. một tiêu chuẩn do server định ra, nếu Các node đóng vai trò nhƣ cả Client yêu cầu đƣợc chấp nhận thì máy (truy vấn thông tin) và Server (cung cấp server sẽ trả về thông tin mà client thông tin). Ƣu điểm: Không cần server riêng, các Ƣu điểm: Tốc độ truy cập nhanh. client chia sẻ tài nguyên.

Khi mạng Khả năng mở rộng cao. Hoạt động với càng đƣợc mở rộng thì khả năng hoạt bất kì loại ứng dụng nào. Sử dụng động của hệ thống càng tốt. Dễ cài đƣợc với các ứng dụng chia sẻ CSDL.

đặt và bảo trì; thuận lợi cho việc chia sẻ Đáng tin cậy hơn (có server riêng). tài nguyên nhƣ tệp tin, máy in, CD- Mức độ an toàn cao nhất.v… Nhƣợc điểm: Chậm. Không tốt cho Nhƣợc điểm: Cần server riêng (nghẽn các ứng dụng CSDL. Kém tin cậy.

Phức tạp trong việc bảo trì, duy trì hoạt động của mạng.3 Lịch sử phát triển của P2P Lịch sử ra đời và phát triển của P2P gắn liền với phần mềm ứng dụng Napster. Năm 1999, Shawn Fanning một sinh viên Đại học 18 tuổi đã rời bỏ trƣờng Đại học để bắt đầu xây dựng phần mềm mang tên Napster (do bức xúc với việc rất khó khăn trong việc đƣa và chia sẻ các file nhạc online trên Internet mặc dù mọi ngƣời đều có nguồn tài nguyên trong đĩa cứng của mình). Napster đƣợc xây dựng thành công và trở thành cách chia sẻ file chính (miễn phí), nó đã làm thay đổi cách download file nhạc và dung lƣợng cũng lớn hơn nhiều so với các chƣơng trình chia sẻ file trƣớc đó. Download phần mềm, bạn có thể chia sẻ files từ máy tính của mình với tất cả mọi ngƣời trên thế giới.

60 triệu ngƣời trên thế giới đã sử dụng (1 triệu ngƣời Nhật) vào thời điểm đó. Tuy nhiên, do có quá z 10 đông ngƣời dùng và vấn đề bản quyền âm nhạc nên công ty Napster đã bị cấm hoạt động, phần mềm không còn đƣợc sử dụng nữa (2003). Sau Napster, rất nhiều các chƣơng trình khác nhƣ Gnutella, KaZaa and WinMP đã xuất hiện. Và P2P đã chuyển sang việc chia sẻ file has moved beyond file-sharing, chia sẻ processor power rỗi của các nodes chứ không phải là chia sẻ các file âm nhạc MP3 nữa.

Sau sự ra đời của Napster, công nghệ P2P phát triển một cách nhanh chóng. Hiện tại các ứng dụng P2P chiếm khoảng 50% (thậm chí 75%) băng thông trên Internet.4 Ứng dụng trong P2P Mạng ngang hàng P2P đƣợc thiết lập để kết nối các máy tính trong khuôn viên nhỏ nhƣ trong gia đình, các bộ phận của các cơ quan, doanh nghiệp trong phạm vi nhỏ hoặc đƣợc thiết lập trên hệ thống mạng internet nhằm chia sẻ tài nguyên, kết nối, trao đổi thông tin giữa các máy tính trong hệ thống mạng.1 Mạng máy tính trong gia đình: Hầu hết các mạng máy tính trong gia đình hiện nay đều là mạng P2P. Ngƣời dùng cấu hình các máy tính theo workgroup cho phép các máy có thể chia sẻ files, máy in và các tài nguyên, thiết bị khác. Cả mạng có dây và không dây trong gia đình đều có thể sử dụng để thiết lập mạng P2P.

Hệ thống mạng này cũng đƣợc áp dụng ở một số phòng, ban hoặc bộ phận nhỏ của các cơ quan, doanh nghiệp phục vụ chia sẻ file, tài nguyên nhƣ máy in, thiết bị khác.2 Mạng máy tính chia sẻ tệp tin: Là mạng P2P phổ biến và nổi tiếng nhất trên Internet hiện nay. Chức năng chủ yếu của mạng là cho phép tìm kiếm và truyền dữ liệu dựa trên giao thức IP (Internet Protocol). Để truy cập vào mạng P2P này, ngƣời dùng chỉ cần tải và cài đặt phần mềm ứng dụng phù hợp cho máy tính của mình. Có nhiều mạng P2P và phần mềm ứng dụng P2P tồn tại hiện nay.

Một số phần mềm chỉ sử dụng đƣợc cho 1 mạng P2P nhất định, một số hoạt động đƣợc với nhiều mạng P2P khác nhau. Một số mạng P2P nổi tiếng trên Internet gồm: eDonkey, BitTorent, Gnutella.3 Phần mềm ứng dụng P2P. Một số phần mềm ứng dụng P2P nổi tiếng hiện nay bao gồm: KazaA, eMule, Bittorent, …. z 11 KazaA: cho phép tìm kiếm và tải các tệp tin đã đƣợc chia sẻ bởi những nhà cung cấp chuyên nghiệp và ngƣời dùng.

KazaA có sử dụng những kết nối nhanh với các SuperNodes: Mỗi SuperNode chứa danh sách các tệp tin chia sẻ bởi ngƣời dùng và nơi lƣu trữ tệp tin. Mô hình mạng ứng dụng Kazaa Emule: Một trong những phần mềm chia sẻ tệp tin trong hệ thống mạng P2P lớn nhất giữa các ngƣời dùng trên Internet. Có thể sử dụng eMule để chia sẻ và tải tất cả các loại tệp tin trên Internet. Mô hình mạng ứng dụng Skype Skype: Là phần mềm VoIP phát triển bởi những ngƣời đã làm KazaA trong hệ thống mạng ngang hàng.

Skype cho phép ngƣời dùng đàm thoại và gửi message tới ngƣời dùng Skype khác. Có 2 loại nút: Original Host (OH) và Super nodes (SN). OH z 12 là một phần mềm ứng dụng cho phép sử dụng để đàm thoại và gửi message. Những nút có địa chỉ IP tĩnh, CPU, memory, băng thông đủ mạnh thì có thể đƣợc xem xét chọn làm super node.

OH kết nối với một Super nodes SN và phải đăng kí với Skype để đăng nhập thành công.2 PHÂN LOẠI MẠNG NGANG HÀNG Mạng ngang hàng đƣợc phân loại theo mục đích sử dụng hoặc mức độ tập trung của mạng. Phân loại mạng ngang hàng theo mục đích sử dụng, nhƣ: Chia sẻ file (file sharing), điện thoại VoIP (telephony), đa phƣơng tiện media streaming (audio, video), diễn đàn thảo luận (Discussion forums). Mạng ngang hàng cũng có thể phân loại theo mức độ tập trung của mạng, gồm 2 loại: Mạng ngang hàng không cấu trúc (unstructured) và Mạng ngang hàng có cấu trúc (structured).