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

i 
LỜI CAM ĐOAN 
Tôi cam đoan rằng nội dung của luận án này là kết quả nghiên cứu của bản 
thân. Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu rõ nguồn 
gốc một cách rõ ràng trong danh mục tài liệu tham khảo. Những đóng góp trong 
luận án là kết quả nghiên cứu đã được công bố trong các bài báo của tác giả và chưa 
được công bố trong bất kỳ công trình khoa học nào khác. 
 Tác giả luận án 
 Vũ Thị Thúy Hà 
ii 
LỜI CẢM ƠN 
Luận án Tiến sĩ này được thực hiện tại Học viện Công nghệ Bưu chính Viễn 
thông dưới sự hướng dẫn của PGS.TS Lê Hữu Lập và PGS.TS Lê Nhật Thăng. 
Trong suốt quá trình nghiên cứu hoàn thành luận án này, tác giả đã được tập thể các 
Thầy hướng dẫn định hướng khoa học và tận tình chỉ bảo. Nhân dịp này, tác giả xin 
kính gửi lòng biết ơn sâu sắc nhất đến các Thầy: PGS.TS Lê Hữu Lập và PGS.TS 
Lê Nhật Thăng. Các Thầy đã liên tục quan tâm, hướng dẫn và định hướng cho tôi từ 
cách đặt vấn đề, phương pháp nghiên cứu khoa học, cho đến những công việc cụ thể 
nhất. 
Tác giả xin trân trọng cảm ơn Ban Giám đốc Học viện Công nghệ Bưu chính 
Viễn thông, Hội đồng Khoa học và Đào tạo, Hội đồng Tiến sĩ, Khoa Quốc tế và 
Đào tạo Sau Đại học của Học viện đã tạo điều kiện thuận lợi cho tác giả được thực 
hiện và hoàn thành chương trình nghiên cứu của mình. 
Xin cảm ơn các Thầy, Cô giáo Khoa Viễn thông 1 và các Thầy, Cô giáo thuộc 
Học viện Công nghệ Bưu chính Viễn thông về những ý kiến quí báu giúp tác giả 
hoàn thiện luận án. 
Chân thành cảm ơn gia đình và bạn bè đã luôn bên cạnh động viên, khích lệ và 
củng cố tinh thần cho tác giả. 
 Tác giả luận án 
 Vũ Thị Thúy Hà 
iii 
MỤC LỤC 
Cont 
Lời cam đoan.......i 
Lời cảm ơn..................................................................................................................ii 
Mục lục......................................................................................................................iii 
Danh mục các ký hiệu các chữ viết tắt......................................................................vi 
Danh mục các bảng..................................................................................................xv 
Danh mục các hình .................................................................................................xvi 
MỞ ĐẦU ...................................................................................................................1 
NỘI DUNG..............................................................................................................10 
Chương 1. Tổng quan về mạng P2P......................................................................10 
1.1. Tổng quan về mạng ngang hàng .................................................................. 10 
1.1.1. Kiến trúc mạng ngang hàng P2P .......................................................... 11 
1.1.2. Một số các ứng dụng điển hình của mạng ngang hàng......................... 14 
1.1.3. Thách thức khi nghiên cứu mạng ngang hàng P2P .............................. 16 
1.2. Tham số hiệu năng mạng ngang hàng ......................................................... 19 
1.3. Các hướng tiếp cận nghiên cứu cải thiện hiệu năng mạng ngang hàng ...... 20 
1.4. Kết luận chương 1 ....................................................................................... 22 
Chương 2. Phân tích đánh giá hiệu năng thuật toán định tuyến DHTs.............23 
2.1. Giới thiệu chung .......................................................................................... 23 
2.2. Bảng băm phân tán - DHT ........................................................................... 24 
2.3. Một số thuật toán định tuyến DHTs ............................................................ 27 
2.3.1 Thuật toán định tuyến Chord ................................................................ 29 
2.3.2 Thuật toán định tuyến Tapestry ............................................................ 33 
2.3.3 Thuật toán định tuyến Kademlia ........................................................... 37 
iv 
2.4. Phân tích, đánh giá hiệu năng một số thuật toán định tuyến DHTs ............ 39 
2.4.1 Các phương pháp phân tích hiệu năng .................................................. 39 
2.4.2 Lựa chọn công cụ mô phỏng mạng chồng phủ ngang hàng ................. 40 
2.4.3 Mô phỏng đánh giá hiệu năng các thuật toán định tuyến DHTs .......... 44 
2.5 Kết luận chương 2 ....................................................................................... 53 
Chương 3. Cải thiện hiệu năng thuật toán định tuyến Chord............................55 
3.1 Giới thiệu chung .......................................................................................... 55 
3.2 Thuật toán định tuyến Chord ....................................................................... 56 
3.2.1 Hàm băm nhất quán (Consistent Hasing) ............................................. 56 
3.2.2 Định tuyến Chord .................................................................................. 57 
3.2.3 Tìm kiếm khóa mở rộng Chord ............................................................ 59 
3.3 Cải thiện hiệu năng thuật toán Chord .......................................................... 61 
3.3.1 Phân tích các điểm yếu của thuật toán Chord ....................................... 61 
3.3.2 Phân tích các nghiên cứu cải thiện hiệu năng giải thuật Chord ............ 63 
3.3.3 Cải thiện hiệu năng thuật toán Chord ................................................... 64 
3.3.4 Thuật toán Chord cải thiện .................................................................. 65 
3.3.5 Mô phỏng đánh giá hiệu năng thuật toán Chord cải thiện .................... 72 
3.4 Kết luận chương 3 ........................................................................................ 74 
 Chương IV. Xây dựng mạng Chord_SL phân cấp cải thiện hiệu năng ...........76 
4.1 Giới thiệu chung .......................................................................................... 76 
4.2 Mô hình mạng Chord_SL phân cấp ............................................................. 77 
4.2.1 Định nghĩa cấu trúc mạng Chord_SL phân cấp .................................... 77 
v 
4.2.2 Gán định danh SN và ON ..................................................................... 80 
4.2.3 Lựa chọn SN (supernode) trong mạng Chord_SL ................................ 82 
4.2.4 Chiến lược tìm kiếm trong mạng Chord_SL ........................................ 86 
4.3 Phân tích, đánh giá hiệu năng mạng Chord_SL .......................................... 88 
4.3.1 Độ dài đường tìm kiếm ......................................................................... 88 
4.3.2 Phân tích dựa trên chi phí ..................................................................... 94 
 4.3.3 Chi phí lựa chọn siêu nút SN ................................................................ 98 
4.4 Kết luận chương 4 ....................................................................................... 99 
KẾT LUẬN VÀ KIẾN NGHỊ ..................................................................................99 
DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN ÁN ..............103 
TÀI LIỆU THAM KHẢO.......................................................................................106 
PHỤ LỤC ...............................................................................................................116 
vi 
DANH MỤC CÁC CHỮ VIẾT TẮT 
Từ viết tắt Tiếng Anh Nghĩa Tiếng Việt 
A 
ALM Apllication Layer Multicast Đa hướng lớp ứng dụng 
AS Autonomous System Hệ thống tự trị 
API Application Programming Interface Giao diện lập trình ứng dụng 
AVC Advanced Video Coding Mã hóa video tiên tiến 
C 
CAN Content Addressable Networks Mạng địa chỉ nội dung 
CDF Cumulative Distribution Function Hàm phân bố tích lũy 
CS 
Csy 
Client – Server 
Centralized Systems 
Mô hình Khách – chủ 
Hệ thống tập trung 
CTMC Continuous Time Markov Chain Chuỗi Markov liên tục theo thời gian 
Chord_SL An improved chord protocol with 
double-layer design and optimal 
supernode selection algorithm 
Mạng Chord phân cấp hai lớp cải 
thiện và giải thuật lựa chọn siêu nút 
tối ưu 
D 
DHT Distributed Hash Table Bảng băm phân tán 
DKS Distributed K-ary System Hệ thống phân tán nhiều chiều 
DNS 
DUSy 
DSSy 
Domain Name System 
Decentralized Unstructured Systems 
Decentralized structured Systems 
Hệ thống tên miền 
Hệ thống phân tán không cấu trúc 
Hệ thống phân tán có cấu trúc 
DoS Denial of Service Từ chối dịch vụ 
DTLS Distributed Storage and Replication 
Layer Security 
Lớp bảo mật sao lưu và lưu trữ phân 
tán 
DTMC Discrete Time Markov Chain Chuỗi Markov thời gian rời rạc 
F 
vii 
FTP File Transfer Protocol Giao thức truyền file 
G 
GUI Graphical User Interface Giao diện đồ họa 
H 
HTML 
HSy 
HyperText Markup Language 
Hybrid Systems 
Ngôn ngữ đánh dấu siêu văn bản 
Hệ thống lai ghép 
HTTP Hyper-Text Transfer Protocol Giao thức truyền siêu văn bản 
I 
ID 
ICMP 
Identifier 
Internet Control Message Protocol 
Định danh 
Giao thức điều khiển Internet 
IETF Internet Engineering Task Force Nhóm chuyên trách kỹ thuật Internet 
IM Instant Messaging Tin nhắn tức thời 
IP Internet Protocol Giao thức Internet 
J 
JXTA Juxtapose Mạng ngang hàng mã nguồn mở của 
Sun Microsystems 
K 
KBR Key Based Routing Định tuyến dựa trên khóa 
M 
MD5 Message-Digest algorithm 5 Thuật toán mã hóa MD5 
MDC Multi Description Code Mã hóa đa mô tả 
N 
NAT Network Address Translation Chuyển đổi địa chỉ mạng 
O 
ONs Ordinary nodes Các nút thông thường 
OSPF Open Shortest Path First Đường đi ngắn nhất 
P 
P2P Peer-to-Peer Ngang hàng 
PDA Personal Digital Assistant Thiết bị số hỗ trợ cá nhân 
viii 
PPP Point-to-Point Protocol Giao thức điểm điểm 
PRR Prefix routing Định tuyến dựa trên tiền tố 
Q 
QoS Quality of Service Chất lượng dịch vụ 
R 
RELOAD Resource Location And Discovery Khai phá và tìm kiếm tài nguyên 
RIP Routing Information Protocol Giao thức thông tin định tuyến 
RTT 
Round Trip Time 
Thời gian gói tin đi tới đích và quay 
trở về nguồn 
S 
SNs Supernodes Các siêu nút 
SHA1 Secure Hash Algorithm Thuật toán băm bảo mật SHA1 
SIP Session Initiation Protocol Giao thức khởi tạo phiên 
T 
TCP Transmission Control Protocol Giao thức điều khiển truyền tải 
TLS Transport Layer Security Bảo mật lớp truyền tải 
TTL Time To Live Thời gian sống của gói tin 
U 
UA User Agent Đại lý người dùng 
UDP User Datagram Protocol Giao thức lược đồ dữ liệu người dùng 
URI Uniform Resource Identifier Định danh tài nguyên 
V 
VOD Video-on-Demand Video theo yêu cầu 
VoIP Voice over Internet Protocol Truyền thoại qua giao thức Internet 
W 
WAN Wide Area Network Mạng diện rộng 
ix 
DANH SÁCH CÁC KÍ HIỆU 
Tstretch: Tỷ lệ trễ dãn cách trung bình 
𝑝(𝑛𝑞,𝑘): Độ dài đường tìm kiếm từ nút có định danh 𝑛𝑞 đến nút có chứa 
khóa k 
k: 
ҡ: 
Định danh của khóa tìm kiếm 
Số nút được lưu trữ trong ҡ-buckets của Kademlia 
𝑟𝑜𝑜𝑡𝑘: Nút gốc chứa khóa k 
K: Số nhóm nội miền trong mô hình phân cấp 
𝛾: Xác xuất cả nút nguồn và nút đích đều trong cùng một lớp nội miền 
trong mô hình phân cấp 
Ҟ: Không gian định danh khóa 
𝜌: Tỷ lệ tìm kiếm thành công 
c(i): Số bước nhảy của mỗi lần tìm kiếm riêng rẽ i 
𝑡ℎ: Giới hạn tổng số bước nhảy của mỗi lần tìm kiếm 
𝑒𝐼𝐷: Định danh ngoài 
E: Không gian định danh ngoài 
I: Không gian định danh nút 
Ɲ: Số nút trong nhóm nội miền 
 𝑛𝑞: 
n: 
Định danh của nút q 
Định danh của nút 
M: Độ dài bít của định danh nút 
𝑇𝑟: Bảng định tuyến 𝑇𝑟 tại mỗi nút n bao gồm t liên kết đến nút tại một 
số khoảng cách trong không gian định danh 
𝑇𝑠: Bảng định tuyến 𝑇𝑠 tại mỗi nút bao gồm liên kết tới s hàng xóm trực 
tiếp trong cấu trúc DHT 
Succ(n): Con trỏ tới nút đầu tiên đứng kề sau nút có định danh n trong không 
gian định danh theo chiều kim đồng hồ 
x 
Pred(n): Con trỏ tới nút đầu tiên đứng kề trước nút có định danh n trong 
không gian định danh theo chiều kim đồng hồ. 
N: Kích thước của mạng chồng phủ 
𝐹𝑁(𝑝): Tập các nút hàng xóm của p 
sn: Định danh của nút nguồn 
Delay[i]: Trễ giữa nút có định danh n và n.finger[i] nhận được bởi lệnh ping 
U: Số siêu – siêu nút (Ultra Super-peer) 
:)(SF Tập hợp các liên kết của một nút S khi ra nhập vòng Chord của lớp 
liên miền trong mô hình phân cấp. 
:)( pF 
Tập hợp các liên kết của nút p khi ra nhập vòng Chord của lớp nội 
miền trong mô hình phân cấp. 
D: Độ dài định danh của nút trong mô hình Chord_SL phân cấp 
D:
Thiết kế phân cấp 
D-d:
Độ dài bít định danh tiền tố 
d: Độ dài bít định danh hậu tố 
if (xi): Hàm chi phí tương ứng với các biến nxxx ,....,, 21 . 
𝑡𝑜𝑛(𝑝): Thời gian hoạt động trung bình của nút 
𝑃(𝑝): Khả năng xử lý CPU (MIPS Million Instruction Per Second) 
𝐵(𝑝): Băng thông của nút 
:flath Độ dài đường tìm kiếm qua mô hình Chord_flat 
h: Độ dài đường tìm kiếm trung bình 
:nsh Độ dài đường tìm kiếm từ nút nội miền đến siêu nút 
:ssh Độ dài đường tìm kiếm siêu nút (SN) trong lớp liên miền 
:nsT Trễ mạng trung bình giữa một nút trong lớp nội miền và một nút 
trong lớp liên miền 
:ssT 
Trễ mạng trung bình giữa hai nút lớp liên miền 
Tbeat: 
Chu kỳ gửi bản tin heartbeat 
xi 
:beatC Chi phí để gửi bản tin heartbeat 
Tstab Chu kỳ chạy thuật toán ổn định stabilization 
Cstab: Chi phí chạy thuật toán ổn định (stabilization) 
l: Thời gian sống của nút 
xii 
DANH MỤC CÁC BẢNG 
Bảng 2-1. Các tham số dùng cho mô phỏng Kademlia ........................................... 47 
Bảng 2-2. Các tham số dùng cho mô phỏng Tapestry ............................................ 47 
Bảng 2-3. Các tham số dùng cho mô phỏng Chord ................................................ 47 
Bảng 3-1. Định nghĩa trường trễ Delay[i] ................................................................ 69 
Bảng 3-2. Cấu trúc bảng định tuyến của nút 8 ........................................................ 69 
Bảng 3-3. Bảng Finger nghiên cứu [86], [11] ........................................................... 70 
Bảng 3-4. So sánh hiệu năng Chord cải thiện .......................................................... 71 
Bảng 4-1. Bảng finger Chord_SL ............................................................................. 80 
xiii 
DANH MỤC CÁC HÌNH 
Hình 1-1. Mô hình mạng chồng phủ ngang hàng P2P ............................................ 11 
Hình 1-2. Kiến trúc phân lớp điển hình mạng ngang hàng P2P ............................ 12 
Hình 1-3. Phân loại kiến trúc mạng chồng phủ P2P .............................................. 12 
Hình 2-1. Tìm kiếm và lưu trữ dữ liệu trong DHT ................................................. 24 
Hình 2-2. Cấu trúc mạng chồng phủ Chord ........................ ...  IEEE. 
87. Jelasity, Márk, et al. "PeerSim P2P simulator." 2011-05-08].  
sourceforge. net (2009). 
88. Liu, M., Harjula, E., Ylianttila, M.: An Efficient Selection Algorithm for 
Building a SuperPeer Overlay, Journal of Internet Services and Applications, 
4(4), (2013) 
89. Montresor, Alberto. "A robust protocol for building superpeer overlay 
topologies." Peer-to-Peer Computing, 2004. Proceedings. Proceedings. Fourth 
International Conference on. IEEE, 2004. 
116 
PHỤ LỤC 1 
1. Đề xuất hàm giá liên kết đa biến 
Các tham số đánh giá năng lực của nút có thể là băng thông, độ trễ, thời gian 
sống của nút, khả năng xử lý của nút, Mục đích của việc xây dựng hàm giá đa 
biến là tìm ra hàm giá cân bằng các yếu tố cần thiết để lựa chọn một nút có năng lực 
làm siêu nút SN. 
a. Xây dựng hàm giá dựa trên băng thông 
Giả sử liên kết của nút i: Tổng băng thông sẵn sàng của liên kết là kw, băng 
thông tối thiểu yêu cầu của siêu nút là xw , hàm giá dựa trên băng thông: f (xw). 
Do kw là băng thông tối đa có sẵn trên liên kết i, vì vậy 0 < xw<kw. Theo thời 
gian với các yêu cầu của ứng dụng xw có thể thay đổi bởi một số gia wx . Điều này 
dẫn tới hàm giá hiện tại cũng thay đổi f (xw + ∆xw ), do đó giá trị hàm giá hiện tại 
phụ thuộc vào: 
- Hàm giá trước: f (xw ), 
- Tỷ lệ khi tăng băng thông yêu cầu một số gia wx : 
ww
w
xx
x
- Tỷ lệ khi băng thông còn lại bị giảm đi một số gia wx : 
w
www
k
xxk 
Cuối cùng, ta có: 
w
www
ww
w
www
k
xxk
xx
x
xfxxf
)(
1)()( 
(5.1) 
Từ (5.1) ta có: 
)(
1
)(
)(lim
)()(
lim
00
wwwww
w
w
x
w
www
x xxkxx
k
xf
x
xfxxf
ww 
)(
)()(
www
w
ww
xkx
k
xfxf
(5.2) 
117 
Thay thế f (xw) bởi y và f’(xw) bởi 
wdx
dy
; từ (5.2) chúng ta có một phương trình vi 
phân bậc 1 theo biến băng thông : 
)( www
w
w xkx
k
y
dx
dy
(5.3) 
Giải phương trình vi phân bậc 1 chúng ta có được hàm giá dựa trên băng thông: 
w
www
w dx
xkx
k
y
dy
)( 
 w
www
w dx
xkx
k
y
dy
)(
cxkxy www )ln()ln()ln( 
Từ đó suy ra hàm giá dựa vào băng thông, trong đó  là hằng số tích phân : 
ww
w
xk
x
y

.
(5.4) 
b. Xây dựng hàm giá liên kết dựa trên trễ 
Ký hiệu biến (xd) trễ yêu cầu của một nút SN đối với dịch vụ, kd trễ tối thiểu 
mà nút có thể đáp ứng khi sử dụng toàn bộ nguồn tài nguyên sẵn có của mạng. Trên 
thực tế trễ yêu cầu (xd) có đặc tính đảo ngược với băng thông yêu cầu (xw). Vì vậy 
bằng cách thay thế : 
ẋd =
1
xd
 , K̇d =
1
Kd
 Và 
dẋd = d (
1
xd
) = −
dxd
x
d2
Thay vào 5.3 ta có: 
dy
dẋd
= y
K̇d
ẋd(K̇d−ẋd)
 −
dy
dxd
xd
2
= y
1
Kd
1
xd
(
1
Kd
−
1
xd
)
Từ đó suy ra vi phân theo biến trễ : 
w
w
ww
ww
w
www
www
x
dx
xk
xkd
dx
xkx
xkx )(
)(
)(
118 
)(
1
ddd xk
y
dx
dy
(5.5) 
Phương trình (5.5) là phương trình vi phân bậc 1 theo biến trễ . Từ đó , ta có: 
)ln()ln()ln( ckxy dd 
dd kx
c
y
Suy ra hàm giá liên kết dựa trên trễ với  là hằng số tích phân: 
dd
d
kx
k
y

.
(5.6) 
c. Xây dựng hàm giá đa biến 
Ký hiệu hàm giá theo cả trễ và băng thông u(xw, xd) xem xét hai tham số băng 
thông yêu cầu (xw) và trễ yêu cầu (xd) của dịch vụ cùng một lúc. Vì biến băng thông 
và trễ là biến độc lập tuyến tính. Từ phương trình vi phân (5.6) (5.3) ta có phương 
trình đạo hàm riêng giả tuyến tính bậc 1(quasi linear first order partial differential 
equation): 
uuxku
k
xkx
dw xddx
w
www 
)(
)(
(5.7) 
Trong đó vi phân riêng phần của hàm u theo xw : 
w
x
x
u
u
w 

Vi phân riêng phần của u hàm theo xd : 
d
x
x
u
u
d 

Để giải phương trình (5.7) đặt xw = xw (t) , xd = xd (t) , u = u(xw (t) , xd (t) ), ta có: 
t
u
u
t
x
u
t
x
dw x
d
x
w






(5.8) 
Từ 5.7 và 5.8 ta có hệ phương trình vi phân riêng phần: 
)(
)(
)( dd
dd
dd
d
xk
kxd
y
dy
xk
dx
y
dy
119 






u
t
u
xk
t
x
k
xkx
t
x
dd
d
w
wwww
)(
)(
(5.9) 
Để giải phương trình (5.7) tìm các hằng số tích phân bao gồm cả các biến dx , wx
và u .Các bước giải phương trình : 
Bước 1: Tìm hằng số tích phân đầu tiên: 
Từ (5.9) ta có: 
)(
)(
www
www
wwww
xkx
dxk
u
du
u
k
xkx
t
u
t
x




(5.10) 
(5.10) có dạng giống với vi phân của băng thông nên suy ra: 
)(
.
ww
w
xk
x
u

Từ đó hằng số : 
w
ww
x
uxk )( 
  
(5.11) 
Bước 2: Tìm hằng số tích phân thứ 2 
Từ (5.9) tương tự chúng ta có thể xác định được hằng số : 
d
dd
k
ukx )( 
  
(5.12) 
Bước 3: Tìm hằng số  tổng quát 
 = (xw; xd, u) = hằng số, mô tả mối quan hệ giữa 3 biến xw; xd, u 
Ta có thể thiết lập hai hằng số bằng nhau, do đó: 
)()(  
Và biểu diễn 
)(  f (5.13) 
Từ (5.11), (5.12), (5.13), ta có: 
120 
d
dd
w
ww
k
ukx
f
x
uxk )()(
(5.14) 
( u được biểu diễn như là hàm theo biến xw và xd còn xw và xd là các biến độc lập ) 
Lấy đạo hàm của (5.14) theo xw và giải tìm 
wx
u . Ký hiệu ),(
)(
uxf
k
ukx
f d
d
dd 
. Ta 
có: 
),(.
)()(
2
uxfu
k
kx
u
x
k
u
x
xk
dx
d
dd
w
w
x
w
ww
ww
 ),().()(
..
uxfkxxkxkx
ukk
u
dddwdwww
dw
xw 
(5.15) 
Tương tự như vậy, lấy đạo hàm (5.14) theo xd và giải tìm 
dx
u ta có: 
dd x
d
dd
dx
w
ww u
k
kxu
uxfu
x
xk )(
),(
)(
wddddww
wd
x
xkxuxfkxk
xuuxf
u
d ).).(,()(
.).,(
(5.16) 
Thay 
wx
u và 
dx
u vào phương trình (5.7) 
 
uu
uxfkxxkxk
xuxfkxkxk
xkxuxfkxk
xuuxf
xk
uxfkxxkxkx
ukk
k
xkx
dddwdww
wddddww
wddddww
wd
dd
dddwdwww
dw
w
www
),().().(
).,().().(
).).(,()(
.).,(
).(...
),().()(
..
.
)(
Bước 4: Thêm điều kiện biên để tìm f 
Từ những đặc điểm tự nhiên của hai tham số độc lập: băng thông yêu cầu (xw) 
và độ trễ yêu cầu (xd), và các hàm giá băng thông và trễ , chúng ta có những điều 
kiện biên: 
121 
2
3
tu
t
kx
k
t
k
xk
dd
d
w
ww
(5.17) 
Thay thế (5.17) vào (5.14) ta có: 
t
tf
t
t
t
t
f
1
)()(
3
22
(5.18) 
Từ (5.18) và (5.14) ta có : 
w
ww
dd
d
d
dd
x
uxk
ukx
k
k
ukx
f
)(
)(
)( 
(5.14) 
Từ đó suy ra hàm giá băng thông và trễ là: 
dd
d
ww
w
dw
kx
k
xk
x
xxu
 .),( 
(5.15) 
Một cách đệ quy, ta có thể chứng minh hàm giá đa biến với các giá chi phí riêng 
thành phần if (xi) 
n
i
n
i
in xfxxxu )(),....,,(
1
21 
(5.16) 
122 
Phụ lục 2: Kịch bản mô phỏng và kết quả 
mesurementTime = 3600s 
One-way Hop Count 
Number of Node 8 16 32 64 128 256 512 1024 2048 4096 
Simple Underlay 
Network 2,086 2,655 3,226 3,736 4,222 4,72 5,242 5,737 6,236 
Inet Underlay 
Network 2,303 2,56 3,047 3,578 4,044 4,526 5,042 5,547 6,021 
One-way Latency 
Number of Node 8 16 32 64 128 256 512 1024 2048 4096 
Simple Underlay 
Network 0,376 0,445 0,45 0,558 0,678 0,736 0,86 0,923 0,971 
Inet Underlay 
Network 0,209 0,248 0,208 0,246 0,289 0,34 0,385 0,632 0,467 
Sent Total Byte/s 
Number of Node 8 16 32 64 128 256 512 1024 2048 4096 
Simple Underlay 
Network 44,72 50,42 56,81 64,32 71,64 79,6 86,52 88,6 108,8 
Inet Underlay 
Network 48,87 62,16 69,23 72,93 79,24 85,85 94,52 103,6 112,6 
targetOverlayTerminalNum=500 
Hop Count 
Sec 1800 2400 3000 3600 4200 
Chord lap 4,977 4,984 4,971 4,949 4,984 
Chord de quy 3,953 3,97 3,966 3,955 3,97 
Kademlia 2,003 1,996 1,997 1,995 2,005 
123 
Pastry 2,348 2,358 2,346 2,339 2,346 
Bandwidth consumption (Bytes/s) 
Sec 1800 2400 3000 3600 4200 
Chord lap 254,2 253,9 252,7 253,8 253,3 
Chord de quy 205,3 207,9 208,2 206,6 209,6 
Kademlia 116 110,6 110,6 109,4 110,2 
Pastry 606,2 624,4 495 503,3 433,7 
Latency 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,761 0,772 0,765 0,738 0,81 
Chord de quy 0,336 0,349 0,347 0,338 0,345 
Kademlia 0,18 0,176 0,178 0,17 0,176 
Pastry 0,205 0,208 0,206 0,208 0,189 
Delivery ratio 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,918 0,916 0,897 0,909 0,911 
Chord de quy 0,918 0,911 0,916 0,9 0,922 
Kademlia 0,958 0,946 0,949 0,96 0,96 
Pastry 1 1 1 1 1 
targetOverlayTerminalNum=1000 
Hop Count 
Sec 1800 2400 3000 3600 4200 
Chord lap 5,476 5,499 5,479 5,475 5,468 
Chord de quy 4,48 4,495 4,48 4,482 4,479 
Kademlia 2,205 2,221 2,225 2,223 2,22 
Pastry 2,655 2,66 2,656 2,661 2,657 
Bandwidth consumption (Bytes/s) 
124 
Sec 1800 2400 3000 3600 4200 
Chord lap 286,6 289 282,4 286,7 282,6 
Chord de quy 230,7 234,2 234,5 231 232,4 
Kademlia 134,2 131 131,8 135,1 132,4 
Pastry 674,4 591,8 666,3 577,4 606,3 
Latency 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,863 0,836 0,888 0,874 0,829 
Chord de quy 0,375 0,37 0,384 0,385 0,387 
Kademlia 0,192 0,188 0,192 0,19 0,197 
Pastry 0,235 0,228 0,239 0,229 0,233 
Delivery ratio 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,899 0,91 0,886 0,904 0,888 
Chord de quy 0,898 0,909 0,881 0,904 0,902 
Kademlia 0,936 0,942 0,939 0,945 0,939 
Pastry 1 1 1 1 1 
targetOverlayTerminalNum=1500 
Hop Count 
Sec 1800 2400 3000 3600 4200 
Chord lap 5,77 5,795 5,781 5,783 5,772 
Chord de quy 4,78 4,791 4,788 4,784 4,794 
Kademlia 2,339 2,335 2,348 2,338 2,338 
Pastry 2,804 2,807 2,797 2,794 2,805 
Bandwidth consumption (Bytes/s) 
Sec 1800 2400 3000 3600 4200 
Chord lap 302,9 309,1 306,2 309 310,3 
125 
Chord de quy 250,3 250,8 251,5 249,6 248,9 
Kademlia 143,4 143,9 143,2 143 143,2 
Pastry 736,1 642,9 653,7 658,5 628,8 
Latency 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,893 0,899 0,895 0,899 0,918 
Chord de quy 0,395 0,402 0,415 0,39 0,408 
Kademlia 0,201 0,208 0,204 0,19 0,196 
Pastry 0,248 0,254 0,24 0,244 0,251 
Delivery ratio 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,887 0,903 0,896 0,898 0,889 
Chord de quy 0,891 0,907 0,904 0,9 0,897 
Kademlia 0,929 0,933 0,94 0,926 0,923 
Pastry 1 1 1 1 1 
targetOverlayTerminalNum=2000 
Hop Count 
Sec 1800 2400 3000 3600 4200 
Chord lap 5,991 5,995 5,994 5,993 5,991 
Chord de quy 4,978 5,001 5,005 4,994 4,995 
Kademlia 2,425 2,424 2,439 2,433 2,423 
Pastry 2,885 2,865 2,877 2,877 2,88 
Bandwidth consumption (Bytes/s) 
Sec 1800 2400 3000 3600 4200 
Chord lap 318,4 318,7 318,2 319,3 318,2 
Chord de quy 259,7 261,1 261,6 260,8 261 
Kademlia 153,4 151,7 154 150,6 151,2 
126 
Pastry 712,3 692,8 711,2 670,3 699,5 
Latency 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,954 0,937 0,957 0,945 0,937 
Chord de quy 0,43 0,447 0,432 0,413 0,415 
Kademlia 0,205 0,211 0,212 0,209 0,212 
Pastry 0,253 0,238 0,236 0,246 0,243 
Delivery ratio 
Sec 1800 2400 3000 3600 4200 
Chord lap 0,885 0,895 0,882 0,896 0,887 
Chord de quy 0,887 0,902 0,894 0,895 0,882 
Kademlia 0,924 0,93 0,937 0,925 0,933 
Pastry 1 1 1 1 1 
127 
128 
129 
[Config ChordInet] 
description = Chord (iterative, InetUnderlayNetwork) 
network = oversim.underlay.inetunderlay.InetUnderlayNetwork 
**.targetOverlayTerminalNum = ${8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096} 
**.measurementTime = 7200s 
**.transitionTime = 120s 
*.underlayConfigurator.churnGeneratorTypes = "oversim.common.LifetimeChurn" 
**.overlayType = "oversim.overlay.chord.ChordModules" 
**.tier1Type = "oversim.applications.kbrtestapp.KBRTestAppModules" 
InetUnderlayNetwork.backboneRouterNum = 1 
InetUnderlayNetwork.overlayAccessRouterNum = 1 
130 
InetUnderlayNetwork.accessRouterNum = 1 
[Config ChordSimple] 
description = Chord (semi-recursive, SimpleUnderlayNetwork, churn, large-scale 
test -> run without GUI) 
**.targetOverlayTerminalNum = ${8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096} 
**.measurementTime = 7200s 
**.transitionTime = 120s 
**.overlayType = "oversim.overlay.chord.ChordModules" 
**.tier1Type = "oversim.applications.kbrtestapp.KBRTestAppModules" 
**.churnGeneratorTypes = "oversim.common.LifetimeChurn" 
**.initPhaseCreationInterval = 0.1s 
**.debugOutput = false 
**.overlay.chord.stabilizeDelay = 20s 
**.overlay.chord.fixfingersDelay = 120s 
**.overlay.chord.checkPredecessorDelay = 5s 
**.overlay.chord.routingType = "iterative" 
[Config Chord-dequy] 
*.underlayConfigurator.churnGeneratorTypes = "oversim.common.LifetimeChurn" 
**.targetOverlayTerminalNum = ${1000, 1500} 
**.measurementTime = 3600s 
**.churnGenerator.lifetimeMean = ${1800, 2400, 3000, 3600,4200} 
**.overlayType = "oversim.overlay.chord.ChordModules" 
**.tier1Type = "oversim.applications.kbrtestapp.KBRTestAppModules" 
**.overlay.chord.fixfingersDelay = 144s 
**.overlay.chord.stabilizeDelay = 144s 
**.overlay.chord.successorListSize = 16 
**.overlay*.chord.numFingerCandidates = 4 
**.overlay*.chord.routingType = "semi-recursive" 
[Config Chord-lap] 
131 
description = Chord (semi-recursive, SimpleUnderlayNetwork, churn, large-scale 
test -> run without GUI) 
**.targetOverlayTerminalNum = ${500, 2000} 
**.measurementTime = 3600s 
**.transitionTime = 120s 
**.overlayType = "oversim.overlay.chord.ChordModules" 
**.tier1Type = "oversim.applications.kbrtestapp.KBRTestAppModules" 
**.churnGeneratorTypes = "oversim.common.LifetimeChurn" 
**.debugOutput = false 
**.overlay.chord.stabilizeDelay = 144s 
**.overlay.chord.fixfingersDelay = 144s 
**.overlay.chord.checkPredecessorDelay = 5s 
**.overlay*.chord.routingType = "iterative" 
**.overlay.chord.successorListSize = 16 
**.overlay.chord.numFingerCandidates = 4 
**.churnGenerator.lifetimeMean = ${1800, 2400, 3000, 3600,4200} 
**.overlay.chord.aggressiveJoinMode = true 
**.overlay.chord.extendedFingerTable = false 
**.overlay.chord.proximityRouting = false 
**.overlay.chord.memorizeFailedSuccessor = false 
**.overlay.chord.mergeOptimizationL1 = false 
**.overlay.chord.mergeOptimizationL2 = false 
**.overlay.chord.mergeOptimizationL3 = false 
**.overlay.chord.mergeOptimizationL4 = false 
[Config Kademlia-dequy] 
description = Kademlia (SimpleUnderlayNetwork) 
*.underlayConfigurator.churnGeneratorTypes = "oversim.common.LifetimeChurn" 
**.overlayType = "oversim.overlay.kademlia.KademliaModules" 
**.tier1Type = "oversim.applications.kbrtestapp.KBRTestAppModules" 
132 
**.targetOverlayTerminalNum = ${500, 1000, 1500, 2000} 
**.churnGenerator.lifetimeMean = ${1800, 2400, 3000, 3600,4200} 
**.overlay*.kademlia.k = 16 
**.overlay*.kademlia.lookupParallelRpcs = 16 
**.overlay*.kademdia.stabilizeDelay = 144s 
**.overlay*.kademlia.routingType = "semi-recursive" 
**.measurementTime = 3600s 
[Config Pastry-dequy] 
description = Pastry (SimpleUnderlayNetwork) 
*.underlayConfigurator.churnGeneratorTypes = "oversim.common.LifetimeChurn" 
**.overlayType = "oversim.overlay.pastry.PastryModules" 
**.enableNewLeafs = false 
**.tier1Type = "oversim.applications.kbrtestapp.KBRTestAppModules" 
**.measureNetwInitPhase = false 
**.useCommonAPIforward = true 
**.neighborCache.enableNeighborCache = true 
**.overlay*.pastry.bitsPerDigit = 4 
**.overlay*.kademdia.stabilizeDelay = 144s 
**.overlay*.pastry.numberOfLeaves = 16 
**.overlay*.pastry.numberOfNeighbors = 10 
**.measurementTime = 3600s 
**.targetOverlayTerminalNum = ${500, 1000, 1500, 2000} 
**.churnGenerator.lifetimeMean = ${1800, 2400, 3000, 3600,4200}