Luận vă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

ô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]