ĐẠ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
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
1
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
2
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
3
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
4
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.
5
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
6
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.
1.2.2.
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.
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
7
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
8
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 “citywashington”. 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
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ị]
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
10
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
11
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
12
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.
13
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
14
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.
15
- Xem thêm -