Tài liệu 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

i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ BÙI THỊ LỆ HẰNG 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 LUẬN VĂN THẠC SĨ Hà Nội - 2009 iii MỤC LỤC 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Ữ .............................................i DANH MỤC CÁC BẢNG BIỂU ............................................................................. ii DANH MỤC HÌNH VẼ ........................................................................................... iii MỞ ĐẦU .................................................................................................................... 1 Chƣơng 1: MẠNG NGANG HÀNG CÓ CẤU TRÚC ......................................................... 4 1.1 Khái quát về mạng ngang hàng ........................................................... 4 1.2 Mạng ngang hàng có cấu trúc .............................................................. 9 1.3 CHORD - Mạng ngang hàng dựa có cấu trúc dựa trên DHT ............ 12 1.4 Kết luận .............................................................................................. 19 Chƣơng 2: KHẢO DUYỆT WEB THEO KIẾN TRÚC MẠNG NGANG HÀNG. 20 2.1. Giới thiệu chung ................................................................................ 20 2.2. Giới thiệu về khảo duyệt web ............................................................ 21 2.3 Khảo duyệt web theo kiến trúc mạng ngang hàng ............................ 24 2.3. Kiến trúc khảo duyệt Apoidea ........................................................... 30 2.4. Kết luận .............................................................................................. 39 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 ........................................................................................... 41 3.1 Giới thiệu chung về thông tin gần kề vị trí ........................................ 41 3.2 Thiết kế mô hình LDHT .................................................................... 44 3.3 Đánh giá hiệu suất LDHT .................................................................. 46 3.4 Kết luận .............................................................................................. 48 iv 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 .................................................................. 51 4.1 Mô hình mạng phủ D-Chord ............................................................. 52 4.2 Kiến trúc hệ thống D-Apoidea .......................................................... 68 4.3 Ổn định mạng trong D-Chord............................................................ 71 4.4 Đánh giá hệ thống D-Apoidea ........................................................... 72 CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ......................................... 81 TÀI LIỆU THAM KHẢO ........................................................................................ 82 i DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ ASN Bloom filter Bootstrap peer Crawler Crawling web Decentralized P2P system DHT Distributed crawler DNS NFS LDHT Overlay network RTT Autonomous Number Bloom filter Bootstrap peer System Số hiệu của nhà cung cấp dịch vụ mạng Bộ lọc bloom Là nút môi giới trong mạng bao phủ dùng để cung cấp các thông tin ban đầu về cấu hình cho các nút mới gia nhập vào mạng. Crawler Bộ thu thập thông tin, là một chƣơng trình tự động duyệt qua các cấu trúc siêu liên kết để thu thập tài liệu & một cách đệ quy nó nhận về tất cả tài liệu có liên kết với tài liệu này Crawling web Khảo duyệt web Decentralized P2P system Hệ thống mạng ngang hàng phi tập trung Distributed Hash Table Bảng băm phân tán Distributed crawler Bộ thu thập thông tin phân tán Tên miền Name System Network File System Locality-aware Distributed Hash Table Overlay network Là hệ thống phân giải tên miền Network File System Tính liền kề vị trí trong DHT Round trip time Là thời gian tính từ khi một gói tin đƣợc gửi đi cho đến khi bên gửi nhận về ACK Mạng ngang hàng Nút Sự thỏa hiệp, 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. Địa chỉ URL World Wide Web P2P Peer Trade-off peer to peer Peer Trade-off URL WWW Uniform Resource Locator World Wide Web Mạng bao phủ ii DANH MỤC CÁC BẢNG BIỂU Bảng 1. Bảng định nghĩa các trƣờng trong bảng định tuyến của Chord .................. 13 Bảng 2 . Độ dài đƣờng đi trung bình (ms) trong LDHT .......................................... 47 Bảng 3. RDP trung bình trong LDHT ...................................................................... 48 Bảng 4. Bảng chứa thông tin định tuyến trong D-Chord ......................................... 54 Bảng 5. Danh sách các nhà cung cấp dịch vụ AS của các nút khảo duyệt .............. 73 Bảng 6. Giá trị băm của các nút và tên miền trên thực tế ........................................ 73 iii DANH MỤC HÌNH VẼ Hình 1. Mạng bao phủ ................................................................................................ 6 Hình 2. Phân loại mạng ngang hàng........................................................................... 7 Hình 3. Bảng băm phân tán ...................................................................................... 10 Hình 4. Không gian khoá đƣợc phân hoạch cho 8 nút ............................................. 11 Hình 5. Mạng Chord với n = 3 ................................................................................. 14 Hình 6. Lƣu giữ khoá trong mạng Chord ................................................................. 15 Hình 7. Bảng định tuyến và các khóa lƣu giữ khi 6 tham gia .................................. 16 Hình 8. Bảng định tuyến và các khóa lƣu giữ khi nút 3 rời khỏi mạng ................... 17 Hình 9. Bộ lọc bloom có 3 hàm băm ........................................................................ 29 Hình 10. Phân chia công việc trong Apoidea ........................................................... 31 Hình 11. Kiểm tra trùng lặp nội dung trong Apodiea .............................................. 32 Hình 12. Kiến trúc hệ thống tại một nút Apoidea .................................................... 34 Hình 13. Lƣu đồ thực hiện của LDHT ..................................................................... 46 Hình 14. Mô hình mạng phủ D-Chord ..................................................................... 53 Hình 15. Ví dụ về danh sách ánh xạ của từng nút .................................................... 54 Hình 16. Quá trình tìm kiếm trên vòng L-Chord. Nút tìm kiếm là nút A, id = 15 ... 56 Hình 17. Quá trình tìm kiếm trên vòng V-Chord. Nút tìm kiếm là nút A, id = 7 .... 57 Hình 18. Mạng D-Chord trong trƣờng hợp chƣa có nút D....................................... 62 Hình 19. Kết quả sau khi nút D chạy hàm L_init_finger_table(A) .......................... 64 Hình 20. Kết quả sau khi nút D chạy hàm L_update_others() ................................. 64 Hình 21. Kết quả sau khi nút D chạy hàm update_other_mapping_list () ............... 66 Hình 22. Mô hình hệ thống D-Apoidea .................................................................... 69 Hình 23. Mô hình phân chia công việc trên vòng V-Chord ..................................... 70 Hình 24. Phần mềm Gnuplot .................................................................................... 75 Hình 25. Không gian định danh khoá với 4 nút ....................................................... 76 Hình 26. Tổng dung lƣợng khảo duyệt hut.edu.vn theo thời gian từ ở Việt Nam, Nhật, Anh, Mỹ. ......................................................................................................... 77 iv Hình 27. Tổng dung lƣợng khảo duyệt theo thời gian đối với từng tên miền của Apoidea và D-Apoidea. ............................................................................................ 77 Hình 28. So sánh tổng dung lƣợng khảo duyệt đƣợc theo thời gian Apoidiea và DApoidea ..................................................................................................................... 78 Hình 29. So sánh băng thông trung bình tại từng nút theo thời gian Apoidiea và DApoidea ..................................................................................................................... 79 Hình 30. So sánh URL trung bình khảo duyệt đƣợc tại từng nút trong 1 giây ........ 79 Hình 31. So sánh tổng URL khảo duyệt đƣợc theo thời gian .................................. 79 1 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] 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à LCAN 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 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 VChord, 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 DApoidea á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. 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.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. 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 client 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ăng 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 client thì server bị sập và mạng sẽ bị sập theo. Việc tăng số lƣợng máy để tăng khả năng chịu tải cho các server là cần thiết. Tuy nhiên, chi phí cho một server không nhỏ chút nào. 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, mà vẫn đảm bảo 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. Có thể hiểu công nghệ ngang hàng 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. Trong mạng ngang hàng, mọi nút đều đóng vai trò là cả client và server Nhƣ vậy, trên ngang hàng, 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. Mô hình mạng ngang hàng 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. Từ đặc điểm này, mạng ngang hàng có nhiều khá nhiều ƣu điểm. 5 Thứ nhất, mạng ngang hàng tận dụng đƣợc tài nguyên nhàn rỗi của các client để làm tăng khả năng tính toán của hệ thống. Xét về khía cạnh sức mạnh xử lý, mạng ngang hàng có tiềm năng cao hơn cả những máy chủ lớn nhất hiện nay do mạng ngang hàng đã 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ý. Do đó, sử dụng mạng ngang hàng 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. Thứ 2, mạng ngang hàng là hệ thống tự tổ chức, không tốn thêm chi phí quản trị. Do vai trò các nút tham gia hệ thống là ngang nhau mà không phụ thuộc nhiều vào một máy trung tâm. Ngoài ra, khi càng nhiều máy tính tham gia vào mạng ngang hàng thì tổng sức mạnh xử lý, khả năng lƣu trữ, 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 ngang hàng. Thứ 3, ngang hàng là thiết kế có tính chịu lỗi. 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 một dịch vụ sẽ nhiều giải pháp khả biến trong việc cung cấp dịch vụ đó. Ngoài ra, mạng ngang hàng cũng tận dụng đƣợc băng thông trên toàn bộ mạng, 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. Tuy nhiên, mô hình mạng ngang hàng cũng còn bộc lộ khá nhiều nhƣợc điểm. Đầ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ó nối đến các máy cung cấp cùng một dịch vụ khác nhau. 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 một máy nào đó có khả năng đáp ứng yêu cầu đó. Ngoài ra, vì mạng ngang hàng nằm trên các máy tính cá nhân và không phải lúc nào các máy này cũng liên kết với mạng nên có thể dẫn tới các tài nguyên có thể biến mất trong một khoảng thời gian nhất định. 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 ngang hàng 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 phần tiếp theo. 6 1.1.2 Định nghĩa mạng bao phủ Hầu hết các mạng ngang hàng đều dựa trên mạng bao phủ. Vậy mạng bao phủ là gì? Mạng bao phủ là mạng máy tính đƣợc xây dựng trên nền của các mạng khác. Các nút trong mạng bao phủ đƣợc xem là nối với nhau bằng liên kết ảo, mỗi liên kết ảo có thể bao gồm rất nhiều các liên kết vật lý của mạng nền. Mạng bao phủ ngang hàng là mạng bao phủ vì mạng này chạy trên nền Internet. Hình 1. Mạng bao phủ Rất nhiều mạng ngang hàng đƣợc gọi là mạng phủ vì nó đƣợc xây dựng trên và hoạt động trên nền của Internet. Ví dụ nhƣ Gnutella, Freenet, Chord, CAN,... Mạng Internet quay số qua modem điện thoại (Dial-up Internet) cũng là mạng bao phủ vì mạng này chạy trên mạng điện thoại (telephone network). Mạng bao phủ ngang hàng bao gồm tất cả các nút mạng đại diện cho các máy tham gia và các liên kết giữa các nút mạng này. Một liên kết tồn tại giữa hai nút mạng khi một nút mạng biết vị trí của nút mạng kia. 1.1.3 Phân loại mạng ngang hàng Mạng ngang hàng có thể đƣợc phân loại theo mức độ tập trung của mạng. Dựa vào cấu trúc liên kết giữa các nút mạng trong mạng bao phủ ta có thể phân loại mạng ngang hàng thành 2 loại: mạng ngang hàng có cấu trúc và mạng ngang hàng phi cấu trúc nhƣ hình vẽ 2. 7 Hình 2. Phân loại mạng ngang hàng Mạng ngang hàng phi cấu trúc: là mạng ngang hàng mà trong đó các liên kết giữa các nút mạng trong mạng bao phủ đƣợc thiết lập ngẫu nhiên tức là không theo một qui luật nào. Những mạng nhƣ thế này dễ dàng đƣợc xây dựng vì một máy mới khi muốn tham gia mạng có thể lấy các liên kết có sẵn của một máy khác đang ở trong mạng và sau đó dần dần tự bản thân nó sẽ thêm vào các liên kết mới của riêng ḿ nh. Khi một máy muốn tìm một dữ liệu trong mạng ngang hàng phi cấu trúc, yêu cầu tìm kiếm sẽ đƣợc truyền trên cả mạng để tìm ra càng nhiều máy chia sẻ càng tốt. Hệ thống này thể hiện rõ nhƣợc điểm chung là không có gì đảm bảo tìm kiếm sẽ thành công. Đối với tìm kiếm các dữ liệu phổ biến đƣợc chia sẻ trên nhiều máy, tỉ lệ thành công là khá cao, ngƣợc lại, nếu dữ liệu chỉ đƣợc chia sẻ trên một vài máy thì xác suất tìm thấy là khá nhỏ. Tính chất này là hiển nhiên vì trong mạng ngang hàng phi cấu trúc, không có bất kì mối tƣơng quan nào giữa một máy và dữ liệu nó quản lý trong mạng, do đó yêu cầu tìm kiếm đƣợc chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số lƣợng máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhƣợc điểm khác của hệ thống này là do không có định hƣớng, một yêu cầu tìm kiếm thƣờng đƣợc chuyển cho một số lƣợng lớn máy trong mạng làm tiêu tốn một lƣợng lớn băng thông của mạng, dẫn đến hiệu quả tìm kiếm chung của mạng thấp. Mạng ngang hàng tập trung: đây chính là mạng ngang hàng thế hệ thứ 1. Đặc điểm của mạng này là vẫn còn dựa trên một máy chủ tìm kiếm trung tâm, chính vì vậy nó còn đƣợc gọi là mạng ngang hàng tập trung. Nguyên tắc hoạt động 8 của mạng này là mỗi client lƣu trữ file định chia sẻ với các nút khác trong mạng, có bảng lƣu trữ thông tin kết nối với ngƣời dùng đăng ký (địa chỉ IP, kết nối, băng thông,...) có bảng liệt kê danh sách các file mà mỗi ngƣời dùng định chia sẻ (tên file, dung lƣợng, thời gian tạo file,...). Mọi máy tính tham gia mạng đƣợc kết nối với máy chủ tìm kiếm trung tâm, các yêu cầu tìm kiếm đƣợc gửi tới máy chủ trung tâm phân tích, nếu yêu cầu đƣợc giải quyết máy chủ sẽ gửi trả lại địa chỉ IP của máy chứa tài nguyên trong mạng và quá trình truyền file đƣợc thực hiện theo đúng cơ chế của mạng ngang hàng, giữa các host với nhau mà không cần quan tâm đến máy chủ trung tâm Napster là mạng ngang hàng đặc trƣng cho hệ thống mạng ngang hàng của thế hệ thứ nhất, chúng đƣợc dùng cho việc chia sẻ các file giữa các ngƣời dùng Internet, đƣợc sử dụng rộng rãi. Tuy nhiên Napster đã phải dừng hoạt động vào năm 2001 bởi yếu tố về luật pháp. Nhƣng Napster đã để lại bài học thành công cho một loạt "hậu duệ". Các trang dịch vụ âm nhạc trực tuyến khác nhƣ Hulu, iTunes đã ra đời theo sau Napster đã trở thành "cầu nối" giữa ngƣời nghe nhạc và nhà sản xuất, giúp "đôi bên cùng có lợi". Mạng ngang hàng thuần túy: mạng ngang hàng thuần tuý là một dạng khác của thế hệ thứ 1 trong các hệ thống mạng ngang hàng. Không còn máy chủ tìm kiếm tập trung nhƣ trong mạng Napster, nó khắc phục đƣợc vấn đề nút cổ chai trong mô hình tập trung. Tuy nhiên vấn đề tìm kiếm trong mạng ngang hàng tuần tuý lại sử dụng cho chế phát tràn, yêu cầu tìm kiếm đƣợc gửi cho tất cả các nút mạng láng giềng với nó, điều này tăng đáng kể lƣu lƣợng trong mạng. Đây là một yếu điểm của các mạng ngang hàng thuần tuý. Mạng ngang hàng thuần túy có các máy trạm có vai trò vừa là máy chủ server vừa là máy client, không có máy chủ trung tâm quản lý mạng và không có bộ định tuyến trung tâm, các máy client có khả năng tự định tuyến. Các mạng ngang hàng "thuần túy" tiêu biểu có thể kể là Gnutella 4.0 và Freenet. Mạng ngang hàng lai: trong quá trình phát triển, nhiều ứng dụng sử dụng các mô hình cải tiến đã ra đời. Điển hình là mô hình lai ghép giữa mô hình Client/Server và ngang hàng. Đây đƣợc gọi là mạng ngang hàng thế hệ 2. Mạng ngang hàng lai có một máy chủ trung tâm dùng để lƣu trữ thông tin của các máy client và trả lời các truy vấn thông tin này. Các máy client có vai trò lƣu trữ thông tin, tài nguyên đƣợc chia sẻ, cung cấp các thông tin về chia sẻ 9 tài nguyên của nó cho máy chủ và sử dụng các client định tuyến để xác định địa chỉ IP của các máy client. Phần ứng dụng biểu cho mạng ngang hàng kiểu này là Gnutella 6.0 và JXTA. JXTA đƣợc bắt đầu phát triển bởi SUN từ 2001 và là giao thức ngang hàng nguồn mở. JXTA đƣợc sử dụng cho máy tính cá nhân, mainframe, cell phone, thiết bị cầm tay PDA để giao tiếp theo cách phi tập trung. Chƣơng trình Skype cũng đƣợc xây dựng dựa trên cấu trúc này. 1.2 Mạng ngang hàng có cấu trúc Để mạng ngang hàng thực sự đảm bảo đƣợc những yêu cầu về: khả năng mở rộng, tính chịu lỗi cao và hoạt động hiệu quả, cần xây dựng các giao thức hoạt động hợp lý cho mạng ngang hàng. Mạng ngang hàng có cấu trúc 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 DHT (tiếng anh: Distributed Hash Table). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng bao 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 một phần dữ liệu 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 cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Một số mạng ngang hàng có cấu trúc dựa trên DHT (based-DHT) nổi tiếng là Chord, CAN, Kademlia, Pastry, Tapestry, HyperCuP,… theo đánh giá của [3] thì ngang hàng dựa trên DHT vừa đơn giản lại vừa hiệu quả. 1.2.1 Giới thiệu mạng DHT DHT là hệ thống mạng phân tán, cung cấp các dịch vụ tìm kiếm dựa vào bảng băm. DHT gồm một cặp (khoá, giá trị). Mỗi một nút 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 tên của giá trị đó. Việc hình thành tên (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 nút 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 nút 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, rời bỏ mạng của các nút cũng trở nên dễ dàng hơn. Với thiết kế này, DHT đƣợc sử dụng để xây dựng nhiều ứng dụng phức tạp nhƣ: hệ thống các file phân tán, hệ thống chia sẻ file ngang hàng, hệ thống nội dung phân tán, tin nhắn tức thời,… 10 Hình 3. Bảng băm phân tán 1.2.2 Các thuộc tính của mạng DHT. Các thiết kế của mạng DHT cần bảo đảm một số các thuộc tính nhất định. Thứ nhất thiết kế DHT cần tính đến thuộc tính phi tập trung hay nói cách khác các nút tham gia cấu thành hệ thống không có thành phần trung tâm làm điều phối mạng. Thứ hai, thiết kết DHT cần tính đến khả năng mở rộng của hệ thống. Hệ thống vẫn có thể hoạt động hiệu quả với hàng nghìn hoặc hàng triệu nút. Thứ ba, thiết kế DHT cần tính đến khả năng chịu lỗi cho hệ thống. Hệ thống vẫn có thể làm việc ổn định ngay cả khi có các sự kiện nút tham gia, rời bỏ, lỗi xảy ra liên tục. Kỹ thuật khóa đƣợc sử dụng để đạt đƣợc mục đích là mỗi nút chỉ cần liên kết với một số ít các nút khác trong hệ thống, thƣờng là O(logn) với n là số nút tham gia. Vì vậy sự thay đổi trong các thành viên chỉ ảnh hƣởng đến một phần nhỏ của hệ thống. Một số thiết kế DHT tìm đến tính bảo mật chống lại những ngƣời tham gia có ý đồ xấu và cho phép ngƣời tham gia giấu danh tính, mặc dù điều này không phổ biến trong các hệ thống ngang hàng chia sẻ file. Cuối cùng, thiết kế DHT phải giải quyết những vấn đề cơ bản của các hệ thống phân tán đó là cần bằng tải, tính toàn vẹn dữ liệu, hiệu năng (cụ thể là đảm 11 bảo các hoạt động nhƣ định tuyến, lƣu trữ, truy vấn phải đƣợc thực thi nhanh chóng). 1.2.3 Các thành phần trong DHT Cấu trúc của DHT đƣợc chia thành nhiều thành phần chính. Ở đây có khái niệm trừu tƣợng không gian khoá hoặc có tên là không gian định danh, là một tập xâu m bit. Các nút và dữ liệu đƣợc ánh xạ vào cùng một không gian khoá. Một lƣợc đồ phân vùng không gian khoá chia tách quyền sở hữu các không gian khoá trong số các nút tham gia. Sau đó, mạng bao phủ thực hiện kết nối các nút này lại với nhau, cho phép chúng có thể tìm đƣợc chủ sở hữu khi biết khoá trong không gian khoá đó. Không gian khoá của DHT là một tập gồm nhiều số nguyên, ví dụ: từ 0,..., 2 3 -1,… 2 160 -1,…. Để lƣu trữ một file gồm tên file và dữ liệu trong DHT, DHT sử dụng hàm băm bảo mật SHA-1 (sinh ra một số 160 bit). Đầu vào của hàm băm: - Địa chỉ IP của một nút. - Tên các file dữ liệu hoặc nội dung của dữ liệu. Ví dụ, trong hình vẽ 4 không gian khoá nằm trong khoảng 0…65535 (2 16 -1) đƣợc phân hoạch cho 8 nút. Hình 4. Không gian khoá đƣợc phân hoạch cho 8 nút Về quản lý dữ liệu trong DHT, địa chỉ IP của một nút đƣợc băm để xác định vị trí của nó trong bảng băm. - ID của nút = SHA-1(địa chỉ IP) Mỗi file dữ liệu đƣợc gán một số định danh (khoá) - Khoá = SHA-1(tên file) hoặc SHA-1(nội dung file). - Khoá là giá trị duy nhất trong không gian khoá. Mỗi nút quản lý một khoảng giá trị trong không gian khoá. Dữ liệu đƣợc lƣu trữ ở nút và đƣợc quản lý khoá của dữ liệu. Dữ liệu có thể đƣợc lƣu trữ trực tiếp hoặc gián tiếp thông qua địa chỉ IP. 12 Việc tìm kiếm dữ liệu trong DHT đƣợc thực hiện bằng cách gửi thông điệp tìm kiếm khoá k sẽ đƣợc chuyển đi lần lƣợt đến trong nút trong DHT cho đến khi gặp nút quản lý khoá k. Thông điệp put(k, dữ liệu) đƣợc gửi tới bất kỳ nút nào trong mạng. Thông điệp này đƣợc chuyển tiếp từ nút này sang nút khác thông qua mạng bao phủ cho đến khi tới đƣợc nút chịu trách nhiệm với khoá k theo quy định của phân vùng không gian khoá, nơi lƣu trữ cặp (k, dữ liệu). Sau đó, bất kỳ client nào khác có thể lấy nội dung file bằng cách băm tên file lần nữa với khoá k và hỏi nút DHT bất kỳ để tìm ra dữ liệu gắn với khoá k cùng bằng thông điệp get(k). Thông điệp này lần nữa sẽ đƣợc định tuyến thông qua mạng bao phủ để tới nút chịu trách nhiệm về khoá k, nút này sẽ phản hồi lại dữ liệu mà mình có cho client. Về cơ chế quản lý, một nút gia nhập hoặc rời bỏ hệ thống đƣợc quản lý nhƣ thế nào đƣợc thực hiện qua các bƣớc. Nút gia nhập: 4 bƣớc 1. 2. 3. 4. Bƣớc 1: Liên lạc với một nút tồn tại trong DHT. Bƣớc 2: Xác định khoảng địa chỉ mà nó quản lý. Bƣớc 3: Cập nhật lại thông tin phục vụ cho việc tìm kiếm. Bƣớc 4: Chuyển tất cả các cặp (khoá, giá trị) thuộc quyền quản lý từ nút trƣớc về nó. Nút rời khỏi hệ thống: 2 bƣớc 1. Bƣớc 1: chuyển các cặp (khoá, giá trị) của nó về nút trƣớc nó. 2. Bƣớc 2: cập nhật lại thông tin phục vụ cho việc tìm kiếm. Các thành phần phân vùng không gian khoá và mạng bao phủ đƣợc mô tả kỹ hơn ở phần tiếp theo để giải thích rõ hơn về ý tƣởng chính trong các mạng sử dụng DHT, còn về chi tiết thì các mạng này khác nhau. 1.3 CHORD - Mạng ngang hàng dựa có cấu trúc dựa trên DHT Theo một đánh giá tổng hợp về các thuật toán định tuyến dựa trên DHT trong các kiến trúc mạng khác nhau nhƣ hình tròn (với giao thức Chord), hình cây , hình hộp (với giao thức CAN),… xét về sự linh hoạt trong việc định tuyến, khả năng phục hồi trạng thái cũng nhƣ khả năng chịu lỗi, kiến trúc vòng đều đƣợc đánh giá cao. Vì vậy, kiến trúc Chord thƣờng hay đƣợc sử dụng nhƣ là mạng phủ để thực hiện các cài đặt cải tiến việc tìm kiếm trên ngang hàng có cấu trúc. 1.3.1 Mô hình mạng Chord Chord [3] cung có tính năng tính toán phân tán nhanh chóng nhờ vào việc sử dụng hàm băm để ánh xạ khóa với các nút chịu trách nhiệm trên mạng. Nhờ vào sử dụng DHT, các nút trong mạng Chord không cần biết tất cả các nút trong mạng. 13 Nút trong Chord chỉ cần biết một số nhỏ thông tin định tuyến về các nút khác. Trong mạng có n nút tham gia, mỗi nút chỉ cần duy trì O(logn) thông tin về các nút khác, do đó thông tin tìm kiếm chỉ là O(logn) thông điệp. Chord phải cập nhật thông tin định tuyến khi có nút mới tham gia và rời mạng, một nút tham gia và rời mạng cần đến O(log 2 n) thông điệp trao đổi. Chord [3] đƣợc mô tả dƣới dạng một vòng tròn và không gian định danh phân bố đều trên vòng tròn tăng dần theo chiều kim đồng hồ. Nếu gọi n là số bit định danh của không gian thì mạng Chord có thế chứa tối đa 2N nút. Mỗi nút trên Chord có một định danh id và duy trì liên kết hai chiều với nút đứng liền trƣớc và liền sau nó theo chiều kim đồng hồ tạo thành một mạch kiên kết vòng. Nút tiếp theo trong vòng tròn đƣợc gọi là Successor(id), và nút liền trƣớc trong vòng tròn đƣợc gọi là Predecessor(id). Thêm vào đó, một nút sẽ lƣu một bảng định tuyến gọi là bảng định tuyến (Finger Table), cho phép nút đó định tuyến tới các nút ở xa. Mỗi dòng trong bảng định tuyến sẽ lƣu thông tin về một nút ở xa, gọi là entry. Không gian định danh có bao nhiêu bit thì bảng định tuyến có bấy nhiêu entry. Các trƣờng trong mỗi entry trong bảng định tuyến đƣợc định nghĩa trong bảng 1: Ký hiệu finger[k].start Chú giải n + 2 ( k 1) mod 2 m , 1 <= k <= m, n là khóa định danh vòng Chord finger[k].interval (finger[k].start, finger[k + 1].start) finger[k].node Nút đầu tiên trên vòng Chord có giá trị định danh >= finger[k].start successor Nút tiếp theo trên vòng Chord, tƣơng đƣơng với finger[k].node predecessor Nút ngay phía trƣớc trên vòng Chord Bảng 1. Bảng định nghĩa các trƣờng trong bảng định tuyến của Chord Trong đó giá trị của trƣờng nút tại dòng i của bảng đƣợc coi nhƣ là finger thứ i của nút n. Thông tin lƣu trong bảng cũng bao gồm cả IP và Port của các nút liên quan. Nút đầu tiên trong bảng định tuyến của n chính là Successor của n, hay còn đƣợc gọi là Immediate Successor. Từ bảng định tuyến ở trên ta có thể thấy rằng:  Mỗi nút trong Chord chỉ cần lƣu trữ thông tin của một số nút nhất định trong bảng định tuyến của mình.  Nút biết thông tin về các nút gần nó nhiều hơn là các nút ở xa.