ĐẠ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 đã
Mục lụcMở đầ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
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
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ị.
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ề
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
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
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 để
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
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.
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
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
đặ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.
Copyright: Tài liệu đại học ©