ĐẠI HỌC QUỐC GIA HÀ NỘI
ÚTVG DỤNG MẠNG NGANG HÀNG VÀO TÌM KIÉM
VÀ QUẢN LÝ THÔNG TIN TÀI NGUYÊN INTERNET
M à số: Q C .07.19
C hủ nhiệm đề tài: TS. N eu v ễn Hoài Sơn
OAI HỌC QUOC GlA hA NÕi
Tf?UNG TÃM -THÔNG ĨIN thư VIẼr\ỉ
Hà N ộ i - 2008
MỤC LỤC
DANH SÁCH NHŨ>4G NGƯỜI THAM GIA THựC HIỆN ĐÈ T ÀI 3
DANH MỤC CÁC BÁNG BIÊU, HÌNH V Ê 4
TÓM TẮT CÁC KẾT ỌUẢ NGHIÊN cứu CHÍNH CUA ĐỀ TÀ I

5
BÁO CÁO TÔNG KÉT 7
1. Đặt vấn đ ề
7
2. Tổng quan nghiên cứu về mạng ngang hàng và tìm kiếm trong mạng ngang hàniỊ 8
2.1 Mạng ngang hàng lai ghép và tìm kiếm ihông tin tronơ mạng ngang hàng lai
ghép 8
2.2 Mạng ngang hàng không có cấu trúc và tìm kiếm trong mạng ngarm hàne khône
có cấu trúc 9
2.3 Mạng ngang hàng có cấu trúc và tìm kiếm thòntí tin trone mạng ngaiiíỉ hànu có
cấu trúc 10
3. Giai pháp tìm kiếm thông tin theo giá trị thuộc tính trên mạng ngang hàng có cấu
trúc SM A V 12
3.1 Tổntỉ quan 12
3.2 Ánh \ạ tên nội dung-khóa và Phân bô nội dung

6 Nguyễn Thị Nhật
Thanh
Ths
Khoa CNTT- ĐH Công nghệ, Đ HQG Hà NỘI
DANH MỤC CÁC BẢNG BIẺU, HÌNH VẼ
Hình I: Mô hinh mạng Napster 8
Hinh 2. Mô hình truy vấn thông tin trên mạng Gnutella 9
Hinh 3. Định tuyến trong mạng Chord 10
Hinh 4 . Mô hình phân bồ thông tin cùa giải thuật SMA V đề xuất
I 5
Hình 5. Ánh xạ khóa thứ cấp 16
Bảng I Báng ánh xạ khỏa phân bổ - nội dung thông tin 16
Báng 2. Bảng ánh xạ khóa thứ cấp 17
Báng 3. Báng ánh xạ khóa không phố biến 17
Hinh 6. Mô hình truy vấn thông tin trong giai thuật đề xuất 18
Hình 7: Tỷ lệ phần trăm tần số xuất hiện 1 thuộc tính/giá trị 21
Hình 8: Phân bổ tên nội dung trong các node
22
Hinh 9:Phân bô sô truy vân giữa các node trong m ạng 22
Hình 10: số ánh xạ sinh ra bói mỗi tên nội dung khi sứ dụng giái thuật SM A V

23
Hình I I: Thòi gian truy vấn 24
TÓM TẮT CÁC KẾT QUẢ NGHIÊN cứ u CHÍNH CỦA ĐỀ TÀI
Tên đề tài: ứng dụng mạng ngang hàng vào tìm kiếm và quán lý thông tin tài ntiu>ên
Internet
Mã số đề tài: Q C .07.19
Chú tri đề tài: TS. Nguyễn Hoài Son
Đơn vị công tác: Bộ môn M ạng và Truyền thông máy tính, Khoa Công nghệ thông
tin, Trường Đại học Công nghệ - Đ HQG Hà Nội

Công nghệ thông tin \ à Tmyền thông”, tháng 6. 2008
Kết quá đào tạo:
- Có 3 cừ nhân \'à 1 thạc sỳ tốt nghiệp trong khuôn khô cùa đề tài
Nâng cao năng lực chuyên môn cho cán bộ bộ môn trong lĩnh \'ực về các eiai
thuật định tuyến và tìm kiếm thông tin trong mạng ngang hàng
BÁO CÁO TỐNG KÉT
1. Đặt vấn đề
Sự phát triển nhanh chóng của Internet đã tạo ra cho chúng ta một cơ hội lớn và
cũng là một thách thức lớn trong việc sử dụng các tài nguyên thông tin trên Internet
một cách hiệu quả. Các tài nguyên này bao gồm các tài nguyên máv tính như CPU,
bộ nhớ, ồ lưu trữ, cúa các máy tính nối mạng, các tài nguyên thông tin như các
trang W eb hay các CSDL lưu trữ thông tin, các dịch vụ dựa trên nền W eb

Đe khai thác và sử dụng các tài nguyên này một cách hiệu qua và họp lý, việc quan
lý và tìm kiếm thông tin các nguồn tài nguyên này ỉà một vấn đề rất quan trọiiíì. Ví
dụ như đề một ứng dụng về tính toán lưới (Grid computing) sử dụng được một lượiiíí
tài nguyên lớn tính toán và lưu trữ thông tin, cần phai cung cấp cho nó các thông tin
về những tài nguyên tính toán trên Internet mà nó có thê sử dụne được. Hay một ứno,
dụng về Web services cần được cung cấp đầy đu các thông tin về các dịch vụ Web
liên quan mà nó có thế truy cập được. Người dùng cũng mong muốn đirợc cung cấp
tự dộng các thông tin cần thiết liên quan đến sớ thích, nhu cầu và tùy thuộc vào điều
kiện và hoàn cánh cúa họ.
Tuy nhiên, với đặc điểm là lượng tài nguyên trên Internet là rất lớn và phân tán ở
khắp nơi nên nếu quản lý các tài nguvên này theo những cách thông thutmg như sư
dụng các CSDL tập trung thì chi phí phát sinh sẽ rấl lớn. khả năng xư lý thỏim tin
hạn chế và mức độ chống chịu lồi không cao.
Vấn đề này có thế được giải qiivết bằng cách sư dụng các giao thức cua mạng
ngang hàng để quản lý và tìm kiếm thông tin về tài nguyên Internet. Mạng ngatm
hàng ra dời từ cuôi những năm 1990 với ứng dụn2 ban đâu là chia xe file nganií hàng
và được người dùng sử dụng rộng rãi, M ạng ngang hàng kết nối các máy tính có kha

ghép
Trong mạng ngang hàng lai ghép, diên hình là Napster[l]. tài nyuyên được phân
tán tại nhiều node khác nhau Iiliưng lồn tại một iTiủv chu index luxi giừ thông tm vẻ
node và tài nguyên lưu giữ tại mỗi node. Đê chia \é tài ntỉuyên thôníí tin. các node
trong mạng sẽ gứi thông tin về tài nguvên lưu giữ ơ node cua mình vê IIKÍ) chu. Cụ
thể với mạng chia xe file ngang hàng Napster, tên file sẽ được gứi vê má> chu index.
Việc truy vấn thông tin sẽ được thực hiện theo hai bước:
- Buớc truy vấn ihôns, tin về tài nguyên tại má>' chu index đẽ biêl ihỏne tin \ê các
node lưu giữ tài nguyên cân tìm kiêm
- Bước truy cập trực tiếp tài nguyên tại node kai yiữ tài nguyên dựa trên thông tin
được cuna cấp bởi máy chu index
llìiih 1 mô tá các bước thực hiện phân bô và truy \'ân ihông tin trong mạng Napstcr.
Niìpstei server
2: lookup (x)
3: peer 1 ÌUÌS X
peei 2
4: {lo>viilo;ì(l X.inp3
Hình 1: Mô hình mạng Napsler
Mô hinh mạrm rmana hàng lai ghép có ưu điêm là có thê giam tai cho má> chu so
với mô hình máv chu-khách truyên thông. Tim kiêm thông tin dựa trên mô hình
m ạng ngang hàng lai ghép được thực hiện tập trung nên đơn giàn và hiệu qua. Tu>’
nhiên, nhưng m ạng ngang hàng lai ghép có nhược điêm là khả năng m ơ rộng kém và
máy chủ index trở thành điểm yếu dễ bị tấn công.
2.2 Mạng ngang hàng không có cấu trúc và tìm kiếm trong mạng ngang hàng
không có cấu trúc
Với mạng ngang hàng lchông có cấu trúc như Gnutella[2], không tồn tại má>- chu
index mà thay vào đó, các node tạo nhiều Hên kết trực tiếp V Ớ I nhau nhưne khône
theo một quy luật nhất định. M ột nút trong mạng thực hiện truY vấn bãng cách phát
tràn thông báo truy vấn đến các nút xung quanh và các nút này sẽ tiếp tục phát tràn
đến các nút hàng xóm. Các node nhận được thông báo truy vấn sẽ tìm kiếm tronc dữ

Hash Table - DHT) đế to chức các nút mạng theo một cấu trúc không gian khóa nhất
định như mạch vòng (giai thuật Chord[5], giai thuật Pastry[6]) hay không gian n-
chiêu (giái thuật C A N [7]). Mỗi node trong mạng phụ irách một phần cua khôim uian
khóa và liên kết với nhau theo vị trí trên không gian khóa, Các thông báo trên mạnu
ngang hàng có câu trúc có địa chi là một khóa k và sẽ được định tu>'ến đến node phụ
trách khóa k này dựa trên các liên kết tronti khôniỉ gian khóa cùa các node.
Ví dụ với giao thức Chord, các node được phân bô vào một không gian khóa kiêu
mạch vòng, trong đó mỗi node duv trì các liên kết đến các node ơ cách nó nhữim
khoang cách nhất dịnh trong không gian khóa. Các liên kết này tạo nên bang định
tuyến (gọi là Bảng finger) ớ mỗi node, Một thông háo trong mạng Chord sẽ dược
định tuyến dựa vào bang finger tại niỗi node mà thông báo đi qua. Hình 3 biêu diền
cách thức định tuyến thông báo cua giao thức Chord,
p, ^ ^
p, - 2
p, *4
p«
p. B p.
P:-
p,. ^ 32
P;'
Po
P.I
: » <1 Ị
p'
Íp :^ 32
P'-
V
Ị_ Look upi 5-1) ~J
' V
______

So với cách thức tim kiếm thông tin trong mạrm ngang hàng khône có cấu trúc. ,
việc tìm kiếm thông tin trong mạng ngang hàng có cấu trúc dược thực hiện với chi I
phí ít hơn rất nhiều do số thông báo tối đa cần gứi chi là 0(!oeN ) thông báo . Neoài
ra nếu thông tin có tồn tại trên mạng thì xác suất tìm thấy thông tin sẽ rất cao. I
Tuy nhiên, giái thuật DHT chỉ hỗ trợ tìm kiếm khóa chính xác. ĩức là tìm kiếm nội
dung thông tin gắn với một khóa k nào đó, trong khi rất nhiều ứng dụng [8.9.10] đòi
hỏi việc tim kiếm nâng cao như tim kiếm theo khoáim 111,12], tim kiếm theo các giá
trị thuộc tính [13-16], tìm kiếm uần đúng [12], Đã có nhiều nghiên cứu \ ê tim
kiếm thông tin trên mạng nganu hàng có cấu trúc nhăm tim aiái pháp nâng cao kha ’
náng tìm kiếm dồng thời đảm bao tính hiệu qua cũnu như khá năng mơ rộng cua hệ
thống.
Đề tài nghiên cứu Q C.07.19 tập trung vào kỹ thuật lìm kiêm thông tin theo giá irỊ
thuộc tính trên mạng ngang hàng có cấu trúc. INS/T\vine[l3J đưa ra mỏ hình hệ
thống tên miền dịch vụ xây dựng trên mạng tmane hànt» có câu trúc với tên miên dịch
vụ là một câv thuộc tính/tiiá trị phân tâng. Môi tên miên dịch vụ được ánh xạ vào niộl
tập hợp các khóa là íỉiá trị bãm của các nhánh cua tên miên. Mặc dù INS/T\vine hó
trợ tìm kiếm theo từng phần ứng với các nhánh cua tẻn miên, nhung \ iệc tìm kiêm sẽ
không thực hiện đưcrc với các truv vân khônẸ thuộc các nhánh cua tên miên. Ngoài ra,
hệ thống INS/Twine không đảm báo tính 4 ^ b ă n g tai giữa các node do các node phụ
trách các gia trị-thuộc tính phố biến sẽ phai chịu tai \ ẻ lưu giữ dữ liệu và tru>' vân lớn,
Giái pháp CDS[14] cũne sử dụng các cặp thuộc tính giá trị đê định danh nội dung
cần chia xe. Tuy nhiên, khác với INS/Twine. CDS tạo nhiêu khóa cho một nội dung
từ mồi cặp giá trị-thuộc tinh trong tên miền và phân bỏ thông tin về nội dung đến các
node phụ trách các khóa đó, N hư vậy. khi truy \ ấn nội dung. CDS chi sừ dụng một
cặp tĩiá trị-nội durm đế tạo klióa truy vấn và taiy vấn đến node phụ trách khóa đó.
CDS cùng đề ra giai pháp tạo Ma trận Cân băng Tai (Load Balancing Matrix - LBM)
dế giai quyết vấn đề cân bàne tai. Tuy nhiên giai pháp CDS Tạo nhiêu dư thừa trong
việc quan lý LBM cũim như dư thừa trong liru giữ dữ liệu và truy \ ân.
(ìiai pháp Data lndexirm[15] tạo các khóa phân bỏ từ các nhánh từ nút ngọn tới núl
uốc cùa cây mô ta dữ liệu và lưu ííiìr ánh xạ giữa các khóa phân bò nà\- tại các node

tính trong tên nội dung. Ví dụ như tên nội dung thông tin về một cuốn sách có thê
được biếu diễn như dưới đâ\’
(tên sách=’'A”, tác íỉiả=’'B''.nlià xuất b ản-'C ". năm phát hành="D". giá == "H".
phân loại = “F”)
trong đó các thuộc tính đã được định nghĩa trước.
Truy vấn thông tin sẽ dựa trên các cặp thuộc tính/giá trị trong đó câu truy \'ân sẽ
chứa một tập các cặp thuộc tínlVeiá trị cân tru\ \'ân. Kêt qua tìm kiêm tra vê sẽ là các
nội dung thông tin với tên nội dung có chứa các cặp ihuộc tinh/giá trị cân truy vân.
Ví dụ như truy vấn sau:
(tác gia='’B".nhà xuất ban=”C'')
sẽ tim kiám nội dunu ihônu tin về sách cúa tác gia B được xuât ban bơi nhà \uấl
hản c, haỵ iru> vấn:
(nhà xuat bíin=”C”.phân loại ="F"}
sè tìm kiếm nội đune thôrm tin \ ề sách thuộc phân loại F cua nhà \uàt ban c.
Nội dung thônc tin sẽ bao uồm các thông tin chi ticl liên quan đên thônt: tin, Nếu
thông tin là file dữ liệu thi nội dunu thônc tin có thê là đườna link đén nơi lưu íiiữ
file dĩr liệu đó.
12
Các node lưu trừ tên nội dung và nội dung thông tin sẽ tạo thành một mạno neanti
hàng có cấu trúc dựa trên một giao thức DH T như Chord, CAN, Các thông báo
phân bô thông tin và truy vần thông tin gửi giữa các node được định tuyến theo địa
chi là các khóa và dựa trên báng định tuyến luiỉ tại mồi node.
Việc phân bô nội dung thông tin sẽ được thực hiện dựa trên việc ánh xạ tên nội
dung vào khóa phân bô và nội dung thông tin sẽ được gửi đến node phụ trách khóa
phân bô. Giải pháp ánh xạ khóa của chúng tôi là tạo khóa phân bô chính từ mỗi cặp
thuộc tính/giá trị trong tên nội dung, Do có những cặp thuộc tínlVgiá trị phô biến nẻn
đê tránh tình trạng quá tải cho các node phụ trách các khỏa phô biến, các node này sẽ
chi lưu một phân nội dung thông tin gán với khóa phô biến, phần còn lại sẽ được liai
tại các node khác dựa trên các khóa thứ cấp. Các khóa thứ cấp lá giá trị băm cua hơn
hai cặp thuộc tính/giá trị có trong tên nội dung được phân bô. Node phụ trách khóa

Ban đầu. tên nội dung cua một nội dung thông tin dược ánh xạ thành nhiều khóa,
mỗi khóa là giá trị bãm cua một c¿ip thuộc tinh-giá tri chứa trong tên miền nội dune
thông tin. Việc sừ dụng hàm băm sẽ đảm bảo các khóa được phân bố đều trona toàn
miên không gian khóa.
Ví dụ, giả sử tên miền của một nội dung thông tin có chứa N cặp thuộc tínli'giá trị
và được ký hiệu là ((ai,Vi), (a2,V2), (aN,v^>)). Khi đó, nút muốn phân bỏ nội dung
thông tin đó vào mạng sẽ tính toán N khóa như sau:
k| = H(a,,V|)
k2 = H(a2,V2)
líN = H{aN,VN)
trong đó H là một hàm bãm như SHA-1, MD5,
Tiếp theo, node phân bổ nội dung sẽ gửi thông báo truy vấn sổ lượng tới các node
«/, /7,vphụ trách các khóa kị. kl, k\ dựa trên eiao thức DHT. Các node nà\ sè
trả vê sô lượng tên miên được ánh xạ vào mỗi khóa và thône tin cùa các node như địa
chi IP. Với mỗi khóa k^{\ <d < N), sẽ có hai trường hợp xảy ra.
• Số lượng nội dung thông tin đã gán với khóa k,¡ nho hơn một số lượng Nmax được
dịnh trước. Trong trường họp này khóa Ấ:,ysẽ trơ thành khóa phân bô và được eọi
là khóa phân bố không phổ biến (viết tất là khóa không phố biến)
• Số lượng nội dung thông tin đã gán với khóa k,! lớn hon hoặc bàne Nmax- Tronu
trường hợp này khóa k,i không được sử dụng làm khóa phân bổ và được tỉọi là
khóa phổ biến và cặp thuộc línỉi/giá trị tương ứim được gọi là cặp thuộc tính/giá
trị phổ biến.
Với mồi khóa không phổ biến nội dunỹ thônti lin sẽ được lưu tại node «,/ phụ
trách khóa này. Node phân bô thông tin sẽ sư dụrm thông tin cua node n,i dê uưi
thông báo phân bổ thông tin irực tiếp đến node n,¡.
Với mỗi khóa phổ biến node phân bô thông tin sè tạo các kJióa thứ cắp là uiá trị
băm của cặp thuộc tính/2.iá trị phố biến ứng với kj \à từng căp thuộc tính/eiá trị phô
biến khác. Các khóa thứ cấp này được gọi là các khóa thứ câp bậc 2 (ứng \ ới hai cặp
thuộc tínli/giá trị), Nếu số lưạne, các cặp thuộc tính/giá trị phô biến là x ' thì số khóa
thứ cấp bậc 2 sẽ là X ' (X ' -1 )/2 không trùng nhau.

Giá sư số nội dunc thôníi tin gắn \ ó'i khóa su b j(! nho hơn NMAxthì nội đung thôns
tin đó sẽ được phân bô đèn nút phụ trách khóa sith kị. đông thời thông tin về khóa
thử cấp bậc 2 sLib_ki. khóa 1<4 và khóa ks ứng với 2 căp thuộc tíiilvgiá trị khôrm phô
biến (a4,V4),(as,V5) sẽ đirợc lưu tại node phụ trách khỏa k|Và node phụ trách khóa Rị.
Nếu số nội dung thônũ tin găn với khóa suh_kỊ lớn hơn Nm \x- các khóa thứ cấp bậc 3
sau đây sẽ được tạo ra:
sub k|| = H((a|.\'i).{a;.\;).(aj;,v3)
15
Viéc ánh xa giüa các khóa dugc mó tá nhu trong Hinh 1.
k2
H(a2,V3)
l<3
H(a:„v,)
k4
Híaj.vj)
k?
H(a5,V5)
Hinh 5. Ánh xa khóa thú cap
Viéc ánh xa khóa nhu Hinh 1 se giúp cho viéc tim kiém bát dáu tir khóa k| dugc
thuc hién mót cách nhanh chóng cho dén khi hét các kliá náng lim kiém thóng tin.
Mói node trong mang ngang háng sé duy Iri mol bang ánh xa khóa phán bó-nói
dung thóng tin nhu Bang 1. Các thóng tin dugc luu trong bang bao góm khóa phñn
bó, tén nói dung vá nói dung thóng tin gán vói khóa phán bó, só luong nói dung
thóng tin gán vói khóa phán bó vá có trán. Khi só lugng nói dung thóng tin gán \ói
khóa phán bó lán han có trán sé dugc bát lén (có giá tri Yes), Só krgng nói
dung thóng tin gán vói khóa phán bó có thé kVn han só lugng nói dung thóng tin
dugc luu trong node khi ca trán dugc bát lén do mót phán nói dung thóng tin dugc
luu tai các node khác. Só dém dói vói mói khóa k, sé dugc táng ién klii có thóng báo
phán bó thóng tin vái khóa phán bó la khóa k, dugc gui dén hoác khi có thóng báo
ánh xa khóa dói vói khóa k, dugc güi dén.

Các khóa không phổ biến và các cặp thuộc línli''ciá trị khône phò
biến tương ứng
ki
{(ai4,V|4),k|4,6},{(ai5,v,5).k|5,5],{(aK,.V|6).k|f„2Ị
•^2
{(a2vV23),k23,1 } ,{(a24A'24)'k24’'^!
3.3 Truy vấn thông tin
A. Tổng quan
Trong hệ thống đề xuất của chúng tôi, truy vân thôna tin dươc tiên hanh theo các
cặp thuộc tính/giá trị trong tên nội dun?. Câu tm> vân thỏnu tin sC' bao gôm các cặp
thuộc tínlVeiá trị truy vấn. và kết quá truy vân tra vê
bao gôm các nội dung thông tin
có tên nội dung chứa các cặp thuộc tính/giá trị tru>' \ân và các cặp thuộc tính/giá trị
có thể có trong các truy vấn tiếp theo.
Dựa trên cách phân bô thông tin như đã trinh hà}' ơ trên, việc tru>' \'án thông tin
dựa trên các cặp thuộc tíiih/giá trị sẽ được thực hiện theo nhiêu bước. Trước tiên,
tươníí tự như bước đẩu tiên khi phân bô nội dung thông tin. node nhận yêu câu truy
vấn sẽ gửi yêu cầu truy vấn số lượng tới các node phụ trách các khóa tương ứng \Ớ1
các cặp thuộc tính/íiiá trị có trong câu truy vấn. Việc gưi gói tin sè thông qua giao
thức cua mạng ngang hàng có cấu trúc. Sau kJìi nhận được kêt qua tra \'ê. nó sẽ chọn
khóa có số lưọiiíỉ thông tin ít nhất làm khóa trm' \ ấn k,, \ à gưi trực tiếp thông báo > êu
cầu truy vấn đến node phụ trách klióa tru>- \ ấn.
Sau khi nhận được Ihônu báo yêu câu truy \ân. node phụ trách khóa truy \'àn
trước tiên sẽ kiếm tra cờ tràn tirơtm ínm với khóa tru> \'ân Nêu cờ tràn không
được bật lên điều đó có imhĩa tất ca các nội dung thông tin gán với khóa Iruy vấn
đều dươc lưu yiừ tại node phụ trách khóa tru> \ẩn. Trong trường họp nà\. node phụ
trách khóa truy vấn k,! sè tìm kiếm nội dung thòng lin lưu giữ trong bang ánh xa khóa
phân bố-nội duiiR thônu tin theo khóa tru\' vân k^,. No sẽ tra \ ê kêt qua lá những nội
dung ihônc tin có tC'n nội duriii chứa tât ca các cặp thuộc tính/giá trị có trong câu tru\
17

.
Nêu câu truỵ vân chi chứa các cặp thuộc linh/giá trị tương úna \ ới khóa truv \ ấn kj
(nói cách khác là giá trị băm cùa tất cà các cặp thuộc tính eiá trị truN vấn
((^h'^
2
) ,(ci¡,vj)) thì node phụ trách khóa tru> vấn sẽ gừi các nội duntí thông tin ỉiẽn
quan đên khóa truy vận mà nó lưu giừ. và danh sách các cặp thuộc tíW aiá trị được
ánh xạ từ khóa truy vân trong báng ánh xạ khóa khônu phô biến và bàna ánh \ạ khóa
thứ câp. Danh sách này sẽ được sắp xếp theo thứ tự RÌam dần cua số lượim các nội
dung thông tin tượng ứng. Người dùng sẽ lựa trọn tiếp các cặp thuộc tínli íiiá trị tiếp
theo đế truy vấn tiếp nếu muốn.
Nêu số lượng cặp thuộc tinh/giá trị trong cảu tru_\ vấn nhiều hơn số lượnu cíỊp
thuộc tính/giá trị tương ứng với khộa truy \ấn. node phụ trách khóa truy \à n sẽ tìm
kiêm trong Báng ánh xạ khóa thứ câp và trong banti ánh xạ khóa khônu phô bien các
entry {(a^
2
,v,
2
) X r J

lưưnu ứníz \'ới khoa tru\' \ân k^i.
Với môi entry nêu cặp thuộc tinh/già trị (a,|,.Vqi) có troni; càu truy vàn
((ai,V
2
), ,(ü„vj), khoa k^, sẽ trơ thành ứng \'iên khóa tru>' vấn tiếp theo, Lne, \ièn
khóa truy vân có sô lượng nội dung thông tin uắn với nó là Iilio nMt sè trơ thanh
khóa truy vấn tiếp theo.
Nêu khóa truy vấn tiểp theo là một khóa thử cấp. node phụ trách khỏa truy \ ấn sẽ
gửi yêu cầu truy vấn đến nút phụ trách khóa thứ cấp nà>. đồng thời nó sẽ tim kiém
các nội dung thông tin mà nỏ lưu giữ thoa mãn diều kiện truy vấn và tra vê kêl qua.

Đê hạn chê sô khóa phân bô tạo ra thì phải hạn chế số cặp thuộc tính aiá trị phô
biên băng cách chọn cận trên Nmax lớn. Tuv nhiên việc nàv có thè dẫn đến việc các
nọde phụ trách các cặp thuộc tính/giá trị phô biến phai chịu tai lớn và do đó sỗ dẫn
đên sự mât cân băng vê tái. Vi vậy, việc lựa chọn cặn trẽn Nmax rất quan trọng và tù>
thuộc vào sự phân bô cua nội dunti thôim tin vào các node trone mạng neaim hàng.
Truy vân thông tin cũng tùy thuộc vào sự phò bicn cua các cặp thuộc tính/eiá trị có
trong câu truy vân. Neu ton tại một cặp ihuộc tính uiá trị không phô biến trong câu
truy vân thì việc truy vấn thông tin chi ihực hiện \X7Ì mội lru\' vấn. Nếu không. \ iệc
truy vấn thông tin sẽ được thực hiện nhiều lần tùy thuộc vao số !ux,mg nội dunu ihỏnti
tin tim kiếm.
Các đánh giá trên mới chi dừng lại ơ mức độ đinh tinh. lYong phần tiếp theo chune
tôi sẽ ihực hiện mô phong giai ihuật đe xuất và tiến hành dánh giá giai Ihiiật mộl cách
định lượng và chi tict hơn.
3.4.2 Đánh giá dựa trên mô phỏng
A. Cách thức mô phỏng
Chương trình mô phong được xâv dựng băny naôn nyừ C# trC’ii MS Visual studio
2008.
Đế thực hiện việc so sánh, chươiig trình mô phonti cài đặt 2 thuật toàn phân phỏi tC-n
nội dung:
• Phân phối tên nội dune theo giá trị bãm cua mỗi cặp giá trị thuộc linh (Phàn phôi
thôim thườiig). Do cách phân bô tên nội dung nlur trên nên việc xư lý tru\ vàn
dược thực hiện bàng cách chọn ngẫu nhiên 1 cặp thuộc tính/giá tri co trong câu
truy vấn và gưi truy vấn tới node phụ trách khoa cua cặp thuộc tính giá trị được
chọn.
• Phân phối tên nội dung theo thuật toán SMAV
Giao thức Chord được sư dụne trong mô phong mạng ngang hàng có câu trúc. Sô
node trong mạng là 2000 \'à không gian khóa là 16.
Cận trên số tên nội duim uắn với 1 khóa N|113\ dược tíiih ihông qua tông sô cặp
thuộc tính/íỊÌá trị trotm tất ca các tên nội dung được chia se trẻn mạng va sô khóa liên
quan đến cac cập thuV’ tính giá trị này, Trong mô phong nà>. chúng tôi tính Nmax

1
0.9
0.8
0.7
06
0 5
0 4
0,3
0 2
0.1
0
- Ftiần
trăm số
thuòc
tinh
11 16
21
26
Tần s ố xuất h iện cua cặp thu ộ c tin h/giá trị
Hình 7: Ty lệ phần trăm tần số xuất hiện 1 thuộc tính/giá trị
F linli 7 thế hiện sự phàn bố cua các cặp aiá trị. thuộc tiiìh trên các lên nội duníi ihône
tin trong mô phóntí. Do tuân theo luật phàn bô Zipf nên ta thây có 1 sô thuộc tinh'gia
tri xuất hiện với tần số rấl lern. Đó chính là các thuộc tinh giá trị phô biên. \uât hiện ơ
nhiều tên nội dunti khác nhau. Ket qua mò phong cho thấ\ \ ới 20.000 tên nội dung,
số lưựnu các thuộc lính/tỉiá trị phô biên tu\ chi chiêm dưởi 5® 0 lônt: sô các thuộc
tính/giá trị sonu tần số xuất hiện cun nó lại rât lớn. có thuộc tính/giá trị xLiât hiện tới
8 IS'’ lần tức là xuất hiện trorm hơn 42% lẽn nội dung. Chinh các thuộc línli uiả trị
nàv tỉâv lên sự mất càn bằim \ ề tai nội dune khi ta thực hiện việc phân bô tên nội
duim dựa trèn DHT.
ve j cuôn sách gôm các thuộc tính như: mã sách, tiêu dè, tác gia. năm xiiắi han. nliLi

0.4
0 3
- Riẳn I
trăm số
thuôc
linh
11 16 21 26
Tằ n s ố xuát h iện c ùa cặp th u ộ c tinh /g iâ trị
Hình 7: T>' lệ phần trăm tần sổ xuất hiện 1 thuộc tínk'giá trị
Hìnli 7 thế hiện sự phân bố cua các cặp giá trị/thuộc tinh trên các tên nội dung thông
tin trong mô phong. Do tuàn theo luật phân bô Zipt'nén ta thây có 1 sô thuộc tính/giá
trị xu¿it hiện VỚI tần số rất lớn. Đỏ chính là các thuộc tính giá trị phô biên, xuât hiện ơ
nhiều lên nội dune khác nhau. Kết qua mô phong cho ihấy với 20.000 lên nội dung,
số lirợng các thuộc tinh/i:iá trị phô biến tu>' chi chiếm dưới 5% lông số các thuộc
tính/giá trị soim tần số xuất hiện CLUI nỏ lại rât kVii, cỏ thuộc tinh giá trị XLiàt hiện tới
8 15^ lần tức là xuất hiện troim hem 42% lên nội dung. Chinh các thuộc tính/giá trị
nàv gây lên sự mất c¿in hàna về tai nội dung khi ta ihực hiện \ iệc phân bò tên nội
dung dựa trên DHT.
21
\
2000
1800
0 1600
■ă
C 1400
ro 1200
C
•ã 1000
‘1 800
I 600

2500
>
2000
"0
1500
ơí
1000
500
0
I

Truy vấn
I I
thương
-Truy vẩn I
theo Ị
SMAV
501 1001 1501 2001
Thứ hạng {rank) cùa các node theo số truy vấn
Hình 9:Phân bỏ số iruy vấn giữa cac node trong mạng
Với giải thuật SMAV, tên nội dung được phân bổ đều hơn trên các node nên việc xư
lý các truy vân liên quan đên tên nội dung trên các node cũng không gâ\ ra sự chênh
ỉệch vê tải nhiêu so với phưomg pháp DHT binh thường. Hình 9 cho thẩ>. khi xét với
5.000 truy vân khác nhau và node thực hiện truv \ ấn được chọn ngẫu nhiên trên
2.000 node của mạng, tải truỵ vấn cúa phương pháp SM AV được phân bố khá đều,
node nhiêu nhât phải xử lý gần 750, trong khi theo phương pháp phân bố dữ liệu
thông thường, có node phải xứ lý tới hơn 4.000 tru> vấn
3
■o
:õ*

Mình 10: số ánh xạ sinh ra bơi mồi tC‘n nôi dune khi sư dụne aiai thuậl
SMAV
Hình 10 cho thấv đồ thị biếu diễn phần trăm số tên nội dung iheo sổ ánh \ạ dưực sinh
ra bởi mồi tên nội dune trong quá trinh phân bô thông lin. Anh xạ ơ đây dược tính là
tổng số tất cả các ánh xạ các loại mà node cân lưu trữ như ánh xạ khóa phân bò va
tên nội dung, ánh xạ khóa thứ cấp các bậc khác nhau, ảnh xạ khônu phô biên \ à ánh
xạ đặc biệt. Có hơn 65% số tên nội dung sinh ra ít hon 32 ánh xạ theo giai thuật phân
bồ SM AV. Số tên nội dunti sinh ra nhiều hơn 77 ánh xạ chiếm khoang 10% tông số
tên nội dune. Đây là số tên nội dung chứa nhiêu cặp thuộc tínlvgiá trị. trong đó có
nhiều cập thuộc tính/aiá trị phổ biến. Kết qua mô phong cũng cho thấ> trung bình
mồi tên nội dunc thônu tin sinh ra khoang 30 ánh xạ.
T h u i y i« , .
xử lý 1 truy
ván theo
cách thõng
thướng
-Thời gian I
xử lý 1 truy I
ván theo 1
SMAV
1001 2001 3001 4001
T h ử h ạ n g cua các câu tru y v ẩn th e o th ờ i g ian x ừ lý
5001
Hình 11: Thời gian truy vân
Khi xư lý 5.000 câu truy vấn trong mạng mỏ phong nói trôn, chúng tôi tiến hành đo
thời gian trung binh để xứ lý 1 câu truy vấn theo cách iruỵ vấn bình thường \'à tlĩeo
giảrthuật SMAV. Thời gian xứ Iv 1 truy vấn được tính băng cách lây tông thời gian
thăm dò số lượng khi thực hiện truy vấn và ihời gian chuỵẻn tiêp câu truy vân tởi
node dích. Với cách thức hoạt độnij, cua SMAV. cân nhiêu thời gian hơn khi xư lý
query so với phương pháp phân bô dữ liệu thông thường, vi trong giai thuật SMAV