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 để diễn đạt tài nguyên có tên gọi là Intentional Naming Language. Về cơ bản, ngôn ngữ này dựa trên hệ thống thứ bậc các cặp thuộc tính và giá trị. Điều này cho phép các nhà cung cấp dịch vụ có thể diễn đạt chính xác thứ họ cung cấp và phía người dùng có thể diễn tả chính xác thứ họ yêu cầu. Việc tìm kiếm tài nguyên dựa trên các mô tả còn cho phép các ứng dụng sử dụng INS có khả năng duy trì tìm kiếm ngay cả khi ví trí của các thiết bị tham gia mạng thay đổi, điều thường xuyên diễn ra tại các môi trường mạng có tính biến thiên lớn như các mạng không dây và di động. Để có thể phản hồi nhanh trước các truy vấn tìm kiếm, hệ thống INS không chỉ sử dụng tên miền để tìm kiếm tài nguyên (hay dịch vụ) mà còn sử dụng chúng để định tuyến các thông điệp truy vấn, việc định tuyến này cần được phân biệt với định tuyến ở tầng mạng. Các máy phân tích dựa vào tên miền được sử dụng để định danh ra các máy phân tích khác mà nó có thông tin (Các thông tin có thể là : địa chỉ IP, thông tin về tên miền lưu trữ, …) và chuyển tiếp thông điệp đến các máy phân tích này. Bộ định danh Được INS dùng để đánh tên miền, bộ định danh được các máy khách sử dụng trong trường tiêu đề của thông điệp gửi đi trong hệ thống. Từ các tên miền được mô tả, thông điệp nhận biết được đích đến cũng như nguồn gốc của thông điệp. Bộ định danh được thiết kết đơn giản và dễ dàng để thực thi. Hai phần chính trong bộ định danh đó là “thuộc tính” và “giá trị”. Một “thuộc tính” là một tiêu chí được sử dụng để phân loại đối tượng (ví dụ: thuộc tính có thể là màu sắc). “giá trị” chính là giá trị mà đối tượng nhận được trong tiêu chí đánh giá đó (ví dụ : giá trị trong trường hợp này là đỏ). Thuộc tính và giá trị đều được biểu diễn 9 dưới dạng một xâu kí tự bất biến được định nghĩa bởi ứng dụng. Mỗi một thuộc tính cùng với giá trị tương ứng với nó tạo thành một cặp thuộc tính giá trị. Mỗi một định danh là một sự sắp đặt theo thứ bậc của các cặp thuộc tính và giá trí qua đó các cặp thuộc tính giá trị kế thừa (con, cháu) sẽ phụ thuộc vào các cặp được kế thừa (cha, ông) . Như trong hình 1 bên dưới ta thấy được “building” với tên gọi “whitehouse” hoàn toàn thuộc và “city” với tên gọi “washington” do đó cặp thuộc tính giá trị “building-whitehouse” là phụ thuộc vào cặp “city- washington”. Các cặp thuộc tính được gọi là “trực giao” nếu chúng cùng phụ thuộc vào một cặp thuộc tính khác và là anh em của nhau trên cây thuộc tính – giá trị. Trong ví dụ thể hiện bộ định danh ở hình 2, data-type và resolusion có ý nghĩa độc lập lẫn nhau và theo đó 2 cặp thuộc tính – giá trị là “datatype-picture” và “resolusion-640x480” là 2 cặp thuộc tính - giá trị “trực giao”. Cách mô tả theo thứ tự của cây thuộc tính – giá trị giúp một định danh trở nên dễ hiểu hơn và làm cho việc phân loại tài nguyên hiệu quả hơn. Hình 1: Mô tả tài nguyên dưới dạng cây Một hình thức mô tả tài nguyên khác cũng tỏ ra hiệu quả và đơn giản không kém được bộ định danh sử dụng thường xuyên hơn trong các thông điệp trao đổi. Mô tả được thể hiện như trong hình 2 dưới dạng các thẻ dữ liệu được lồng ghép 10 Hình 2:Mô tả tài nguyên dưới dạng các cặp thẻ [thuộc tính = giá trị] Việc mô tả như trong hình 2 vẫn giữ được hệ thống thứ bậc đối với các cặp thuộc tính giá trị nhưng dễ dàng hơn cho máy tính trong quá trình thực hiện phân tích tài nguyên từ bộ định danh. 1.2.3. Kiến trúc hệ thống Để tìm kiếm và phân bổ tài nguyên hệ thống cần có một hệ thống máy xử lý các yêu cầu của nhà cung cấp dịch vụ và người sử dụng. Các hệ thống xử lý thường là một mạng phân tán bao gồm nhiều máy phân tích tham gia trong việc tìm kiếm tên miền và chuyển thông điệp. Một cách dễ thực hiện, các máy phân tích nên được tự động cấu hình, cập nhật dữ liệu khi tham gia vào hệ thống. Người dùng hoàn toàn có thể có được thông tin mong muốn từ một máy phân tích bất kì trong hệ thống. Một tính năng thường thấy ở các hệ thống tìm kiếm tài nguyên đó là khả năng lớn mạnh và dễ dàng triển khai trên mạng Internet mà không cần thay đổi hay loại bỏ bất kì mô hình hay cấu trúc mạng sẵn có nào. Các hệ thống thường được xây dựng như là một ứng dụng đặt trên nền tảng của tầng mạng, nơi mà các thông điệp được đánh địa chỉ và định tuyến thực sự. Các dịch vụ chỉ được phép cung cấp tài nguyên và thông tin diễn tả chúng, còn người sử dụng cũng không cần quan tâm đến kiến trúc mạng cũng như cấu hình phía dưới mà trực tiếp tìm kiếm tài nguyên dựa trên các mô tả đặc trưng. Ứng dụng trên các máy phân tích sẽ thực hiện phân tích tên miền theo mô tả và chọn giải pháp trả lời truy vấn hoặc gửi đến các máy phân tích khác mà nó có thông tin. Toàn bộ việc định tuyến và đánh địa chỉ đều được thực hiện bởi tầng mạng. Khóa luận sẽ giới thiệu về kiến trúc của INS như là một ví dụ cụ thể cho kiến trúc hoàn chỉnh của hệ thống tìm kiếm tài nguyên. Trong INS các ứng dụng có thể là các dịch vụ hoặc các ứng dụng khách hàng, dịch vụ cung cấp chức năng 11 và dữ liệu, khách hàng yêu cầu và truy cập vào dữ liệu thông qua hệ thống. Kiến trúc của hệ thống INS như trong hình 3 được chia làm 2 phần chính:
Trung tâm của hệ thống là các máy phân tích (INR)
Phía rìa của hệ thống là các dịch vụ và các máy khách trực tiếp gửi yêu cầu về quảng bá cũng như tìm kiếm tài nguyên trên hệ thống. Hình 3: Sơ đồ kiến trúc mạng INS Các INRs (Intentional Name Resolovers) mà ta sẽ gọi là các “máy phân tích” làm nhiệm vụ định tuyến cho các yêu cầu đến được với các dịch vụ tương ứng, tại các máy phân tích một thuật toán và giao thức đơn giản sẽ được thực thi để đảm bảo nó có thể hoạt động tốt ngay cả với những máy tính có khả năng tính toán thấp. Các máy phân tích làm việc trên tầng ứng dụng phía trên của mạng để trao đổi những mô tả về dịch vụ và xây dựng một cơ sở lưu trữ nội bộ. Mỗi dịch vụ gắn với một máy phân tích bất kì và thông báo cơ sở dữ liệu về thuộc tính giá trị, mô tả dịch vụ, ứng dụng điểu khiển. Mỗi máy khách giao tiếp với một máy phân tích bất kì khác và gửi yêu cầu với một truy vấn mô tả, do mô tả dịch vụ được rải trên hệ thống các máy phân tích nên mỗi dịch vụ mới sẽ được quảng bá bởi các máy phân tích trong hệ thống và đến được với máy khách yêu cầu dịch vụ. Khi một thông điệp được gửi từ bên ngoài đến một máy phân tích, yêu cầu của thông điệp sẽ được xử lý trên cơ sở của tên đích đến. Máy phân tích sẽ quyết định xử lý trực tiếp yêu cầu hay chuyển tiếp xử lý sang các máy phân tích khác tùy thuộc vào đặc tính của dịch vụ hay tài nguyên được yêu cầu. Thông điệp 12 trong hệ thống INS có hỗ trợ cho lựa chọn đặc biệt là early-binding flag, khi một thông điệp truy vấn có sử dụng lựa chọn này máy phân tích sẽ lập tức trả về một danh sách các IP tương ứng với tên miền được dùng trong truy vấn để trả lời, với danh sách các IP này máy khách có thể lựa chọn một thiết bị cuối có khoảng cách gần nhất để lấy dữ liệu hay tài nguyên mà nó tìm kiếm. Trong trường hợp xử lý muộn (không sử dụng lựa chọn early-binding flag) hệ thống hỗ trợ 2 tùy chọn để xử lý thông điệp đó là : intentional anycast và intentional multicast. Chúng sẽ giúp cho hệ thống linh hoạt hơn trong những hoàn cảnh thay đổi. Ở đây, các địa chỉ IP không được trả lại trực tiếp cho các máy khách , nhưng thay vào đó yêu cầu sẽ được chuyển tiếp đến các máy phân tích khác, với lựa chọn intentional anycast nó sẽ gửi đến chính xác một máy phân tích khác có khả năng trả lời yêu cầu tốt nhất, với lựa chọn còn lại yêu cầu sẽ được gửi đến toàn bộ các máy phân tích trong danh sách lưu trữ của máy phân tích đang trả lời. Hệ thống máy phân tích được tự động cấu hình trên cây “spanning tree” phủ trên topology của tầng mạng, tối ưu hóa thời gian trễ giữa các máy phân tích. Spanning tree cũng được sử dụng trong việc quảng bá các dịch vụ đến các máy phân tích trong hệ thống, hay gửi tin nhắn tìm kiếm. Trong hệ thống INS, các máy phân tích được ứng cử và danh sách các hoạt động mà chúng thực hiện được duy trì bởi một đối tượng của hệ thống gọi là Domain Space Resolver (DSR). DSR được cho là giống như một hệ thống DNS mở rộng dùng để quản trị miền đang chứa chính bản thân nó bến trong. Khi một máy phân tích mới muốn gia nhập và hệ thống cần được liên hệ trước với DSR để lấy danh sách các máy phân tích đang hoạt động và sau đó chọn ra một máy phân tích có kết quả “ping” đến nó nhỏ nhất và công bó làm hàng xóm. 1.2.4. Tìm kiếm và phân bổ tài nguyên Trong phần trước ta đã nói về kiến trúc của một hệ thống tìm kiếm tài nguyên, các thành phần hoạt động trong hệ thống, công việc mà chúng phụ trách cũng như mối liên hệ giữa các thành phần. Trong phần này ta sẽ trình bày việc làm sao để hệ thống có thể phân bổ và tìm kiếm tài nguyên trên các máy phân tích trong mạng phân tích mà ta đã đề cập đến. Phân bổ tài nguyên 13 Trong hệ thống, các dịch vụ theo chu kì quảng cáo về tên miền mà chúng cung cấp với một trong các máy phân tích, các tài nguyên theo đó được chuyển vào hệ thống cùng với tên miền mô tả chúng. Mỗi máy phân tích lắng nghe trên một cổng định trước các thông báo để lấy thông tin của các dịch vụ đang chạy trên những thiết bị cuối hay các máy phân tích khác. Các máy phân tích có nhiệm vụ rải rắc thông tin về tài nguyên trong mạng phân tích. Công việc này được thực hiện bởi 1 giao thức định tuyến kết hợp với định kì cập nhật và cập nhật khi có yêu cầu đề cập nhật thông tin giữa các máy phân tích là hàng xóm của nhau. Ta sẽ tìm hiểu làm thế nào một máy phân tích lưu trữ tài nguyên. Việc lưu trữ tài nguyên sẽ phụ thuộc vào cách thức diễn tả tài nguyên đã được đưa ra. Do đó trong khóa luận ta sẽ tìm hiểu cách thức phân bổ và lưu trữ tài nguyên dựa trên mô tả có được từ bộ định danh của INS. Hệ thống sử dựng “name-trees” mà sau này ta sẽ dùng thuật ngữ cây tên miền để lưu trữ tương ứng giữa một định danh với một bản ghi dữ liệu tài nguyên. Thông tin chưa trong một bản ghi dữ liệu bao gồm định tuyến đến những máy phân tích phù hợp tiếp theo ( next-hop INR), địa chỉ IP của đích đến hoặc thời hạn của bản ghi (khoảng thời gian tồn tại có giá trị của bản ghi tài nguyên). Cấu trúc của một cây tên miền gần giống cấu trúc cây được bộ định danh sử dụng bao gồm các tầng luân phiên của các cặp thuộc tính – giá trị, nhưng có sự khác biết đó là một thuộc tính có thể bao gồm nhiều giá trị tương ứng với nó, điều này có thể hiểu đơn giản khi trong hệ thống chứa nhiều tài nguyên tương tự nhau có cùng các tiêu chí đánh giá tương ứng với các thuộc tính được mô tả, nhưng mỗi tài nguyên lại cho mỗi giá trị phân biệt ứng với các thuộc tính. Một cây tên miền sẽ là một sự tổng hợp của các cây định danh mà máy phân tích biết đến. Hình 4 mô tả một cây tên miền tương ứng với các bộ định danh mà một trong số đó được mô tả trong hình 1. 14 Hình 4:Ví dụ về việc phân bổ tài nguyên trong hệ thống Tìm kiếm tài nguyên Thuật toán tìm kiếm theo tên miền sử dụng truy vấn là một định danh có được theo cách thức mô tả của hệ thống để tìm chính xác tài nguyên mà định danh mô tả, định danh sẽ được chuyển đến các máy phân tích, tại các máy phân tích cụ thể thuật toán tìm kiếm nội bộ sẽ được sử dụng để tìm ra bản ghi tương ứng với tài nguyên. Kết quả tổng hợp từ tất cả các máy phân tích trong hệ thống. Trong hình 5 là mô tả về thuật toán tìm kiếm được sử dụng trong hệ thống INS, ý tưởng chung của thuật toán này là chuyển tên miền tìm kiếm theo kiểu flooding từ một máy phân tích. Thuật toán sử dụng những lời gọi để quy để giảm 15 dần số lượng các bản ghi phù hợp với truy vấn, tập hợp các bản ghi được đề cử ban đầu là toàn bộ các bản ghi có thể của hệ thống (kí hiệu tập hợp này là S). Hình 5 :Thuật toán tìm kiếm tài nguyên theo tên miền Với mỗi cặp thuộc tính – giá trị nằm trong định danh thuật toán sẽ bắt đầu tìm kiếm với node thuộc tính trong cây tên miền của máy phân tích, nếu node giá trị trong bộ định danh mang giá trị tự do (thể hiện bởi dấu *) thì tập hợp S sẽ được thay thế bởi S’ là hợp của tất cả các bản ghi thuộc về cây con với gốc là node con của node thuộc tính được dùng để bắt đầu tìm kiếm. Nếu giá trị của node thuộc tính không mang giá trị tự do, thuật thoán sẽ tiếp tục với node giá trị tương ứng với node thuộc tính đã được dùng đến. Khi đó nếu node giá trị là node lá của cây định danh hay cây tên miền thuật toán sẽ trả về bản ghi có trong node giá trị đang được gọi đến. Ngược lại thuật toán sẽ gọi đệ quy đến toàn bộ cây định danh có root là node con của node giá trị đang được gọi đến. 16 1.2.5. Đánh giá chung Việc phân bổ tài nguyên sẽ đánh giá tính hiệu quả hầu hết các hoạt động của hệ thống vì thế người thiết lập hệ thống cần phải chú trọng để xử lý thật tốt. Hệ thống INS cho thấy ưu điểm lớn trong việc mô tả tài nguyên, không chỉ giúp phân loại tài nguyên tốt, mà còn có khả năng diễn đạt tốt đối với cả máy tính và con người (những người xây dựng ứng dụng). Việc sử dụng tên miền để tìm kiếm tài nguyên thay thế cho việc định vị chính xác tài nguyên là một giải pháp tốt phù hợp tính biến động của kiến trúc mạng ngày nay khi phải tích hợp với nhiều thiết bị di động có tính biến thiên cao. Có thể nói tính năng này của INS tương đương với việc thay thế câu hỏi tìm kiếm tài nguyên ở đâu? bằng câu hỏi tìm kiếm cái gì?. Rất đơn giản, chỉ cần đưa ra mô tả về tài nguyên muốn tìm kiếm hệ thống sẽ tìm kiếm tài nguyên mà không quan tâm đến việc cấu trúc mạng hay địa chỉ IP biến đổi liên tục trong hệ thống. Kiến trúc phân tán đối hệ thống là không thể tách rời. Tuy nhiên hệ thống cần phải có một thuật toán tìm kiếm hiệu quả hơn là truyền flooding giữa các máy phân tích. Hệ thống INS cho thấy rõ nhược điểm trong trường hợp này, nó khiến cho khả năng mở rộng của hệ thống sẽ bị ảnh hưởng rất nhiều. Rõ ràng việc không có được khả năng mở rộng là hạn chế rất lớn, vì các ứng dụng tìm kiếm tài nguyên với tầm quan trọng của nó cần được thực hiện trên những kiến trúc mạng lớn có thể vươn tới tầm cỡ như mạng Internet. Ta hy vọng sẽ tìm ra những giải pháp mới cho hệ thống để hạn chế được vấn đề này. 17 Chương 2. Tìm kiếm tài nguyên trên mạng ngang hàng có cấu trúc Trong chương một, khóa luận đã giới thiệu về tầm quan trọng của tài nguyên và các dịch vụ cung cấp chúng đối với cuộc sống công nghệ thông tin ngày nay. Ngoài ra khóa luận cũng đề cập đến các bước trong việc thực hiện xây dựng hệ thống tìm kiếm tài nguyên mạng, bao gồm biểu diễn tài nguyên, thiết kế thuật toán tìm kiếm và phân bổ tài nguyên trong hệ thống. Tiếp theo, chương hai của khóa luận sẽ đưa ra một số giải pháp thực thi khác khả năng tìm kiếm và phân bổ tài nguyên tương đối hiệu quả. Các hệ thống được trình bày đều được đặt trên cơ sở là những mạng ngang hàng có cấu trúc, sử dụng bảng băm phân tán – DHT[10] để định tuyến các thông điệp. 2.1. Tổng quan về mạng ngang hàng 2.1.1. Khái niệm mạng ngang hàng Mạng ngang hàng [8], là mạng mà trong đó hai hay nhiều máy tính chia sẻ tập tin và truy cập các thiết bị như máy in mà không cần đến máy chủ hay phần mềm máy chủ. Hay ở dạng đơn giản nhất, mạng p2p được tạo ra bởi hai hay nhiều máy tính được kết nối với nhau và chia sẻ tài nguyên mà không phải thông qua một máy chủ dành riêng. Mạng ngang hàng có thể là kết nối tại chỗ – hai máy tính nối với nhau qua cổng USB để truyền tập tin. Mạng ngang hàng cũng có thể là cơ sở hạ tầng thường trực kết nối 5, 6 máy tính với nhau trong một văn phòng nhỏ bằng cáp đồng. Hay nó cũng có thể là một mạng có quy mô lớn hơn nhiều, dùng các giao thức và ứng dụng đặc biệt để thiết lập những mối quan hệ trực tiếp giữa người dùng trên Internet. Cấu trúc mạng ngang hàng là biểu hiện của một trong những khái niệm quan trọng nhất của Internet, mô tả trong "RFC 1, Host Software" xuất bản ngày 7 tháng 4 năm 1969. Gần hơn, khái niệm này đã được sự công nhận rộng rãi trong các cấu trúc chia sẻ nội dung mà không có máy chủ trung tâm. Hình 6. Mô hình mạng ngang hàng 18 Mô hình mạng ngang hàng (Hình 6) không có khái niệm máy chủ và máy khách, nói cách khác, tất cả các máy tham gia đều bình đẳng và được gọi là peer, là một nút mạng đóng vai trò đồng thời là máy khách và máy chủ đối với các máy khác trong mạng. Với mô hình khách chủ (Hình 7), máy khách gửi yêu cầu, thực hiện việc nhận dữ liệu một chiều từ phía máy chủ. Mạng ngang hàng thế hệ thứ nhất sử dụng một máy chủ trung tâm cho một số tác vụ. Tiếp đến thế hệ thứ 2 với việc cải tiến sử dụng mô hình ngang hàng cho tất cả các tác vụ, nên các mạng này thường được xem như là mạng ngang hàng đúng nghĩa. Ngày nay thế hệ mạng ngang hàng thứ 3 tức mạng ngang hàng có cấu trúc được chú ý rất nhiều do đặc tính ưu việt của nó so với các thế hệ trước. Chi tiết về thế hệ thứ 3 này sẽ được trình bày cụ thể trong phần sau. 2.1.2. Đánh giá ưu nhược điểm của mạng ngang hàng Ưu điểm Không cần server riêng, các client chia sẻ tài nguyên. Khi mạng càng được mở rộng thì khả năng hoạt động của hệ thống càng tốt. Khắc phục nhược điểm “nút cổ chai” trong mô hình mạng máy khách – máy chủ. Thuận lợi cho việc chia sẽ file, máy in, CD-ROM v.v… Tính chất phân tán của mạng ngang hàng cũng giúp cho mạng hoạt động tốt khi một số máy gặp sự cố. Đối với cấu trúc tập trung, chỉ cần máy chủ gặp sự cố thì cả hệ thống sẽ ngưng trệ. Mô hình mạng ngang hàng dễ cài đặt và tổ chức và quản trị, chi phí thiết bị thấp. Ngày nay, các máy tính cá nhân đủ mạnh để có thể làm nhiều hơn công việc của một client, do đó khi tham gia vào mạng ngang hàng là rất khả thi. Nhược điểm Hình 7. Mô hình mạng khách chủ 19 Trong mạng ngang hàng dữ liệu thường chỉ được chuyển giao trong khoảng thời gian ngắn và với số lượng tương đối nhỏ, chất lượng đường truyền chậm do thường phải chuyển những dữ liệu có kích thước lớn. Các nút đột ngột rời khỏi mạng sẽ làm sai bảng định tuyến trong một thời gian nhất định, làm cho việc truy vấn thiếu chính xác. Dữ liệu mà nút đó phụ trách cũng có thể bị mất theo. Kết quả truy vấn trả về có thể là rất nhiều và bị trùng lặp do kết nối đến nhiều nút khác nhau, sự đồng bộ chưa hoàn thiện giữa các nút. Không tốt với các ứng dụng dùng cơ sở dữ liệu. Hơn nữa sự bảo mật dữ liệu là kém do dữ liệu bị phân tán. Vì thế độ tin cậy về dữ liệu trong các mạng ngang hàng là không cao. 2.2. Mạng ngang hàng có cấu trúc Trong phần này ta sẽ tìm hiểu kĩ hơn về mạng ngang hàng có cấu trúc - thế hệ thử 3 của mạng ngang hàng với nhiều ưu điểm nổi trội. Nó được đánh giá là một lựa chọn hoàn hảo cho các hệ thống ngang hàng hiện tại và trong tương lai. 2.2.1. Kiến trúc mạng Trong mạng ngang hàng có cấu trúc các kết nối ở tầng phủ là cố định, và mạng thường sử dụng bảng băm phân tán - DHT[10] để ánh xạ dữ liệu. Các liên kết giữa các nút mạng trong mạng phủ tuân theo một thuật toán cụ thể, xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với phần dữ liệu nào được chia sẻ trong mạng. Mạng ngang hàng có cấu trúc luôn đảm bảo mọi nút tham gia mạng đều có thể định tuyến truy vấn tới các nút khác chứa dữ liệu mong muốn, ngay cả khi dữ liệu đó không phổ biến. Ngoài ra, trong mạng một kỹ thuật băm phù hợp được sử dụng để gán quyền quản lý dữ liệu cho những nút tham gia cụ thể, cũng như bảng băm truyền thống, mỗi khóa sẽ được gán cho những nút mạng cụ thể. Một số mạng based-DHT phổ biến có thể kể là: Chord, Pastry, CAN,…. Bảng băm là một tập hợp các cặp (khóa, giá trị). Mỗi một nút tìm giá trị tương ứng dựa vào khóa của nó. Việc hình thành 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, do đó việc rời nút hay hỏng học không làm ảnh hưởng nhiều đến hệ thống. Cộng với việc mỗi nút chỉ lưu thông tin của xấp xỉ log(N) nút khiến cho khả năng mở rộng của mạng 20 DHT là cực lớn, quá trình kiểm soát việc tham gia, dời bỏ mạng của các nút cũng trở nên dễ dàng hơn. 2.2.2. Giao thức Chord Chord[1] là một trong những mạng DHT phổ biến nhất, với nhiều ưu điểm nổi bật. Hai trong số đó là khả năng tìm kiếm dữ liệu nhanh và cân bằng tải giữa các nút. Trong phạm vi khóa luận chúng ta chọn Chord như đại diện thay thế cho mạng DHT nói chung. Các hệ thống tìm kiếm tài nguyên được ta giới thiệu và kể cả hệ thống được đề xuất trong giải pháp cũng sử dụng Chord làm tầng phủ (overlay). Hình 8 thể hiện không gian định danh dạng vòng (ring) của Chord. Cũng như trong các mạng ngang hàng có cấu trúc khác sự phân bổ khóa trong giao thức Chord thường đi kèm với dữ liệu, thường là một cặp (khóa, dữ liệu). Khóa được xem như một công cụ chỉ đường để có thể tìm thấy dữ liệu mong muốn một cách nhanh chóng nhất. Hệ thống Chord là đại diện tiêu biểu nhất của hệ thống mạng ngang hàng có cấu trúc DHT, được sử dụng làm nên tảng cho nhiều ứng dụng phát triển trên mạng ngang hàng. Một số nghiên cứu đã chỉ ra rằng: Chord không chỉ là một mạng DHT đơn thuần mà còn mang nhiều ưu điểm khác mà một số mạng DHT không có. Những đặc điểm nổi bật có thể kể đến đó là:
Khả năng cân bằng tải (Load Balance): Quá trình hình thành và phân bổ khóa của Chord dựa trên thuật toán Consistent Hashing. Chính những đặc điểm của thuật toán này đã tạo cho Chord một khả năng cân bằng tải một cách tự nhiên ngay khi mạng được khởi tạo.
Sự phân quyền: Trong giao thức Chord, các nút được coi như nhau không có sự phân biệt ưu tiên giữa các nút, phương pháp phân quyền này được thực hiện rất hiệu quả trong giao thức Chord. Một số mạng P2P Hình 8: Mạng ngang hàng có cấu trúc Chord dạng vòng tròn. 21 ban đầu cũng có những đặc điểm tương tự nhưng vẫn tồn tại những yếu điểm mà Chord đã khắc phục được.
Khả năng mở rộng (scalable): Trong quá trình hình thành mạng, tìm kiếm dữ liệu, thêm và rời nút trong Chord độ phức tạp tính toán chỉ được tính theo hàm số logarit. Chính điều này tạo cho Chord khả năng mở rộng với số lượng rất lớn các nút, cải thiện hiệu suất tìm kiếm một cách tối đa.
Tính sẵn sàng: Mỗi nút trong Chord có khả năng tự điều chỉnh bảng định tuyến (Finger Table) của chính nó khi có một nút tham gia hoặc dời mạng. Việc thực hiện các chức năng xử lý khi thêm nút, rời nút là tự động khiến hệ thống có khả năng tự động cao, chịu ít ảnh hưởng của các yếu tố bên ngoài, tăng khả năng của hệ thống so với các hệ thống khác. Mô hình mạng Chord Mạng Chord được cấp phát không gian định danh cỡ N, các định danh được sắp xếp liên tục theo thứ tự như trên một vòng tròn (ring). Mỗi nút mạng có một định danh id, và các id trong mạng Chord sắp xếp thành vòng tròn và tăng theo chiều kim đồng hồ. Chord sử dụng một hàm băm để sinh định danh cho nút và dữ liệu, đầu ra của hàm băm là một giá trị N bit.. Một định danh xác định hai nút kề nó bằng các hàm Successor(id), và Predecessor(id). Các nút liên kết với nhau dựa vào Succcessor và Predecessor tương ứng với định danh nó. Hình 9 : Một mạng Chord với 3 nút 22 Mỗi nút sẽ lưu một bảng định tuyến gọi là Finger Table (Hình 9). Thay vì phải tìm kiếm tuyến tính, bảng định tuyến cho phép một nút định tuyến tới các nút ở xa. Mỗi dòng trong bảng Finger Table sẽ lưu thông tin về 1 nút ở xa, gọi là 1 liên kết (entry). Entry thứ i sẽ lưu nút là successor của khóa có định danh cách định danh nút đang xét 2i theo chiều tiến của vòng Chord. Vì vậy, không gian định danh có bao nhiêu bit thì Finger Table có bấy nhiêu entry. Ánh xạ khóa vào một nút trong Chord Chord ánh xạ các khóa vào các nút, thường sẽ là một cặp khóa và giá trị. Một giá trị có thể là 1 address, 1 văn bản, hoặc 1 mục dữ liệu. Chord có thể thực hiện chức năng này bằng cách lưu các cặp khóa/gía trị tại các nút mà khóa được ánh xạ (Hình 10). Một nút sẽ chịu trách nhiệm lưu giữ một khóa k nếu nút đó là nút có định danh id nhỏ nhất và lớn hơn k. Một nút khi lưu giữ khóa k cũng sẽ được gọi là Successor(k). Hình 10. Lưu giữ key trong mạng Chord Tìm kiếm trong mạng Chord Khi một nút cần tìm kiếm một khóa có định danh id, nút đó sẽ tìm nút chịu trách nhiệm lưu giữ id đó. Nếu nút ở xa so với vị trí của nút lưu giữ id, nút có thể nhờ vào thông tin trong bảng Finger Table để định tuyến đến các nút xa hơn, từ đó dần dần biết được nút chịu trách lưu giữ id. Một ví dụ được chỉ trong hình 9, giả sử nút 3 muốn tìm successor của ID (hoặc còn có thể coi là khóa) 1. ID 1 thuộc khoảng [7, 3), tức là 3.finger[3].interval. nút 3 kiểm tra entry thứ 3 trong bảng định tuyến của nó, là 0. Bởi vì 0 trước 1, nút 3 sẽ hỏi nút 0 để tìm successor của 1. Quay trờ lại, nút 0 sẽ 23 suy ra từ bảng định tuyển rằng successor của 1 chính là nút 1, và trả về nút 1 cho nút 3. Tham gia và ổn định mạng Trong những hệ thống mạng động, hoạt động của nó thường xuyên gặp phải những sự thay đổi về các nút tham gia mạng, có thể là thêm nút mới và có thể rời mạng hay hỏng hóc một cách đột ngột. Để có thể xác định được vị trí của các khóa ở trong mạng, Chord cần được thỏa mãn 2 yêu cầu:
Mỗi successor của 1 nút phải đc duy trì một cách chính xác
Với mỗi khóa k, nút successor(k) có trách nhiệm quản lý khóa k Khi tham gia vào một mạng Chord, một nút n cần chọn cho nó một định danh id và thông báo cho các nút hàng xóm biết về sự tham gia của nó. Các nút Successor và Predecessor sẽ cần phải cập nhật thông tin về nút mới tham gia vào mạng. Nút n sẽ khởi tạo bảng định tuyến Finger Table rỗng và cập nhật dần từ các nút khác trong hệ thống bằng việc tìm các nút là Successor của các id trong từng entry của Finger Table, các id sẽ có được trong quá trình hoạt động của hệ thống. Để mạng vẫn định tuyến đúng sau khi có sự tham gia của nút n, các nút cần thường xuyên chạy thuật toán ổn định mạng để cập nhật thông tin về nút hàng xóm. Một số nút sẽ có n trong bảng Finger Table, nên cần cập nhật một số entry của Finger Table. Cuối cùng là nút Successor của n sẽ chuyển một phần khóa mà bây giờ n là Successor(khóa), cho n lưu giữ. Việc chuyển khóa sẽ do tầng trên của ứng dụng thực hiện. Khi một nút chuẩn bị rời khỏi mạng, nó cần thông báo cho các nút bên cạnh biết để ổn định lại mạng. Nút đó cũng sẽ chuyển các khóa nó lưu giữ cho nút Successor của nó. Trong trường hợp các nút gặp sự cố rời đột ngột khỏi mạng, hệ thống Chord thông thường sẽ mất toàn bộ dữ liệu được lưu tại nút đó, sau đó các nút khác sẽ cập nhật lại bảng định tuyến mà không có nút vừa rời đi. 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. Tính hiệu quả của các hệ thống mạng ngang hàng có cấu trúc là không còn phải bàn cãi, chính vì vậy việc thực hiện tìm kiếm tài nguyên mạng một cách hiệu quả hiện nay đa số đều được thực hiện trên các hệ thống ngang hàng có cấu trúc. Trong phần 24 này chúng ta sẽ giới thiệu một số những hệ thống tiêu biểu, đồng thời cũng là nền tảng cho ý tưởng chính được đề ra trong khóa luận này. 2.3.1. Hệ thống INS/TWINE INS/Twine[3] là hệ thống tìm kiếm tài nguyên dựa trên nền tảng chính từ INS. Hệ thống cải tiến so với INS[2] trong việc phân tầng thực hiện các công việc để đạt hiệu quả cao hơn, và cho phép thực hiện các truy vấn theo khoảng phù hợp hơn với các nhu cầu tìm kiếm tài nguyên. Trong phần này ta sẽ tìm hiểu chi tiết hơn về hệ thống này. Mô tả tài nguyên Tài nguyên trong hệ thống được mô tả với một như một hệ thống thứ bậc của các cặp thuộc tính – giá trị. Cách tiếp cận là chuyển chúng về dạng chính tắc atributes-value tree(Avtre). Tài nguyên được chú thích bằng mô tả meta-data và được biểu diễn dưới dạng cây Hình 11: Ví dụ về mô tả tài nguyên trong INS/TWINE Trong INS/Twine, 1 tài nguyên d là kết quả trả về cho 1 câu truy vấn q nếu cây AVTree được thiết lập từ q là khớp với AVTree sinh ra bởi đặc tả của d, ngoài ra hệ thống được hộ trợ cho phép tìm kiếm theo truy vấn từng phần (partial query). Điều này cho phép các truy vấn có dạng q=camera vẫn có thể tìm kiếm được tài nguyên có mô tả như hình vẽ. Kiến trúc hệ thống Hệ thống INS được phân chia làm 3 tầng thực hiện các công việc riêng biệt giúp hệ thống hoạt động một cách hiệu quả hơn. 25 Hình 12: Kiến trúc của hệ thống INS/TWINE Các tầng trong hệ thống:
Tầng phân tích (resolver) Tầng trên cùng Resolvers ,tương tác với cây lưu trữ avtree cục bộ và bộ truy vấn, nắm giữ các mô tả tài nguyên và xử lí các truy vấn. Sử dụng thuật toán phân chia các thành phần của mô tả , mục đích là để tách mô tả ra thành các phấn có ý nghĩa mà các máy phân tích có thể đưa vào một tập con của các mô tả. Hình 13: Ví dụ về việc chia nhánh từ cây avtree Hình trên thể hiện việc trích AVTree thành các nhánh. Số nhánh được tính theo công thức: s = 2a – t, với a là số cặp thuộc tính - giá trị, t là độ cao của AVTree. 26 Tính toán yêu cầu lưu trữ tại mỗi node được cho bởi công thức: Trong đó: • R: số node trong hệ thống • S: số trand trung bình cho mỗi đặc tả tài nguyên. • N: số resolver trong mạng • K: mức độ sao chép thông tin tài nguyên, K được chọn sao cho S*K<<N. Trong hệ thống INS/Twine 1 giá trị ngưỡng nhằm giới hạn số tài nguyên tối đa liên quan đến một khóa được sự dụng để tránh trường hợp nút phụ trách khóa do nhánh sinh ra có thể bị quá tải, giá trị này phụ thuộc vào khả năng của node có thể là khả năng lưu trữ, tính toán,... . Khi ngưỡng này bị vượt quá, các tài nguyên nào liên quan đến khóa tương ứng sẽ không được tiếp nhận. Trong quá trình giải quyết truy vấn, nếu một nút trả về kết quả không hoàn chỉnh do ngưỡng gây ra, một nhánh khác sẽ được chọn để tìm tiếp. Việc này được lặp lại cho đến khi danh sách tất cả tài nguyên có đặc tả phù hợp được tìm thấy hoặc khi đã duyệt hết tất cả các nhánh. Thêm vào đó, nếu gặp trường hợp một truy vấn quá ngắn hoặc chỉ gồm thông tin đặc tả phổ biến, để trách cho nút chịu trách nhiệm quản lý nhánh phổ biến bị quá tải, những nút hàng xóm sẽ duy trì cơ chế caching để lưu một số kết quả nhằm hỗ trợ các truy vấn dạng này.
Tầng ánh xạ (strandMapper) Chịu trách nhiệm tương tác với các khóa ánh xạ đến các thành phần của mô tả. Thực hiện bằng cách móc nối các bộ thuộc tính – giá trị vào trong một xâu duy nhất và thực hiện băm giá trị bằng hàm băm 128- bit MD5. Ví dụ: 27 Input strand: res-camera-man-ACompany h1 = hash(res-camera) h2 = hash(res-camera-man) h3 = hash(res-camera-man-ACompany)
Tầng định tuyến khóa (keyRoute) Trực tiếp thực hiện việc định tuyến các khóa trong hệ thống, sử dụng hệ thống Chord[1] làm tầng phủ cho công việc định tuyến Quyết định máy phân tích nào nên lưu thông tin về tài nguyên hoặc tham gia giải quyết truy vấn. Quản lý trạng thái Với mục tiêu của hệ thống là khi một node tham gia vào, hoặc rời mạng, hoặc sửa đổi thông tin về đặc tả tài nguyên, thông tin update sẽ được chuyển tới các nút cần thiết. Các máy phân tích coi thông tin tài nguyên luôn có trạng thái mềm (soft – state), yêu cầu tài nguyên phải định kì refresh lại thông tin. Để đảm bảo thông tin là cập nhật thì điều hướng tới là làm cho chu kỳ cập nhật nhỏ, tuy nhiên sẽ làm tốn băng thông của mạng. Mô hình lai ghép mà INS/Twine sử dụng như mô hình dưới là sự kết hợp giữa việc quản lý soft – state và yêu cầu về băng thông nhỏ hard – state. Hình 14: Việc quản lý trạng thái trong hệ thông INS/Twine. Mỗi tài nguyên R gửi thông tin cập nhật của nó tới một máy phân tích theo chu kỳ δ. Các máy phân tích cập nhật thông tin trong mạng với chu kỳ 28 ∆ dài hơn. Nếu một tài nguyên ra khỏi mạng mà không thông báo thì máy phân tích gần nhất sẽ nắm được thông tin này trong khoảng thời gian δ và sẽ thông báo cho các máy phân tích khác. Tương tự với việc cập nhật thông tin của tài nguyên. Khi một máy phân tích gặp sự cố phải rời mạng, thông tin về tài nguyên liên quan tồn tại trên mạng không quá thời gian ∆. 2.3.2. Data Indexing[4] Tương tự INS/TWINE hệ thống cũng sử dụng Chord làm tầng phủ, trong hệ thống mỗi một item sẽ được ánh xạ đến 1 hay nhiểu nút. Data Indexing[4] sử dụng hệ thống dữ liệu cây thư mục chứa các bài báo khoa học làm ví dụ, các file được mô tả bởi các thuộc tính mà con người có thể hiểu được như : tên tác giả, năm công bố, hội thảo công bố,… Các đặc tả sau đó được xử lý qua hàm băm để ánh xạ đến khóa k: k = h(d). Tiếp theo, khóa k sẽ được sử dụng để xác định nút chịu trách nhiệm quản lý file f . Để tìm được f, node n cần biết khóa hoặc đặc tả đầy đủ của f. Đặc tả dữ liệu và truy vấn Dữ liệu được mô tả dưới dạng semi-structure(tương tự mô tả XML) một mô tả d sẽ đại diện cho tài nguyên f tương ứng. Hình 15 Ví dụ về đặc tả file trong hệ thống Indexing Đặc tả chứa thuộc tính của file (chẳng hạn các thông tin về tác giả, tiêu đề tài liệu, …). Đặc tả truy vấn có khác biệt so với đặc tả tài nguyên. Data Indexing dùng ngôn ngữ Xpath XML để mô tả truy vấn. Một biểu diễn Xpath chứa nhiều phần 29 nhỏ phân tách bởi dấu “/”. Mỗi phần chỉ định 1 phần tử với 0 hay nhiều tính chất khác nhau hay chính là thuộc tính của tài nguyên muốn tìm kiếm. Với mỗi đặc tả d luôn tồn tại một truy vấn q tương ứng một – một với nó. Truy vấn này được gọi là truy vấn đặc trưng nhất của d (the most specific query). Trong hệ thống truy vấn ta định nghĩa khái niệm truy vấn là “phủ” của một truy vấn khác: Giả sử tồn tại 2 truy vấn q và q’, ta hiểu q’ chứa q (q’ là phủ của q) nếu như mọi đặc tả d phù hợp với q thì cũng phù hợp với q’. Ví dụ: q1 =/article[author[first/John][last/Smith]] _ _ _ [title/TCP][conf/SIGCOMM][year/1989][size/315635] q2 =/article[author[first/John][last/Smith]][conf/INFOCOM] q3 =/article/author[first/John][last/Smith] q4 =/article/title/TCP q5 =/article/conf/INFOCOM q6 =/article/author/last/Smith Hình dưới là đồ thị biểu diễn các câu truy vấn được đưa ra trong hình Với ký hiệu qi  qj tức là qi chứa qj. Hình 16: Đồ thị biểu diễn các câu truy vấn được đưa ra trong ví dụ Phân bổ dữ liệu 30 Hình 17 : Lược đồ chỉ mục cho dữ liệu cây thư mục (bibliographic database) Như trong hình vẽ ta có thể thấy dữ liệu được xây dựng thành dạng cây, cây sẽ mô tả một tập hợp các tài nguyên. Trong hình trên, cuối của mỗi mũi tên lưu ánh xạ giữa khóa của chỉ mục của nó và khóa của chỉ mục được lưu ở đầu mũi tên. Các danh sách chỉ mục khác lưu ánh xạ query-to-query(từ truy vấn đến truy vấn) và cho phép người sử dụng có thể thực hiện lặp lại việc tìm kiếm dữ liệu và xác định được file mong muốn. Cây thư mục sẽ được xây dựng trước bởi người thiết lập hệ thống, các tài nguyên khi được thêm vào hệ thống sẽ được phân bổ vào các nút trên hệ thống, việc tìm kiếm các nút này sẽ dựa vào cấu trúc của cây thư mục. Để thực hiện quá trình đánh chỉ mục cho dữ liệu, hệ thống sử dụng 2 hàm chính là insert(q,qi) với q bao hàm qi để thêm liên kết giữa q và qi vào nút phụ trách q. Và hàm lookup(q) để trả về danh sách các qi bao hàm bởi q trong nút phụ trách q. Khi thực hiện đánh chỉ mục hệ thống sẽ lần lượt làm các công việc sau :
Với tài nguyên f có mô tả d tương ứng với nó là truy vấn tối ưu q thì lưu f tại node phụ trách k = h(q)
Sinh tập hợp các truy vấn (q1,q2,...) có thể đc sinh ra bời người dùng qi bao hàm q và lưu trữ liên kết (qi,q) tại các nút phụ trách ki=h(qi)
Lặp lại quá trình thực hiên sinh truy vấn với các truy vấn q1,q2,... Đến khi mọi nội dung index mong muốn được thiết lập 31 Hình 18 : Ví dụ về index dữ liệu Tìm kiếm dữ liệu Giả sử cần tìm kiếm tài nguyên f sử dụng 1 truy vấn q, các bước được thực hiện để tìm kiếm sẽ là
Gửi truy vấn đến nút phụ trách h(q) để nhận đc danh sách các truy vấn gần tối ưu hơn q.
Chọn một hoặc nhiều trong số các truy vấn và lặp lại 1 cách đệ quy đến khi nhận được kết quả mong muốn. Ngoài ra để tiện cho việc tìm kiếm các dữ liệu phổ biến hệ thống sử dụng “shortcut” để truy vấn. Các shortcut sẽ được ánh xạ trực tiếp đế dữ liệu hay tài nguyên mà không cần thông quá nhiều bước lặp để tìm kiếm. Để làm được điều này hệ thống sẽ hộ trợ thêm cơ chế cache tại các nút để lưu ánh xạ khi cần thiết 32 Chương 3. Ý tưởng và giải pháp cho vấn đề “Tìm kiếm tài nguyên trên hệ thống tên miền trong mạng ngang hàng” Chương hai cho chúng ta thấy được tổng quan những vấn đề, ưu điểm trong việc tìm kiếm tài nguyên trên mạng ngang hàng có cấu trúc. Đó là lí do để nhiều hệ thống tìm kiếm đã được xây dựng sử dụng mạng ngang hàng có cấu trúc làm tầng phủ cho hệ thống. Việc trình bày một số giải pháp đã được thực hiện cũng đem lại nhiều ý tưởng cho giải pháp được để xuất sau đây. Trong chương ba, giải pháp về một hệ thống tìm kiếm tài nguyên sẽ được đề xuất và làm rõ tính hiệu quả của nó trên phương diện lý thuyết. Giải pháp này dựa trên một số ý tưởng là ưu điểm của các giải pháp đã để ra đồng thời thêm vào những ý tưởng mới để khắc phục các tồn tại trong các giải pháp nói trên cũng như trong các hệ thống tìm kiếm tài nguyên mạng nói chung. 3.1. Vấn đề giải quyết Qua một số giải pháp đã nêu ở chương 2. Đã cho ta cái nhìn tổng thể về một hệ thống tìm kiếm tài nguyên, những công việc phải làm khi xây dựng hệ thống, các vấn đề tồn tại trong một hệ thống tìm kiếm tài nguyên Vấn đề tồn tại Trong một số hệ thống, việc lưu trữ số lượng lớn các bản sao của tài nguyên làm lãng phí tài nguyên của hệ thống, tài nguyên trong hệ thống ở đây có thể hiểu là khả năng lưu trữ của các nút tham gia mạng. Có thể kể đến hệ thống INS/TWINE như một ví dụ điển hình cho trường hợp này. Để có thể hỗ trợ tìm kiếm tài nguyên theo yêu cầu bằng việc sử dụng các truy vấn tổng quát (partial query) thông tin về tài nguyên sẽ được lưu trữ trong tất cả các nhánh được trích ra từ cây thuộc tính – giá trị (avtree) mô tả tài nguyên. Khi số lượng các nhánh tăng lên số lượng các bản sao sẽ tăng lên rất nhiều lần. Trên thực tế các nút chứa dữ liệu của một nhánh bao hàm hoàn toàn có thể ánh xạ đến các nút chứa nhánh con của nó để lấy thông tin cho truy vấn mà không cần phải tạo ra một bản sao riêng để lưu trữ. Việc lưu trữ nhiều bản sao tài nguyên trong hệ thống không chỉ đơn thuần làm lãng phí tài nguyên của hệ thống mà còn làm ảnh hưởng đến quá trình truy vấn tìm kiếm cũng như phân bổ tài nguyên trong hệ thống. Trong trường hợp tìm kiếm truy vấn sẽ được gửi đi nhiều nút chuyển tiếp để trả lời cho người dùng, và kết quả sẽ có thể mang nhiều giá trị trùng lặp làm hệ thống mất nhiều thời gian để tổng hợp các kết quả trước khi trả lời yêu cầu tìm kiếm. 33 Các hệ thống được ta xem xét và nghiên cứu đều được sử dụng cấu trúc cây để lưu trữ mô tả của toàn bộ tài nguyên trong hệ thống và hiệu quả của nó là rất rõ ràng. Tuy nhiên, việc giảm tải cho các nút phía gần gốc của cây mô tả tài nguyên là vô cùng quan trọng, vì các nút này luôn phải chịu tải rất lớn mỗi khi truy vấn vào hệ thống, đặc biệt là nút gốc nơi được duyệt qua bởi toàn bộ các truy vấn cũng như khi cập nhật tài nguyên mới. Việc xử lý hiệu quả đối với các cặp thuộc tính - giá trị phổ biến cũng là vấn đề đối với các hệ thống tìm kiếm tài nguyên mạng. Trong thực tế, các truy vấn của người dùng sẽ thường chứa các thuộc tính phổ biến, trong nhiều trường hợp có thể là 1 cặp thuộc tính – giá trị. Ví dụ như trường hợp tìm kiếm tài nguyên là một tài liệu (document) là một bài báo khoa học thuộc tính phổ biến có thể kể đến như : article, author, confference… một cặp thuộc tính - giá trị phổ biến có thể là confference – SIGCOMM. Truy vấn nhiều đến các cặp phổ biến có thể làm cho nút chứa dữ liệu phổ biến bị quá tải và bị đánh sập. Ngoài ra việc chỉ sử dụng một ID duy nhất để ánh xạ tài nguyên lưu trong một nút mạng tương ứng sẽ là không hiệu quả vì khi gặp hỏng hóc trên nút này sẽ làm mất dữ liệu lưu trữ Mục tiêu hướng tới Mục tiêu chính của hệ thống mà chúng ta xây dựng chính là việc tận dụng tối đa các ưu điểm có được trong ý tưởng của các hệ thống đã được xây dựng đồng thời khác phục những nhược điểm của các hệ thống tìm kiếm tài nguyên. Những mục tiêu đó bao gồm :
Sử dụng một phương pháp mô tả tài nguyên có khả năng diễn đạt mềm dẻo và hiệu quả để có thể diễn đạt được lượng tài nguyên lớn phong phú và đa dạng mà vẫn đảm bảo sự tương ứng một – một giữa một tài nguyên với một mô tả.
Duy trì cấu trúc cây trong việc lưu trữ tài nguyên chung của hệ thống. Cấu trúc cây làm cho việc tìm kiếm nhanh và hiệu quả hơn. Khi trong cấu trúc của cây thuộc tính – giá trị các cặp thuộc tính – giá trị được sắp xếp theo thứ bậc thì các yêu cầu chi tiết trong truy vấn có thể được đáp ứng một cách chính xác và cụ thể.
Tăng cường khả năng cần bằng tải của hệ thống ở mức tốt nhất có thể. Có hai hướng để thực hiện mục tiêu này đó là khắc phục hạn chế trong trường hợp truy vấn bao hàm các cặp thuộc tính – giá trị phổ biến và phân bố tài nguyên 34 đều trên các nút trong hệ thống. Ngoài ra cần sử dụng phương pháp ánh xạ tốt để hạn chế dữ liệu thực sự về tài nguyên được lưu trữ.
Hai mục tiêu cuối cùng và cũng rất quan trọng đó là cung cấp khả năng mở rộng và tính sẵn sàng cho hệ thống. 3.2. Ý tưởng Trong phần này chúng ta sẽ giới thiệu về ý tưởng cho một hệ thống mới, ý tưởng này xuất phát từ những nhu cầu cần thiết cho hệ thống và cố gắng khắc phục những tồn tại thường xảy ra trong các hệ thống tìm kiếm tài nguyên mạng. Mô tả tài nguyên Hệ thống sẽ sử dụng cách thức mô tả tài nguyên đã được trinh bày trong hệ thống INS tại chương 1. Hai phần chính được sử dụng để mô tả tài nguyên đó là “thuộc tính” và “giá trị”. Ta có thể hiểu “thuộc tính” là một tính chất trong mô tả đặc điểm của tài nguyên phần lớn được dùng để phân loại đối tượng tài nguyên với nhau. Còn “giá trị” chính là kết quả tương ứng với tính chất đó. Thuộc tính và giá trị đều được biểu diễn dưới dạng một xâu kí tự bất biến được định nghĩa bởi ứng dụng. Việc mô tả tài nguyên sẽ đi liền với việc sắp xếp các cặp thuộc tính giá trị theo thứ tự nhất định và mối quan hệ phụ thuộc giữa chúng để có được sử diễn tả tốt nhất đối với một tài nguyên nhất định, phân biệt nó với những tài nguyên khác. Trong hệ thống ta thực hiện mô tả bằng việc sắp xếp các cặp thuộc tính giá trị dưới dáng cây thuộc – tính giá trị, các cặp thuộc tính - giá trị con sẽ chịu mối quan hệ phụ thuộc đối với các cặp thuộc tính – giá trị cha. VD : cặp thuộc tính - giá trị “công ty – Canon” và cặp thuộc tính “model – AD3XZ” dùng để thể hiện mô tả cho tài nguyên là một camera giao thông đặt tại ngã tư Kim Mã. Thì cặp “model – AD3XZ” sẽ chịu sự phụ thuộc vào cặp “công ty – Canon” vì model AD3XZ chỉ tồn tại với những camera được sản xuất bởi Canon. Ta sẽ hiểu rõ hơn về việc mô tả sử dụng cấu trúc cây qua 2 cách thể hiện trong hình vẽ: 35 Hình 19: Ví dụ về mô tả tài nguyên của hệ thống Tại hình 19.a là mô tả tài nguyên dưới dạng cây, còn tại hình 19.b là mô tả tài nguyên dưới dạng thẻ dữ liệu trong đó các thẻ dữ liệu con được chứa trong thẻ dữ liệu lớn hơn sẽ mô tả cặp thuộc tính – giá trị con phụ thuộc và cặp thuộc tính giá trị cha. Việc mô tả tài nguyên này đem lại nhiều ưu điểm cho hệ thống. Thứ nhất cấu trúc cây được duy trì với sắp xếp thứ bậc của các cặp thuộc tính giá trị được đảm bảo giúp việc mô tả tài nguyên chính xác và mềm dẻo hơn, đồng thời phân loại chúng tốt hơn. Thứ hai, việc sử dụng các xâu kí tự để biểu diễn thuộc tính và giá trị sẽ giúp cho việc xử lý tại các máy tính đơn giản và hiệu quả. 36 Với việc mô tả như nêu trên, việc tìm kiếm tài nguyên trên mạng trở thành tìm kiếm tên miền, với các miền giá trị đơn giản là các cặp thuộc tính – giá trị, hay có thể chỉ là các thuộc tính. Sử dụng tầng phủ DHT Qua thực nghiệm đánh giá của các hệ thống đã đưa ra có thể thấy rõ được hiệu quả của các hệ thống mạng ngang hàng có cấu trúc đặc biệt là các hệ thống sử dụng bảng băm phân tán (DHT) có hiệu quả như thế nào đối với các hệ thống tìm kiếm tài nguyên mạng.
Trước hết khả năng mở rộng được nâng cao rõ rệt do không có điểm tập trung gây ra hiện tượng thắt nút cổ chai tại những điểm này, đây là một trong những ưu điểm nổi trội nhất của các giao thức DHT.
Việc tìm kiếm trong màng ngang hàng có cấu trúc sử dụng DHT là hiệu quả khi sử dụng thuật toán tím kiếm cụ thể khác với việc truyền tin “flooding”, với số lượng các “hope” khi trả lời truy vấn là thấp, số lượng “hope” đạt sự phức tạp trong tính toán là log(N) với N là số lượng các nút tham gia mạng, khả năng tìm kiếm tài nguyên theo đó sẽ tăng lên rất đáng kể, và giảm thiếu ở mức thấp nhất các nút tham gia trả lời 1 truy vấn điều này cũng giúp giảm tải cho hệ thống khi truy vấn, tiết kiệm băng thông mạng.
Ngoài ra, tầng phủ với việc sử dụng bảng băm phân tán sẽ giúp cho việc phân bổ tài nguyên đều hơn giữa các nút mạng. Đem lại tính hiệu quả trong việc lưu trữ tài nguyên trong hệ thống và đảm bảo được sự công bằng giữa các nút trong hệ thống mạng ngang hàng. Hệ thống được phát triển của chúng ta sẽ vẫn sử dụng tầng là mạng ngang hàng có cấu trúc. Tuy nhiên như đã đề cập đến ở các phần trước, DHT chỉ cung cấp cho chúng ta cách thức tìm kiếm ánh xạ một – một giữa ID và thông tin lưu trữ, trong khi hệ thống lại cần được cung cấp khả năng tìm kiếm nhiều tài nguyên trong một truy vấn. Do đó ý tưởng đưa ra là cung cấp một cơ chế ánh xạ giữa dải ID và tập hợp các tài nguyên. Khóa luận sẽ sử dụng giao thức Chord trong định tuyến mạng ngang hàng. Chord sử dụng việc phân bổ ID cho các nút trên dải ID liên tục được bố trí theo đường tròn thuận tiện cho phương pháp ánh xạ sử dụng những dải ID liên tục với tài nguyên. Ngoài ra Chord cũng có nhiều ưu điểm khác phù hợp với hệ thống mà chúng ta thiết kế. 37 Đầu tiên đó là khả năng cân bằng tải nhờ việc phân bổ khóa của Chord dựa trên thuật toán Consistent Hashing. Chính những đặc điểm của thuật toán này đã tạo cho Chord một khả năng cân bằng tải một cách tự nhiên ngay khi mạng được khởi tạo. Sự phân quyền trong giao thức Chord, với việc coi các nút có độ quan trọng tương đương không nút nào quan trọng hơn nút nào. Khả năng mở rộng mộng có được do các thuật toán sử dụng trong Chord chỉ biến thiên theo hàm số logarit. Một đặc điểm khác nhưng cũng không kém phần quan trọng trong mạng Chord đó là quá trình duy trì sự tồn tại của mạng diễn ra hoàn toàn tự động, chính điều này đã giảm thiểu khả năng đổ vỡ xuống mức tối thiểu khi quá trình tham gia và dời bỏ mạng của các nút diễn ra. Các ưu điểm của giao thức này đã rõ ràng, và công việc của chúng ta chỉ là xây dứng ứng dụng phía trên của giao thức, điều này sẽ khiến cho công việc của chúng ta đơn giản đi nhưng vẫn đem lại một hiệu quả mong muốn. Phân bổ tài nguyên Rõ ràng trong các nghiên cứu cho thấy một hệ thống cho phép các tài nguyên được phân bổ trên một cây mô tả chung về toàn bộ hệ thống trong tài nguyên sẽ giúp ích nhiều cho hệ thống trong việc tìm kiếm tài nguyên, tuy nhiên vấn đề cân bằng tải cho hệ thống cũng cần được xem xét.
Trong vấn đề tìm kiếm, cấu trúc cây sẽ giúp cho việc phân loại tài nguyên là tốt hơn, lấy ví dụ như việc cùng 1 thuộc tính mô tả tài nguyên nhưng với nhiều tài nguyên thì có thể có nhiều giá trị khác nhau, như trong ví dụ về tài nguyên là camera cùng thuộc tính là “công ty” tức hãng sảng xuất có thể có nhiều giá trị như : canon, sony … Việc hỗ trợ tìm kiếm nhiều tài nguyên thỏa mãn yêu cầu cũng dễ dàng đạt được hơn chỉ trong một truy vấn, chẳng hạn sử dụng truy vấn [resource = camera[company = canon]] để tìm kiếm các tài nguyên là camera của hãng sản xuất canon mà không mô tả cụ thể về mẫu mã (model) hay chức năng riêng biệt nào, truy vấn phải tiếp túc tìm sâu xuống các tầng dưới để cho kết quả là toàn bộ các tài nguyên thỏa mãn, với trường hợp này nếu sử dụng cấu trúc cây thì câu trả lời sẽ là cây con (sub tree) với nút giá trị canon làm gốc.
Để thực hiện vấn đề cân bằng tải cho hệ thống như đã nói ở trên chúng ta sử dụng tầng phủ là mạng ngang hàng có cấu trúc sử dụng bảng băm phân tán. Khi thực hiện phân bổ dữ liệu về tài nguyên sẽ được hàm băm để lấy giá trị trước khi đưa vào công thức tính toán vị trí phân bổ. Với tính chất của bảng băm dữ liệu có thể được phân bố đều trên các nút mạng. 38 Ý tưởng của hệ thống là đưa ra một cây mô tả chung toàn bộ tài có hình dáng cố định và cân bằng về số lượng con cho mỗi nút và độ chênh lệch về chiều sâu giữa các nhánh trong cây. Điều này thể hiện mong muốn tài nguyên sẽ được dàn đều trên hệ thống và để cây có được cấu trúc tìm kiếm đơn giản và hiệu quả. Sau đây, ta sẽ trình bày việc thực hiện phân bổ tài nguyên với cấu trúc cây mô tả chung như đã đề ra. Để tiện theo dõi ta sẽ gọi cây mô tả chung dữ liệu này là “cây phân bổ”. Trong hệ thống DHT với giao thức Chord mạng các nút tham gia được phân bổ ID trên một dải ID liên tục, ta sẽ chọn ra một giá trị cho tham số tương ứng với số nhánh con được tạo ra bởi mỗi nút trong cây phân bổ, giả sử giá trị được chọn là m. Tại tầng đầu của cây phân bổ (tức root) nút duy nhất sẽ quản lý toàn bộ dải ID được cung cấp bởi tầng phủ Chord. Tại các tầng tiếp theo mỗi nút cha sẽ chia dải ID mà nó phụ trách thành m phần bằng nhau và giao cho các nút con của nó phụ trách, theo cách đó cây phân bổ sẽ được xây dựng cho những tầng tiếp theo. Trong hình 20 là một ví dụ về cây phân bổ với việc chọn m=2. Giả sử dải ID của hệ thống là [0,1] Khi đó nút root sẽ quản lý dải ID [0,1]. Các nút A và B sẽ quản lý các dải ID [0,12 ] và [ 1 2 ,1]. Tương tự các dải ID [0, 1 4 ], [ 1 4 , 1 2 ], [12 , 3 4 ], [ 3 4 ,1] sẽ chịu sử quản lý của các nút C, D và E, F. Với việc xây dựng cây phân bổ như vậy ta sẽ phải quan tâm đến một tham số khác đó là chiều sâu của cây phân bổ, giả sử tham số biểu diễn của nó là h. Ta nhận thấy rằng h sẽ phải đủ lớn để có thể mô tả mọi tài nguyên có trong hệ thống, tức là h > hMAX với hMAX là chiều sâu lớn nhất có thể có của một tài nguyên trong mô tả tài nguyên giống như mô tả trong hình 19.a. Như vậy mỗi khi có một tài nguyên mới Hình 20 : Ví dụ mô tả cây nhị phân 39 được mô tả với chiều sâu của cây mô tả lớn hơn thì cây phân bổ sẽ phải tự động tăng chiều sâu (tăng giá trị h), tiếp tục chia nhỏ dải ID để phân bổ tài nguyên vào dài ID đó. Việc ánh xạ giữa các nút lá nơi lưu trữ tài nguyên với các nút mạng thực sự có được chính là nhờ việc sử dụng mạng ngang hàng có cấu trúc sử dụng giao thức Chord. Cụ thể việc chỉ rõ tài nguyên thực sự được lưu trữ tại các nút mạng nào sẽ được trình bày trong phần tiếp theo – Chi tiết về giải pháp. Việc quản lý tài nguyên như trên sẽ giúp hệ thống có thể tăng cường khả năng cân bằng tải giữa các nút. đối với các thuộc tính và giá trị ở phía trên của cây mô tả tài nguyên càng gần với gốc hơn thì càng có nhiều nút quản lý, dải ID càng rộng. Trong một dải ID mà chịu sử quản lý của một nút trên cây phân bổ, toàn bộ các nút mạng trong đó sẽ lưu trữ thông tin giống nhau. Tuy nhiên các thông tin này chỉ thuộc về tầng tương ứng của nút quản lý. 3.3. Chi tiết giải pháp Trong phần này ta sẽ mô tả chi tiết hệ thống trả lời truy vấn và thêm tài nguyên vào bằng cách nào. Thêm tài nguyên Khi thêm tài nguyên vào hệ thống hệ thống chỉ cần sử dụng một mô tả của tài nguyên tạo bởi bộ định danh để đưa vào hệ thống. Sau đó, hệ thống sẽ tiền hành theo thứ tự các công việc sau Đầu tiên tài nguyên sẽ được tách thành các nhánh, mỗi nút lá sẽ cho một nhánh tương ứng, nhánh này sẽ lưu trữ theo thứ tự các thuộc tính và giá trị đi từ nút root đến đến nút lá tương ứng với nhánh. Như trường hợp mô tả trong hình 19 các nhánh tương ứng sẽ là :
Nhánh 1: [res = camera [man = Acompany]]
Nhánh 2: [res = camera [model = Amodel]]
Nhánh 3: [subject = traffic] Sau đó, hệ thống sẽ tiến hành băm từng nhánh rồi gửi yêu cầu đến các máy phân tích nằm trong dải ID tương ứng các nhánh, mỗi dải ID [kMIN, kMAX] được xác định theo công thức: 40 kMIN = { 1m H(a1) + 1 m 2 H(v1) + 1m3 H(a2) + 1 m 4 H(v2) + … + 1mN-1 H(an) + 1 m N H(vn) } * (m-1). kMAX = kMIN + 1 m N+1 H(vn) Trong đó : - a1, a2, …, an là các thuộc tính - v1, v2, …, vn là các giá trị tương ứng với các thuộc tính - H(x) là hàm băm phân tán được thực hiện với xâu kí tự x - N là chiều sâu của mô tả ,m là tham số của cây phân bổ. Với kMIN, kMAX được tính như trong công thức trên hệ thống sẽ xác định được dải ID tại tầng tương ứng với chiều sâu của nhánh trong cây phân bổ. Xem xét công thức ta có thể thấy giá trị m-1 m H(a1) trong công thức tính kMIN sẽ thực hiện tìm giới hạn dưới tương ứng của dải ID tại tầng 1 (sau tầng root) trong cây phân bổ. Với H(a1) biến thiên từ 0 đến 2T (T là số bít sử dụng trong hàm băm) giá trị này sẽ cho tương ứng giới hạn dưới của dải ID con từ 0 đến m-1 với H(a1) đạt giá trị nhỏ nhất thì dải ID tương ứng là dải đầu tiên, H(a1) đạt giá trị lớn nhất thì sẽ là dải ID cuối cùng. Một cách tượng tự ở các tầng sau dải ID sẽ chia nhỏ hơn với các giá trị tương ứng m-1 m 2 , ..., m-1 m i . Khi tìm được giới hạn dưới của dải ID thì giới hạn trên được xác định đơn giản bằng việc cộng giới hạn dưới kMIN với kích dải ID, kích thước dải ID càng nhỏ khi dải ID nằm tại tầng càng lớn, tại tầng i sẽ là 1 m i+1 . Sau khi xác định được dải ID cần thiết hệ thống sẽ tiến hành multicast yêu cầu về thêm tài nguyên đến các nút mạng trên dải ID này, thông tin của tài nguyên sẽ được sao chép tại các nút mạng này. Việc thực hiện băm nhiều nhánh khác nhau sẽ dẫn đến trường hợp dải ID của các nhánh sau khi băm là giao nhau. Khi đó để tránh trường hợp những dải ID chung này phải lưu lặp lại nhiều lần bản sao của tài nguyên ta sẽ cung cấp cơ chế xác định dải ID tổng hợp cần lưu trước khi tiến hành multicast đồng loại đến các nút mạng. Dải ID tổng hợp này sẽ là hợp của các dải ID có được từ việc băm các nhánh của tài tài nguyên Giả sử ta có : IN = [kMIN(N), kMAX(N)] 41 Khi đó dải ID tổng hợp sẽ là : I = 1 n N N I = ∪ Việc multicast đến các nốt trong dải ID tổng hợp sẽ được thực hiện trên cơ sở bảng định tuyến của các nút mạng và các hàm hỗ trợ tìm successor, preccessor. Độ phức tạp tính toán trong việc phân bổ tài nguyên do đó cũng chỉ là log(N). Các công thức sử dụng hàm băm phân tán do đó với số lượng lớn các nút mạng và tài nguyên thì tài nguyên sẽ được phân bổ đều trên cây nhị phân mô tả của hệ thống. Đồng thời với việc chịu trách nhiệm lưu trữ tài nguyên trên một dải ID thì khi một nút bị mất đi tài nguyên vẫn có thể được truy vấn tới tại các nút khác trong dải. Xử lý truy vấn Hình 21 : Ví dụ về mô tả truy vấn trong giải pháp 42 Một truy vấn sẽ có mô tả tương tự như trong hình 21 hệ thống sẽ phân tích các token để tách các xâu biểu diễn thuộc tính và giá trị theo thứ tự từ gốc của truy vấn, các thuộc tính và giá trị sau khi tách ra sẽ lưu các liên kết đến các thuộc tính hoặc giá trị là con của nó trong mô tả truy vấn đế phục vụ việc truy vấn về sau. Hệ thống sẽ thực hiện các hàm băm đối với các thuộc tính và giá trị riêng biệt sau đó sử dụng công thức chung để tìm ra vị trí gửi truy vấn đến trên dải ID của mạng Chord. Với giá trị là dấu hoa thị hệ thống sẽ bỏ qua. Công thức này sẽ tùy thuộc vào việc sử dụng cây mô tả chung trong mô tả tài nguyên hay chính xác hơn phụ thuộc vào giá trị của tham số m. Các bước để thực hiện truy vấn trong hệ thống :
Ban đầu truy vấn được gửi đến một nút bất kì trong hệ thống để tránh việc gây tải lớn cho một số node. Do việc xây dựng cây mô tả tài nguyên như đã nêu nên mọi nút trong hệ thống đều có thể chuyển truy vấn đến nơi có thể trả lời yêu cầu của nó
Tại các nút được gửi đến truy vấn sẽ được phân tích để chọn ra nhánh có chiều sâu lớn nhất, việc tìm kiếm theo nhánh có chiều sâu lớn nhất sẽ làm giảm không gian ID phải tìm kiếm. Dải ID được sử dụng để tìm kiếm được xác định là [kMIN, kMAX] với kMIN, kMAX tính theo công thức: kMIN = { 1m H(a1) + 1 m 2 H(v1) + 1m3 H(a2) + 1 m 4 H(v2) + … + 1mP-1 H(an) + 1 m P H(vn) } * (m-1). kMAX = kMIN + 1 m P+1 H(vn) Trong đó : - a1, a2, …, an là các thuộc tính - v1, v2, …, vn là các giá trị tương ứng với các thuộc tính - H(x) là hàm băm phân tán được thực hiện với xâu kí tự x - N là chiều sâu của mô tả truy vấn - m là tham số của cây phân bổ.
Khi có được dải ID hệ thống sẽ sử dụng bảng định tuyến của các nút trong mạng Chord đưa truy vấn đến các nút mạng nằm trong dải ID này
Số nút phải tham gia truyền thông điệp sẽ là O(logN) cộng với số nút nằm trong dải ID. 43 Qua việc sử dụng thuật toán tìm kiếm như trên ta có thể thấy là với những truy vấn đến chính xác một tài nguyên cụ thể hệ thống sẽ không phải sử dụng hàm multicast mà chỉ cần sử dụng khóa kMIN để xác định nút chứa tài nguyên. Thêm vào đó việc nhánh tách được từ truy vấn nếu có chiều sâu càng càng lớn thì việc tìm kiếm sẽ càng hiệu quả do dải ID được ánh xạ sẽ bé hơn, với những truy vấn mà có chiều sâu các nhánh là bé thì dải ID lớn sẽ làm cho các nút phải tham gia truy vấn tăng lên, đây là một nhược điểm của giải thuật. Tuy nhiên với việc hỗ trợ tốt tìm kiếm theo dải ID, giúp tìm kiếm tài nguyên thỏa mãn các partial query và độ phức tạp trong tính toán tìm kiếm thấp thì giải thuật đã có sự vượt trội so với các giải thuật trong những hệ thống khác . 3.4. Đánh giá chung về giải pháp Mô tả tài nguyên sử dụng là hiệu quả đem lại độ chính xác cao trong phân loại và tổng hợp tài nguyên. Tính diễn tả tốt giúp người dùng và hệ thống có thể tùy biến trong việc diễn tả tài nguyên, bằng việc sử dụng các cặp thuộc tính giá trị khác nhau. Sử dụng tầng phủ DHT làm tăng khả năng mở rộng cho hệ thống, hệ thống trở nên dễ cài đặt và có tính vững chắc. Về khá năng tìm kiếm giải pháp với việc tìm kiếm thực chất là dựa trên tìm kiếm khóa qua đó ánh xạ đến giá trị thật của thông tin. Ngoài ra việc hỗ trợ truy vấn theo dải được thực hiện tốt nhờ sử dụng ánh xạ dải ID với một tập hợp tài nguyên. Với sự hỗ trợ của mạng Chord việc tìm kiếm này có độ phức tạp biến thiên theo hàm logarit. Khả năng tìm kiếm nhanh rõ ràng là đã được thực hiện một cách hiệu quả. Hàm băm phân tán được sử dụng sẽ giúp cho việc phân bổ tài nguyên đều trên cây nhị phân, khi thực hiện thêm tài nguyên việc sử dụng hàm băm để tính toán dải ID chịu trách nhiệm cũng chỉ có độ phức tạp thuật toán là log(N).Việc cân bằng tài giữa các nút mạng cũng được thực hiện tốt nhờ giao thức của tầng phủ cộng với việc các nút (các nút trong cây mô tả tài nguyên) gần tầng root sẽ chịu quản lý bởi dải ID rộng hơn và được chia sẻ tải nhiều hơn bởi số lượng các nút mạng là nhiều hơn. 44 Chương 4. Đánh giá hiệu quả của giải pháp bằng mô phỏng Để thấy được hiệu quả của giải pháp mới và xem xét các ưu điểm của nó, chúng ta cần có những thống kê, thể hiện sự hoạt động thực sự của mạng. Trên lý thuyết việc thực hiện giải pháp trên một hệ thống thực luôn mang lại những đánh giá hiệu quả nhất. Nhưng điều kiện để xây dựng một mạng với kích thước lớn là rất khó khăn trong thực tế , do đó ta sẽ lựa chon việc mô phỏng mạng. Chương 4 sẽ trình bày về chương trình mô phỏng, các bước để thực hiện chương trình mô phỏng, chạy thử, thống kê kết quả và đánh giá. Việc mô phỏng có thể đem lại những sai khác so với thực tế nên mục đích của chương này là đưa ra được những đánh giá sơ bộ, tổng quát nhất. 4.1. Môi trường mô phỏng Chương trình mô phỏng bao gồm hai phần chính là dữ liệu và thực thi. Phần dữ liệu bao gồm các loại dữ liệu mô phỏng các thông tin tài nguyên và phần mã nguồn chương trình tạo ra chúng. Phần thực thi là phần mô tả hoạt động của mạng ngang hàng Chord ở tầng phủ và ứng dụng mà ta xây dựng ở tầng trên. Ngoài ra cũng có những mô phỏng cho mô hình cơ sở hạ tầng mạng phía dưới tầng vật lý. 4.1.1. Xây dựng chương trình mô phỏng Để thực hiện được quá trình mô phỏng, trước tiên chúng ta cần có một mô hình mạng tầng liên kết vật lý trong hệ thống, thời gian trễ giữa các nút trên mạng có thể được bỏ qua vì trong hệ thống của chúng ta chỉ thực hiện mô phỏng việc truy vấn và phân bổ tài nguyên ảnh hưởng đến việc lưu trữ tới các nút trong hệ thống, số lượng các bản sao dữ liệu. Chương trình sẽ xây dựng một topo mạng đơn giản theo các điều kiện giả định. Vì là mạng giả lập với yêu cầu đơn giản, nên các điều kiện ở đây mang tính quy ước, các tham số dựa vào mạng thực tế và kinh nghiệm của nhóm làm khóa luận. Chương trình được thực hiện bằng ngôn ngữ C, gồm việc mô phỏng giao thức Chord ở tầng phủ, và ứng dụng tìm kiếm tài nguyên phía trên. Ứng dụng tìm kiếm bao gồm các hàm chức năng phục vụ việc truy vấn và phân bổ tài nguyên. Các đối tượng được xây dựng để thiết lập giao thức Chord phía dưới bao gồm: 45
Areas : Đối tượng lưu trữ thông tin về miền, tệp chứa miền, các thao tác với dữ liệu miền.
NodeLocation : Lưu thông tin về vị trí nút, chính xác là một nút bất kỳ thuộc miền nào.
FingerEntry Thể hiện một liên kết (entry) trong bảng định tuyến. Thuộc tính idSuccessor với ý nghĩa là định danh successor của khóa mục tiêu tại entry đang xét.
Node : Mô tả thông tin một nút trong mạng với tên, miền mà nút thuộc về, thời gian trễ nội miền, định danh trên vòng không gian địa chỉ Chord, định danh successor và predeccessor, cuối cùng là bảng định tuyến có kiểu là FingerEntry.
Network : Đối tượng lưu trữ toàn bộ thông tin về các Node tham gia mạng Chord đồng thời được cung cấp các hàm để hỗ trợ việc định tuyến trong mạng Chord, có thể kể đến các hàm tiêu biểu birth(), death(), fixFingerTables(), findSuccessor(). Ta sẽ xây dựng các ứng dụng của mình trên các hàm được cho trong đây.
InputGenerator : Đối tượng chứa các phương thức để tạo ra các tệp dữ liệu như đã mô tả phần trên. Bao gồm cả dữ liệu về file contruct.txt và file resource.txt để khởi tạo mô hình mạng và tài nguyên sẽ phân bổ trong mạng. Dữ liệu này sẽ được nhắc đến trong phần tiếp theo.
Distribution : Đây là đối tượng cho phép sinh các giá trị theo luật phân bố Pareto như đã nêu. 4.1.2. Các tham số mô phỏng Chương trình mô phỏng sử dụng khá nhiều loại dữ liệu. Các dữ liệu mô phỏng tài nguyên cũng như các dữ liệu mô phỏng cơ sở mạng tại tầng vật lý. Phần này chỉ nói đến ý nghĩa của các tệp dữ liệu, cấu trúc dữ liệu được lưu trữ trong các file dữ liệu, việc tạo ra các tệp dữ liệu này sẽ được trình bày một cách chi tiết trong chương này. Thông tin miền Thông tin về miền bao gồm số lượng miền. Các nút mạng trên mỗi miễn, ta sẽ sử dụng 1.000 nút trong mô phỏng mạng ngang hàng sử dụng giao thức Chord. 46 Các nút sẽ được mô tả trong file construct.txt và khi bắt đầu hệ thống sẽ lần lượt thêm các nút (máy tính) này vào hệ thống. Quá trình thêm các nút vào hệ thống sẽ làm thay đổi bảng định tuyến của các nút, successor và precessor của các nút trong giao thức Chord. Công việc này sẽ được hệ thống tự động thực hiện. Dữ liệu trong file construct.txt sẽ được tạo bởi một hàm sinh ngẫu nhiên theo luận phân bổ Pareto[11]. File construct.txt gồm 2 trường dữ liệu mô tả định danh các nút và vùng phụ thuộc của các nút. Thông tin về tài nguyên Một file dữ liệu khác được sử dụng đó là danh sách các tài nguyên resource.txt được sinh ra theo phân bổ Zipf[12], số lượng các tài nguyên được sử dụng là 100.000, trong đó các cặp thuộc tính – giá trị được xem là phổ biến sẽ xuất hiện nhiều lần hơn trong các tài nguyên này. Tổng số cặp thuộc tính giá trị được sử dụng cũng là 100.000 cặp được sinh ngẫu nhiên. Các tài nguyên được mô tả bởi bộ định danh tương ứng với 1 cây thuộc tính giá trị. Các tham số của cây:
Số tầng, mỗi cây gồm từ 4 đến 10 tầng được sinh ngẫu nhiên, mỗi tầng là thuộc tính hoặc giá trị được phân phổi cho cây từ các cặp thuộc tính – giá trị đã sinh ra. Các cặp thuộc tính giá trị được chọn ưu tiên theo thứ tự các tầng gần root hơn sẽ là các cặp thuộc tính giá trị phổ biến hơn.
Với nút root, số nút con của root là random từ 2 đến 4
Với các nút khác trong cây, số nhánh con được random từ 0 đến 4, nếu số nhánh con là 0 thì nút đó chính là nút lá File dữ liệu resource.txt sẽ lưu dữ liệu gồm các dòng mỗi dòng sẽ mô tả một nhánh trong một cấu trúc tài nguyên có định dạng như bên dưới Định dạng dữ liệu : n a1 v1 a2 v2 … am vm Trong đó n là số thự tự tài nguyên mà nhánh thuộc về, a1, a2,…, am là các thuộc tính và v1, v2, …, vm là các giá trị lấy từ các cặp thuộc tính giá trị đã được sinh ra. 47 4.2. Đánh giá kết quả Phần này sẽ trình bày kết quả mô phỏng đạt được. Kết quả đánh giá sẽ tập trung vào 2 tiêu chí. Hiệu quả trong việc phân bổ tài nguyên, và hiệu quả trong xử lý truy vấn. 4.2.1. Hiệu quả trong phân bổ tài nguyên Để thấy được hiệu quả trong việc phân bổ tài nguyên trong hệ thống. Ta sẽ tính toán việc số lượng bản sao thực sự của tài nguyên mà hệ thống phải lưu trữ là bao nhiêu.. Và việc thay đổi cây mô tả khi chia nhỏ với số các nhánh lần lượt là 2 và 3 sẽ khác nhau ra sao. Cụ thể ta sẽ có 2 thống kê :
Số lượng bản sao trên mỗi tài nguyên được phân bổ vào hệ thống
Số lượng bản sao tài nguyên được lưu trữ trên mỗi nút trong hệ thống Với các tham số đưa vào để đánh giá là 100.000 tài nguyên mỗi tài nguyên được mô tả bởi bộ định danh dưới dạng cây tài nguyên có các tham số giống với phần truy vấn tìm kiếm đó là :
Mỗi cây gồm từ 4 đến 10 tầng, mỗi tầng là thuộc tính hoặc giá trị
Bắt đầu là root, số nút con của root là random từ 2 đến 4
Tương tự với các nút khác số nhánh con là từ 0 đến 4, nếu số nhánh con là 0 thì nút đó chính là nút lá Ta thấy rằng mỗi một nhánh bắt đầu từ gốc đến một nút lá sẽ cho ta một giá trị băm khác nhau và sẽ được lưu trữ tại những nơi khác nhau, trong hình vẽ dưới ta sẽ đánh giá dựa trên tổng số các bản sao của mỗi tài nguyên 48 0 20 40 60 80 100 <=2 <=5 <=20 <=30 <=40 <=50 Sồ bản sao/1 tài nguyên Tổ n g số tà i n gu yê n (% ) 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 Trên hình 22 ta có thể thấy được hơn 50% tổng số tài nguyên chỉ phải lưu trữ với ít hơn 5 bản sao, so với sốt nút lá trong mô tả tài nguyên có thể lên đến vài chục thì thậm chí số lượng bản sao còn ít hơn, điều này có được do việc sử dụng cây nhị phân để tìm dải ID lưu trữ, các nhánh có giá trị băm gần nhau có thể năm chung trong 1 dải ID và chỉ được lưu trữ 1 lần chứ không phải lặp lại nhiều lần. Hơn 80% tổng số tài nguyên được lưu trữ ít hơn 30 bản sao, cho thấy hầu hết các tài nguyên đều rơi vào khoảng này. Và hầu như toàn bộ tài nguyên chỉ phải lưu trữ nhiều nhát là 40 bản sao, một số rất ít các tài nguyên phải lưu trữ tới 50 bản sao. Như vậy theo đồ thị có thể thấy số lượng các tài nguyên có lượng bản sao lớn là ít so với số lượng những tài nguyên có số lượng bản sao ít và vừa phải rất nhiều, rõ ràng hệt thống thực sự hiệu quả trong việc giảm số lượng bản sao, phần lớn sử dụng ảnh xạ để tham chiếu đến tài nguyên thực sự. 49 0 20 40 60 80 100 <=2 <=3 <=5 <=7 <=10 <=12 <=15 Sồ bản sao/ 1 tài nguyên Số tà i n gu yê n (% ) 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 Hình 23 là đánh giá về tỷ lệ số lượng bản sao trên mỗi tài nguyên trong trường hợp sử dụng cây mô tả chung được chia nhánh với giá trị là 3, tức là mỗi nút trên cây mô tả sẽ có 3 nút con tương ứng. Có thể nhận thấy ngay là gần như 100% các tài nguyên có số lượng bản sao ít hơn 15 chỉ bằng 1/3 hoặc ít hơn so với trong việc chia đôi các nhánh trong xây dựng cây mô tả. Ngoài ra ta vẫn thấy được số lượng tài nguyên với số bản sao nhỏ cỡ 2, 5 bản sao chiếm lượng lớn trong tổng số tài nguyên. Trong đồ thì chỉ rõ lần lượt là lớn hơn 60% với trường hợp <=2 bản sao và hơn 70% trong trường hợp <=5 bản sao. Ngoài ra để có thêm chứng minh cho hiệu quả của việc phân bổ tài nguyên trong hệ thống ta sẽ phân tích số lượng bản sao mà mỗi node phải lưu trong hệ thống, đánh giá này sẽ cho 1 góc nhìn khác về hệ thống, tương tự ta cũng thực hiện với 2 trường hợp xây dựng cây mô tả chung. Trường hợp một thể hiện trong hình 26 là với cây mô tả có số nhánh con của mỗi nút là 2. Trường hợp hai thể hiện trong hình 27 là với cây mô tả có số nhánh con của mỗi nút là 4 và trong hình 28 với số nhánh con là 6. 50 0 20 40 60 80 100 <=10 <=50 <=100 <=500 <=1000 <=5000 <=10.000 <=15.000 Số tài nguyên / 1 node Tổ n g số n o de (% ) 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 Trong hình 24 ta có thể thấy số lượng nút có có nhiều bản sao là giảm dần với so với số lượng node có ít bản sao hơn. Từ đồ thị cũng thấy được hơn 40% các nút mạng chỉ cần lưu trữ 1000 bản sao của các tài nguyên, so với số lượng 100.000 tài nguyên thì rõ ràng là hiệu quả của việc phân bố tài nguyên là khá cao. Và các nút lưu trữ tài nguyên nhiều nhất phải lưu trữ tối đa là 15.000 tài nguyên. Tuy nhiên số lượng các nút như thế là rất ít. 51 0 20 40 60 80 100 <=10 <=20 <=50 <=100 <=200 <=500 <=1000 <=2000 Số tài nguyên / 1 node Tổ n g số n o de (% ) 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 Hình 25 cho thấy trong trường hợp chia cây mô tả ra nhiều nhánh hơn tại mỗi nút (4 nhánh) sẽ cho kết quả các nút phải lưu trữ ít tài nguyên hơn, một nút tối đa chỉ lưu trữ khoảng 2.000 tài nguyên, số lượng các nút lưu trữ nhiều hơn hơn 2.000 bản sao tài nguyên không còn thay vào đó số lượng các nút lưu trữ bản sao tài nguyên trong khoảng từ 500 đến 1000 tăng lên, cho thấy là các nút đã dàn đều số bản sao sang các nút có ít bản sao tài nguyên hơn. Với việc chia 4 nhánh tại mỗi nút của cây phân bổ khả năng phân bổ đều trên các nút rõ rệt hơn rất nhiều. 52 0 20 40 60 80 100 <=10 <=20 <=50 <=100 <=200 <=500 <=1000 <=1500 Số tài nguyên/ 1 node Tổ n g số n o de (% ) 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 Hình 26 là kết quả của việc chia 6 nhánh tại mỗi nút của cây mô tả chung. Ta thấy rằng kết quả là khá hơn một chút nhưng tương đối giống với trong việc chia 4 nhánh, Kết quả này là do việc thực hiện sinh dữ liệu về tài nguyên của chúng ta, các tài nguyên thường được chia nhánh từ 2 đến 4 cho mỗi nút thuộc tính hoặc giá trị. Trên thực tế thì sẽ không như vậy, do đó việc chia nhánh cây phân bổ để phân bổ tài nguyên còn phải phụ thuộc nhiều vào các tài nguyên trong thực tế. 4.2.2. Hiệu quả trong xử lý truy vấn Để thấy được hiệu quả của giải pháp đề xuất, phần này sẽ tính số lượng truy vấn trên mỗi nút trong 1000 nút tham gia hệ thống khi phải trả lời 1000 truy vấn khác nhau, và số lượng hope khi truy vấn trên mỗi truy vấn Kết quả được thể hiện ở hình vẽ 53 0 20 40 60 80 100 <=5 <=7 <=9 <=10 <=11 <=12 <=13 <=14 <=15 Số hope/truy vấn Số tr u y v ấ n (% ) 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 Trong hình 27 ở trên ta có thể thấy số truy vấn có số lượng hope <=15 gần như là tuyệt đối(100%) điều này thể hiện sự tương ứng với lý thuyết khi tìm kiếm với độ phức tạp log(N) với N là số nút mạng trong trường hợp này là 1000. Các tham số khác cũng cho thấy hệ thống thực chất không cần chuyển truy vấn nhiều như vậy, gần 70% số lượng các truy vấn được trả lời trọn vẹn chỉ trong ít hơn 5 lần chuyển truy vấn. Các con số còn lại cũng cho thấy việc số hope thậm chí còn nhỏ hơn do khi random nút để chuyển truy vấn có thể nút đó rất gần hoặc chính là nút trả lời truy vấn 54 0 20 40 60 80 100 <=2 <=5 <=10 <=20 <=50 <=100 Số lượng truy vấn / 1 node Tổ n g số n o de (% ) 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 Kết quả về số lượng truy vấn trên một nút trong hình 28 cho thấy 60,2% tổng số các nút chỉ phải tham gia trả lời trong nhiều nhất 2 truy vấn, 85,4% tổng số các nút chỉ phải tham gia trong ít hơn 5 truy vấn. Qua đó có thể thấy được hiệu quả của việc tìm kiếm trong hệ thống, số lượng các truy vấn mà mỗi nút phải trả lời là rất thấp. Theo đó 1000 truy vấn được gửi đi thì hầu như được giải quyết chỉ trong nhiều nhất 5 lần chuyển truy vấn giữa các nút. 55 Chương 5. Kết luận Trong chương này ta sẽ tổng kết lại các vấn đề nghiên cứu và giải pháp đề ra, theo đó đưa ra hướng đi chính trong tương lai cho việc nghiên cứu tiếp vấn đề tìm kiếm tài nguyên mạng. 5.1. Kết luận Khóa luận đưa ra một giải pháp cho việc tìm kiếm tài nguyên trên mạng ngang hàng thông qua tên miền khái niệm, cụ thể ở đây là trên mạng ngang hàng có cấu trúc, khóa luận đặc biệt sử dụng giao thức Chord để thay cho tầng phủ DHT nói chung. Bắt đầu bằng việc tìm hiểu và đánh giá mô hình chung của một hệ thống tìm kiếm tài nguyên, đánh giá hiệu quả của nó ta đã đưa ra những mục tiêu chính cho một hệ thống tìm nguyên tài nguyên có khả năng hoạt động hiệu quả. Các giải pháp xây dựng hệ thống tìm kiếm tài nguyên đã được đề xuất trên mạng ngang hàng có cấu trúc mang lại cho ta những nhận xét và ý tưởng của hệ thống mà ta xây dựng. Dựa vào những vấn đề còn tồn tại của các giải pháp cũ, và những mục tiêu đưa ra, khóa luận đã đề xuất một giải pháp mới. Hệ thống đưa ra đã thực hiệu theo những tiêu chí nhận định ban đầu của một hệ thống tìm kiếm tài nguyên hiệu quả. Thứ nhất, hệ thống có được khả năng mở rộng nhờ kế thừa ý tưởng của một số giải pháp trước đã đề ra là sử dụng tầng phủ là mạng ngang hàng có cấu trúc, mà cụ thể là những mạng có sử dụng DHT. Thứ hai, hệ thống sử dụng bộ định danh được xây dựng và định nghĩa như trong hệ thống INS – hệ thống tìm kiếm tài nguyên theo tên miền khái niệm, việc sử dụng bộ định danh đem lại hiệu quả cao trong việc mô tả tài nguyên, các mô tả tài nguyên theo quan hệ thứ bậc các cặp thuộc tính – giá trị giúp việc phân loại và mô tả tài nguyên sát thực và hiệu quả. Thứ ba, hệ thống mang lại hiệu quả cao trong tìm kiếm và phân bổ tài nguyên. Việc tìm kiếm tài nguyên thực hiện trên cây nhị phân được mô tả trong hệ thống với yêu cầu tính toán có độ phức tạp log(N) (với N là số nút mạng trong hệ thống) rõ ràng là đạt yêu cầu về tốc độ tìm kiếm. Thêm vào đó cây nhị phân được xây dựng hộ trợ cho việc xây dựng các ánh xạ tài nguyên để giảm thiểu số lượng bản sao tài nguyên cần lưu trữ trong hệ thống, và thiết lập khả năng tìm kiếm theo dải (tập hợp các tài nguyên thỏa mãn chung tính chất). Để đánh giá hiệu năng của giải pháp mới, khóa luận đã xây dựng một chương trình, mô phỏng lại ứng dụng tìm kiếm đã đưa ra, việc thực hiện ứng dụng cũng yêu cầu giao thức Chord hoạt động trên một mạng vật lý ảo bên dưới, chương trình thử nghiệm giải pháp với việc truy vấn và phân bổ một số lượng lớn các tài nguyên được 56 mô tả và một mạng với số lượng rất lớn các nút tham gia. Kết quả của các phép thử cho thấy, phương pháp đề ra đem lại hiệu quả rõ rệt trong việc phân bổ khi lượng tài nguyên phân bố đều trên tất cả các nút trong hệ thống. Việc truy vấn cũng được chia sẻ tải tốt giữa các nút mạng. 5.2. Hướng phát triển tiếp theo của đề tài Kết quả mô phỏng cho thấy tiềm năng của giải pháp là rất lớn. Tuy nhiên, đó chỉ là mạng mô phỏng. Để đánh giá hiệu năng của giải pháp một cách đúng đắn nhất, cần thử nghiệm trên một mạng thực sự. Vì thế, trong thời gian sắp tới, hướng đi tiếp của đề tài khóa luận là thực thi giải pháp trên một mạng ngang hàng thực sự có quy mô lớn, mà trong thực tế chính là quy mô của mạng Internet. Theo lý thuyết hệ thống mà ta xây dựng lên có khả năng chống chịu tốt đối với việc thêm vào và rời đi của các nút mạng, tuy nhiên hiệu quả trong vấn đề đó cũng cần được đánh giá trên một kiến trúc mạng thật sự với độ trễ và xắc suất thêm vào rời đi là thực tế. Việc sử dụng các hàm random để chọn nút mạng mỗi khi gửi truy vấn cũng chưa thực sự hiểu quả, ta hoàn toàn có thể cải tiến việc này và thay thế bằng việc gửi truy vấn để những nút mạng ít bị truy vấn đến để việc chia cân bằng tải của hệ thống thực hiện tốt hơn. Như vậy, việc nghiên cứu và phát triển đề tài còn rất nhiều vấn đề cần được giải quyết. Mà cần có sự đầu tư về thời gian và công sức của người thực hiện nghiên cứu. Chúng ta hy vọng trong tương lai hệ thống có thể được hoàn thiện để đưa ra giải pháp tốt nhất cho vấn đề tìm kiếm tài nguyên trên mạng. 57 Tài liệu tham khảo [1] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. In Proceedings of SIGCOMM 2001, San Deigo - CA, August 2001. [2] William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, Jeremy Lilley, The design and implementation of an intentional naming system, Proc. 17th ACM SOSP, Kiawah Island, SC, Dec. 1999. [3] Magdalena Balazinska, Hari Balakrishnan, David Karger, INS/Twine: A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery, International Conference on Pervasive Computing 2002, Zuric, Switzerland, August 2002. [4] L. Garcés-Erice, P. A. Felber, E. W. Biersack, G. Urvoy-Keller, K. W. Ross, Data Indexing in Peer-to-Peer DHT Networks, icdcs, pp.200-208, 24th IEEE International Conference on Distributed Computing Systems (ICDCS'04), 2004 [5] D. A. Tran, T. Nguyen, Hierarchical Multidimensional Search in Peer-to-Peer Networks, Department of Computer Science, University of Massachusetts, Boston, MA 02125, USA [6] Hoaison NGUYEN , Hiroyuki MORIKAWA ,and Tomonori AOYAMA , SENS: A Scalable and Expressive Naming System for Resource Information Retrieval ,IEICE TRANS. COMMUN., VOL.E89–B, NO.6 JUNE 2006 [7] Hoai Son NGUYEN, Thanh Dat NGUYEN, SMAV: A solution for multiple- attribute search on DHT-based P2P network, Department of Information Technology College of Technology, Vietnam National University, Hanoi [8] G Fox - Computing Peer-to-peer networks, in Science & Engineering, 2001 [9] RFC 1591, Domain Name System Structure and Delegation (Informational) [10] Ali Ghodsi. Distributed k-ary System: Algorithms for Distributed Hash Tables. KTH-Royal Institute of Technology, 2006. [11] William J. Reed , The Pareto, Zipf and other power laws [12] George K. Zipf (1935) The Psychobiology of Language. Houghton-Mifflin [15] [16]