1

ĐẠI

HỌ
C
QUỐ
C
GIA

HÀ

NỘI

TRƯỜNG

ĐẠI

HỌC

CÔNG

NGHỆ
ĐỖ CAO MINH
2
Hà Nội - 2010MỤC LỤC……………………………………………………………………. …… 1
DANH MỤC THUẬT NGỮ………………………………………………….…… 3
DANH MỤC HÌNH VẼ…………………………………………………… …… 4
MỞ ĐẦU …………… …………………………….……………………….…………6

CHƯƠNG 1 - TỔNG QUAN VỀ MẠNG NGANG HÀNG……………………… 9
1.1 Tổng quan về mạng ngang hàng 9
1.1.1 Khái niệm về mạng ngang hàng 9
1.1.2 Ưu điểm của mạng ngang hàng 10
1.1.3 Nhược điểm của mạng ngang hàng 11
1.2 Phân loại mạng ngang hàng 11
1.2.1 Phân loại theo mức độ tập trung của các node mạng 11
1.2.2 Phân loại theo cấu trúc liên kết 13
1.3 Mạng ngang hàng có cấu trúc dựa trên DHT(Distributed Hash Table)
………………………………….……………………………………………….15
1.3.1 Giới thiệu DHT 15
1.3.2 Mạng chord 17
a. Mô hình mạng Chord 17
b. Ánh xạ khóa vào một node trong Chord 19
c. Tìm kiếm trong mạng Chord 19

3.1 Một số khái niệm 41
3.2 Thuật toán ThresholdPlus 41
3.3 Đánh giá: 46

CHƯƠNG 4 - ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI PHÁP ĐỀ XUẤT DỰA TRÊN
MÔ PHỎNG ………………………………………………… ………………… 48
4.1 Ảnh hưởng thời gian sống của một node tới các thuật toán cân bằng tải….48
4.2 Ảnh hưởng của số lượng các câu truy vấn tới các thuật toán cân bằng tải 49
4.3 Ảnh hưởng của câu truy vấn dạng Zipf tới các thuật toán cân bằng tải …50
4.4 So sánh kết quả thực nghiệm của thuật toán Threshol Plus với các thuật
toán đã có: 51
4.5 Kết luận 52

CHƯƠNG 5 - KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN………………… 54
5.1 Kết luận 54
5.2 Hướng phát triển tiếp theo 54

4

Partial query Truy vấn từng phần
Predecessor(n) Node đứng liền sau n (Tính theo chiều kim
đồng hồ)
Query Truy vấn
Successor(n) Node đứng liền trước n (Tính theo chiều
kim đồng hồ)
Target Tải lớn nhất mà một node có thể nhận
Unilization Hệ số sử dụng
Workload Tải làm việc 5

DANH MỤC HÌNH VẼ

Hình 1. Mô hình mạng ngang hàng 9
Hình 2. Mô hình mạng ngang hàng thuần tuý 12
Hình 3. Hệ thống mạng ngang hàng lai ghép 13
Hình 4. Tìm kiếm dữ liệu chia sẻ trong Gnutella 14
Hình 5. Một mạng Chord với 3 node 0, 1, 3 và các bảng Finger Table ứng với mỗi
node. N = 3 bit nên có 3 entry 18
Hình 6. Lưu giữ key trong mạng Chord: node 0 lưu key 6, node 1 lưu key 1 và node 3
lưu key 2 19
Hình 7. Định danh các node không cân bằng 24

Hình 24. Node A thực hiện cân bằng tải, node A chia tải cho node láng giềng B bằng
cách dịch chuyển định danh của A về phía B. 44
Hình 25. Node A hỏi thư mục 1 để tìm một node nhẹ tải có thể dịch chuyển được
(đường mũi tên nét liên). Định danh của node nhẹ tải E được chuyển đến giữa
predecessor(A) và A để nhận tải hộ node A (đường mũi tên nét đứt). 45
Hình 26. Thời gian sống trung bình của một node thay đổi, các câu truy vấn thực hiện
với phân bố Zipf và Uniform. 49
Hình 27. Số câu truy vấn đặt vào một node thay đổi, truy vấn được phân bố ở dạng
Zipf và Uniform 50
Hình 28. Truy vấn đặt vào các node ở dạng phân bố Zipf với tỷ lệ thay đổi. 51
Hình 29. So sánh ThresholdPlus với Tranfer và Propotion. 52


node trong mạng.
Nội dung luận văn gồm 5 chương cụ thể cho từng chương như sau:
Chương 1: Giới thiệu tổng quan về mạng ngang hàng, những khái niệm cơ
bản về mạng ngang hàng đồng thời giới thiệu giao thức Chord, giao thức được
sử dụng để triển khai mạng phủ DHT khi xây dựng chương trình mô phỏng.
Chương 2: Tìm hiểu về vấn đề cân bằng tải trên mạng ngang hàng, một số
nguyên nhân dẫn đến mất cân bằng tải, các giải pháp đã được đề xuất và phân
tích về các giải pháp này. 8

Chương 3: Trên cơ sở các vấn đề tìm hiểu được ở chương 2. Chúng tôi đề
xuất giải pháp cân bằng trên mạng ngang hàng có cấu trúc theo hướng không sử
dụng server ảo. Đó là một giải thuật cải tiến của giải thuật cân bằng tải theo
ngưỡng.
Chương 4: Trình bày cách thực hiện chương trình mô phỏng đồng thời
trình bày kết quả đánh giá giải thuật cân bằng tải dựa trên mô phỏng của chúng
tôi.
Chương 5: Trình bày các công việc mà chúng tôi đã thực hiện được,
những vấn đề còn tồn tại của luận văn và hướng phát triển tiếp theo của chúng
tôi.
1.1.1 Khái niệm về mạng ngang hàng
Mạng ngang hàng là một mạng mà kiến trúc của nó được tạo nên bởi các
máy tính liên kết với nhau, các máy tính tham gia trong mạng đều bình đẳng như
nhau và được gọi là các peer, mỗi máy tính tham gia mạng là một phần và duy
trì sự tồn tại của mạng. Các máy tính trong mạng thường xuyên liên lạc với các
máy tính khác để ổn định mạng và chia sẻ dữ liệu với nhau. Dữ liệu được chứa
trên các máy tính và được chia sẻ trực tiếp với nhau giữa các máy tính tham gia
vào mạng.

Hình 1. Mô hình mạng ngang hàng 10

Ứng dụng thường xuyên gặp nhất của mạng ngang hàng là chia sẻ tệp tin,
tất cả các dạng như: âm thanh, hình ảnh, dữ liệu hoặc để truyền dữ liệu thời
gian thực… . Việc sử dụng mạng ngang hàng mang lại nhiều ưu điểm cho người
dùng . Luận văn xin trình bày một số ưu điểm của mạng ngang hàng.
1.1.2 Ưu điểm của mạng ngang hàng
Mục đích quan trọng của mạng ngang hàng là các máy tính tham gia mạng
đều đóng góp tài nguyên bao gồm băng thông, lưu trữ, khả năng tính toán. Do
đó khi càng nhiều mày tính tham gia mạng thì khả năng tổng thể của mạng càng
lớn. Do việc các thông tin lưu trữ không chỉ trên máy chủ mà còn được lưu trữ ở
chính các máy tham gia mạng nên mô hình này rất phù hợp với tính phi tập
trung của Internet.
Xét về khía cạnh sức mạnh xử lý, mạng ngang hàng có khả năng xử lý
cao hơn cả những máy chủ lớn hiện nay, do đó sử dụng mạng ngang hàng có thể
cải thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu và giải
các bài toán phức tạp. Sở dĩ làm được như vậy là vì mạng ngang hàng có thể tận
dụng được khả năng xử lý, khả năng lưu trữ còn thừa của các máy tham gia

1.2 Phân loại mạng ngang hàng
Mạng ngang hàng có nhiều tiêu trí phân loại khác nhau, trong luận văn
này xin được trình bày hai tiêu trí phân loại mạng ngang hàng đó là: Phân loại
theo mức độ tập trung của các node mạng và phân loại theo cấu trúc liên kết của
các node.
1.2.1 Phân loại theo mức độ tập trung của các node mạng
Nếu lấy tiêu chí về mức độ tập trung của các node mạng, mạng ngang
hàng có thể phân làm 2 loại: mạng ngang hàng thuần tuý và mạng ngang hàng
lai
a. Mạng ngang hàng thuần tuý
Trong mạng ngang hàng thuần tuý thì vai trò của các máy trong mạng là
ngang nhau và trong mô hình mạng này đã loại bỏ sự tồn tại của các máy chủ
tập trung. Trong mạng này đã khắc phục được vấn đề node nghẽn cổ chai trong
mô hình tập trung. Tuy nhiên vấn đề tìm kiếm trong mạng ngang hàng thuần tuý
sử dụng cơ chế phát tràn (Flooding), yêu cầu tìm kiếm được gửi tới tất cả các
node mạng là láng giềng với nó, điều này làm tăng đáng kể lưu lượng trong
mạng. 12Hình 2. Mô hình mạng ngang hàng thuần tuý
b. Mạng ngang hàng lai ghép
Trong mô hình này, các peer lưu giữ nội dung chia sẻ với các node khác ở
trên mạng. Tất cả các peer đều kết nối tới một server, server này lưu giữ thông
tin về:
- Bảng thông tin kết nối của người dùng đăng kí (địa chỉ IP, băng thông
kết nối…)
- Bảng liệt kê danh sách các file mà các peer nắm giữ và chia sẻ ở trên

trên nhiều máy thì tỉ lệ thành công là khá cao, ngược lại nếu dữ liệu chỉ được 14

chia sẻ trong một vài máy thì xác suất tìm thấy là rất nhỏ. Tính chất này là hiển
nhiên trong mạng ngang hàng không có cấu trúc vì không có bất kỳ mối tương
quan nào giữa một máy và dữ liệu của nó quản lý trong mạng, do vậy yêu cầu
tìm kiếm được chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số
máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Do khi
muốn tìm kiếm trên mạng ngang hàng không có cấu trúc, yêu cầu tìm kiếm được
phát trên toàn mạng nên không có cấu trúc định hướng, một yêu cầu thường
chuyển cho số lượng lớn các máy tính trong mạng làm tiêu tốn băng thông, dẫn
đến hiệu quả tìm kiếm thấp.
Một mô hình mạng ngang hàng không cấu trúc điển hình đó là mạng
Gnutella. Các máy tính trong Gnutella được mô tả như là những “servent”, các
thành viên trong mạng và được chia sẻ file. Các máy tính khác có thể lấy được
những file chia sẻ này. Việc tìm kiếm file trên mạng mô tả trong hình 4, khi một
máy tính A tìm kiếm file X, nó sẽ gửi một truy vấn broadcast tới tất cả các máy
tính nó biết, được coi là hàng xóm của nó. Truy vấn sau đó sẽ được chuyển dần
qua các bước và tới được máy tính có chứa file X. Gnutella có mã nguồn mở và
có giao thức mô tả rõ ràng trên mạng Internet, bất cứ ai quan tâm cũng có thế
tìm hiểu và phát triển để tạo ra một mạng ngang hàng của riêng mình với các
tính năng muốn có.

Hình 4. Tìm kiếm dữ liệu chia sẻ trong Gnutella 15


những mạng tương tự chuyển sang sử dụng mô hình phát tràn các thông điệp
truy vấn (flooding query model), mỗi truy vấn được đưa ra tương ứng với việc
một thông điệp được broadcast tới tất cả các node có trong mạng. Vì vậy, mặc 16

dù tránh được điểm yếu của thành phần trung tâm như trên, thì phương pháp này
lại kém hiệu quả hơn so với Napster. Cuối cùng, Freenet thực sự là phân tán, nó
sử dụng cơ chế routing dựa trên khóa, mỗi file được gán một khóa, các khóa gần
giống nhau sẽ cùng được lưu ở một tập các node. Các truy vấn sẽ được định
tuyến đi trong mạng mà không phải ghé thăm tất cả các node có trên mạng. Tuy
nhiên, Freenet không đảm bảo dữ liệu sẽ được tìm thấy.
DHT sử dụng cơ chế định tuyến dựa trên khóa trên một kiến trúc mạng chặt
chẽ hơn để có thể đạt được cả tính phân tán về tài nguyên của Gnutella và
Freenet, tính hiệu quả về truy vấn của Napster. Có một hạn chế là DHT chỉ hỗ
trợ tìm kiếm chính xác chứ không hỗ trợ tìm kiếm theo từ khóa, hay tìm kiếm
theo khoảng, tuy nhiên các chức năng này có thể triển khai mở rộng trên nền
DHT.
Distributed hash tables (DHTs) là hệ thống mạng phân tán, cung cấp các
dịch vụ tìm kiếm dựa vào bảng băm. Bảng băm là một cặp ( tên, giá trị). Mỗi
một node khi tham gia vào mạng có thể dễ dàng tìm thấy giá trị mong muốn dựa
vào tên của giá trị đó. Việc hình thành tên (khóa) và gắn các khóa đó với giá trị
tương ứng được thực hiện trực tiếp tại các node trong mạng, chính vì vậy khả
năng sập mạng được giảm tối thiểu khi các node tham gia hoặc dời bỏ mạng.
Chính lý do này khiến khả năng mở rộng của mạng DHT là cực lớn, quá trình
kiểm soát việc tham gia, dời bỏ mạng của các node cũng trở nên dễ dàng hơn.
Với cấu trúc vững mạnh, DHT được sử dụng để xây dựng nhiều ứng dụng
phức tạp như: Hệ thống các file phân tán, hệ thống chia sẻ file ngang hàng, hệ
thống nội dung phân tán, tin nhắn tức thời, Multicast… Các mạng DHT nổi

kiến trúc Ring đều được đánh giá cao. Vì vậy, kiến trúc Chord[1] thường hay
được sử dụng như là mạng phủ để thực hiện các cài đặt cải tiến việc các ứng
dụng, xử lý trên P2P có cấu trúc.
a. Mô hình mạng Chord
Chord[1] được mô tả dưới dạng một vòng tròn và không gian định danh
phân bố đều trên vòng tròn tăng dần theo chiều kim đồng hồ. Nếu gọi N là số bit
định danh của không gian thì mạng Chord có thể chứa tối đa 2
N
node. Mỗi node
trên Chord có một định danh id và duy trì liên kết 2 chiều với node đứng liền
trước và liền sau nó theo chiều kim đồng hồ tạo thành một mạch liên kết vòng.
Node liền trước được gọi là Successor(id), và node liền sau được gọi là
Predecessor(id). Thêm vào đó, một node sẽ lưu một bảng định tuyến gọi là
Finger Table, cho phép node đó định tuyến tới các node ở xa. Mỗi dòng trong
bảng Finger Table sẽ lưu thông tin về 1 node ở xa, gọi là 1 entry. Không gian
định danh có bao nhiêu bit thì Finger Table có bấy nhiêu entry. 18Hình 5. Một mạng Chord với 3 node 0, 1, 3 và các bảng Finger Table ứng với
mỗi node. N = 3 bit nên có 3 entry
Các trường trong mỗi entry trong bảng Finger Table được định nghĩa trong
bảng dưới:
Notation Definition
Finger[k].start
(n+2
k-1
) mod 2

được gọi là Successor của k, ký hiệu là Successor(k).

Hình 6. Lưu giữ key trong mạng Chord: node 0 lưu key 6, node 1 lưu key 1 và
node 3 lưu key 2.
c. Tìm kiếm trong mạng Chord
Khi một node n cần tìm kiếm một khóa có định danh id, node n sẽ tìm node
chịu trách nhiệm lưu giữ id đó. Nếu node n ở xa so với vị trí của node lưu giữ id,
n có thể nhờ vào thông tin trong bảng Finger Table để định tuyến đến các node
xa hơn, từ đó dần dần tìm ra node chịu trách nhiệm lưu giữ id. 20

Một ví dụ được chỉ trong hình 8, giả sử node 3 muốn tìm successor của ID
= 1 (hoặc còn có thể coi là khóa). ID =1 thuộc khoảng [7, 3). Node 3 kiểm tra
entry thứ 3 trong bảng định tuyến của nó, là 0. Bởi vì 0 nằm ngay trước 1 trên
vòng tròn, node 3 sẽ hỏi node 0 để tìm successor của 1. Tiếp theo, node 0 sẽ tìm
trong bảng định tuyến của nó và suy ra successor của 1 chính là node 1, và trả
lời node 3 rằng node 1 chính là successor của khóa ID = 1.
d. Tham gia và ổn định mạng
Trong 1 mạng động, thường xuyên có sự thay đổi với các node tham gia và
rời khỏi bất kì lúc nào. Để có thể xác định được vị trí của các khóa ở trong
mạng, Chord cần thỏa mãn 2 điểm sau:
 Mỗi successor của một node phải được duy trì đúng
 Với mỗi khóa k, node successor(k) có trách nhiệm quản lý k
Khi tham gia vào một mạng Chord, một node n cần chọn cho nó một định
danh id và báo cho các node bên cạnh biết sự tham gia của nó. Các node
Successor và Predecessor sẽ cần phải cập nhật thông tin về node mới tham gia
vào mạng. Node n cũng khởi tạo bảng định tuyến Finger Table. Để mạng vẫn
định tuyến đúng sau khi có sự tham gia của node n, các node cần thường xuyên

22

CHƯƠNG 2 - CÂN BẰNG TẢI TRÊN MẠNG NGANG HÀNG CÓ CẤU
TRÚC
Cân bằng tải là một trong những điều kiện để giúp cho mạng có thể hoạt
động một cách có hiệu quả. Có rất nhiều các nguyên nhân dẫn đến mất cân bằng
tải và đã có một số nghiên cứu và đã có các giải pháp cho vấn đề cân bằng tải.
Trong chương này xin trình bày các nghiên cứu về một số nguyên nhân dẫn đến
mất cân bằng tải và một số giải pháp cân bằng tải đã được công bố.
2.1 Khái niệm về tải trên mạng ngang hàng
2.1.1 Khái niệm
Mục đích chính của các hệ thống P2P là chia sẻ tài nguyên sẵn có

l



Khi µ
i
> 1, node n bị “nặng tải”, ngược lại node n được coi là “nhẹ
tải”.



n nodes
n
n nodes
n
c
l


µ – Hệ số sử dụng của hệ thống (system utilization). 23

2.1.2 Node quá tải
Khả năng tải của một node (C,Target): Là tải lớn nhất mà một node có thể
nhận được.
Với mỗi nút n
i
mà tải thực tế tại thời điểm bất kỳ vượt quá khả năng chịu tải

tham gia hệ thống cũng được coi là có khả năng như nhau về băng thông, lưu
trữ, xử lý của CPU… Trong thực tế lại có một sự khác biệt lớn về tải giữa các
nút hay còn gọi là sự mất cân bằng tải. Có thể có nhiều nguyên nhân dẫn tới việc
mất cân bằng tải trên mạng ngang hàng, ở đây luận văn xin đưa ra bốn nguyên
nhân chính dẫn đến mất cân bằng tải.
2.2.1 Định danh các node không cân bằng
Do định danh được chọn một cách ngẫu nhiên nên mỗi nút phải chịu quản
lý một vùng với số lượng files dữ liệu được gán khác nhau (Thông thường các
vùng lớn hơn sẽ được gán số lượng files dữ liệu nhiều hơn). Trong những hệ
thống lớn với giải thuật sinh ra ID cho các nút mà không có tình trạng sung đột 24

- node

- data
thì sự khác nhau về kích cỡ của vùng nhỏ nhất và lớn nhất có thể lên tới
O(NlogN).

Hình 7. Định danh các node không cân bằng
2.2.2 Định danh dữ liệu không cân bằng
Giả sử vấn đề định danh node đã được giải quyết, nếu dữ liệu được phân bố
quá tập trung vào một vùng thì cũng sẽ gây tình trạng “nặng tải” tại khu vực đó.
Nói cách khác, vị trí đặt files cũng có thể gây ảnh hưởng lớn tới hiệu năng của
hệ thống.

Hình 8. Dữ liệu các node không cân bằng
Kết quả mô phỏng hệ thống DHT Chord ở hình 9 với 4,096 node và
khoảng 500,000 files dữ liệu cho thấy không có sự phân bố tối ưu dữ liệu trên