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à


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.

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

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


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ị


Hệ thống tập trung

Continuous Time Markov Chain

Chuỗi Markov liên tục theo thời gian

C

CS
Csy
CTMC

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

Denial of Service

DTLS

Distributed Storage and
Replication Layer Security

DTMC
F

Discrete Time Markov Chain

Từ chối dịch vụ
Lớp bảo mật sao lưu và lưu trữ phân
tán
Chuỗi Markov thời gian rời rạc


FTP

File Transfer Protocol

Giao thức truyền file

Graphical User Interface

Giao diện đồ họa

HyperText Markup Language



Giao thức Internet

Juxtapose

Mạng ngang hàng mã nguồn mơ của

G
GUI
H
HTML
HSy
HTTP
I
ID
ICMP

Nhóm chuyên trách kỹ thuật Internet

J
JXTA

Sun Microsystems
K
KBR

Key Based Routing

Định tuyến dựa trên khóa


Peer-to-Peer

Ngang hàng

PDA

Personal Digital Assistant

Thiết bị số hỗ trợ cá nhân

M

N
NAT
O

P


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ố


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

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


Voice over Internet Protocol

Truyền thoại qua giao thức Internet

Wide Area Network

Mạng diện rộng

T

U

V

W
WAN


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

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:
Fℵ( S ) :

Số siêu – siêu nút (Ultra Super-peer)

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.

Fℵ( p ) :

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ố
fi (xi): Hàm chi phí tương ứng với các biến x1, x2 ,...., xn .

: Thời gian hoạt động trung bình của nút

𝑞()
𝑞 ():

Khả năng xử lý CPU (MIPS Million Instruction Per Second)


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


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........................................................... 31
Hình 2-3. Quá trình ra nhập, rời mạng................................................................... 32
Hình 2-4. Bảng định tuyến của nút 5712................................................................. 34
Hình 2-5. Quá trình tìm kiếm từ nút nguồn 5230 tới nút đích 42AD....................35
Hình 2-6. Quá trình quảng bá chỉ mục dữ liệu....................................................... 35
Hình 2-7. Quá trình truy vấn chỉ mục dữ liệu........................................................ 36
Hình 2-8. Không gian ID của mạng Kademlia (N=16).......................................... 37
Hình 2-9. Các k-bucket của một nút........................................................................ 37
Hình 2-10. Quá trình tìm kiếm................................................................................. 38
Hình 2-11. Kiến trúc OverSim [6]............................................................................ 44
Hình 2-12. Kiến trúc các khối chức năng của OverSim......................................... 45
Hình 2-13. Mô hình mô phỏng................................................................................. 46

Hình 4-1. Mô hình mạng phân cấp Chord_SL........................................................ 79
Hình 4-2.Gán định danh cho nút SN và nút ON [25]............................................. 81
Hình 4-3.Hiệu năng của các nút tham gia lớp nội miền Chord_SL....................... 83
Hình 4-4. Ma trận bầu chọn SN............................................................................... 84
Hình 4-5. Kích thước nhóm nội miền và độ dài đường tìm kiếm..........................90
Hình 4-6. Không gian lưu trữ của siêu nút và kích thước mạng...........................91
Hình 4-7. Độ dài đường tìm kiếm và kích thước nhóm nội miền..........................93
Hình 4-8. Độ dài đường tìm kiếm và xác suất tìm kiếm nội miền.........................94


15

MỞ ĐẦU

1.

Tính cấp thiết của luận án
Mạng ngang hàng P2P là một mạng hỗn hợp, được tạo lập trên diện rộng bao

gồm cả những người dùng mạng Internet và các mạng máy tính chuyên nghiệp. Các
mạng chồng phủ, dưới dạng các mạng P2P, đang trơ nên rất phổ biến trong những
năm gần đây, do các tính năng làm cho chúng phù hợp với việc phát triển hay triển
khai các dịch vụ mới như truyền thông đa hướng, chia sẻ dữ liệu phạm vi rộng và
phân phối nội dung như Kazaa, Napster, Bittorrent, Skype, Sopcast [4],... Kiến trúc
của mạng viễn thông ngày nay đang chuyển thành hướng dịch vụ thay vì xu hướng
mạng trước đây, nhằm cho phép mơ hạ tầng viễn thông cho các nhà phát triển ứng
dụng để tạo ra các dịch vụ mới theo mô hình của mạng Internet.
Ian Clarke sáng lập viên mạng FreeNet [67] khẳng định “P2P là bước tiến
hoá hoàn toàn tự nhiên và hoàn hảo của mạng Internet. Thực tế, P2P đã mang
Internet trở lại nguyên bản theo đúng ý tưởng của những người đầu tiên sáng lập

kiếm tập trung, cho phép tìm kiếm thông tin nhanh chóng, tuy nhiên điểm yếu của
mô hình là không có khả năng mơ rộng vì tải trên máy chủ se tăng tuyến tính với
các nút tham gia vào mạng.
Thế hệ thứ hai đã khắc phục nhược điểm của thế hệ thứ nhất. Mạng P2P thế hệ
thứ hai không có bất kỳ máy chủ nào mà tất cả các nút đều có vai trò như nhau.
Điểm yếu của thế hệ này là triển khai cơ chế định tuyến trên cơ sơ phát tràn lụt yêu
cầu truy vấn, kỹ thuật tràn lụt đã sinh ra quá nhiều lưu lượng mạng dẫn tới tính năng
mơ rộng của thế hệ này thậm chí còn kém hơn thế hệ thứ nhất. Mạng điển hình cho
thế hệ thứ hai là Gnutella [4].
Nhằm đáp ứng các vấn đề mơ rộng quy mô và khắc phục các nhược điểm của
mạng thế hệ thứ nhất và thứ hai, một số nhóm nghiên cứu đã đưa ra mạng P2P thế
hệ thứ ba. Các hệ thống P2P thế hệ thứ ba sử dụng thuật toán tìm kiếm dựa trên cơ
chế bảng băm phân tán DHT. DHTs điển hình như: Kademlia [48], [50], Chord [60],
Pastry [57], Tapestry [82], CAN [62], ... Mỗi nút trong hệ thống có một định danh
thu được từ việc băm các thuộc tính đặc trưng của nút đó như: Địa chỉ IP,


cổng TCP/IP, dữ liệu. Bảng băm lưu trữ dữ liệu dưới dạng cặp khóa - giá trị
(key/value). Nút tham gia trong DHTs được liên kết với nhau dựa trên mạng nền
tảng (ví dụ mạng Internet), thông qua cơ chế định tuyến riêng của mình các nút thực
hiện kết nối và truyền thông với nhau. Vì vậy một mạng được xây dựng bơi cơ chế
DHT được gọi là mạng chồng phủ (Overlay Network) và mạng cho phép mạng
chồng phủ hoạt động trên đó được gọi là mạng nền tảng (Underlay Network).
Thuật toán định tuyến là chức năng cốt lõi của DHTs, nó có nhiệm vụ xác định
vị trí trên mạng chồng phủ chứa dữ liệu cần tìm kiếm hoặc vị trí lưu dữ liệu một
cách tối ưu nhất. Mục tiêu thuật toán định tuyến của DHTs đưa ra nhằm cải thiện
hiệu năng: Giảm độ dài đường tìm kiếm và giảm số lượng trạng thái phải duy trì tại
mỗi nút, cải thiện hiệu quả tìm kiếm, phù hợp với việc triển khai dịch vụ trên quy
mô lớn [48], [75]. Tuy nhiên, khi triển khai DHTs trên mạng P2P có độ ổn định thấp
gặp một số vấn đề về hiệu năng: Chi phí để duy trì cấu trúc của mạng tăng do phải

nhiên DHTs mới chỉ giải quyết được vấn đề mơ rộng quy mô và hiệu quả tìm kiếm.
Nhưng khi triển khai DHTs trong mạng không đồng nhất và độ ổn định thấp thì
DHTs có nhiều hạn chế [27], [36], [43], [53], [54], [63], [77], [80].
Để cải thiện tỷ lệ tìm kiếm thành công và độ dài trung bình đường tìm kiếm
các nghiên cứu [11], [14], [15], [86] đã sửa đổi cấu trúc bảng bảng định tuyến và
dùng bộ nhớ để lưu trữ các phiên truyền thông gần nhất. Nhóm tác giả của nghiên
cứu [86] xây dựng bảng định tuyến hai chiều. Bảng định tuyến chứa con trỏ chỉ tới
các nút cùng chiều và ngược chiều kim đồng hồ, giúp mơ rộng không gian tìm kiếm
trong mạng chồng phủ. Nghiên cứu [84] sử dụng bộ nhớ Cache, để cải thiện tỷ lệ
tìm kiếm thành công trong mạng P2PSIP. Các nghiên cứu này nhằm giải quyết vấn
đề “Churn rate” cao trong mạng ngang hàng.
Thông tin trễ RTT tại các nút qua lớp nền được đo theo chu kỳ và cập nhật vào
bảng định tuyến [26], [79], [80]. Đường định tuyến tốt có thể là đường định tuyến
có khoảng cách định danh ID là nhỏ nhất và có khoảng cách vật lý ngắn nhất. Các
nghiên cứu này nhằm giải quyết vấn đề “Topology Mismatch”.
Từ những khảo sát và phân tích các nghiên cứu về cải thiện hiệu năng mạng
ngang hàng đã được đề xuất trước đây, cho thấy các nghiên cứu mới chỉ giải quyết
được một vấn đề. Tuy nhiên để cải thiện hiệu năng của P2P cần phải cân bằng được
hai yếu tố giảm chi phí để duy trì mạng và giảm trễ qua mạng chổng phủ. Xuất phát
từ các khảo sát và phân tích ơ trên luận án đề xuất cải thiện cấu trúc của mạng P2P


và cải thiện thuật toán định tuyến để cân bằng hai yếu tố phân tích ơ trên. Luận án
tập trung vào hai mục tiêu chính sau đây:
Mục tiêu thứ nhất:
Xây dựng mạng Chord_SL phân cấp cải thiện hiệu năng. Với mục tiêu tìm
kiếm nhanh và giảm trễ qua mạng ngang hàng, mô hình được chia làm hai lớp (lớp
liên miền và lớp nội miền). Lớp liên miền quản lý các nút với năng lực toàn diện ơ
mức cao (băng thông rộng, tốc độ xử lý cao, thời gian online dài) như một siêu nút
(SN), trong khi các nút khác không có những khả năng như thế được coi như là nút

kiếm, kích thước bảng định tuyến, tỷ lệ tìm kiếm thành công, chi phí bầu chọn siêu
nút,...
Để đạt được mục tiêu và đối tượng nghiên cứu đã nêu ơ trên, nhiệm vụ nghiên
cứu trong luận án tập trung vào các vấn đề sau:
Khảo sát các hướng nghiên cứu cải thiện hiệu năng mạng ngang hàng, phân
tích các thách thức ảnh hương tới hiệu năng của mạng ngang hàng. Từ đó sáng
tỏ cách thức tiếp cận, giải quyết vấn đề nhìn từ khía cạnh phương pháp luận và
xác định công cụ phân tích và mô phỏng sử dụng trong nghiên cứu của luận
án.
Phân tích và xây dựng kịch bản so sánh hiệu năng các thuật toán định tuyến
DHTs Kademlia, Tapestry và Chord theo các yếu tố: Khả năng mơ rộng của
DHTs (mô phỏng đã chạy với 20.000 nút), tính hiệu quả của các thuật toán
trong môi trường mạng có kích cỡ khác nhau và mạng không ổn định (có
nghĩa là các nút gia nhập và rời mạng vào thời gian bất kỳ không thể dự đoán
được). Ngoài ra, qua việc đánh giá và so sánh hoạt động của các thuật toán
định tuyến DHTs ta có thể phân tích được các ưu nhược điểm của từng thuật
toán qua đó lựa chọn thuật toán Chord phù hợp với mục tiêu của luận án và đề
xuất hướng cải thiện hiệu năng.
Phân tích các mạng phân cấp dựa trên thuật toán Chord của các nghiên cứu
trước, từ đó đề xuất mạng phân cấp cải thiện hiệu năng. Sử dụng các công cụ
toán học và mô phỏng so sánh hiệu năng với các mô hình mạng phân cấp đã
nghiên cứu [2], [25], [35], [61], [85].
3.

Phương pháp nghiên cứu
Nghiên cứu các phương pháp cải thiện hiệu năng được công bố từ trước đến
nay, để từ đó cải thiện và áp dụng vào bài toán của luận án.


Phân tích, mô phỏng và đánh giá, so sánh các phương pháp được đề xuất trong

Phần mở đầu: Trình bày tính cấp thiết của luận án, mục tiêu và phạm vi của luận
án, phương pháp nghiên cứu, những đóng góp chính của luận án. Các kết quả
nghiên cứu và đóng góp mới được trình bày trong các chương, mục theo cấu trúc
sau:


Chương 1. Tổng quan về mạng P2P
Chương một trình bày tổng quan về những vấn đề liên quan đến luận án, bao
gồm: Kiến thức nền tảng về mạng P2P, các thách thức khi nghiên cứu hiệu năng
mạng ngang hàng, các vấn đề về thuật toán định tuyến DHT và các tham số hiệu
năng định tuyến. Trong đó, đáng chú ý là nội dung khảo sát về các hướng cải thiện
hiệu năng mạng ngang hàng để làm sáng tỏ phạm vi nghiên cứu và cách tiếp cận
của luận án. Nội dung của chương này là các kết quả nghiên cứu công bố trong các
công trình [V1].
Chương 2. Đánh giá hiệu năng thuật toán định tuyến DHTs
Chương hai tập trung phân tích lý thuyết và đánh giá hoạt động ba thuật toán
định tuyến DHTs: Kademlia, Tapestry và Chord. Cả ba thuật toán đều được thiết kế
nhằm giảm độ trễ trong quá trình tìm kiếm dữ liệu. Tuy nhiên, mỗi thuật toán lại
tiếp cận DHT theo các cách khác nhau để xây dựng thuật toán định tuyến. Phần cuối
của chương luận án sử dụng phần mềm mô phỏng OverSim [6] để đánh giá hiệu
năng của ba thuật toán định tuyến DHTs, từ đó xác định thuật toán Chord được chọn
để tiếp tục nghiên cứu ơ chương 3 và chương 4. Thuật toán Chord được đánh giá là
thuật toán đơn giản, dễ triển khai, tìm kiếm hiệu quả và có khả năng mơ rộng [18].
Nội dung của chương là kết quả của công trình nghiên cứu [V2].
Chương 3. Cải thiện hiệu năng thuật toán định tuyến Chord
Nội dung chương đi sâu phân tích thuật toán định tuyến Chord gốc [18], [60]
từ đó thấy được ưu nhược điểm của thuật toán và đưa ra hướng cải thiện. Thuật toán
được cải thiện trong luận án có hiệu năng tốt hơn các nghiên cứu trước đây [11],
[15], [64], [79], [86]. Nội dung của chương là kết quả của công trình nghiên cứu
[V3].

ngày nay thì mô hình client/server có rất nhiều vấn đề cần được xem xét. Khi số
lượng máy khách tăng đến một mức độ nào đó thì nhu cầu về tải, băng thông tăng
và máy chủ không có khả năng cung cấp dịch vụ cho các máy khách thêm vào. Mô
hình P2P được xem như một giải pháp khắc phục nhược điểm của mô hình
client/server khi triển khai dịch vụ trên diện rộng và quy mô lớn [1], [7], [21], [65],
[67], [70], [73].
Mạng P2P đã được phát triển trong suốt những năm 1990, nhưng chỉ đến khi
Internet bùng nổ, cùng với sự ra đời của các dịch vụ chia sẻ file, âm thanh, hình ảnh
trong thời gian gần đây thì mạng ngang hàng mới được chú ý đến như là một công
nghệ quan trọng của Internet hiện tại và tương lai. Theo Dự báo chỉ số tăng trương
mạng (VNI) hàng năm của Cisco lần thứ 10 (the 10th annual Cisco® Visual
Networking Index™ [VNI] Forecast), lưu lượng IP hàng năm se tăng gấp ba lần
trong giai đoạn từ 2014 - 2019, và se đạt mức kỷ lục là 2 zettabytes, đặc biệt là các
ứng dụng P2P chiếm khoảng 50% (thậm chí 75%) băng thông trên Internet [1],
[21]. Vậy mạng ngang hàng là gì?.


Một mạng ngang hàng đúng nghĩa không có khái niệm máy chủ và máy
khách, tất cả các máy tham gia đều bình đẳng và được gọi là nút, nó đóng vai trò
của cả máy chủ và máy khách đối với các máy khác trong mạng.
Qua khảo sát các định nghĩa về mạng P2P của một số nghiên cứu [9], [58],
[65], [69] các nghiên cứu đều thống nhất một số điểm đặc trưng của P2P: Các nút
trong mạng P2P có vai trò như nhau, chia sẻ tài nguyên và có khả năng tự trị, dê
dàng triển khai, khả năng định tuyến trên diện rộng, tìm kiếm dữ liệu hiệu quả, tin
cậy và bảo mật, khả năng mở rộng và chịu đựng lỗi. Mạng chồng phủ ngang hàng
được định nghĩa như sau:
Mạng chồng phủ ngang hàng là mạng máy tính được xây dựng trên nền của
một mạng khác. Các nút trong mạng ngang hàng được kết nối với nhau bằng liên
kết logic, mỗi liên kết logic có thể bao gồm rất nhiều các liên kết vật lý của mạng
nền (Internet) [69].