Khóa luận Nghiên cứu giải pháp tìm kiếm tài nguyên hiệu quảtheo tên miền trên mạng ngang hàng có cấu trúc

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đỗ Việt Kiên NGHIÊN CỨU GIẢI PHÁP TÌM KIẾM TÀI NGUYÊN HIỆU QUẢ THEO TÊN MIỀN TRÊN MẠNG NGANG HÀNG CÓ CẤU TRÚC KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin Cán bộ hướng dẫn: TS. Nguyễn Hoài Sơn HÀ NỘI - 2010 LỜI CẢM ƠN Em xin chân thành cảm ơn các thầy cô giáo trong trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình giúp đỡ và truyền đạt kiến thức cho em trong suốt 4 năm học qua để em có đủ kiến thức hoàn thành khóa luận này. Đặc biệt, em xin gửi lời cảm ơn sâu sắc tới thầy Nguyễn Hoài Sơn – người đã nhiệt tình giúp đỡ, định hướng cũng như động viên em trong quá trình nghiên cứu và hoàn thành khóa luận. Em xin cảm ơn sự nhiệt tình chia sẻ kinh nghiệm, đóng góp ý kiến của nhóm nghiên cứu do thầy Nguyễn Hoài Sơn hướng dẫn, của các anh chị cao học. Mặc dù đã rất cố gắng hoàn thành khóa luận này, xong khóa luận sẽ khó tránh khỏi những thiếu sót, kính mong quý thầy cô tận tình chỉ bảo giúp em. Một lần nữa em xin cảm ơn tất cả mọi người. Hà Nội, tháng 5 năm 2010 Sinh viên Đỗ Việt Kiên Tóm tắt Ngày nay, sự phát triển các dịch vụ cung cấp tài nguyên mạng khiến cho việc xây dựng một hệ thống có khả năng tìm kiếm nhanh các tài nguyên theo yêu cầu là rất cần thiết. Thách thức đặt ra là làm sao để hệ thống có thể hoạt động tốt trong những hệ thống mạng quy mô lớn nhưng tiềm tàng nhiều biến động. Một mối quan tâm khác là bằng cách nào người dùng có thể diễn tả và tìm kiếm được tài nguyên mà họ mong muốn. Khóa luận sẽ trình bày một giải pháp tìm kiếm thông tin trên hệ thống mạng ngang hàng với thành phần là các máy phân tích, đóng vai trò như những kho dữ liệu lưu trữ tài nguyên và xử lý các yêu cầu tìm kiếm. Giải pháp thực thi việc mô tả tài nguyên bằng một câu trúc cây thuộc tính-giá trị có khả năng biểu diễn cao, mô tả mềm dèo và chính xác tài nguyên. Tầng phủ DHT với cơ chế ánh xạ khóa đến dữ liệu được sử dụng giúp hệ thống đạt hiệu quả trong việc tìm kiếm nhanh và mở rộng quy mô. Tuy nhiên, để hỗ trợ việc tìm kiếm mở rộng sử dụng truy vấn tổng quát, giải pháp sẽ cung cấp thêm khả năng ánh xạ từ dải khóa đến tập hợp tài nguyên để cái tiến cơ chế một – một của các mạng DHT. Ngoài ra hệ thống cũng giải quyết được vấn đề cân bằng lưu trữ trên các máy phân tích. Mục lục Mở đầu ........................................................................................................................3 Chương 1. Tổng quan về tìm kiếm tài nguyên mạng ....................................................6 1.1. Tầm quan trọng của tài nguyên và các dịch vụ cung cấp tài nguyên................6 1.2. Tổng quan hệ thống tìm kiếm tài nguyên mạng ..............................................7 1.2.1. Giới thiệu...................................................................................................7 1.2.2. Diễn đạt tài nguyên....................................................................................7 1.2.3. Kiến trúc hệ thống ...................................................................................10 1.2.4. Tìm kiếm và phân bổ tài nguyên ..............................................................12 1.2.5. Đánh giá chung........................................................................................16 Chương 2. Tìm kiếm tài nguyên trên mạng ngang hàng có cấu trúc ...........................17 2.1. Tổng quan về mạng ngang hàng ...................................................................17 2.1.1. Khái niệm mạng ngang hàng....................................................................17 2.1.2. Đánh giá ưu nhược điểm của mạng ngang hàng .......................................18 2.2. Mạng ngang hàng có cấu trúc .......................................................................19 2.2.1. Kiến trúc mạng ........................................................................................19 2.2.2. Giao thức Chord ......................................................................................20 Mô hình mạng Chord ..........................................................................................21 Ánh xạ khóa vào một nút trong Chord.................................................................22 Tìm kiếm trong mạng Chord ...............................................................................22 Tham gia và ổn định mạng ..................................................................................23 2.3. Một số giải pháp về tìm kiếm tài nguyên trên mạng ngang hàng có cấu trúc. 23 2.3.1. Hệ thống INS/TWINE .............................................................................24 2.3.2. Data Indexing[4] .......................................................................................28 3.1. Vấn đề giải quyết..........................................................................................32 3.2. Ý tưởng ........................................................................................................34 3.3. Chi tiết giải pháp ..........................................................................................39 3.4. Đánh giá chung về giải pháp.........................................................................43 4.1. Môi trường mô phỏng...................................................................................44 4.1.1. Xây dựng chương trình mô phỏng............................................................44 4.1.2. Các tham số mô phỏng.............................................................................45 4.2. Đánh giá kết quả...........................................................................................47 4.2.1. Hiệu quả trong phân bổ tài nguyên...........................................................47 4.2.2. Hiệu quả trong xử lý truy vấn ..................................................................52 5.1. Kết luận........................................................................................................55 5.2. Hướng phát triển tiếp theo của đề tài ............................................................56 Tài liệu tham khảo .....................................................................................................57 1 Danh mục hình ảnh Hình 1: Mô tả tài nguyên dưới dạng cây......................................................................9 Hình 2:Mô tả tài nguyên dưới dạng các cặp thẻ [thuộc tính = giá trị] .......................10 Hình 3: Sơ đồ kiến trúc mạng INS..............................................................................11 Hình 4:Ví dụ về việc phân bổ tài nguyên trong hệ thống ............................................14 Hình 5 :Thuật toán tìm kiếm tài nguyên theo tên miền ...............................................15 Hình 9 : Một mạng Chord với 3 nút ...........................................................................21 Hình 10. Lưu giữ key trong mạng Chord....................................................................22 Hình 11: Ví dụ về mô tả tài nguyên trong INS/TWINE ...............................................24 Hình 12: Kiến trúc của hệ thống INS/TWINE ............................................................25 Hình 13: Ví dụ về việc chia nhánh từ cây avtree ........................................................25 Hình 14: Việc quản lý trạng thái trong hệ thông INS/Twine.......................................27 Hình 15 Ví dụ về đặc tả file trong hệ thống Indexing ................................................28 Hình 16: Đồ thị biểu diễn các câu truy vấn được đưa ra trong ví dụ.........................29 Hình 17 : Lược đồ chỉ mục cho dữ liệu cây thư mục (bibliographic database)...........30 Hình 18 : Ví dụ về index dữ liệu.................................................................................31 Hình 19: Ví dụ về mô tả tài nguyên của hệ thống .......................................................35 Hình 21 : Ví dụ về mô tả truy vấn trong giải pháp .....................................................41 Hình 22: Biều đồ phân tích số lượng bản sao thực hiện trên mỗi tài nguyên, trường hợp cây mô tả chung chia 2 nhánh tại mỗi nút ...........................................................48 Hình 23 :Biều đồ phân tích số lượng bản sao thực hiện trên mỗi tài nguyên, trường hợp cây mô tả chung chia 3 nhánh tại mỗi nút ...........................................................49 Hình 24: Biều đồ phân tích số lượng bản sao lưu trên mỗi nút mạng, trong trường hợp cây mô tả chung chia 2 nhánh tại mỗi nút ...........................................................50 2 Hình 25: Biều đồ phân tích số lượng bản sao lưu trên mỗi nút mạng, trong trường hợp cây mô tả chung chia 4 nhánh tại mỗi nút ...........................................................51 Hình 26 : Biều đồ phân tích số lượng bản sao lưu trên mỗi nút mạng, trong trường hợp cây mô tả chung chia 6 nhánh tại mỗi nút ...........................................................52 Hình 27: Biều đồ đánh giá hiệu quả của truy vấn thông qua số lượng các hope trên mỗi truy vấn...............................................................................................................53 Hình 28: Biểu đồ đánh giá hiệu quả của việc thực hiện truy vấn thông qua số lượng truy vấn / 1 nút mạng .................................................................................................54 3 Mở đầu Trong những năm gần đây, Internet đã không còn xa lạ đối với đời sống con người. Sự phát triển và lớn mạnh của Internet giúp cho con người có thể trao đổi,chia sẻ thông tin hay tài nguyên một cách dễ dàng hơn. Tuy nhiên lượng thông tin là vô cùng lớn và không phải thông tin nào cũng hữu ích đối với tất cả mọi người, mỗi một cá nhân khác nhau có nhu cầu về thông tin khác nhau. Do đó việc xây dựng một hệ thống tìm kiếm thông tin, tài nguyên mạng là rất cần thiết. Các máy tìm kiếm phổ biết nhất có thể kể đến đó là Google[15], Yahoo[16], ngoài ra còn rất nhiều những hệ thống tìm kiếm tương tự khác. Điểm chung của các hệ thống này là chỉ hỗ trợ việc tìm kiếm dựa từ khóa xuất hiện trên nội dung của các websites. Chúng không cung cấp khả năng tìm kiếm thông tin đối với nhiều loại tài nguyên khác nhau như các dịch vụ cung cấp thông tin trực tuyến, hay một dạng tài nguyên rất phổ biến khác đó là các files tài nguyên được chia sẻ trên mạng ngang hàng. Hệ thống DNS[9] có thể được xem là một hệ thống tìm kiếm tài nguyên đơn giản, ánh xạ tên miền tới IP. Nhưng mô tả tài nguyên trong hệ thống này là chưa hiệu quả với những tài nguyên phức tạp có nhiều thuộc tính. Việc xây dựng một hệ thống tìm kiếm tài nguyên là không hề đơn giản, nó phải chịu sự tác động từ rất nhiều yếu tố. Trước tiên, hệ thống luôn phải chịu tác động của sự thay đổi động trong trong các hệ thống mạng, ví dụ như : việc ra vào của các nút, thay đổi vị trí, địa chỉ của các thiết bị ... Sự thay đổi thường xuyên trong những mạng như vậy là thách thức với việc định vị thiết bị và tài nguyên trong quá trình tìm kiếm. Thứ hai, là thách thức trong việc lưu trữ số lượng lớn tài nguyên trong hệ thống. Với sự phát triển về số lượng các dịch vụ theo nhu cầu của người sử dụng thì số lượng tài nguyên cũng không ngừng tăng lên và việc phân bổ lưu trữ chúng hợp lý sẽ là một vấn đề quan trọng. Thêm vào đó các tài nguyên cũng cần được cập nhật thường xuyên và hệ thống cần phải có cơ chế giúp các nhà cung cấp dịch vụ thực hiện điều này. Để xây dựng được một hệ thống hoạt động hiệu quả, hệ thống cần hiện được một số yêu cầu quan trọng. Thứ nhất, cần có một các thức mô tả tài nguyên tốt, mang tính biểu đạt cao, có thể diễn đạt mềm dẻo các tích chất đa dạng của tài nguyên. Thứ hai, hệ thống phải có khả năng mở rộng tốt để có thể triển khai trên những quy mô mạng lớn. Thứ ba, hệ thống phải đảm bảo hiệu quả trong tìm kiếm và phân bổ tài nguyên. Hiệu quả trong tìm kiếm được đánh giá qua thời gian thực hiện yêu cầu và việc cân bằng tải giữa các nút trong hệ thống trước nhiều yêu cầu về tìm kiếm. Hiệu quả trong phân bổ tài nguyên được đánh giá thông qua số lượng bản sao so với tài nguyên thực 4 và cân bằng lưu trữ tài nguyên giữa các nút mạng. Cuối cùng, cần phải luôn đảm bảo tính sẵn sàng của hệ thống trước những vấn đề về hỏng hóc, bảo trì, hay cập nhật thiết bị. Khóa luận sẽ đưa ra một giải pháp cụ thể dựa trên những luận điểm trên... Một hệ thống có khả năng diễn đạt tài nguyên tốt đó là hệ thống INS với việc sử dụng bộ định danh để biểu diễn các cặp thuộc tính – giá trị một cách có thự tự, theo cấu trúc phân cấp. Mỗi một mô tả có được khi sử dụng bộ định danh sẽ tương đương với một cây thuộc tính – giá trị. Để đảm bảo khả năng tìm kiếm và phân bố hiệu quả hệ thống đề xuất việc sử dụng mạng ngang hàng có cấu trúc. Trong mạng ngang hàng có cấu trúc, các thông điệp được định tuyến theo khóa một cách hiệu quả với số hop khoảng O(logN) trong đó N là số node trong mạng. Các ưu điểm khác của mạng này là đem lại cho hệ thống khả năng mở rộng, tính sẵn sàng trong các trường hợp xử lý lỗi và đảm bảo cân bằng tải giữa các nút. Tuy nhiên, giải thuật bảng băm phân tán chỉ hỗ trợ tìm kiếm chính xác tài nguyên theo khóa tương ứng, trong khi đó hệ thống của chúng ta cần có khả năng trả lời những truy vấn theo dải (partial query). Khóa luận đề xuất việc tìm kiếm theo dải ID, việc thực hiện bằng cách xây dựng một cấu trúc cây lưu trữ dựa trên dải ID cấp phát bởi mạng ngang hàng phía dưới. Việc xây dựng như sau, tại tầng đầu nút root của cây sẽ quản lý toàn bộ dải ID, ở các tầng tiếp theo, dải ID được chia nhỏ cho các nút con quản lý, thông tin về tài nguyên thực sự chỉ được lưu tại các nút lá. Nhờ đó, khi tìm kiếm đến một nút hệ thống sẽ ánh xạ đến dải ID mà nó quản lý, nếu nút không phải nút lá, dải ID của nó sẽ chứa toàn bộ dải ID của các nút lá nhờ đó việc tìm kiếm trên dải ID này sẽ cho kết quả là tập hợp các tài nguyên thỏa mãn yêu cầu chứa tại các nút lá. Việc sử dụng dải ID để ánh xạ còn giúp hệ thống chống chịu tốt hơn với việc hỏng hóc của các nút mạng, khi một nút mạng rời đi các nút mạng cùng dải ID vẫn có thể trả lời kết quả. Để đánh giá hiệu quả của giải pháp đề xuất, khóa luận xây dựng một chương trình mô phỏng với số lượng lớn các nút mạng ảo và tài nguyên ảo. Các kết quả thử nghiệm sẽ chứng minh cho hiệu quả của giải pháp đề ra. Khóa luận được chia thành năm chương: Chương 1: Giới thiệu tổng quan về tầm quan trọng của tài nguyên và các dịch vụ cung cấp tài nguyên, sơ lược về một hệ thống tìm kiếm tài nguyên mạng 5 Chương 2: Đề cập đến việc thực hiện hệ thống tìm kiếm tài nguyên trên mạng ngang hàng có cấu trúc, ưu điểm của nó và giới thiệu một số hệ thống đã được thực thi. Chương 3: Từ các hệ thống và phương pháp giải quyết đã được trình bày trong 2 chương trước đưa ra các đánh giá chung và mục tiêu phát triển. Trên cơ sở đó đề đạt ý tưởng và giải pháp để xây dựng hệ thống chia sẻ tài nguyên. Chương 4: Xây dựng chương trình mô phỏng, các bước thực thi chương trình và những đánh giá từ kết quả đạt được. Chương 5: Kết luận, những vấn đề nảy sinh và hướng đi tiếp theo. 6 Chương 1. Tổng quan về tìm kiếm tài nguyên mạng Tìm kiếm tài nguyên hay thuật ngữ tiếng anh là Resource Discovery đã được sử dụng từ lâu trên các hệ thống mạng đặc biết là trong mạng Internet ngày nay. Trong nỗ lực khiến cho việc tìm kiếm tài nguyên mạng trở nên dễ sử dụng với người dùng nhiều hệ thống tìm kiếm trong lĩnh vực này đã được ra đời. Chương này, khóa luận sẽ giới thiệu tổng quan về thế nào là tài nguyên mạng và tầm quan trọng của chúng cũng như các dịch vụ cung cấp chúng, các vấn đề trong việc xây dựng một hệ thống tìm kiếm tài nguyên, những tiêu chí được đề ra cho một hệ thống được cho là hoàn chỉnh. 1.1. Tầm quan trọng của tài nguyên và các dịch vụ cung cấp tài nguyên. Định nghĩa Tài nguyên mạng, là những thứ trực tiếp cung cấp thông tin hay khả năng sử dụng đối với một người dùng mạng. Mọi tài nguyên đều được định nghĩa bởi một tập hợp các thuộc tính. Mỗi thuộc tính thể hiện một tính chất của tài nguyên, có thể là các tính chất về hình dạng như chiều dài, chiều rộng, … cũng có thể là các tính chất về chất liệu hay các mối quan hệ phụ thuộc. Các tài nguyên mạng phổ biến nhất gồm các tài nguyên mềm như là tệp tin, tất cả các dạng như âm thanh, hình ảnh, dữ liệu,... hoặc các tài nguyên phần cứng như camera, máy in, … Tầm quan trọng của tài nguyên Với sự phát triển của công nghệ thông tin ngày nay, đặc biệt là sự phát triển của các mạng không dây và di động khiến cho nhu cầu về thông tin của con người cũng phát triển mạnh mẽ hơn. Con người có thể thỏa mãn nhu cầu thông tin ở mọi nơi và mọi lúc chỉ với một thiết bị di động trong tay, các hình thức của thông tin cũng đa dạng hơn rất nhiều, từ dữ liệu về chữ viết đến hình ảnh hay thậm chí là video cũng trở nên thường xuyên hơn. Từ nhu cầu thông tin của con người các dịch vụ cung cấp chúng được phát triển nhanh chóng cả về chất lượng lẫn số lượng, các dịch vụ này tập trung vào khai thác những nhu cầu tìm kiếm thông tin của con người trong cuộc sống, và truyền tải nó thông qua các hệ thống mạng mà điển hình là các mạng di động. Một ví dụ điển hình như dịch vụ cung cấp hình ảnh được truyền tải từ camera giao thông trong một thành phố, các hình ảnh về tình trạng giao thông trên các tuyến đường, sự cố tắc nghẽn hay 7 các thông tin liên quan. Qua đó có thể thấy tầm quan trọng của các dịch vụ cung cấp tài nguyên là rất quan trọng đối với cuộc sống hiện đại ngày nay. Vấn đề là làm sao để thực hiện được một hệ thống cung cấp hiệu quả nhưng vẫn phải mang tính thuận tiện với người sử dụng. 1.2. Tổng quan hệ thống tìm kiếm tài nguyên mạng Như đã trình bày trong phần trước, việc xây dựng và cung cấp một hệ thống tìm kiếm tài nguyên là rất quan trọng, trong phần này ta sẽ trình bày cụ thế về một hệ thống hoàn chỉnh. 1.2.1. Giới thiệu Một hệ thống tìm kiếm tài nguyên hoàn chỉnh đòi hỏi rất nhiều tiêu chí, các tiêu chí đánh giá nhằm giúp hệ thống có được hiệu quả trong việc triển khai thực tế. Dựa trên cơ bản về môi trường thực thi và các ứng dụng của hệ thống, hệ thống được xây dựng theo 4 tiêu chí :
Tính diễn đạt : hệ thống tên miền sử dụng phải thật sự linh hoạt để có thể vẫn dụng trên các thiết bị di động và các dịch vụ khác nhau nhưng vẫn phải đảm bảo khả năng diễn đạt một cách mềm dẻo và chính xác các tài nguyên trong hệ thống cũng như các truy vấn dùng khi tìm kiếm.
Phản hồi nhanh : hệ thống cần có đáp ứng nhanh các yêu cầu về tìm kiếm cũng như yêu cầu chia sẻ tài nguyên mới.
Tính vững chắc : hệ thống cần phải có khả năng ổn định khi gặp các vấn đề về tải và lưu lượng đường truyền trên mạng, ngoài ra khả năng phục hồi lỗi và sửa chữa nhanh là rất quan trọng.
Dễ cài đặt : hệ thống nên mang tính tự động và giảm thiểu các yêu cầu can thiệp từ bên ngoài ở mức thấp nhất. 1.2.2. Diễn đạt tài nguyên Các vấn đề trong diễn tả tài nguyên Các ứng dụng trong môi trường mạng thông thường không thể biết được chính xác vị trí mạng có thể thỏa mãn được yêu cầu thông tin của nó. Do đó chúng ta sẽ tập trung vào giải quyết vấn đề làm sao cho các ứng dụng này có thể diễn tả được chúng “tìm kiếm cái gì?” thay cho việc “tìm kiếm ở đâu?”. Vậy làm 8 sao để diễn tả chính xác và hiệu quả được những tài nguyên mà ứng dụng tìm kiếm? Hệ thống INS[2] đã đưa ra giải pháp rất tốt để giải quyết cho vấn đề này. Hệ thống INS hay chính xác là Intentional Naming System là một thiết kế và thực thi của một hệ thống tìm kiếm tài nguyên và dịch vụ trên các môi trường mạng có tính biến thiên cao. INS sử dụng tên miền khái niệm để diễn đạt tài nguyên và ánh xạ từ tên miền đến tài nguyên được cất giữ trong hệ thống. INS sử dụng một ngôn ngữ đặc trưng