Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
Cộng hoà xã hội chủ nghĩa Việt Nam
Độc lập – Tự do – Hạnh phúc
***

LỜI CAM Đ
OAN

Luận văn thạc sỹ này do tôi nghiên cứu và thực hiện dưới sự hướng dẫn của
Thầy giáo TS. Phạm Việt Bình. Để hoàn thành bản luận văn này, ngoài các tài liệu
tham khảo đã liệt kê, tôi cam đoan không sao chép các công trình nghiên cứu của
người khác. Thái Nguyên, ngày 13 tháng 10 năm 2010
Ngƣời cam đoan
2010 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1
Mục lục
Danh mục thuật ngữ, từ viết tắt 3
Danh mục thuật ngữ, t ừ viết tắt 3
1.2.1. Bảng băm (Hash table) 28
1.2.2. Bảng băm phân tán - Distributed Hash Table (DHTs) 28
Chƣơng 2. Một số dạng bảng băm trong mạng ngang hàng 31
2.1. Kademlia 32
2.2. Tapestry 34
2.3. Kelips 39
2.4. Chord 41
Chƣơng 3. Chƣơng trình thử nghiệm 51
3.1. Bài toán thực tế 51
3.2. Khảo sát các simulator mô phỏng mạng overlay 52
3.3. Phần mềm mô phỏng P2PSim 54
3.3.1. Các bước mô phỏng với phần mềm P2PSim 56
3.3.2. Kịch bản mô phỏng 58
3.3.3. Đánh giá hiệu năng giao thức Chord trong mạng ngang hàng thông
qua các kết quả mô phỏng 58
a) Kết quả mô phỏng ảnh hưởng của Churn rate đến tỷ lệ tìm kiếm lỗi . 58
b) Kết quả mô phỏng ảnh hưởng của số lượng Node đến tỷ lệ tìm kiếm lỗi
62
c) Kết quả mô phỏng ảnh hưởng của RTT đến tỷ lệ tìm kiếm lỗi 65
d) Kết quả mô phỏng các tham số của Chord đối với tỷ lệ tìm kiếm lỗi . 68
Kết luận 71
Tài liệu tham khảo 73
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Item
Một đơn vị dữ liệu

Structured
Có cấu trúc

Overlay
Mạng được xây dựng trên các mạng khác

Hash table
Bảng băm

Join
Gia nhập (mạng ngang hàng)

Leave
Rời khỏi (mạng ngang hàng)

Failure
Lỗi

Churn rate
Số lượng peer rời khỏi/gia nhập mạng
trong một khoảng thời gian

Danh mục hình vẽ
Hình 1.1. (a) Mô hình Client/Server 9
Hình 1.1. (b) Mô hình P2P 9

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Hình 3.1 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 10s 59
Hình 3.2 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 60s 60
Hình 3.2 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 60s 60

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5
Hình 3.3 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 120s 60
Hình 3.3 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 120s 60
Hình 3.4 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 300s 61
Hình 3.4 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 300s 61
Hình 3.5 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 600s 61
Hình 3.5 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 600s 61
Hình 3.6 (a) Kết quả mô phỏng tổng hợp với 100 node 62 Hình 3.6 (b) Kết quả mô phỏng tổng hợp với 1000 node 62
Hình 3.7 (a) Kết quả mô phỏng 100 node, khoảng thời gian vào/ra mạng là 300s 63
Hình 3.7 (b) Kết quả mô phỏng 100 node, khoảng thời gian vào/ra mạng là 600s 63
Hình 3.8 (a) Kết quả mô phỏng 250 node, khoảng thời gian vào/ra mạng là 300s 64
Hình 3.8 (b) Kết quả mô phỏng 250 node, khoảng thời gian vào/ra mạng là 600s 64
Hình 3.9 (a) Kết quả mô phỏng 500 node, khoảng thời gian vào/ra mạng là 300s 64
Hình 3.9 (b) Kết quả mô phỏng 500 node, khoảng thời gian vào/ra mạng là 600s 64
Hình 3.10 (a) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 300s 64
Hình 3.10 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 600s 64
Hình 3.11 (a) Kết quả mô phỏng tổng hợp khoảng thời gian vào/ra mạng là 300s 65
Hình 3.11 (b) Kết quả mô phỏng tổng hợp khoảng thời gian vào/ra mạng là 600s 65
Hình 3.12 (a) Kết quả mô phỏng RTT = 0,5s khoảng thời gian vào/ra mạng là 300s 66
Hình 3.12 (b) Kết quả mô phỏng RTT = 0,5s khoảng thời gian vào/ra mạng là 600s 66

Thuật toán 2.2. Giả mã cho hoạt động join vào mạng của một node 46
Thuật toán 2.3. Giả mã cho quá trình stabilization 47

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Lời mở đầu
Khoảng mười năm trở lại đây, thế giới đã chứng kiến sự bùng nổ của Internet
băng thông rộng, cùng với nó là sự phát triển mạnh mẽ của các ứng dụng peer-to-peer.
Với nhiều ưu điểm hứa hẹn như tính hiệu quả, linh hoạt và khả năng mở rộng cao, các
mạng peer-to-peer overlay đã và đang thu hút được nhiều sự quan tâm từ cộng đồng
nghiên cứu. Các mạng peer-to-peer overlay đã phát triển qua ba thế hệ, thế hệ hiện nay
là mạng structured overlay dựa trên khả năng lưu trữ và tìm kiếm dữ liệu hiệu quả của
cơ chế bảng băm phân tán (Distributed Hash Table - DHTs).
DHTs là cơ sở để xây dựng các hệ thống ứng dụng phân tán như distributed file
systems, peer-to-peer file sharing và content distribution systems. Bên cạnh đó là các hệ
thống web caching, multicast, anycast, domain name services, và instant messaging. Các
hệ thống ứng dụng sử dụng DHTs đáng chú ý có BitTorrent, eDonkey
Các DHTs được thiết kế để làm trong môi trường tương đối ổn định với các peer là
máy tính. Tuy nhiên, vài năm gần đây, các thiết bị nối mạng ngày càng phong phú, đa
dạng như tivi hay các thiết bị wireless như điện thoại, PDA, …. Các thiết bị này kết nối
và rời khỏi mạng sau một thời gian ngắn (churn rate cao) khiến cho thông tin về các
peer trên mạng liên tục thay đổi dẫn đến hiệu năng của các DHTs giảm sút rõ rệt.
Đánh giá và cải thiện hiệu năng của các DHTs trong điều kiện mạng churn rate cao là
bài toán đang rất được quan tâm hiện nay.
Luận văn bao gồm ba phần. Phần thứ nhất tóm tắt lý thuyết chung về mạng
peer-to-peer. Phần thứ hai, luận văn tìm hiểu cơ chế DHTs thông qua một số DHTs nổi
tiếng như Chord, Kademlia, Tapestry, Kelips. Phần thứ ba luận văn văn tiến hành phân
tích, đánh giá hiệu năng của một DHTs cụ thể (Chord DHTs) và căn cứ vào các kết quả
phân tích đó mở ra hướng khắc phục các hạn chế của các DHTs.

9 Hình 1.1. (a) Mô hình Client/Server Hình 1.1. (b) Mô hình P2P

 Theo Miller: P2P là một kiến trúc trong đó các máy tính có vai trò và trách
nhiệm như nhau. Mô hình này đối lập với mô hình client/server truyền thống, trong đó
một số máy tính được dành riêng để phục vụ các máy tính khác. P2P có năm đặc điểm:
- Việc truyền dữ liệu và thông tin giữa các peer trong mạng dễ dàng.
- Các peer vừa có thể hoạt động như client vừa có thể hoạt động như server.
- Nội dung chính trong mạng được cung cấp bởi các peer.
- Mạng trao quyền điều khiển và tự trị cho các peer.
- Mạng hỗ trợ các peer không kết nối thường xuyên và các peer không có địa chỉ
IP cố định
 Theo P2P Working Group: P2P computing là sự chia sẻ tài nguyên và dịch vụ
bằng cách trao đổi trực tiếp giữa các hệ thống. Tài nguyên và dịch vụ ở đây bao gồm
thông tin, chu kỳ xử lý, không gian lưu trữ. Peer-to-peer computing tận dụng sức mạnh
tính toán của các máy tính cá nhân và kết nối mạng, cho phép doanh nghiệp tận dụng
sức mạnh tổng hợp của các client.
Các định nghĩa về P2P thống nhất ở một số khái niệm: chia sẻ tài nguyên, tự
trị/phân tán, địa chỉ IP động, vai trò vừa là client vừa là server.
 Overlay network:
+ 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 nodes
trong mạng overlay được xem là nối với nhau bằng liên kết ảo (logical links), mỗi liên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10
kết ảo có thể bao gồm rất nhiều các liên kết vật lí của mạng nền.

trực tiếp với peer chứa file mà không thông qua server nữa.

Hình 1.3. Mô hình centralized directory
Đóng góp chính của thế hệ thứ nhất là đã đưa ra kiến trúc mạng không xem các
máy tính như client và server mà xem chúng như các máy cung cấp và sử dụng tài
nguyên với vai trò tương đương nhau. Mô hình centralized directory cho phép tìm kiếm
thông tin trong không gian lưu trữ một cách nhanh chóng, tuy nhiên, điểm yếu của của
mô hình này là tính khả mở vì tải trên index server sẽ tăng tuyến tính với số lượng peer.
Đồng thời các hệ thống sử dụng mô hình này, điển hình là Napster còn gặp vấn đề về
bản quyền các tài nguyên.
 Thế hệ thứ hai
Thế hệ thứ hai bắt đầu với các ứng dụng như Gnutella, Freenet làm việc mô

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12
hình flooded requests. Mô hình này không có bất kỳ server nào, các peer bình đẳng
như nhau. Các hệ thống peer to peer thế hệ thứ hai là các hệ thống peer to peer thuần
túy. Không giống thế hệ thứ nhất, các peer không thông báo về các nội dung chúng
chia sẻ, khi một peer muốn tìm kiếm một file, nó gửi yêu cầu tới các peer kết nối trực
tiếp với nó, nếu các peer đó không tìm thấy file, mỗi peer sẽ gửi yêu cầu tìm kiếm đến
các peer kết nối trực tiếp với nó, quá trình cứ diễn ra như vậy cho đến khi yêu cầu bị
từ chối. Quá trình gửi yêu cầu tìm kiếm đi như vậy gọi là flooding. Hình 1.2 biểu diễn
một mô hình flooding request.

Hình 1.4. Mô hình flooding request
Thế hệ thứ hai xóa bỏ được một số điểm xử lý tập trung trong mạng nhưng tính khả
mở còn kém hơn do mạng sử dụng thuật toán flooding sinh ra quá nhiều traffic.
Thêm nữa, các mạng làm việc theo mô hình này không đảm bảo sẽ tìm được dữ liệu có

Các hàm này hoàn thành sau khi đi qua một số nhỏ các chặng. Giải pháp DHTs
đảm bảo cho mạng có tính khả mở và khả năng tìm thấy thông tin cao trong khi vẫn
hoàn toàn phân tán. DHT đang được xem như là cách tiếp cận hợp lý cho vấn đề định
vị và định tuyến trong các hệ thống P2P. Cộng đồng nghiên cứu đã đưa ra nhiều DHT
khác nhau. Mỗi DHT hoạt động theo nguyên lý chung và có ưu điểm riêng, Chord với
thiết kế đơn giản, Tapestry và Pastry giải quyết được vấn đề proximity routing, … Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14
P2P

Cl
ie
nt
/
S
er
ve
r
- Một mạng ngang hàng cho phép các
node (PCs) đóng góp, chia sẻ nguồn tài
nguyên với nhau. Tài nguyên riêng rẽ
của các node (ổ cứng, CD-ROM, máy
in …. Các nguồn tài nguyên này có thể
được truy cập từ bất cứ node nào trong
mạng.
- Các node đóng vai trò như cả Client (truy

- Mức độ an toàn cao nhất.
+ Nhƣợc điể
m:

- Chậm.
- Không tốt cho các ứng dụng CSDL.
- Kém tin cậy.
+ Nhƣợc
đ
iể
m:

- Cần server riêng (nghẽn cổ chai).
- Đắt.
- Phức tạp trong việc bảo trì, duy trì
hoạt động của mạng.
Bảng 1.1. So sánh ưu, nhược điểm của hệ thống P2P và Client/Server
1.1.3. Phân loại các mô hình mạng ngang hàng
Mạng ngang hàng có thể được phân loại theo mục đích sử dụng như: Chia sẻ file (file
sharing), Điện thoại VoIP (telephony), Đa phương tiện media streaming (audio, video),

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15
Diễn đàn thảo luận (Discussion forums)… Mạng ngang hàng cũng có thể được phân loại
theo mức độ tập trung của mạng (đối với P2P overlay networks). Hiện nay các hệ thống
mạng ngang hàng có thể được phân loại thành một số nhóm sau:

Bảng 1.2. Các mô hình P2P

máy chủ sẽ gửi trả lại địa chỉ IP của máy chứa tài nguyên trong mạng và quá trình truyền
file được thực hiện theo đúng cơ chế của mạng ngang hàng, giữa các host với nhau mà
không cần quan máy chủ trung tâm.

Ưu điểm:

- Dễ xây dựng.
- Tìm kiếm file nhanh và hiệu quả 
Nhược điểm:

- Vấn đề luật pháp, bản quyền.
- Dễ bị tấn công.
- Cần quản trị (central server).
Napster là mạng ngang hàng đặc trưng cho hệ thống mạng ngang hàng của thế hệ
thứ nhất, chúng được dùng cho việc chia sẻ các file giữa các người dùng Internet,
được sử dụng rộng rãi, tuy nhiên nhanh chóng bị mất thị trường bởi yếu tố về luật
pháp. Khái niệm và kiến trúc của Napster vẫn còn được sử dụng trong các ứng dụng
khác như: Audiogalaxy, WinMX.
Với Napster, việc tìm kiếm file bị thất bại khi bảng tìm kiếm trên máy chủ vì lý do
nào đó không thực hiện được. Chỉ có các file truy vấn và việc lưu trữ được phân tán, vì
vậy máy chủ đóng vai trò là một nút cổ chai. Khả năng tính toán và lưu trữ của máy

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17
chủ tìm kiếm phải tương xứng với số nút mạng trong hệ thống, do đó khả năng mở rộng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18
Gnutella 0.6 và JXTA (Juxtapose). JXTA được bắt đầu phát triển bởi SUN từ 2001
(Đây là giao thức P2P mã nguồn mở). JXTA được sử dụng cho PCs, mainframes, cell
phones, PDAs – để giao tiếp theo cách không tập trung. Skype cũng được xây dựng
dựa trên cấu trúc này.

Hình 1.6. Mô hình mạng ngang hàng lai (Hybrid)
Trong mô hình mạng ngang hàng lai tồn tại một trật tự phân cấp bằng việc định nghĩa
các Super Peers. Các SupperPeer tạo thành một mạng không cấu trúc, có sự khác
nhau giữa SupperPeers và ClientPeers trong mạng, mỗi SupperPeer có nhiều kết nối đến
các ClientPeers. Mỗi SupperPeer chứa một danh sách các file được cung cấp bởi các
ClientPeer và địa chỉ IP của chúng vì vậy nó có thể trả lời ngay lập tức các yêu cầu truy
vấn từ các ClientPeer gửi tới.  Ưu điểm:
- Hạn chế việc Flooding các query, làm giảm lưu lượng trong mạng, nhưng vẫn
tránh được hiện tượng nút cổ chai (do có nhiều SuperPeers).
- Khắc phục được nhược điểm về sự khác nhau về CPU power, bandwidth …, ở
mạng ngang hàng thuần túy, các SuperPeer sẽ chịu tải chính, các node khác chịu tải
nhẹ.
d) Mạng ngang hàng có cấu trúc (Structured)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19
20
- Vấn đề cân bằng tải trong mạng.
1.1.4. Các lĩnh vực ứng dụng của mạng ngang hàng
Sự ra đời của mạng ngang hàng đã tạo ra cách thức quản lý mới cho hàng loạt các
lĩnh vực ứng dụng. Phần này đưa ra một cách nhìn tổng quát cho vấn đề các lĩnh vực
ứng dụng của mạng ngang hàng như: giao tiếp (communication), chia sẻ file (file
sharing),
băng thông (bandwidth), vấn đề lưu trữ (storage), các chu trình xử lí (processor cycles).
a) Giao tiếp (communication)
- Đóng một vai trò quan trọng trong các ứng dụng mạng ngang hàng.
- Là nhân tố quyết định trong các mạng ngang hàng vì nó cung cấp thông tin về các
Peers và các nguồn tài nguyên nào là sẵn sàng trên mạng.
- Tạo ra khả năng cho các Peer kết nối trực tiếp với các Peer khác và yêu cầu
các nguồn tài nguyên.
- Một ví dụ điển hình về ứng dụng mạng ngang hàng trong giao tiếp là hệ thống
chuyển tin nhắn trực tiếp (instant messaging).
 Instant messaging:
- Thông thường, server trung tâm lưu trữ thông tin và danh sách người dùng đăng
k
í
.

- Khi có sự giao tiếp giữa các node, việc tìm kiếm người dùng (node khác) được
thực hiện trên server.
- Trong trường hợp người dùng không online, hệ thống sẽ phải lưu trữ các tin
nhắn cho đến khi người dùng này online.