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



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



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

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

Client – Server

Mô hình Khách – chủ

Csy


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

Domain Name System

Hệ thống tên miền

DUSy

Decentralized Unstructured Systems

Hệ thống phân tán không cấu trúc

DSSy

Decentralized structured Systems

Hệ thống phân tán có cấu trúc


Giao thức truyền file

Graphical User Interface

Giao diện đồ họa

HTML

HyperText Markup Language

Ngôn ngữ đánh dấu siêu văn bản

HSy

Hybrid Systems

Hệ thống lai ghép

HTTP

Hyper-Text Transfer Protocol

Giao thức truyền siêu văn bản

ID

Identifier

Định danh

G
GUI
H

I

J
JXTA

Sun Microsystems
K
Key Based Routing

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

MD5

Message-Digest algorithm 5

Thuật toán mã hóa MD5

MDC

Multi Description Code

Mã hóa đa mô tả

Network Address Translation

Chuyển đổi địa chỉ mạng

O

P


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ố

Quality of Service

Chất lượng dịch vụ

RELOAD

Resource Location And Discovery

Khai phá và tìm kiếm tài nguyên

RIP


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

Time To Live

Thời gian sống của gói tin

UA

User Agent

Đại lý người dùng

UDP


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
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
𝑛𝑞 : Định danh của nút q
n: Định danh của nút

D-d: Độ dài bít định danh tiền tố
d: Độ dài bít định danh hậu tố
f i (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)
𝐵(𝑝) : Băng thông của nút
h flat :

Độ dài đường tìm kiếm qua mô hình Chord_flat

h: Độ dài đường tìm kiếm trung bình
hns : Độ dài đường tìm kiếm từ nút nội miền đến siêu nút

hss : Độ dài đường tìm kiếm siêu nút (SN) trong lớp liên miền

Tns :

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

Tss : 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

Cbeat : Chi phí để gửi bản tin heartbeat


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 2-14. Độ dài đường tìm kiếm trung bình Chord_iterative và Chord_recursive
48
Hình 2-15. Trễ trung bình Chord_iterative và Chord_recursive .......................... 48
Hình 2-16. Tỷ lệ thành công của Chord_iterative và Chord_recursive ................ 49
Hình 2-17. Băng thông tiêu tốn ( số bytes /s) Chord_iterative, Chord_recursive 49
Hình 2-18. Bytes/s gửi từ SimpleUnderlayNetwork và InetUnderlayNetwork ... 49
Hình 2-19. Độ dài đường định tuyến qua mạng ...................................................... 50
Hình 2-20. Trễ tìm kiếm của SimpleUnderlayNetwork và InetUnderlayNetwork50
Hình 2-21. Tỷ lệ tìm kiếm thành công và số nút...................................................... 50
Hình 2-22. Tỷ lệ trễ dãn cách trung bình- Tstretch và số nút .............................. 51
Hình 2-23. Băng thông tiêu tốn và số nút ................................................................. 51


xiv

Hình 2-24. Tỷ lệ tìm kiếm thành công và thời gian hoạt động............................... 52
Hình 2-25. Băng thông tiêu tốn và thời gian hoạt động ......................................... 52
Hình 2-26. Tỷ lệ trễ dãn cách trung bình- Tstretch và thời gian........................... 52
Hình 3-1. Biểu diễn vòng Chord (M= 6) gồm 10 nút .............................................. 57
Hình 3-2. (a)Định tuyến lặp


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 ra
Internet”.
Qua nghiên cứu khảo sát hầu hết các dự án đều đề xuất P2P là xu hướng mạng
và dịch vụ của Internet trong tương lai. Điển hình là dự án Planet Lab [65], GENI
[7], [70], G-Lab [69]. Vì vậy nghiên cứu về mạng ngang hàng là một trong những
hướng nghiên cứu có tính thời sự và có ý nghĩa khoa học, công nghệ sâu sắc trong
bối cảnh bùng nổ các ứng dụng đa phương tiện.
Mạng ngang hàng với các ưu điểm như: Khả năng mở rộng, khả năng chịu
đựng lỗi, dễ dàng triển khai,...Tuy nhiên chính cơ chế truyền thông ngang hàng và
các yêu cầu cung cấp chất lượng dịch vụ đã cho thấy một số thách thức mà mạng
P2P cần phải giải quyết. Cụ thể các thiết bị đầu cuối hoạt động trong môi trường
mạng không dây như điện thoại thông minh, máy tính bảng ,... đã và đang phát triển
rất mạnh mẽ và đa dạng. Các thiết bị này có đặc điểm là thời gian tham gia kết nối
vào mạng ngắn, thời gian kết nối thậm chí có thể chỉ trong vài giây bởi chính sách
tiết kiệm năng lượng và do thói quen di động của người sử dụng. Điều này dẫn tới


2

cấu trúc của mạng thay đổi liên tục trong khoảng thời gian rất ngắn hay còn gọi là
mạng có độ ổn định thấp (hay còn gọi mạng có “Churn rate” cao) [29], [47], [73].
Hơn nữa đối với mạng ngang hàng, các nút tức các phần tử ngang hàng tự tổ

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 liên tục cập nhật bảng định tuyến, tỷ lệ trễ dãn cách trung bình tăng cao do hiệu
năng không đồng nhất giữa mạng IP và mạng chồng phủ.
Để có thể triển khai các dịch vụ trên quy mô lớn hầu hết nghiên cứu đều tập
trung vào mạng ngang hàng thế hệ thứ ba. Các nghiên cứu đề xuất giải pháp cải
thiện hiệu năng mạng P2P dựa trên cơ chế bảng băm phân tán DHT. Qua khảo sát
hướng nghiên cứu cải thiện hiệu năng của tác giả trước chủ yếu tập trung vào hai
hướng chính:
(i) Hướng nghiên cứu thứ nhất: Tối ưu cấu trúc mạng chồng phủ: Các tác
giả trước đều tập trung giải quyết hai vấn đề: Mạng có có độ ổn định thấp và hiệu
năng không đồng nhất giữa mạng nền và mạng chồng phủ. Mô hình phân cấp có
hiệu năng định tuyến tốt hơn so với mô hình không phân cấp [2], [14], [25], [35],
[37], [61]. Việc tính toán kích thước của nhóm trong mạng phân cấp cũng ảnh
hưởng tới độ dài đường tìm kiếm [37]. Các tác giả [2], [25] đã thiết kế mô hình hai
lớp dựa trên thuật toán DHT: Kademlia và Chord. Thời gian tìm kiếm qua mô hình
hai lớp đã giảm đáng kể, do việc xây dựng cấu trúc của các lớp chưa xét tới các yếu
tố trễ của mạng nền, nên mô hình này vẫn chưa giải quyết được vấn đề “Topology


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


5

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
thông thường (ON) do lớp nội miền quản lý. Để cải thiện tỷ lệ trễ dãn cách trung
bình và độ dài trung bình đường tìm kiếm, mô hình phân cấp đã kết hợp với việc
phân cấp dựa trên vị trí của các nghiên cứu [61], [85].
Mục tiêu thứ hai:
Cải thiện hiệu năng thuật toán định tuyến Chord tại các lớp trong mạng phân
cấp. Việc cải thiện tập trung cải thiện cấu trúc bảng định tuyến, tăng khả năng kết
nối với các nút hàng xóm trong vòng tròn Chord. Việc cải thiện hiệu năng tìm kiếm
có tính tới yếu tố “Topology Mismatch”.
2.

Mục tiêu và phạm vi của luận án
Với mục tiêu xây dựng mạng phân cấp cải thiện hiệu năng hệ thống P2P. Luận

án đã chọn mô hình mạng phân cấp triển khai trên thuật toán định tuyến Chord.
Tuy nhiên qua phân tích hướng nghiên về mạng phân cấp và cải thiện hiệu
năng định tuyến dựa trên cơ chế bảng băm phân tán, các nghiên cứu trước chỉ tập

đượ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.


7

Phân tích, mô phỏng và đánh giá, so sánh các phương pháp được đề xuất trong
luận án với các phương pháp đã có.
4.

Những đóng góp chính của luận án
Dựa trên cơ sở nghiên cứu về: Cải thiện hiệu năng thuật toán định tuyến DHT

trên mạng ngang hàng, luận án đề xuất một số đóng góp khoa học chính như sau:
Đề xuất cải thiện hiệu năng thuật toán định tuyến Chord có ưu điểm hơn các
công trình nghiên cứu trước [11], [15], [64], [79], [86] về một số các tham số
hiệu năng như: Kích thước bảng định tuyến giảm một nửa so với nghiên cứu
[11], [86], độ dài đường tìm kiếm giảm một nửa so với nghiên cứu [79]. Các
kết quả chính là nội dung của bài báo khoa học “Cải thiện hiệu năng thuật toán

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].
Chương 4. Xây dựng mạng ngang hàng Chord_SL phân cấp cải thiện hiệu
năng
Chương bốn phân tích các nghiên cứu xây dựng mô hình mạng phân cấp ứng
dụng triển khai dịch vụ thời gian thực, từ đó xây dựng mô hình mạng Chord_SL
phân cấp cải thiện hiệu năng. Chord_SL được chia làm hai lớp: Lớp nội miền và lớp


9

liên miền. Cả hai lớp đều được cấu trúc dạng vòng tròn Chord và sử dụng thuật toán

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 sẽ tăng gấp ba lần
trong giai đoạn từ 2014 - 2019, và sẽ đạ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ì?.


11

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].
Mạng chồng phủ

Mạng nền tảng


Overlay Network Layer

tìm kiếm tài nguyên…

( Lớp mạng chồng phủ)

TCP, UDP/IP

Underlying Network Layer
( Lớp mạng nền )

Hình 1-2. Kiến trúc phân lớp điển hình mạngP2P
Dựa trên cấu trúc và thuật toán định tuyến trong lớp mạng chồng phủ, kiến
trúc mạng chồng phủ P2P được chia thành mô hình tập trung, phân tán và lai ghép
[48], [63]. Mô hình phân tán được chia làm hai loại không cấu trúc, có cấu trúc,
phân cấp và không phân cấp (Hình 1-3).
P2P

Tập trung

Có cấu trúc

Phân tán

Lai ghép

Không cấu trúc

Hình 1-3. Phân loại kiến trúc mạng chồng phủ P2P


tới việc tăng lưu lượng mạng khi mở rộng mạng. Tuy nhiên các hệ thống không cấu
trúc lại thích ứng với sự thay đổi thường xuyên của mạng.