BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

LUẬN VĂN THẠC SĨ KHOA HỌC

NGÔ HOÀNG GIANG
NGÀNH: CÔNG NGHỆ THÔNG TIN

CÔNG NGHỆ THÔNG TIN
ĐÁNH GIÁ HIỆU NĂNG CỦA MỘT SỐ
THUẬT TOÁN BẢNG BĂM PHÂN TÁN DHT
VÀ ĐƯA RA GIẢI PHÁP CẢI TIẾN HIỆU
NĂNG CỦA THUẬT TOÁN CHORD

NGÔ HOÀNG GIANG 2006 - 2008
Người hướng dẫn khoa học: TS. NGUYỄN CHẤN HÙNG
HÀ NỘI 2008
Luận văn tốt nghiệp Ngô Hoàng Giang
1
BỘ GIÁO DỤC ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
***

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. Nguyễn Chấn Hùng. Để 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ệp, những người luôn cổ vũ động viên tôi hoàn thiện bản luận văn này.
Hà Nội, ngày 28 tháng 10 năm 2008

Ngô Hoàng Giang

Luận văn tốt nghiệp Ngô Hoàng Giang
3
Mục lục
ULỜI CAM ĐOANU 1
ULỜI CẢM ƠNU 2
UMục lụcU 3
UDanh mục thuật ngữU 5
UDanh mục hình vẽU 6
UDanh mục thuật toánU 8
UDanh mục bảngU 9
ULời mở đầuU 10
UChương 1.U ULý thuyết tổng quanU 11
U1.1.U ULý thuyết chung về về mạng P2PU 11
U1.1.1.U UKhái niệm mạng P2PU 11
U1.1.2.U UQuá trình phát triển của các hệ thống P2PU 12
U1.1.3.U UỨng dụng p2pU 16

U3.4.2.U UCơ chế làm việcU 79
U3.5.U UGiải pháp dùng nhân bản đối xứng cải tiếnU 87
U3.5.1.U UMục tiêuU 87
U3.5.2.U UCơ chế làm việcU 87
UKết luậnU 92
UTài liệu tham khảoU 93
Luận văn tốt nghiệp Ngô Hoàng Giang
5
Danh mục thuật ngữ
Tiếng Anh Tiếng Việt
Peer-to-peer Mạng ngang hàng
Peer Đồng đẳng trong mạng ngang hàng
Node Một thiết bị nối mạng (một peer)
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
Distributed hash table Bảng băm phân tán
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.


theo băng thông trung bình một node sử dụng (average live bandwidth) trong mạng
Kademlia 100 node (trái) và 1000 node (phải).
U 49
UHình 2.4. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công theo băng thông trung bình một
node sử dụng trong mạng Chord 100 node (trái) và 1000 node (phải).
U 50
UHình 2.5. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công theo băng thông trung bình một
node sử dụng trong mạng Kelips 100 node (trái) và 1000 node (phải).
U 51
Luận văn tốt nghiệp Ngô Hoàng Giang
7
UHình 2.6. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công theo băng thông trung bình một
node sử dụng trong mạng Tapestry 100 node (trái) và 1000 node (phải).
U 52
UHình 2.7. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công theo băng thông trung bình một
node sử dụng trong mạng Chord với interval=5s (trái) và interval=10s (phải).
U 55
UHình 2.8. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công theo băng thông trung bình một
node sử dụng của Kelisp và Tapestry với RTT=1s, 10s và node join/leave với
interval=5s (trái) và 10s (phải).
U 56
UHình 2.9. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công theo băng thông trung bình một
node sử dụng trong mạng Chord 1000 node với interval=120s (trái) và interval=600s
(phải).
U 59
UHình 2.10. Tác động của churn rate đối với tỷ lệ tìm kiếm thất bại (hình trên) và độ trễ
tìm kiếm trung bình (hình dưới) trong các mạng có kích thước khác nhau.
U 60
UHình 2.11. Đồ thị biểu diễn tỷ lệ tìm kiếm thành công (hình trên) và độ trễ tìm kiếm
trung bình (hình dưới) theo băng thông trung bình một node sử dụng trong các mạng có

UThuật toán 3.9. Xử lý failure trong nhân bản đối xứngU 90
UThuật toán 3.10. Thuật toán bulk owner operationU 91
Luận văn tốt nghiệp Ngô Hoàng Giang
9
Danh mục bảng
UBảng 1.1. Trạng thái phát triển của các simulatorU 41
UBảng 1.2. Đặc điểm của các simulatorU 42
UBảng 2.1. Bảng tham số của KademliaU 49
UBảng 2.2. Bảng tham số của ChordU 50
UBảng 2.3. Bảng tham số của KelipsU 51
UBảng 2.4. Bảng tham số của TapestryU 52
UBảng 2.5. Giá trị churn rate để các DHT đạt được tỷ lệ tìm kiếm thành công 90% trong
mạng 100 và 1000 node
U 53
UBảng 2.6. Điều kiện mô phỏngU 54
UBảng 2.7. Giá trị tham số của ChordU 54
UBảng 2.8. Giá trị tham số của TapestryU 54
UBảng 2.9. Giá trị tham số của KelipsU 55

Đánh giá và cải thiện hiệu năng của các DHT 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 phân tích, đánh giá hiệu năng của một số DHT nổi
tiếng như Chord, Kademlia, Tapestry, Kelips trong điều kiện mạng churn rate cao. Dựa
trên kết quả đạt được, luận văn phân tích hạn chế của giao thức Chord và đưa ra giải
pháp cải tiến hiệu năng của giao thức này trong điều kiện churn rate cao.
Các kết quả nghiên cứu trong luận văn đã được công bố
trên một số bài báo
quốc tế và trong nước [15, 16, 17, 18]. Luận văn tốt nghiệp Ngô Hoàng Giang
11
Chương 1. 0BLý thuyết tổng quan
1.1. Lý thuyết chung về về mạng P2P
1.1.1. Khái niệm mạng P2P
Trong khoảng 10 năm trở lại đây, lĩnh vực P2P nhận được sự quan tâm của rất
nhiều nhóm nghiên cứu, của các công ty, trường đại học và đã có những bước phát
triển mạnh mẽ. Ngày nay các ứng dụng peer-to-peer được sử dụng rộng rãi cho nhiều
mục đích khác nhau như chia sẻ tài nguyên và nội dung, chat, chơi game, …
Cũng giống như các xu hướng đang trong quá trình phát triển khác, hiện nay
chưa có một định nghĩ
a chính xác về mạng P2P. Dưới đây là một số định nghĩa về P2P:
Theo Oram, P2P là một lớp các ứng dụng tận dụng các tài nguyên như bộ nhớ,
năng lực xử lý, nội dung, … tại các điểm cuối trong mạng Internet. Bởi vì truy cập vào
các tài nguyên phân tán này cũng có nghĩa là hoạt động trong một môi trường liên kết
không ổn định và với địa chỉ IP có thể thay đổi, các node P2P phải hoạt động ngoài hệ
thống DNS và có quyền tự trị cao hoặc hoàn toàn tự trị.

trò như nhau, một số peer có vai trò lớn hơn và được gọi là các server.
XHình 1.1X cho thấy một ví dụ về mô hình centralized directory. Trong mô hình
này, các peer muốn chia sẻ file với các peer khác sẽ thông báo với server về các file
này. Khi một peer muốn tìm một file nào đó, nó sẽ gửi yêu cầu đến server, dựa trên các
thông tin đã thu thập được, server sẽ tìm ra các peer chứa file đó và trả kết quả tìm
kiếm cho peer yêu cầu. Kết quả trả về là peer phù hợp dựa trên một số thông số như tốc
độ kết nối, kích thước file, …. Sau khi nhận được kế
t quả, peer tìm kiếm sẽ trao đổi file
trực tiếp với peer chứa file mà không thông qua server nữa. Luận văn tốt nghiệp Ngô Hoàng Giang
13

Hình 1.1. 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ô
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

điều khiển tập trung. Nỗ lực giải quyết bài toán này là sự xuất hiện của “structured P2P
overlay networks”.
Thế hệ thứ ba được khởi đầu với các dự án nghiên cứu như Chord, CAN, Pastry,
Tapestry và P-Grid. Các dự án này đưa ra khái niệm Distributed Hash
Table (DHT). Mỗi peer trong hệ thống có một ID thu được từ việc băm các đặc thuộc
tính đặc trưng của peer đó như địa chỉ IP hay public key. Mỗi data item cũng có một ID
thu được theo cách tương tự với các peer. Hash table lưu data dưới dạng cặp key-value.
Như vậy, node ID và cặp key-value được băm vào cùng một không gian ID. Các node
sau đó được nối với nhau theo một topology nào đó. Quá trình tìm kiếm dữ liệu trở
thành quá trình định tuyến với kích thước bảng định tuyến nhỏ và chiều dài đường đi
cực đại. Thế hệ thứ ba đảm bảo xác xuất tìm thấy thông tin cao.
Các DHT được xây dựng nhằm mục đích cho phép các peer hoạ
t động như một
cấu trúc dữ liệu phân tán với hai hàm chính Put(key,value) và Get(Key). Hàm Put lưu
dữ liệu tại một peer nào đó sao cho bất kỳ peer nào cũng có thể tìm được bằng hàm Get.
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 DHT đả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, …
Luận văn tốt nghiệp Ngô Hoàng Giang
16
1.1.3. Ứng dụng p2p
Các ứng dụng p2p có thể chia vào bốn nhóm:
Chia sẻ file (file sharing): lưu trữ và chia sẻ nội dung là ứng dụng thành công
nhất của công nghệ p2p. Các ứng dụng chia sẻ file tập trung vào việc lưu trữ thông tin
trên các peer khác nhau trên mạng và lấy thông tin từ các peer đó. Các ứng dụng thuộc
nhóm này bao gồm Napster, Gnutella, Freenet, Kazaa, Chord, ….

tác và xử lý phân tán trong các hệ thống p2p.
Tính tin cậy (reliability): một hệ thống tin cậy là một hệ thống có khả năng hồi
phục sau khi xuất hiện lỗi. Các cơ chế đảm bảo
độ tin cậy trong mạng p2p bao gồm
nhân bản dữ liệu, phát hiện và khôi phục node bị lỗi, xây dựng nhiều cơ chế đảm bảo
thông tin định vị, tránh “single point of failure” và đảm bảo nhiều đường đi tới dữ liệu.
Tính linh hoạt (flexibility): một trong những tính chất quan trọng nhất trong các
hệ thống p2p là các peer tự chủ, chúng có thể join/leave bất kỳ lúc nào. Các hệ thống
p2p gần đây có quy mô lớn, điều khiể
n phân tán và hoạt động trong môi trường động.
Để giải quyết vấn đề quy mô và tính động của các hệ thống p2p, khi xây dựng các hệ
thống p2p cần chú ý đến khả năng điều chỉnh và tự tổ chức.
Cân bằng tải (load balancing) : vấn đề phân tán dữ liệu và tính toán rất quan
trọng đối với hiệu quả hoạt động của các mạng p2p. Một trong những giải pháp cho
vấn đề phân tán này là distributed hash table (DHT). Trong cách tiế
p cận này, cân bằng
tải được xem xét trên hai khía cạnh: cân bằng không gian địa chỉ tức là cân bằng phân
phối của không gian key address trên các node và cân bằng item trong trường hợp phân
phối của các item trong không gian địa chỉ không thể là ngẫu nhiên. Cân bằng tải giữa
các node tính toán trong hệ thống p2p cũng có thể được cài đặt sử dụng mô hình tự tổ
chức dựa trên agent.
Luận văn tốt nghiệp Ngô Hoàng Giang
18
1.2. Lý thuyết về Distributed Hash Table (DHT)
1.2.1. Hash Table (bảng băm)
Một hash table là một cấu trúc dữ liệu ánh xạ giữa key và value. Tức là tương
ứng với một key, hash table sẽ trả về một value. Để thực hiện việc ánh xạ, hash table
sử dụng hash function tính toán vị trí lưu value dựa trên key. Hash function phải đảm
bảo: tránh xung đột và dễ dàng thực hiện. Tránh xung đột nghĩa là ánh xạ giữa không
gian key và không gian địa chỉ phải đều và ngẫu nhiên đến mức có thể.

Server truyền thống:
− DHT cho phép hoạt động phân tán, không cần duy trì một server trung tâm để
điều khiển hoạt động của mạng p2p. Cũng vì vậy, các ứng dụ
ng p2p sử dụng
DHT là các ứng dụng p2p thuần túy.
− Hệ thống có tính khả mở, nghĩa là hệ thống vẫn hoạt động tốt ngay cả với số
lượng node và lưu lượng trên mạng lớn.
− Tải được cân bằng giữa các peer trong mạng
− Hệ thống dựa trên giả định rằng mạng không tĩnh và các thay đổi xuất hiện
thường xuyên với các node join vào mạng và leave khỏi m
ạng (còn gọi là churn)
− Việc định tuyến và lấy dữ liệu nhanh và có thể hoàn thành trong thời gian tỷ lệ
loga
− Hệ thống mạnh mẽ, nghĩa là nó có thể đứng vững ngay cả khi bị tấn công trên
diện rộng

DHT cung cấp dịch vụ lưu trữ, tìm kiếm dữ liệu thông qua hai hàm insert và lookup.
Luận văn tốt nghiệp Ngô Hoàng Giang
20

Hình 1.3. Distributed Hash Table
1.3. Giới thiệu một số DHT
Trong phần này chúng ta sẽ xem xét một số well-known DHT như Chord, Kelips,
Tapestry, Kademlia. Ta phân tích các DHT này dựa trên một số khía cạnh như sau:
Overlay Graph (sơ đồ mạng overlay): đây là tiêu chuẩn chính để phân biệt các hệ
thống với nhau. Đối với mỗi overlay graph, chúng ta sẽ xem xét graph và bảng định
tuyến của mỗi node trong graph.
Mapping Items Onto Nodes (ánh xạ giữa item và node): đối với mỗi overlay
graph, chúng ta quan tâm đến mối quan hệ giữa ID của node và ID của các item lưu
trên node đó, tức là một item cụ thể

M. Với cách lựa chọn finger thế này, tong mạng Chord, các node quan sát không gian
ID vòng như là không gian này b
ắt đầu từ ID của chúng. Đồng thời với cách lựa chọn
finger của Chord, không gian ID sẽ được chia đôi, nửa thứ nhất cũng được chia đôi, rồi
phần tư thứ nhất lại được chia đôi, …

XHình 1.4X cho thấy một mạng với không gian ID N = 16, mỗi node có
M=log
2
(N)= 4 finger. Mạng có các node với ID lần lượt là 0, 3, 5, 9, 11, 12. Cách xây
Luận văn tốt nghiệp Ngô Hoàng Giang
22
dựng bảng finger table được thể hiện trong XHình 1.4X(b) . Node n chọn các finger của nó
bằng cách xem nó như là điểm khởi đầu của không gian ID, rồi chọn finger là
successor của các ID n + 2
0
, n + 2
1
, n + 2
2
, và n + 2
3
. ID cuối cùng n + 2
3
chia không
gian ID thành hai phần bằng nhau, ID trước đó n + 2
2
chia nửa thứ nhất thành hai phần
bằng nhau, ID n + 2
1