Luận án Nghiên cứu cải thiện hiệu năng định tuyến mạng ngang hàng P2P

in liên hệ về mỗi nút khác trong mạng để định tuyến 
47 
các bản tin truy vấnvà các nút mạng có thể lựa chọn gửi song song đồng thời bản tin 
truy vấn trên nhiều tuyến đường. Vì vậy hiệu năng tìm kiếm sẽ bị ảnh hưởng bởi 
tham số Alpha (số yêu cầu tìm kiếm đồng thời), trong kịch bản mô phỏng chọn giá 
trị Alpha lớn nhất để cải thiện hiệu năng tìm kiếm Kademlia. 
Bảng 2-1. Các tham số dùng cho mô phỏng Kademlia 
Tham số Ý nghĩa Giá trị 
Alpha Số yêu cầu tìm kiếm đồng thời trong ҡ-bucket 16 
ҡ Số liên hệ (contact) trong ҡ-bucket 16 
Stabtimer 
(s) 
Chu kỳ chạy thuật toán ổn định 144 
Bảng 2-2. Các tham số dùng cho mô phỏng Tapestry 
Tham số Ý nghĩa Giá trị 
Base Cơ số của ID 16 
Stabtimer (s) Chu kỳ chạy thuật toán ổn định 144 
Redundancy Số nút dự phòng 4 
Max_repair_num Số nút hỗ trợ sửa lỗi 10 
Bảng 2-3. Các tham số dùng cho mô phỏng Chord 
Tham số Ý nghĩa Giá trị 
Base Cơ số ID 16 
Successor Số lượng hàng xóm (successor) 16 
Pnstimer (s) Chu kỳ cập nhật bảng fingers 144 
Basictimer (s) Chu kỳ chạy thuật toán ổn định 144 
48 
2.4.3.3 Kết quả mô phỏng và thảo luận 
Nhóm 1: Kết quả mô phỏng cho thấy khi mô phỏng các tham số hiệu năng, 
định tuyến đệ quy cải thiện đáng kể so với định tuyến lặp. Cụ thể hình 2-14 độ dài 
đường tìm kiếm khi sử dụng Chord đệ quy đã cải thiện 25% so với Chord định 
tuyến lặp. 
Hình 2-14. Độ dài đường tìm kiếm trung bình Chord_iterative và 
Chord_recursive 
Độ trễ trung bình khi sử dụng định tuyến đệ quy đã giảm 50% so với định 
tuyến lặp hình 2-15, ngoài ra băng thông tiêu tốn và tỷ lệ tìm kiếm thành công cũng 
được cải thiện đáng kể. 
Hình 2-15. Trễ trung bình Chord_iterative và Chord_recursive 
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
0 900 1800 2700 3600
A
ve
ra
ge
 h
o
p
 c
o
u
n
t
Life mean(s)
 Chord _ Iterative
Chord_Recursive
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0 900 1800 2700 3600
A
v
e
r
a
g
e
 l
a
te
n
c
y
Life mean(s)
 Chord _ Iterative Chord_Recursive
49 
Hình 2-16. Tỷ lệ thành công của Chord_iterative và Chord_recursive 
Hình 2-17. Băng thông tiêu tốn ( số bytes /s) Chord_iterative, Chord_recursive 
Kết quả mô phỏng khi cài đặt mạng SimpleUnderlay và InetUnderlay cho thấy 
các tham số hiệu năng như băng thông tiêu tốn hình 2-18 và độ dài đường tìm kiếm 
hình 2-19 là gần như đồng nhất. Tuy nhiên trễ tìm kiếm qua InetUnderlay giảm tới 
300% so với mô hình SimpleUnderlay hình 2-20. Đây chính là nhược điểm của định 
tuyến qua mạng chồng phủ, trễ giữa hai nút của mạng chồng phủ quá lớn so với 
đường định tuyến lớp nền tảng. 
Hình 2-18. Bytes/s gửi từ SimpleUnderlayNetwork và InetUnderlayNetwork 
0
10
20
30
40
50
60
70
80
90
100
0 900 1800 2700 3600
A
v
e
r
a
g
e
 d
e
li
e
r
y
 r
a
ti
o
(%
)
Life mean(s)
 Chord _ Iterative Chord_Recursive
0
10000
20000
30000
40000
50000
60000
0 900 1800 2700 3600
A
v
e
r
a
g
e
 b
a
n
d
w
id
th
 c
o
n
su
m
p
ti
o
n
Life mean(s)
 Chord _ Iterative Chord_Recursive
50
55
60
65
70
75
80
85
90
95
100
105
110
115
120
125
130
0 5000 10000 15000 20000
B
as
e
O
ve
rl
ay
: S
en
t 
To
ta
l B
yt
es
/s
Network size
SimpleUnderlayNetwork InetUnderlayNetwork
50 
Hình 2-19. Độ dài đường định tuyến qua mạng SimpleUnderlayNetwork 
và InetUnderlayNetwork 
Hình 2-20. Trễ tìm kiếm SimpleUnderlayNetwork và InetUnderlayNetwork 
Nhóm 2: Các kết quả mô phỏng cho cả ba thuật toán định tuyến DHTs: 
Kademlia, Tapestry và Chord được thể hiện trong hình 2-21 đến 2-26. Hình 2-21 
thể hiện tỷ lệ tìm kiếm thành công của cả ba thuật toán với kích thước mạng khác 
nhau. Khi kích thước mạng tăng thuật toán Kademlia có tỷ lệ tìm kiếm giảm đáng 
kể so với Chord và Tapestry. Tapestry duy trì tỷ lệ tìm kiếm thành công đến 99% 
khi kích thước mạng tăng. Chord cũng duy trì khá tốt ở tỷ lệ tìm kiếm 97%. 
Hình 2-21. Tỷ lệ tìm kiếm thành công và số nút 
2.5
3
3.5
4
4.5
5
5.5
6
6.5
7
0 5000 10000 15000 20000K
B
R
T
e
st
A
p
p
:O
n
e
-w
a
y
 H
o
p
 c
o
u
n
t
Network size
SimpleUnderlayNetwork InetUnderlayNetwork
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0.55
0.6
0.65
0.7
0 5000 10000 15000 20000K
B
R
T
e
st
A
p
p
:O
n
e
-w
a
y
 L
a
te
n
c
y
Network size
SimpleUnderlayNetwork InetUnderlayNetwork
51 
Kết quả hình 2-22 cho thấy tỷ lệ trễ liên kết trung bình của các thuật toán với 
kích thước mạng khác nhau. Thuật toán Tapestry sử dụng kỹ thuật sao lưu đường 
dẫn, vì vậy Tapestry có Tstretch nhỏ nhất. Thuật toán Chord cũng duy trì khá tốt khi 
số nút trong mạng tăng. 
Hình 2-22. Tỷ lệ trễ dãn cách trung bình Tstretch và số nút 
Hình 2-23 thể hiện băng thông tiêu tốn của cả ba thuật toán (bytes/s) với mạng 
có kích thước mạng khác nhau. Băng thông tiêu tốn của thuật toán Chord giảm đáng 
kể so với hai thuật toán còn lại. 
Hình 2-23. Băng thông tiêu tốn và số nút 
Phần kịch bản mô phỏng tiếp theo được thực hiện với mạng có kích cỡ 1000 
nút và phân bố xác xuất tham gia và rời mạng của các nút theo phân bố weibull. 
Thời gian hoạt động trung bình của một nút (lifetime mean) thay đổi lần lượt 1800s, 
2400s, 3000s, 3600s, 4200s. Khi mạng có độ ổn định thấp Chord có tỷ lệ tìm kiếm 
thành công khá thấp, kết quả được thể hiện hình 2-24. Tuy nhiên băng thông tiêu 
tốn của Chord duy trì không đổi và tốt nhất trong cả ba thuật toán ( Hình 2-25) 
0
0.5
1
1.5
2
2.5
3
0 1000 2000
T
st
re
tc
h
Số nút
 Chord
Tapestry
 Kademlia
52 
Hình 2-24. Tỷ lệ tìm kiếm thành công và thời gian hoạt động 
 trung bình của nút 
Hình 2-25. Băng thông tiêu tốn và thời gian hoạt động 
trung bình của nút 
Hình 2-26 thể hiện tỷ lệ trễ dãn cách trung bình khi thời gian hoạt động trung 
bình của nút thay đổi. Tapestry duy trì khá tốt, Chord cải thiện khi mạng có độ ổn 
định cao. 
Hình 2-26. Tỷ lệ trễ dãn cách trung bình Tstretch và thời gian 
hoạt động trung bình của nút 
0
1
2
3
4
5
1800 2400 3000 3600 4200
T
s
tr
e
tc
h
Thời gian hoạt đo ̣ng trung bình của nút(s)
Chord
 Taspestry
 Kademlia
53 
 Dựa trên kết quả mô phỏng, có thể thấy Tapestry hoạt động tốt khi số nút 
tăng, băng thông tiêu tốn tăng không đáng kể, tỷ lệ thành công được duy trì trên 
99%, Tstretch hầu như không thay đổi. Đối với Kademlia, khi số nút tăng, tỷ lệ tìm 
kiếm thành công giảm xuống dưới 96%, Tstretch tăng, băng thông tiêu tốn giảm. Điều 
đó chỉ ra rằng, Kademlia hoạt động tốt với số nút ít hơn nhưng tiêu tốn băng thông 
nhiều hơn. Đối với Chord, khi số nút tăng, băng thông tiêu tốn tăng không đáng kể, 
tỷ lệ thành công được duy trì trên 96%. Tuy nhiên khi mạng có độ ổn định thấp có 
nghĩa là khi thời gian hoạt động trung bình của nút nhỏ thì tỷ lệ tìm kiếm thành 
công giảm đáng kể. Hơn nữa tỷ lệ trễ dãn cách trung bình giữa đường định tuyến 
lớp chồng phủ và đường định tuyến của lớp nền tảng quá lớn khoảng gấp ba lần. 
Điều này dẫn tới trễ tìm kiếm tăng và dẫn tới giảm chất lượng dịch vụ khi triển khai 
qua mạng P2P. 
Qua kết quả phân tích và mô phỏng để phù hợp với mục tiêu của luận án, thuật 
toán Chord sử dụng kỹ thuật tìm kiếm đệ quy đã được chọn vì các tham số hiệu 
năng của Chord khá ổn định khi triển khai trên mạng diện rộng, đặc biệt chi phí cho 
việc duy trì ổn định của mạng nhỏ hơn so với các thuật toán khác. Chord tìm kiếm 
đệ quy còn cải thiện 50% thời gian trễ trung bình so với Chord tìm kiếm lặp. Tuy 
nhiên Chord cũng còn một số vấn đề cần giải quyết như: đường định tuyến lớp 
chồng phủ quá xa so với đường định tuyến lớp nền tảng, hiệu năng thấp khi mạng 
không ổn định. 
2.5 Kết luận chương 2 
Chương hai phân tích hoạt động của ba thuật toán DHTs, qua kết quả phân 
tích lý thuyết và mô phỏng Chord phù hợp với các ứng dụng quy mô lớn triển khai 
trên mạng ngang hàng, với rất nhiều các đặc tính hấp dẫn như: Đơn giản, phân tán, 
tự tổ chức, khả dụng, mở rộng, cân bằng tải, 
Bên cạnh đó việc đánh giá hiệu năng của các thuật toán định tuyến DHTs cũng 
được thực hiện qua phần mềm mô phỏng OverSim, qua kết quả mô phỏng cho thấy 
các tham số hiệu năng của thuật toán Chord duy trì ổn định khi mạng có kích thước 
54 
lớn và cấu trúc mạng có “Churn rate” cao. Nội dung của chương là kết quả nghiên 
cứu được công bố tại [V2]. 
55 
3. CHƯƠNG 3. CẢI THIỆN HIỆU NĂNG THUẬT TOÁN ĐỊNH 
TUYẾN CHORD 
 Chord là một thuật toán định tuyến DHT được đánh giá đơn giản, dễ triển 
khai, hiệu quả tìm kiếm phù hợp với mạng có kích thước lớn. Chương ba phân tích 
hoạt động của thuật toán định tuyến Chord, qua đó thấy được ưu nhược điểm của 
thuật toán; đồng thời phân tích các hướng nghiên cứu cải thiện Chord của các tác 
giả trước để đưa ra hướng nghiên cứu cải thiện. Chord đại diện tiêu biểu cho thuật 
toán định tuyến DHT, được phát triển từ lâu và rất thích hợp để triển khai các dịch 
vụ trên diện rộng. Nội dung chương phân tích lý do chọn thuật toán Chord trong 
nghiên cứu; Các hướng cải thiện thuật toán Chord; Cải thiện thuật toán định tuyến 
Chord và phân tích đánh giá mô phỏng so sánh với các nghiên cứu cải thiện trước 
đây. 
3.1 Giới thiệu chung 
Với sự gia tăng mạnh mẽ của băng thông Internet và ứng dụng của P2P trên 
mạng Internet như VoIP (Voice over IP), dịch vụ này nhanh chóng trở thành một 
phương tiện truyền thông rất phổ biến do chi phí thấp và tiện lợi cho người sử dụng 
Internet. Không giống như các hệ thống chia sẻ file, dữ liệu được sao lưu tại nhiều 
người dùng. Trong khi đó người dùng thoại Internet là duy nhất trong hệ thống, do 
đó khó khăn hơn và tốn kém để xác định chính xác vị trí người sử dùng. Việc tìm 
kiếm nhanh để xác định người sử dụng là một trong những vấn đề then chốt để đảm 
bảo chất lượng lượng dịch vụ [77], [83]. 
Ngoài ra, cơ sở hạ tầng P2P VoIP dự báo sẽ là ứng dụng phổ biến trên mạng 
Internet [42]. Thuật toán Chord đã được IETF P2PSIP nhóm 79 lựa chọn như một 
tiêu chuẩn của bộ giao thức P2PSIP [76], [77]. Như vậy, tất cả các ứng dụng thoại 
VoIP qua mạng P2P chọn Chord như một giao thức nền tảng [2], [25], [54], [77], 
[75],Do đó, việc cải thiện hiệu năng thuật toán định tuyến Chord góp phần cải 
thiện chất lượng dịch vụ thoại qua mạng ngang hàng (P2P VoIP). 
56 
3.2 Thuật toán định tuyến Chord 
 Trong Chord cả nút và dữ liệu đều được khai báo định danh có độ dài M bít 
bởi hàm băm bảo mật SHA-1. Hàm băm SHA-1 được chứng minh có phân bố khá 
tốt và xác suất để hai khóa hoặc hai nút có cùng định danh băm là rất nhỏ [60]. 
3.2.1 Hàm băm bảo mật SHA1 
Không gian định danh của Chord bao gồm các chuỗi hữu hạn các bít nhị phân. 
Chiều dài của định danh có thể là M = 160 bits hoặc M = 128 bits và nó được sắp 
xếp trên một vòng tròn định danh modulo 2𝑀, định danh được gán từ 0 đến 2𝑀−1. 
Chord dùng địa chỉ IP và địa chỉ cổng TCP/IP như định danh ngoài eID. Định danh 
của một nút là giá trị băm địa chỉ IP và địa chỉ cổng TCP/IP của nút đó, ví dụ: 𝑛 =
ℎ𝑐ℎ𝑜𝑟𝑑(𝐼𝑃 − 𝑎𝑑𝑑𝑟𝑒𝑠𝑠). Định danh của một khóa là giá trị băm của khóa đó 𝑘 =
ℎ𝑐ℎ𝑜𝑟𝑑(𝑘𝑒𝑦). Trong đó M được gọi là độ dài của định danh, M phải đủ lớn để xác 
suất hai nút hoặc khóa có cùng định danh là rất nhỏ (hàm băm ℎ𝑐ℎ𝑜𝑟𝑑() như SHA-1 
thì M = 160 bits). 
Hàm băm gán khóa vào các nút trong mạng Chord được thực hiện như sau: 
Sắp xếp các định danh theo thứ tự trên vòng định danh gồm 2𝑀 vị trí sắp xếp. Vòng 
tròn định danh là vòng tròn gồm các số từ 0 đến 2𝑀−1, chiều thuận là chiều kim 
đồng hồ. Vòng định danh còn được gọi là vòng Chord. Khóa k sẽ được gán cho nút 
đầu tiên có định danh bằng hoặc đứng sau định danh của k trong không gian định 
danh. Nút này được gọi là nút hàng xóm kề sau (successor) của k, được viết là 
succ(k). 
Để tăng tốc độ tìm kiếm, mỗi nút n duy trì một bảng định tuyến gồm tối đa M 
dòng (trong Chord số thực thể trong bảng định tuyến O(log2N), gọi là bảng finger 
(finger table). Hình 3.1 biểu diễn vòng Chord và bảng finger của nút 8, 42, 51 với 
độ dài M = 6 bits. Vòng Chord này có 10 nút. 
57 
Hình 3-1. Biểu diễn vòng Chord (M= 6) gồm 10 nút 
Biểu diễn hàm băm SHA1 của Chord như sau: Ánh xạ 𝑓𝑛𝑜𝑑𝑒−𝑚𝑎𝑝𝑝𝑖𝑛𝑔: (𝑒𝐼𝐷) →
𝑛 ∈ 𝐼 gán mỗi nút tương ứng với một định danh được thực hiện bằng cách sử dụng 
hàm băm SHA-1. Ánh xạ 𝑓𝑘𝑒𝑦−𝑚𝑎𝑝𝑝𝑖𝑛𝑔: Ҟ → I gán một giá trị thuộc Ҟ vào một 
định danh ID-Key trong I, cũng được thực hiện thông qua SHA-1. Ưu điểm của việc 
này là các đối tượng được phân bố đều trong không gian định danh. 
3.2.2 Định tuyến Chord 
Hai thành phần cơ bản của định tuyến DHT quyết định tới hiệu năng của thuật 
toán, đó là cấu trúc bảng định tuyến và kỹ thuật định tuyến. Trong phần này nghiên 
cứu phân tích kỹ hoạt động của hai thành phần trên của thuật toán Chord . 
Cấu trúc bảng định tuyến: Bảng định tuyến 𝑇𝑟 tại mỗi nút có định danh n 
gồm tối đa M= log2N dòng, gọi là bảng finger. Dòng thứ j trong 𝑇𝑟 bao gồm địa chỉ 
IP của nút đầu tiên theo sau n bởi ít nhất 2j-1 vị trí trên vòng tròn định danh. 
𝑓𝑟𝑜𝑢𝑡𝑖𝑛𝑔−𝑡𝑎𝑏𝑙𝑒=[𝑠𝑢𝑐𝑐((𝑛 + 2
0)𝑚𝑜𝑑2𝑀 , 𝑠𝑢𝑐𝑐((𝑛
+ 21)𝑚𝑜𝑑2𝑀 ,  , 𝑠𝑢𝑐𝑐((𝑛 + 2𝑀−1)𝑚𝑜𝑑2𝑀] 
 (3.1) 
Dòng đầu tiên trong 𝑇𝑟 liên kết trực tiếp tới nút tiếp theo. Dòng cuối cùng 
trong 𝑇𝑟 bao gồm liên kết đến nút theo sau n là 2
𝑀−1 vị trí trong vòng tròn Chord. 
Ngoài ra bảng định tuyến trong Chord còn chứa con trỏ chỉ tới nút có khoảng cách 
định danh nhỏ nhất với nó theo chiều ngược kim đồng hồ pred(n). Để phục vụ cho 
việc cải thiện Chord luận án đưa ra một số các định nghĩa sau: 
58 
Định nghĩa 3.1. Khoảng cách định danh trong không gian I là khoảng cách theo 
chiều kim đồng hồ. Cụ thể hơn, với 2 nút có định danh u và v, khoảng cách theo 
chiều kim đồng hồ 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒(𝑢, 𝑣), giữa chúng là: 
dclockwise(u,v) = {
𝑣 − 𝑢 𝑛ế𝑢 𝑣 ≥ 𝑢
2𝑚 + 𝑣 − 𝑢 𝑛ế𝑢 𝑣 ≺ 𝑢
 (3.2) 
Vì không gian định danh của Chord không đối xứng nên khi xét trên khía cạnh 
khoảng cách theo chiều kim đồng hồ, có nghĩa là 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒(𝑢, 𝑣) ≠ 
𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒(𝑣, 𝑢) (trừ trường hợp 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒(𝑢, 𝑣) = 2
𝑀−1. Chính xác hơn 
𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒(𝑢, 𝑣) = 2
𝑀 - 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒(v,u). 
Định nghĩa 3.2. Một nút p được cho là nút đứng gần n nhất theo chiều ngược kim 
đồng hồ (predecessor) trong vòng tròn Chord, ký hiệu là pred (n), nếu 
𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒(𝑓𝑛𝑜𝑑𝑒−𝑚𝑎𝑝𝑝𝑖𝑛𝑔(𝑝), 𝑛)= min 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒( 𝑓𝑛𝑜𝑑𝑒−𝑚𝑎𝑝𝑝𝑖𝑛𝑔(𝑞), 𝑛) (3.3) 
 Nút p gọi là predecessor một nút q khác nếu p = pred( 𝑓𝑛𝑜𝑑𝑒−𝑚𝑎𝑝𝑝𝑖𝑛𝑔(𝑞)). 
Định nghĩa 3.3. Một nút p gọi là successor của một định danh n trong vòng tròn 
Chord, ký hiệu là succ(n), nếu 
𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒((𝑛, 𝑓𝑛𝑜𝑑𝑒−𝑚𝑎𝑝𝑝𝑖𝑛𝑔(𝑝)) = min 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒( 𝑛, 𝑓𝑛𝑜𝑑𝑒−𝑚𝑎𝑝𝑝𝑖𝑛𝑔(𝑞)) (3.4) 
Một nút p được cho là successor của nút q khác nếu p =succ (𝑓𝑛𝑜𝑑𝑒−𝑚𝑎𝑝𝑝𝑖𝑛𝑔(𝑞)). 
Kỹ thuật định tuyến: Để duy trì cấu trúc bảng định tuyến, Chord sử dụng hai thuật 
toán: 
 Thuật toán ổn định: Mỗi nút chạy định kỳ các thuật toán ổn định để duy trì 
việc cập nhật thông tin về hàng xóm (successor) của nó. Mỗi lần một nút chạy 
thuật toán, nó hỏi successor về những nút predecessor của nó và nhận biết nếu 
có một nút mới có khả năng sẽ trở thành successor của nó. 
 Thuật toán sửa bảng finger (fix_fingers): Mỗi nút định kỳ chạy thuật toán 
này. Thuật toán fix_fingers làm mới lại chính xác một finger. Để sửa lại tất cả 
các fingers, thuật toán fix_fingers ghi nhớ chỉ số i của finger được cập nhật 
cuối cùng và trong chu kỳ fix_finger tiếp theo, nó làm mới finger thứ (i+1). 
Ngoài ra, mỗi nút mạng cũng thực hiện một thuật toán để kiểm tra định kỳ các 
predecessor của nó. 
59 
 Chiến lược định tuyến Greedy: Nút chuyển bản tin truy vấn đến nút có ID 
lớn nhất trong bảng định tuyến nhưng phải nhỏ hơn định danh khóa. Sau một 
số lần lặp hoặc đệ quy bản tin truy vấn sẽ được chuyển tới nút gần nhất với 
định danh khóa, nút kế tiếp này có trách nhiệm với định danh khóa đó là nút 
gốc 𝑟𝑜𝑜𝑡𝑘. Trong Chord độ dài đường định tuyến trung bình là O(𝑙𝑜𝑔 𝑁). 
Định nghĩa 3.4 (Clockwise GREEDY Routing): Trong một mạng Chord ánh xạ 
khoảng cách 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒 , định tuyến GREEDY đòi hỏi các quyết định sau đây: Đối 
với một khóa k cho trước, một nút p với tập các hàng xóm 𝐹𝑁(𝑝) sẽ chuyển tiếp bản 
tin truy vấn tới một nút mạng hàng xóm q∈ 𝐹𝑁(𝑝) sao cho 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒 (q,k) = min (x 
∈ 𝐹𝑁(𝑝) ) 𝑑𝑐𝑙𝑜𝑐𝑘𝑤𝑖𝑠𝑒 (x,k). 
Chord chuyển truy vấn tìm kiếm theo kiểu lặp, đệ quy hoặc bán đệ quy. Với truy 
vấn lặp nút được liên hệ 𝑛𝑖 sẽ trả nút 𝑛𝑗 gần nhất với khóa k từ bảng định tuyến của 
nó đến nút truy vấn. Với truy vấn đệ quy truy vấn chuyển trực tiếp 𝑛𝑖 đến nút 𝑛𝑗 . 𝑛𝑗 
tiếp tục định tuyến truy vấn đệ quy cho đến khi đạt được nút gốc 𝑟𝑜𝑜𝑡𝑘. Kết quả 
được trả về theo đường ngược lại. Trong truy vấn bán đệ quy việc tìm kiếm thực 
hiện giống đệ quy, nhưng kết quả của khóa tìm kiếm được gửi trực tiếp từ nút 𝑟𝑜𝑜𝑡𝑘 
đến nút đến 𝑛𝑖 
Hình 3-2. (a) Định tuyến lặp (b) Định tuyến đệ quy (c) Định tuyến bán đệ quy 
3.2.3 Tìm kiếm khóa mở rộng Chord 
Để tăng tốc tìm kiếm, Chord duy trì thêm thông tin định tuyến phụ. Mỗi nút n 
duy trì một bảng định tuyến gồm tối đa M dòng gọi là bảng finger. 
60 
Khi nút n muốn tham gia vào mạng, nó phải tìm định danh của mình thông 
qua một số liên hệ trong mạng và chèn chính nó vào giữa succ(s) và pred(s) nhờ sử 
dụng một thuật toán ổn định (stabilization) chạy định kỳ. Bảng định tuyến của n 
được khởi tạo bằng cách sao chép bảng định tuyến của s hoặc yêu cầu s tìm các 
finger của n. Tập các nút cần điều chỉnh bảng định tuyến sau khi n ra nhậpvào mạng 
nhờ các nút này đều chạy thuật toán stabilization định kỳ. Nhiệm vụ cuối cùng là 
chuyển một phần các dữ liệu đang lưu trên nút s có định danh nhỏ hơn hoặc bằng n 
sang nút n. Việc di chuyển dữ liệu này được thực hiện bởi tầng ứng dụng của n và s. 
Thuật toán stabilization gồm 6 chức năng : 
 create() 
 join() 
 stabilize() 
 notify() 
 fix_fingers() 
 check_predecessor() 
Mỗi nút sẽ chạy thủ tục stabilize() định kì để biết về các nút mới ra nhập. Mỗi 
lần nút n chạy stabilize(), nó hỏi successor của nó về predecessor của nút này, nút 
p, và quyết định liệu p có phải là successor của nút này hay không. Nếu đúng, thì 
nút p chính là nút mới gia nhập mạng. Thêm vào đó, stabilize() thông báo successor 
của n về sự hiện diện của n để successor này thay đổi predecessor của nó về n. 
Successor chỉ thực hiện điều này nếu nó biết không có predecessor nào gần hơn n. 
Quá trình một nút n ra nhập mạng và chạy ổn định mạng Chord gồm các bước : 
Giả sử nút n gia nhập hệ thống, và định danh của nó nằm giữa nút np và ns. Trong 
hàm gọi join(), thì n sẽ xác nhận ns là successor của nó. Nút ns khi nhận được thông 
báo từ n, sẽ nhận n là predecessor của mình. Sau đó, trong lần chạy thủ tục 
stabilize() tiếp theo, np sẽ hỏi ns về predecessor của ns (bây giờ là n), sau đó np nhận 
n là successor của nó. Cuối cùng, np thông báo cho n và n sẽ nhận np làm 
predecessor của nó. Đến đây, tất cả các predecessor và successor đều đã đúng. Tại 
61 
mỗi bước trong quá trình này, ns vẫn là successor của np, nghĩa là việc tìm kiếm có 
thể xảy ra đồng thời với việc nút mới gia nhập mà mạng vẫn không bị sập. Ngay sau 
khi các con trỏ successor đã chính xác, việc gọi hàm find_successor() sẽ phản ánh 
có nút mới trong mạng. Các nút mới gia nhập mạng chưa được phản ánh trong bảng 
finger của các nút khác có thể khiến cho find_successor() ban đầu không tới được 
các nút cần tìm, nhưng vòng lặp trong thuật toán tìm kiếm sẽ theo