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] LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.