Luận văn thạc sĩ sử dụng thông tin gần kề vị trí trong khảo duyệt web theo phương thức mạng ngang hàng

Phân tích toàn diện sử dụng thông tin vị trí trong khảo sát web mạng ngang hàng, đề xuất mô hình mới, nâng cao hiệu quả ứng dụng trong chuyên ngành

• 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: Nghiên Cứu Sử Dụng Thông Tin Vị Trí Trong Khảo Sát Web Mạng Ngang Hàng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2009
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ
• DANH MỤC CÁC BẢNG BIỂU
• DANH MỤC HÌNH VẼ
• MỞ ĐẦU
• 1. CHƯƠNG 1: MẠNG NGANG HÀNG CÓ CẤU TRÚC
• 1.1. Khái quát về mạng ngang hàng
• 1.2. Định nghĩa mạng ngang hàng
• 1.3. Phân loại mạng ngang hàng
• 2. CHƯƠNG 2: KHẢO DUYỆT WEB THEO KIẾN TRÚC MẠNG NGANG HÀNG
• 2.1. Giới thiệu chung
• 2.2. Giới thiệu về khảo duyệt web
• 2.3. Khảo duyệt web theo kiến trúc mạng ngang hàng
• 2.4. Kiến trúc khảo duyệt Apoidea
• 3. CHƯƠNG 3: SỬ DỤNG THÔNG TIN GẦN KỀ VỊ TRÍ TRONG MẠNG NGANG HÀNG CÓ CẤU TRÚC
• 3.1. Giới thiệu chung về thông tin gần kề vị trí
• 3.2. Thiết kế mô hình LDHT
• 3.3. Đánh giá hiệu suất LDHT
• 4. CHƯƠNG 4: GIẢI PHÁP SỬ DỤNG THÔNG TIN LIỀN KỀ VỊ TRÍ TRONG KHẢO DUYỆT WEB NGANG HÀNG
• 4.1. Mô hình mạng phủ D-Chord
• 4.2. Kiến trúc hệ thống D-Apoidea
• 4.3. Ổn định mạng trong D-Chord
• 4.4. Đánh giá hệ thống D-Apoidea
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khái quát về mạng ngang hàng

Mạng ngang hàng (P2P) là một mô hình mạng mà trong đó các nút (peer) có thể kết nối trực tiếp với nhau để chia sẻ tài nguyên mà không cần thông qua một máy chủ trung tâm. Thông tin vị trí trong mạng ngang hàng đóng vai trò quan trọng trong việc tối ưu hóa quá trình tìm kiếm và phân phối dữ liệu. Mô hình này cho phép các nút không chỉ yêu cầu dịch vụ mà còn cung cấp dịch vụ cho các nút khác, tạo ra một hệ thống phân tán hiệu quả. Theo nghiên cứu, mạng ngang hàng có thể được phân loại thành hai loại chính: mạng ngang hàng có cấu trúc và mạng ngang hàng phi cấu trúc. Mạng ngang hàng có cấu trúc sử dụng các giao thức định hướng để quản lý kết nối giữa các nút, trong khi mạng ngang hàng phi cấu trúc cho phép các kết nối được thiết lập ngẫu nhiên. Điều này dẫn đến sự khác biệt trong hiệu suất và khả năng mở rộng của từng loại mạng.

1.1 Định nghĩa mạng ngang hàng

Mạng ngang hàng là một mô hình mạng mà trong đó mọi nút đều có thể đóng vai trò là cả client và server. Điều này có nghĩa là mọi thiết bị trong mạng đều có thể cung cấp và yêu cầu dịch vụ. Khảo sát web trong mạng ngang hàng cho phép tối ưu hóa việc thu thập thông tin từ các nguồn khác nhau mà không cần phụ thuộc vào một máy chủ trung tâm. Mô hình này giúp giảm thiểu tắc nghẽn và tăng cường khả năng chịu lỗi của hệ thống. Tuy nhiên, mạng ngang hàng cũng gặp phải một số thách thức như việc đảm bảo tính nhất quán và độ tin cậy của dữ liệu. Việc sử dụng công nghệ thông tin trong mạng ngang hàng giúp cải thiện khả năng chia sẻ và truy cập dữ liệu một cách hiệu quả hơn.

II. Khảo sát web theo kiến trúc mạng ngang hàng

Khảo sát web trong mạng ngang hàng là quá trình thu thập thông tin từ các trang web thông qua các nút trong mạng. Khảo sát web dựa trên kiến trúc mạng ngang hàng cho phép phân phối công việc thu thập thông tin giữa các nút, từ đó giảm tải cho từng nút và tăng cường hiệu suất tổng thể. Hệ thống khảo sát như Apoidea đã cho thấy khả năng mở rộng và hiệu quả trong việc tìm kiếm thông tin. Tuy nhiên, việc tối ưu hóa thông tin vị trí trong quá trình khảo sát là rất cần thiết để đảm bảo rằng các nút gần nhau về mặt địa lý có thể chia sẻ thông tin một cách nhanh chóng và hiệu quả. Việc áp dụng các mô hình như DHT (Distributed Hash Table) giúp cải thiện khả năng định tuyến và tìm kiếm trong mạng ngang hàng.

2.1 Giới thiệu về khảo sát web

Khảo sát web là quá trình thu thập thông tin từ các trang web thông qua việc theo dõi các liên kết. Trong bối cảnh mạng ngang hàng, khảo sát web có thể được thực hiện một cách phân tán, cho phép nhiều nút cùng tham gia vào quá trình thu thập dữ liệu. Công nghệ thông tin đóng vai trò quan trọng trong việc phát triển các thuật toán và giao thức cho khảo sát web, giúp tối ưu hóa tốc độ và hiệu quả thu thập thông tin. Việc sử dụng dữ liệu địa lý trong khảo sát web giúp cải thiện khả năng tìm kiếm và phân phối thông tin, từ đó nâng cao trải nghiệm người dùng.

III. Sử dụng thông tin gần kề vị trí trong mạng ngang hàng có cấu trúc

Thông tin gần kề vị trí là yếu tố quan trọng trong việc tối ưu hóa hiệu suất của mạng ngang hàng. Việc áp dụng dữ liệu địa lý giúp các nút trong mạng có thể xác định được vị trí của nhau, từ đó cải thiện khả năng tìm kiếm và thu thập thông tin. Mô hình LDHT (Locality-aware Distributed Hash Table) đã được đề xuất để giải quyết vấn đề này, cho phép các nút gần nhau về mặt địa lý có thể kết nối và chia sẻ thông tin một cách hiệu quả hơn. Nghiên cứu cho thấy rằng việc sử dụng thông tin gần kề vị trí không chỉ giúp cải thiện tốc độ khảo sát mà còn tăng cường khả năng chịu lỗi của hệ thống.

3.1 Giới thiệu chung về thông tin gần kề vị trí

Thông tin gần kề vị trí trong mạng ngang hàng đề cập đến việc xác định vị trí địa lý của các nút trong mạng. Việc này giúp tối ưu hóa quá trình tìm kiếm và thu thập thông tin, từ đó nâng cao hiệu suất của hệ thống. Phân tích dữ liệu cho thấy rằng các nút gần nhau về mặt địa lý có khả năng chia sẻ thông tin nhanh chóng hơn, từ đó giảm thiểu độ trễ trong quá trình khảo sát. Việc áp dụng các mô hình như LDHT giúp cải thiện khả năng định tuyến và tìm kiếm trong mạng ngang hàng, từ đó nâng cao hiệu quả của quá trình khảo sát web.

IV. Giải pháp sử dụng thông tin liền kề vị trí trong khảo sát web ngang hàng

Giải pháp sử dụng thông tin liền kề vị trí trong khảo sát web ngang hàng nhằm tối ưu hóa hiệu suất thu thập thông tin. Mô hình D-Chord được đề xuất để kết hợp giữa việc duy trì tính cân bằng tải và sử dụng thông tin gần kề vị trí. Mô hình này cho phép các nút trong mạng có thể xác định được vị trí của nhau, từ đó cải thiện khả năng tìm kiếm và thu thập thông tin. Việc áp dụng mô hình này vào hệ thống khảo sát web như D-Apoidea giúp tăng tốc độ khảo sát và cải thiện hiệu quả tổng thể của hệ thống.

4.1 Mô hình mạng phủ D Chord

Mô hình D-Chord là một giải pháp mới nhằm tối ưu hóa việc sử dụng thông tin gần kề vị trí trong mạng ngang hàng. Mô hình này kết hợp giữa hai mạng phủ: V-Chord và L-Chord. V-Chord đảm bảo tính cân bằng tải trong khi L-Chord phản ánh cấu trúc mạng vật lý, từ đó cung cấp thông tin gần kề vị trí. Việc áp dụng mô hình này vào hệ thống khảo sát web giúp cải thiện tốc độ và hiệu quả thu thập thông tin, đồng thời giảm thiểu độ trễ trong quá trình tìm kiếm.

V. Kết luận và hướng phát triển

Nghiên cứu về việc sử dụng thông tin vị trí trong khảo sát web mạng ngang hàng đã chỉ ra rằng việc áp dụng các mô hình như D-Chord và LDHT có thể cải thiện đáng kể hiệu suất của hệ thống. Việc tối ưu hóa thông tin gần kề vị trí không chỉ giúp tăng tốc độ khảo sát mà còn nâng cao khả năng chịu lỗi của hệ thống. Hướng phát triển trong tương lai có thể tập trung vào việc cải tiến các thuật toán và giao thức để tối ưu hóa hơn nữa quá trình thu thập thông tin trong mạng ngang hàng.

5.1 Hướng nghiên cứu trong tương lai

Hướng nghiên cứu trong tương lai có thể tập trung vào việc phát triển các mô hình mới nhằm tối ưu hóa việc sử dụng thông tin gần kề vị trí trong mạng ngang hàng. Việc cải tiến các thuật toán định tuyến và tìm kiếm sẽ giúp nâng cao hiệu suất của hệ thống khảo sát web. Ngoài ra, nghiên cứu cũng có thể mở rộng sang các lĩnh vực khác như bảo mật và quản lý dữ liệu trong mạng ngang hàng.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh Internet phát triển nhanh chóng với hàng tỷ trang web, việc tìm kiếm thông tin chính xác và hiệu quả trở thành một thách thức lớn. Quá trình khảo duyệt web (web crawling) đóng vai trò then chốt trong công nghệ máy tìm kiếm, giúp thu thập và lưu trữ dữ liệu từ các trang web. Tuy nhiên, các hệ thống khảo duyệt truyền thống theo mô hình client/server như Google hay Mercator gặp phải các vấn đề về tắc nghẽn, điểm nghẽn cổ chai và chi phí quản trị cao.

Nghiên cứu này tập trung vào việc cải tiến hệ thống khảo duyệt web dựa trên kiến trúc mạng ngang hàng có cấu trúc, đặc biệt là mạng ngang hàng dựa trên Distributed Hash Table (DHT). Mục tiêu chính là ứng dụng thông tin gần kề vị trí (locality-aware) để nâng cao hiệu suất khảo duyệt, giảm độ trễ và tăng tốc độ tìm kiếm. Phạm vi nghiên cứu tập trung vào việc thiết kế và đánh giá mô hình D-Chord và hệ thống khảo duyệt D-Apoidea, được thực hiện trong khoảng thời gian từ năm 2008 đến 2009 tại Việt Nam.

Nghiên cứu có ý nghĩa quan trọng trong việc phát triển các hệ thống khảo duyệt web phi tập trung, tận dụng tài nguyên mạng hiệu quả, giảm thiểu chi phí và tăng khả năng mở rộng. Các chỉ số hiệu suất như độ dài đường đi trung bình, thời gian phản hồi (RTT), và tổng dung lượng khảo duyệt được sử dụng để đánh giá hiệu quả của giải pháp.

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

Khung lý thuyết áp dụng

Nghiên cứu 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): Mạng ngang hàng dựa trên DHT như Chord, CAN, Pastry, Tapestry, trong đó các nút được gán định danh và dữ liệu được phân phối đồng đều trên không gian khóa. Mạng này đảm bảo khả năng mở rộng, tự quản lý và chịu lỗi cao.

• Giao thức Chord: Là mô hình mạng phủ vòng tròn, sử dụng bảng định tuyến Finger Table với O(log n) entry, cho phép tìm kiếm dữ liệu trong O(log n) bước nhảy. Chord duy trì tính ổn định mạng qua các cơ chế successor, predecessor và thuật toán ổn định định kỳ.

• Thông tin gần kề vị trí (Locality-aware): Khái niệm LDHT (Locality-aware Distributed Hash Table) nhằm gán định danh nút dựa trên vị trí vật lý hoặc ASN để giảm độ trễ mạng, cải thiện hiệu suất định tuyến và khảo duyệt.

• Bộ lọc Bloom: Kỹ thuật kiểm tra trùng lặp URL và nội dung trang web hiệu quả về mặt bộ nhớ, giảm thiểu chi phí lưu trữ và truy vấn.

• Kiến trúc khảo duyệt web Apoidea: Hệ thống khảo duyệt web phi tập trung dựa trên DHT, sử dụng bộ lọc Bloom để quản lý URL và nội dung, phân chia công việc dựa trên không gian khóa và vị trí địa lý.

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

• Nguồn dữ liệu: Nghiên cứu sử dụng dữ liệu mô phỏng và thực nghiệm từ hệ thống khảo duyệt web Apoidea và mô hình D-Chord, bao gồm các thông số như số nút mạng, thời gian phản hồi, dung lượng dữ liệu khảo duyệt từ các quốc gia như Việt Nam, Nhật Bản, Anh và Mỹ.

• Phương pháp phân tích: Sử dụng mô hình mạng phủ D-Chord kết hợp hai vòng V-Chord (đảm bảo cân bằng tải) và L-Chord (phản ánh thông tin gần kề vị trí). Phân tích hiệu suất dựa trên các chỉ số như tổng dung lượng khảo duyệt, băng thông trung bình, số URL khảo duyệt trên giây.

• Timeline nghiên cứu: Nghiên cứu được thực hiện trong năm 2009, bao gồm các giai đoạn thiết kế mô hình, xây dựng hệ thống D-Apoidea, mô phỏng và đánh giá hiệu suất.

• Cỡ mẫu và chọn mẫu: Mô hình mạng giả lập với số lượng nút từ vài trăm đến vài nghìn, lựa chọn các nút dựa trên vị trí địa lý và định danh trong không gian khóa để đánh giá tính hiệu quả của phương pháp gần kề vị trí.

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

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

1. Hiệu suất khảo duyệt tăng đáng kể với D-Chord: Mô hình D-Chord kết hợp V-Chord và L-Chord giúp cải thiện tốc độ khảo duyệt web so với mô hình Apoidea truyền thống. Tổng dung lượng khảo duyệt theo thời gian tăng khoảng 20-30% trong các thử nghiệm mô phỏng.

2. Giảm độ trễ và tăng tốc độ tìm kiếm: Việc sử dụng thông tin gần kề vị trí trong L-Chord giúp giảm đáng kể độ trễ mạng, thể hiện qua chỉ số RTT trung bình giảm khoảng 15-25% so với mạng phủ không sử dụng thông tin vị trí.

3. Cân bằng tải hiệu quả: Vòng V-Chord đảm bảo cân bằng tải giữa các nút, giữ cho băng thông trung bình tại từng nút ổn định, không bị quá tải dù số lượng nút tăng lên. Băng thông trung bình tại các nút duy trì ổn định trong khoảng 5-10 Mbps.

4. Giảm trùng lặp URL và nội dung: Bộ lọc Bloom được áp dụng hiệu quả trong việc kiểm tra trùng lặp URL và nội dung trang, giảm thiểu khoảng 8.5% các trang bị trùng lặp, giúp tiết kiệm tài nguyên lưu trữ và xử lý.

Thảo luận kết quả

Các kết quả trên cho thấy việc tích hợp thông tin gần kề vị trí trong mạng ngang hàng có cấu trúc dựa trên DHT là một hướng đi hiệu quả để nâng cao hiệu suất khảo duyệt web. Việc giảm độ trễ mạng không chỉ cải thiện tốc độ tìm kiếm mà còn giảm tải cho các nút mạng, từ đó tăng khả năng mở rộng của hệ thống.

So sánh với các nghiên cứu trước đây, mô hình D-Chord khắc phục được nhược điểm của Apoidea khi các nút được phân bố ngẫu nhiên trong không gian khóa mà không phản ánh vị trí vật lý, dẫn đến độ trễ cao. Việc sử dụng hai vòng mạng phủ song song (V-Chord và L-Chord) tạo ra sự cân bằng giữa tính cân bằng tải và tính gần kề vị trí, điều mà các mô hình DHT truyền thống chưa làm được.

Dữ liệu có thể được trình bày qua các biểu đồ so sánh tổng dung lượng khảo duyệt theo thời gian, biểu đồ RTT trung bình, và bảng so sánh băng thông trung bình tại các nút giữa Apoidea và D-Apoidea, giúp minh họa rõ ràng hiệu quả của giải pháp.

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

1. Triển khai mô hình D-Chord trong các hệ thống khảo duyệt web hiện có: Động từ hành động: Áp dụng; Target metric: Tăng tốc độ khảo duyệt và giảm độ trễ; Timeline: 6-12 tháng; Chủ thể thực hiện: Các tổ chức phát triển công nghệ tìm kiếm và mạng ngang hàng.

2. Phát triển phần mềm middleware hỗ trợ D-Apoidea: Động từ hành động: Phát triển; Target metric: Tối ưu hóa quản lý bộ lọc Bloom và bảng định tuyến; Timeline: 9 tháng; Chủ thể thực hiện: Các nhóm nghiên cứu và phát triển phần mềm.

3. Tăng cường cơ chế sao lưu và phục hồi dữ liệu: Động từ hành động: Cải tiến; Target metric: Giảm thiểu mất mát dữ liệu khi nút rời mạng đột ngột; Timeline: 6 tháng; Chủ thể thực hiện: Nhà phát triển hệ thống mạng ngang hàng.

4. Mở rộng nghiên cứu áp dụng thông tin gần kề vị trí cho các ứng dụng phân tán khác: Động từ hành động: Nghiên cứu; Target metric: Mở rộng phạm vi ứng dụng và nâng cao hiệu quả; Timeline: 12-18 tháng; Chủ thể thực hiện: Các viện nghiên cứu và trường đại học.

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

1. Nhà nghiên cứu và phát triển công nghệ mạng ngang hàng: Luận văn cung cấp kiến thức sâu về mạng ngang hàng có cấu trúc, DHT và ứng dụng thông tin gần kề vị trí, giúp phát triển các hệ thống phân tán hiệu quả.

2. Chuyên gia phát triển hệ thống máy tìm kiếm và khảo duyệt web: Các giải pháp cải tiến trong khảo duyệt web phi tập trung giúp tăng tốc độ thu thập dữ liệu và giảm chi phí vận hành.

3. Sinh viên và học viên cao học ngành Công nghệ Thông tin, Mạng máy tính: Tài liệu là nguồn tham khảo quý giá về lý thuyết mạng ngang hàng, thuật toán định tuyến và ứng dụng thực tiễn.

4. Doanh nghiệp phát triển phần mềm và dịch vụ Internet: Có thể áp dụng các mô hình và giải pháp để xây dựng hệ thống tìm kiếm, chia sẻ dữ liệu phân tán với hiệu suất cao và chi phí thấp.

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

1. Mạng ngang hàng có cấu trúc khác gì so với mạng ngang hàng phi cấu trúc?
   Mạng ngang hàng có cấu trúc sử dụng thuật toán định tuyến dựa trên DHT để phân phối dữ liệu và định vị nút chịu trách nhiệm, giúp tìm kiếm hiệu quả trong O(log n) bước. Trong khi đó, mạng phi cấu trúc thiết lập liên kết ngẫu nhiên, tìm kiếm bằng cách truyền broadcast, tốn nhiều băng thông và không đảm bảo thành công.

2. Tại sao cần áp dụng thông tin gần kề vị trí trong mạng ngang hàng?
   Thông tin gần kề vị trí giúp giảm độ trễ mạng bằng cách gán định danh nút dựa trên vị trí vật lý hoặc ASN, từ đó cải thiện tốc độ định tuyến và khảo duyệt, tránh trường hợp nút gần nhau trong không gian khóa nhưng lại cách xa về mặt vật lý.

3. Bộ lọc Bloom hoạt động như thế nào trong kiểm tra trùng lặp URL?
   Bộ lọc Bloom sử dụng một vector bit và nhiều hàm băm để kiểm tra nhanh một phần tử có thuộc tập đã lưu hay không, với xác suất sai thấp. Điều này giúp tiết kiệm bộ nhớ và tăng tốc độ kiểm tra trùng lặp URL và nội dung trang.

4. Mô hình D-Chord có ưu điểm gì so với Chord truyền thống?
   D-Chord kết hợp hai vòng mạng phủ V-Chord và L-Chord, vừa đảm bảo cân bằng tải (V-Chord) vừa phản ánh thông tin gần kề vị trí (L-Chord), giúp giảm độ trễ và tăng hiệu suất khảo duyệt so với Chord chỉ dựa trên định danh ngẫu nhiên.

5. Làm thế nào để hệ thống xử lý khi một nút rời khỏi mạng đột ngột?
   Hệ thống sử dụng cơ chế sao lưu dữ liệu Seen-URL và Seen-Content trên các nút phụ, đồng thời thuật toán ổn định mạng cập nhật bảng định tuyến và successor để duy trì tính liên tục và chịu lỗi của mạng.

Kết luận

• Nghiên cứu đã phát triển thành công mô hình D-Chord, kết hợp cân bằng tải và thông tin gần kề vị trí trong mạng ngang hàng dựa trên DHT.
• Hệ thống khảo duyệt web D-Apoidea ứng dụng mô hình này cho hiệu suất khảo duyệt vượt trội so với các hệ thống truyền thống.
• Việc sử dụng bộ lọc Bloom giúp giảm thiểu trùng lặp URL và nội dung, tiết kiệm tài nguyên mạng và bộ nhớ.
• Giải pháp đề xuất có khả năng mở rộng cao, chịu lỗi tốt và phù hợp với các ứng dụng phân tán quy mô lớn.
• Các bước tiếp theo bao gồm triển khai thực tế, phát triển phần mềm hỗ trợ và mở rộng ứng dụng sang các lĩnh vực phân tán khác.

Kêu gọi hành động: Các nhà nghiên cứu và doanh nghiệp trong lĩnh vực mạng phân tán và máy tìm kiếm nên xem xét áp dụng mô hình D-Chord và hệ thống D-Apoidea để nâng cao hiệu quả và khả năng mở rộng của hệ thống khảo duyệt web.

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

MỞ ĐẦU Công nghệ máy tìm kiếm đóng vai trò vô cùng quan trọng trong quá trính lớn mạnh của WWW. Khả năng tìm kiếm đƣợc nội dung mong muốn giữa một lƣợng lớn dữ liệu khổng lồ giúp ích rất nhiều trong mọi lĩnh vực. Một thành phần quan trọng trong công nghệ này là chính là quá trình thu thập thông tin hay còn gọi là khảo duyệt. Quá trình khảo duyệt chính là quá trình xem xét WWW bằng cách lần theo các hyperlink và lƣu trữ các trang web đã tải về.

Hiện nay, hầu hết các hệ thống khảo duyệt web hiện nay nhƣ Google [5], Mercator [6] đều sử dụng mô hình client/server. Với mô hình này, việc khảo duyệt đƣợc thực hiện thông qua một hoặc nhiều máy có liên hệ chặt chẽ để phân chia công việc thu thập và kết quả thu đƣợc sẽ đƣợc quản lý trong hệ thống tập trung. Giải pháp tập trung hóa đƣợc biết đến có nhiều vấn đề nhƣ tắc nghẽn tại các nút dẫn tới hiện tƣợng thắt nút cổ chai, điểm duy trì kết nối bị lỗi có thể khiến toàn hệ thống sụp đổ và việc quản trị là khá tốn kém. Với sự phát triển thành công của các ứng dụng nhƣ Gnutella, Kazaa, và Freenet,… công nghệ mạng ngang hàng đã đƣợc nhìn nhận lại ở tầm cao hơn trong một vài năm qua.

Các hệ thống ngang hàng là các hệ thống tính toán phân tán mà trong đó các nút tham gia kết nối trực tiếp với nhau để thực hiện nhiệm vụ phân phối hoặc trao đổi thông tin hoặc thực thi nhiệm vụ. Mạng ngang hàng dựa trên DHT là một trong các hệ thống ngang hàng có cấu trúc và đóng vai trò quan trọng trong quá trình định tuyến. Kiến trúc mạng ngang hàng dựa trên DHT nhƣ Chord [3], CAN [8], Tapestry [10], Pastry [11] có một số đặc điểm đối lập so với kiến trúc client/server truyền thống, vì kiến trúc này có khả năng mở rộng trên phạm vi rộng lớn, nên các ứng dụng có đƣợc các đặc tính mong muốn nhƣ khả năng mở rộng, tự quản lý, tự tổ chức… Mặc dù các ứng dụng nhƣ tên miền chia sẻ file và hệ thống lƣu trữ đã thu đƣợc nhiều lợi ích từ việc sử dụng kiến trúc mạng ngang hàng nhƣng vẫn chƣa đạt đến thành các ứng dụng cốt lõi và nhiều dịch vụ sử dụng công nghệ ngang hàng ở quy mô toàn cầu. Lý do chính ở đây là các hệ thống khó đáp ứng đƣợc cả hai yêu cầu: khả năng mở rộng, và thông tin gần kề vị trí.

Cân bằng hệ thống là điều kiện cần thiết cho khả năng mở rộng trên mạng dựa trên DHT gồm cân bằng định tuyến và cân bằng tải. Tính năng cân bằng tải của hệ thống DHT đã đƣợc giới thiệu trong khá nhiều các nghiên cứu nhƣ [3]. Với yêu cầu thứ hai là khái niệm gần kề vị trí đƣợc hiểu là nút trong hệ thống DHT phải đƣợc phân bố theo cấu trúc topo mạng. Các nút trong mạng phủ đƣợc bố trí làm sao có thể phản ánh chính là mô hình trên mạng vật lý thật.

Để làm đƣợc điều này, mạng phủ cần có thông tin về về vị trí và không gian giữa các nút kề nhau. Khái niệm về gần kề vị trí cũng đã đƣợc đề cập trong [4] đƣợc gọi là LDHT. Tác giả [4] z 2 thay vì gán ngẫu nhiên định danh nút trong mô hình DHT truyền thống đã sử dụng ASN để thực hiện gán định danh nút theo vị trí địa lý mạng. Theo cách này, các nút gần nhau về mạng vật lý cũng sẽ gần nhau trong không gian khoá.

Đã có một số bài báo nghiên cứu cơ chế kết hợp cả hai yêu cầu về khả năng mở rộng và thông tin gần kề vị trí. Nhƣ trong bài báo [2] đã đề xuất một kiến trúc dựa trên DHT đáp ứng đƣợc yêu cầu về liền kề vị trí trong mạng phủ mà không mất đi thuộc tính cân bằng tải hệ thống. Tác giả [2] đã áp dụng xây dựng trên mô hình CAN và đƣa ra hai mạng phủ, V-CAN dùng để duy trì cân bằng hệ thống và L- CAN dùng để phản ánh mô hình mạng sử dụng thông tin gần kề vị trí. Theo tác giả [2] hệ thống này có thể đƣợc sử dụng hiệu quả cho các ứng dụng mạng trong phạm vi rộng lớn.

Tuy nhiên bài báo cũng mới chỉ đề ra kiến trúc nền tảng mà chƣa đƣa ra cách thức xây dựng L-CAN phản ánh đƣợc mô hình mạng vật lý thật. Chính nhờ vào những ƣu điểm nổi bật của mạng ngang hàng mà đặc biệt là mạng ngang hàng dựa trên DHT, nên đã có khá nhiều hệ thống khảo duyệt web dựa trên mạng ngang hàng nhƣ Apoidea [3], Odissea, UbiCrawler. Hệ thống khảo duyệt Apoidea do có mô hình gần giống với mạng Chord nên đã đáp ứng đƣợc các yêu cầu của hệ thống khảo duyệt web trên mạng ngang hàng nhƣ cân bằng tải giữa các nút, hiệu quả trong việc tìm kiếm nút chịu trách nhiệm, có tính mở rộng và khả năng chịu lỗi. Tuy nhiên [3] mới chỉ đề cập vấn đề gần kề về mặt địa lý của các nút sau khi các nút này đã đƣợc phân bố trên không gian định danh nên rất có thể việc phân bố ngẫu nhiên đó có thể cho kết quả là các nút khảo duyệt tên miền không gần nhau về mặt địa lý với server đƣợc khảo duyệt, trong khi đó có nhiều nút khác gần hơn có thể khảo duyệt tốt hơn.

Vì vậy vấn đề đặt ra ở đây là làm sao có thể áp dụng thông tin gần kề vị trí để cải tiến về tốc độ khảo duyệt web và tốc độ tìm kiếm của hệ thống Apoidea? Với ý tƣởng này, chúng tôi đề xuất một mô hình kiến trúc có thể phản ánh đƣợc thuộc tính liền kề vị trí mà không làm mất đi tính cân bằng tải của hệ thống, để từ đó áp dụng mô hình kiến trúc này vào hệ thống khảo duyệt web Apoidea. Trong báo cáo luận văn này, chúng tôi xin đề xuất một kiến trúc dựa trên DHT đáp ứng đƣợc yêu cầu về liền kề vị trí trong mạng phủ mà không mất đi thuộc tính cân bằng tải hệ thống mà chúng tôi gọi là D-Chord (Double Chord). Nút trong hệ thống D-Chord đƣợc gắn kết với hai mạng phủ. Mạng phủ đầu tiên đƣợc gọi là V-Chord (Virtual Chord), đúng nhƣ tên gọi, là một không gian khóa ảo và không có bất cứ kết nối gì giữa các nút trên mạng phủ này.

V-Chord đóng vai trò đảm bảo tính cân bằng tải của hệ thống, và bất kì thuật toán băm nào đảm bảo tính cân bằng tải đều có thể áp dụng cho vòng V-Chord. Mạng phủ thứ hai mà chúng tôi đề xuất z 3 gọi tên là L-Chord (Locality Chord) đƣợc dựa trên mô hình mạng phủ LDHT [4], qua đó tận dụng đƣợc những ƣu điểm của mạng phủ LDHT nhƣ phản ánh đƣợc cấu trúc mạng vật lý, từ đó cung cấp sự tính toán tính liền kề tuyệt đối. Chúng tôi sử dụng mạng phủ L-Chord để thực hiện tất cả các chức năng tìm kiếm của hệ thống khảo duyệt web, ngoài ra còn sử dụng để tìm kiếm nút tốt nhất để khảo duyệt một tên miền nào đó. Về mặt thiết kế, hệ thống D-Chord mới này hoạt động nhƣ một framework cho bất kì thuật toán nào đảm bảo tính cân bằng tải áp dụng cho V- Chord, mà không ảnh hƣởng đến tính chất liền kề tuyệt đối của vòng L-Chord.

Với phƣơng thức nhƣ vậy, chúng tôi đã tạo ra sự kết hợp tốt nhất giữa việc khai thác cấu trúc mạng vật lý với việc cân bằng tải. Từ thiết kế D-Chord mới này, chúng tôi đề xuất một hệ thống khảo duyệt cải tiến mới từ Apoidea [1] là D-Apoidea. Hệ thống D-Apoidea là hệ thống khảo duyệt web theo mô hình mạng ngang hàng, sử dụng mô hình mạng phủ D-Chord và là sự kết hợp giữa hệ thống Apoidea [1] và bảng băm phân tán LDHT [4]. Hệ thống D- Apoidea áp dụng bảng băm phân tán LDHT cho vòng L-Chord để phản ánh đƣợc cấu trúc mạng vật lý, và áp dụng mô hình mạng Apoidea cho vòng V-Chord.

Hệ thống D-Apoidea tổng hợp các ƣu điểm của hệ thống Apoidea và mô hình mạng phủ LDHT, đồng thời dựa vào mô hình mạng phủ D-Chord mà chúng tôi thiết kế, chúng tôi đƣa ra cơ chế lựa chọn nút chịu trách nhiệm khảo duyệt nhằm tăng tốc độ khảo duyệt web của hệ thống. Xin lƣu ý báo cáo luận văn chỉ tập trung vào việc áp dụng tin gần kề vị trí trong khảo duyệt web theo phƣơng thức mạng ngang hàng mà không tập trung vào đặc điểm cân bằng tải và xây dựng máy tìm kiếm hoàn thiện. Báo cáo luận văn gồm 5 chƣơng và nội dung cụ thể của từng chƣơng nhƣ sau: - Chƣơng 1: Giới thiệu tổng quan mạng ngang hàng có cấu trúc sẽ đề cập về mạng ngang hàng, mạng ngang hàng có cấu trúc, giao thức Chord. - Chƣơng 2: Trình bày sâu về kiến trúc khảo duyệt web dựa trên mạng ngang hàng, mô hình khảo duyệt web ngang hàng phi tập trung và hệ thống khảo duyệt Apoidea.

- Chƣơng 3: Trình bày về khái niệm gần kề vị trí trong mạng ngang hàng và các vấn đề liền kề vị trí LDHT trong kiến trúc khảo duyệt web. - Chƣơng 4: Dựa trên việc phân tích về khảo duyệt duyệt web và liền kề vị trí theo phƣơng thức ngang hàng đã trình bày trong chƣơng 2 và 3, chƣơng 4 sẽ trình bày về giải pháp sử dụng thông tin gần kề vị trí trong khảo duyệt web theo kiến trúc mạng ngang hàng, ngoài ra có xây dựng chƣơng trình khảo duyệt web, và đánh giá hiệu giải pháp dựa trên chƣơng trình mô phỏng - Chƣơng 5: Cuối cùng là kết luận và hƣớng nghiên cứu trong tƣơng lai. z 4 Chƣơng 1: MẠNG NGANG HÀNG CÓ CẤU TRÚC 1.1 Khái quát về mạng ngang hàng 1.1 Định nghĩa mạng ngang hàng Hầu nhƣ các dịch vụ trên Internet ngày nay đề dựa trên mô hình client/server. Theo mô hình này, các máy client kết nối với một máy server thông qua một giao thức nhất định nhƣ WWW, FTP, Telnet, email.

Tài nguyên tập trung tại server hoặc một số nút để cung cấp cho các client truy cập 24/7. Mô hình client/server có nhiều ƣu điểm bao gồm ƣu điểm nổi trội là mọi xử lý đều nằm trên server do đó sẽ tránh cho client những tính toán nặng nề, và phía client không cần có cấu hình mạnh. Tuy nhiên, với chế độ hoạt động theo kiểu client chỉ đóng vai trò thụ động, là yêu cầu dịch vụ từ server mà không 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.