ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

Ngô Văn Chí

BẢNG BĂM PHÂN TÁN
VÀ ĐỊNH TUYẾN TRÊN MẠNG NGANG HÀNG

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

Chuyên ngành: Cơ sở toán học cho tin học
Mã số ngành: 60 46 01 10

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Lê Trọng Vĩnh

Hà Nội – 2015


Mục lục

Danh sách hình vẽ

iii

Danh sách bảng

v

Lời mở đầu

1

1 Tổng quan về mạng ngang hàng

4

1.1

Giới thiệu về mạng ngang hàng . . . . . . . . . . . . . . . . . . . .

4

1.2

Sự tiến hóa của cấu trúc mạng . . . . . . . . . . . . . . . . . . . .

5

1.2.1

Kiến trúc khách–chủ . . . . . . . . . . . . . . . . . . . . . .

5

1.2.2

Kiến trúc lưới . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.2.3


Kiến trúc ngang hàng . . . . . . . . . . . . . . . . . . . . .

6

1.3

Phân loại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.4

Tìm kiếm trên mạng ngang hàng . . . . . . . . . . . . . . . . . . .

9

1.5

Ưu và nhược điểm của mạng ngang hàng . . . . . . . . . . . . . . 11
1.5.1

Ưu điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5.2

Nhược điểm . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.6


Một số vấn đề trong mạng ngang hàng . . . . . . . . . . . . . . . . 13

1.7

Một số phương pháp định tuyến trên P2P . . . . . . . . . . . . . . 16
1.7.1

Mạng tập trung hoặc được cấu hình tĩnh . . . . . . . . . . 17

1.7.2

Mạng ngang hàng trên mạng chồng lấn . . . . . . . . . . . 18

i


2 Bảng băm phân tán
2.1

2.2

2.3

21

Bảng băm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1

Bảng địa chỉ trực tiếp . . . . . . . . . . . . . . . . . . . . . 21


2.1.2

Bảng băm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Băm ổn định . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.1

Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2.2

Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2.3

Xây dựng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2.4

Các tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Bảng băm phân tán . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1

Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.3.2

Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37


2.3.3

Tính chất của DHT . . . . . . . . . . . . . . . . . . . . . . . 38

2.3.4

Cấu trúc của DHT . . . . . . . . . . . . . . . . . . . . . . . 40

2.3.5

Các cơ chế của DHT . . . . . . . . . . . . . . . . . . . . . . 40

2.3.6

Các giao diện DHT . . . . . . . . . . . . . . . . . . . . . . . 42

2.3.7

Nhận xét . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3 Định tuyến trên mạng ngang hàng

45

3.1

Định tuyến trên P2P có sử dụng DHT . . . . . . . . . . . . . . . . 45

3.2


Thuật toán CAN và Chord . . . . . . . . . . . . . . . . . . . . . . 46
3.2.1

Thuật toán CAN . . . . . . . . . . . . . . . . . . . . . . . . 46

3.2.2

Thuật toán Chord

3.2.3

So sánh khả năng định tuyến giữa thuật toán CAN và

. . . . . . . . . . . . . . . . . . . . . . . 52

Chord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Kết luận

60

Tài liệu tham khảo

65

ii


Danh sách hình vẽ
1.1


Kiến trúc khách – chủ . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2

Mô hình máy chủ trung tâm . . . . . . . . . . . . . . . . . . . . . . 17

1.3

Phương pháp làm ngập trên mạng chồng lấn . . . . . . . . . . . . 19

1.4

Mô hình mạng siêu ngang hàng . . . . . . . . . . . . . . . . . . . . 19

2.1

Bảng địa chỉ trực tiếp . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2

Bảng băm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3

Một ví dụ về phương pháp bảng băm mở . . . . . . . . . . . . . . 25

2.4


Một ví dụ về phương pháp thử tuyến tính . . . . . . . . . . . . . . 26

2.5

Một ví dụ về hệ thống phân phối thông qua các máy chủ cache . 29

2.6

Hệ thống phân phối thông qua các máy chủ cache với một nút lỗi

2.7

Khoảng đơn vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.8

Một DHT đơn giản . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.9

Tra cứu khóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.1

Mạng CAN 2–chiều với 6 nút. Mỗi nút được gán cho một zone

30

và các nút được phân biệt bởi biên của mỗi zone tương ứng . . . 47
3.2


Định tuyến đến nút có khoá k(x, y) trong không gian 2–chiều. . . 48

3.3

Nút mới N7 đến zone của N1. N1 tự chia thành hai phần một
phần gán cho N7. Cập nhật tập hàng xóm của N1:{N7, N2, N6,
N5} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.4

Không gian khóa của Chord . . . . . . . . . . . . . . . . . . . . . . 53

iii


3.5

Bảng finger trong các nút mạng . . . . . . . . . . . . . . . . . . . . 54

3.6

Kết quả thực nghiệm mô phỏng . . . . . . . . . . . . . . . . . . . . 61

iv


Danh sách bảng
3.1


Quan hệ giữa số lượng nút mạng và thời gian định tuyến trung
bình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

v


Lời mở đầu
Mạng máy tính từ lâu đã trở thành một phần không thể thiếu trong nhiều
lĩnh vực của đời sống xã hội từ các hệ thống mạng cục bộ dùng để chia sẻ tài
nguyên trong các công ty, cơ quan, đơn vị,... cho đến hệ thống mạng toàn cầu
như mạng Internet.
Kiến trúc của các hệ thống mạng ngày càng được cải tiến và phát triển.
Trong đó, kiến trúc của mạng ngang hàng với nhiều đặc tính tốt như khả năng
mở rộng cao, khả năng chịu lỗi tốt, hiệu năng cao,... thu hút được sự chú ý của
người sử dụng, các nhà nghiên cứu cũng như các đơn vị phát triển ứng dụng.
Tất cả những ưu điểm trên đã tạo lên một cuộc cách mạng trong lĩnh vực mạng
truyền thông. Rất nhiều ứng dụng lớn đã và đang được xây dựng trên mạng
ngang hàng như FreeNet, Napster, BitTorent,... Bên cạnh những ưu điểm trên,
mạng ngang hàng cũng gặp phải một vài hạn chế như vấn đề định tuyến, vấn đề
về bảo mật, về khả năng cân bằng tải,... Trong đó, việc định tuyến trên mạng
ngang hàng là một bài toán quan trọng và phức tạp. Nó vẫn đang được các nhà
khoa học trong và ngoài nước đi sâu vào nghiên cứu.
Có rất nhiều phương pháp được thiết kế để phục vụ cho việc định tuyến trên
mạng ngang hàng, trong số đó phải kể đến các phương pháp như: sử dụng máy
chủ trung tâm, cơ chế làm ngập (flooding), cấu trúc mạng siêu ngang hàng, định
tuyến theo ngữ nghĩa,... các phương pháp này đều tồn tại những hạn chế nhất
định. Phương pháp định tuyến trong mạng ngang hàng áp dụng ý tưởng của
bảng băm phân tán [19] mang lại những kết quả tốt hơn và đồng thời khắc phục

1



được các nhược điểm mà phương pháp định tuyến đã nêu trên gặp phải. Vì vậy,
luận văn này tập trung nghiên cứu về bảng băm phân tán và ứng dụng nó trong
việc định tuyến trên các mạng ngang hàng.
Cấu trúc luận văn gồm có 03 chương. Nội dung của các chương được tóm tắt
như sau:
Chương 1: Tổng quan về mạng ngang hàng
Trong chương này, luận văn trình bày những kiến thức tổng quan về kiến
trúc mạng, mạng ngang hàng, phân loại mạng ngang hàng và những thách thức
đặt ra với mạng ngang hàng. Cuối chương là phân tích về những hạn chế của
các phương pháp định tuyến đã được xây dựng và chỉ ra phương pháp thay thế
tốt hơn.
Chương 2: Bảng băm phân tán
Trong chương này, luận văn sẽ trình bày phương pháp phân bố tài nguyên
sao cho các thao các như thêm, xóa, sửa và tra cứu chỉ thực hiện trong thời gian
O(1). Phương pháp được nhắc đến ở đây chính là bảng băm, bảng băm gồm ba

phần là tập dữ liệu S , hàm băm h và bảng băm T . Các phần tử ei ∈ S sử dụng
hàm băm h để xác định vị trí của nó trong T . Trong một số môi trường, như
môi trường mạng, bảng băm T không phải lúc nào cũng ổn định vì vậy trong
[16] các tác giả đã xây dựng một phương pháp mới được gọi là băm ổn định.
Phương pháp này khắc phục được tình trạng không ổn định của bảng băm T .
Với các đặc tính tốt của băm ổn định, người ta đã áp dụng nó vào việc tra cứu
dữ liệu trong các hệ thống phân tán và gọi nó là bảng băm phân tán. Phương
pháp này không những tỏ ra hiệu quả mà còn mang lại nhiều tính năng tốt.
Trong nội dung này, luận văn đi phân tích các cấu trúc, tính chất của bảng băm
phân tán và áp dụng nó vào trong thủ tục định tuyến trên mạng ngang hàng
được gọi thiệu ở Chương 3.
Chương 3: Định tuyến trên mạng ngang hàng

Trong chương cuối này, luận văn trình bày bài toán định tuyến trên mạng

2


ngang hàng có áp dụng ý tưởng của bảng băm phân tán. Sau đó, luận văn đi
phân tích chi tiết hai thuật toán định tuyến tiêu biểu là thuật toán CAN và
thuật toán Chord. Cuối cùng là các phân tích và so sánh những kết quả thực
nghiệm đạt được, qua đó rút ra những kết luận và định hướng cho những nghiên
cứu tiếp theo.

3


Chương 1
Tổng quan về mạng ngang hàng
1.1

Giới thiệu về mạng ngang hàng

Mạng ngang hàng (Peer–to–Peer network, P2P network ) là một loại hệ thống
phân tán phi tập trung trong đó các nút mạng (được gọi là các peer ) đóng vai
trò vừa máy chủ vừa là máy khách trong mô hình khách–chủ. Nghĩa là, các peer
có thể yêu cầu tài nguyên từ các peer khác và cũng có thể trả lời các yêu cầu tại
cùng một thời điểm. Điều này trái ngược với mô hình khách–chủ truyền thống,
mà ở đó chỉ có máy khách gửi yêu cầu đến một (hoặc một vài) máy chủ và (các)
máy chủ sẽ trả lời các yêu cầu đó.
Với cách tiếp cận theo mô hình khách–chủ, hiệu năng của toàn bộ hệ thống
sẽ giảm xuống khi số lượng các máy khách (có yêu cầu các dịch vụ) tăng lên.
Trong khi đó, đối với mạng ngang hàng, hiệu năng trong toàn mạng càng tăng

lên khi số lượng các máy (peer ) được thêm vào mạng càng nhiều. Các peer có
thể tự tổ chức thành các nhóm, trong các nhóm đó chúng giao tiếp, cộng tác và
chia sẻ băng thông với nhau giúp nhau hoàn thành các công việc mong muốn.
Ví dụ, trong hệ thống chia sẻ tệp tin ngang hàng, mỗi peer có thể tải lên và tải
xuống các tệp tin cùng một lúc và trong các tiến trình như vậy, các peer mới có
thể tham gia vào nhóm và các peer cũ có thể rời đi bất cứ lúc nào. Việc tổ chức
nhóm các peer này được thực hiện một cách tự động và trong suốt với người
4


Hình 1.1: Kiến trúc khách – chủ

dùng.

1.2
1.2.1

Sự tiến hóa của cấu trúc mạng
Kiến trúc khách–chủ

Ngày nay, có rất nhiều ứng dụng chạy trên mạng Internet như WWW, FTP,
Email,... sử dụng kiến trúc khách–chủ (Client–Server Architecture)(Hình 1.1).
Đối với kiến trúc này, các máy khách yêu cầu và nhận các dịch vụ từ (các) máy
chủ. Mọi nội dung, tài nguyên và dịch vụ được lưu trữ và cung cấp bởi máy chủ.
Các tài nguyên có thể được phát hiện và sử dụng một cách hiệu quả bằng việc
truy vấn đến (các) máy chủ tập trung nếu như chúng có đủ khả năng phục vụ
mọi yêu cầu của tất cả máy khách tại cùng một thời điểm.
Tuy nhiên, sự tập trung của kiến trúc khách–chủ gây ra hàng loạt các vấn đề
mà nguyên nhân chính là sự giới hạn về tài nguyên như băng thông, khả năng
tính toán, tốc độ đọc/ghi dữ liệu và không gian lưu trữ ở phía máy chủ. Các

máy chủ có thể bị quá tải nếu nhận được quá nhiều yêu cầu từ phía các máy
khách. Để khắc phục các hạn chế này, người ta cần phải nâng cấp, bổ sung thêm
các tài nguyên cho các máy chủ. Nhưng chi phí cho việc nâng cấp và bổ sung
này cực kỳ đắt đỏ. Ví dụ, cụm máy chủ của Google cần hơn 200.000 máy chủ
chỉ để thực hiện dịch vụ đánh chỉ số website (Web indexing) [8].
Hơn nữa, sự tập trung của kiến trúc khách–chủ cũng dẫn đến các điểm lỗi
5


đơn (Single Point Of Failure, SPOF ). Nếu các máy chủ tập trung bị tháo gỡ
hoặc không làm việc thì không có bất kỳ máy chủ nào khác có thể thay thế
những máy chủ đó và mọi dịch vụ trên các máy chủ này có thể bị mất.

1.2.2

Kiến trúc lưới

Điện toán lưới (Grid Computing) đang nổi lên nhanh chóng từ lĩnh vực khoa
học và học thuật cho đến công nghiệp và thương mại. Các hệ thống điện toán
lưới hiện nay là ví dụ nổi bật nhất của kiến trúc khách–chủ trong việc tính toán
phân tán.
Viễn cảnh của điện toán lưới là cung cấp các tính toán hiệu năng cao và cơ
sở hạ tầng dữ liệu hỗ trợ linh hoạt, an toàn và cộng tác trong việc chia sẻ tài
nguyên giữa các cá nhân và tổ chức được biết đến với cái tên là “tổ chức ảo”
(virtual organization). Trọng tâm của kiến trúc lưới là khả năng tích hợp các
nguồn cung cấp tài nguyên và người dùng để thiết lập quan hệ chia sẻ (sharing
relationship), cái mà cần phải có giao thức chung tại mỗi lớp của kiến trúc. Nó
được thiết kế để cung cấp các truy cập liên tục và thống nhất vào các nguồn
tài nguyên quan trọng mà không cần phải xem xét vị trí địa lý của chúng. Các
tài nguyên trong lưới có thể là các siêu máy tính hiệu năng cao có không gian

lưu trữ lớn, các cảm biến, phần mềm ứng dụng và dữ liệu của các tổ chức khác
nhau được kết nối thông qua Internet. Lưới cung cấp cơ sở hạ tầng cho phép
các tổ chức độc lập, riêng rẽ trở thành các tổ chức ảo chia sẻ tài nguyên và cộng
tác để giải quyết các vấn đề chung.

1.2.3

Kiến trúc ngang hàng

Mạng ngang hàng là một hệ thống phân tán phi tập trung và cho phép các
máy tính chia sẻ và tích hợp các tài nguyên, dữ liệu và các dịch vụ lẫn nhau.
Mặc dù khái niệm ngang hàng và lưới có rất nhiều đặc điểm giống nhau nhưng
chúng được đề xuất để giải quyết các vấn đề khác nhau. i) Mạng ngang hàng
6


thường áp dụng cho một loạt các công nghệ, cái mà có thể làm tăng một cách
nhanh chóng việc sử dụng các tài nguyên ở rìa của mạng Internet như: thông
tin, băng thông, khả năng tính toán. ii) Điện toán lưới thì tập trung vào việc
thúc đẩy khả năng mở rộng và tương tác giữa các ứng dụng, các nền tảng khác
nhau [2].
Ngược lại với mô hình lưới đã có, kiến trúc ngang hàng không phụ thuộc vào
bất kỳ máy chủ tập trung nào để cung cấp các dịch vụ. Kiến trúc ngang hàng
đề xuất một sự thay thế hoàn hảo cho mô hình lưới đã có, đặc biệt là trong các
ứng dụng phân tán có phạm vi lớn. Trong mô hình ngang hàng, mỗi máy (peer )
thực hiện nhiệm vụ của cả máy khách và máy chủ, yêu cầu tài nguyên bằng
cách gửi đi các truy vấn và phục vụ tài nguyên cho các máy khác. Mạng ngang
hàng là một mạng chồng lấn logic trên cơ sở hạ tầng của mạng vật lý, nó cung
cấp một môi trường ảo cho phép các lập trình viên dễ dàng thiết kế và cài đặt
các môi trường truyền thông và các giao thức riêng trên các mạng đã có.

Sự phổ biến của mạng ngang hàng được tăng theo cấp số nhân vì những lợi
ích mà nó mang lại cho người dùng cuối (end–user ). Phân loại mạng ngang hàng
và chỉ ra ưu, nhược điểm của nó sẽ được trình bày trong phần tiếp theo.

1.3

Phân loại

Có nhiều tiêu chí để phân loại các mạng ngang hàng. Trong số đó, phân loại
mạng ngang hàng theo mức độ tập trung là tiêu chí hay được dùng nhất. Theo
tiêu chí này, mạng ngang hàng sẽ được phân chia thành từng loại mạng riêng
biệt và đi kèm với đó là ví dụ về các mạng cụ thể, đã và đang hoạt động, đại
diện cho từng loại.
Có rất nhiều loại mạng ngang hàng thú vị như các hệ thống chia sẻ tệp
tin, nhắn tin, truyền giọng nói trên giao thức IP (Voice over Internet Protocol,
VoIP ), tính toán hiệu năng cao, tìm kiếm,... Trong số các mạng ngang hàng đã

7


và đang được sử dụng có thể được chia thành hai loại dựa theo tiêu chí mức độ
tập trung của mạng: mạng ngang hàng tập trung và mạng ngàng hàng phi tập
trung [3].
• Mạng ngang hàng tập trung:

Mặc dù, mô hình ngang hàng được xem như là ngược lại với mô hình
khách–chủ tập trung nhưng thế hệ đầu tiên của các hệ thống mạng ngang
hàng vẫn bắt đầu với khái niệm tập trung. Tuy nhiên, ngược lại với các hệ
thống khách–chủ truyền thống, các máy chủ trong mạng ngang hàng chỉ
giữ các thông tin mô tả (meta–information) về các tài nguyên được chia

sẻ trong mạng mà không lưu trữ nội dung của chúng. Mạng ngang hàng
tập trung rất đơn giản, thao tác định vị dữ liệu cũng rất nhanh chóng và
hiệu quả. Nhưng chúng cũng rất dễ bị kiểm duyệt cũng như bị tấn công.
Ngoài ra, chính sự tồn tại của máy chủ tập trung nên các mạng loại này
có ít nhất một điểm SPOF. Đồng thời, chúng không có khả năng mở rộng
vì hạn chế của cơ sở dữ liệu và khả năng phục vụ của máy chủ tập trung.
Bởi vì, cần phải cập nhật cơ sở dữ liệu ở máy chủ một cách liên tục hoặc
theo chu kỳ.
Napster và BitTorrent là hai ứng dụng tiêu biểu cho hệ thống mạng ngang
hàng tập trung.
• Mạng ngang hàng phi tập trung:

Để giải quyết các vấn đề của mạng ngang hàng tập trung như khả năng
mở rộng, SPOF và các vấn đề pháp lý,... mạng ngang hàng phi tập trung
đã ra đời và được sử dụng rộng rãi. Loại mạng này không hề sử dụng bất
kỳ trung tâm điều khiển nào. Các nút trong mạng là tương đương nhau về
chức năng.
Ta biết rằng khả năng mở rộng của bất kỳ một hệ thống nào cũng đều bị
hạn chế bởi số lượng các thao tác tập trung cần thiết. Do đó, để mở rộng
8


mạng thì cần phải tránh sử dụng các trung tâm hoặc các máy chủ. Chính
vì không sử dụng các máy chủ hoặc các trung tâm điều khiển nên mạng
ngang hàng phi tập trung có khả năng mở rộng cực kỳ lớn. Loại mạng này
có khả năng chịu lỗi rất tốt, không có SPOF và việc bổ sung các peer mới
vào mạng cũng rất dễ dàng. Mức độ tự trị trên các dữ liệu và tài nguyên
là rất cao. Tuy nhiên, việc khôi phục dữ liệu trong hệ thống khi bị lỗi là
rất chậm và chất lượng dịch vụ không cao và do thiếu thông tin về toàn
bộ mạng nên việc dự đoán hành vi của toàn bộ mạng là rất khó khăn.

Gnutella và FreeNet là hai loại mạng cài đặt mô hình mạng ngang hàng
phi tập trung.

1.4

Tìm kiếm trên mạng ngang hàng

Do việc tìm kiếm tài nguyên và các dịch vụ trong điện toán lưới giống với
việc tìm kiếm các tài nguyên trong mạng ngang hàng nên các phương pháp tìm
kiếm trong mạng ngang hàng cũng được áp dụng giống với các hệ thống điện
toán lưới có kích thước lớn. Hệ thống tìm kiếm trong mạng ngang hàng được
chia thành hai loại: tìm kiếm có cấu trúc và tìm kiếm không có cấu trúc, tương
ứng với hai loại tìm kiếm này chúng ta cũng có hai loại cấu trúc mạng ngang
hàng là: mạng ngang hàng có cấu trúc và mạng ngang hàng không có cấu trúc.
• Tìm kiếm có cấu trúc:

Mạng ngang hàng có cấu trúc là một cấu trúc mạng chuyên biệt trên mạng
chồng lấn–mạng có thể thiết lập liên kết giữa nơi lưu trữ nội dung và địa
chỉ (IP) của các nút. Tìm kiếm có cấu trúc đã được sử dụng rộng rãi cho
việc phát hiện tài nguyên trong các hệ thống mạng loại này và tỏ ra rất
hiệu quả.
Trong các mạng ngang hàng dựa trên bảng băm phân tán, mỗi tài nguyên
được gán với một khoá, khóa này được sinh bằng cách băm tên hoặc nội
9


dung,... của mỗi tài nguyên. Mỗi nút trong hệ thống chịu trách nhiệm lưu
trữ một phạm vi khóa nhất định. Cấu trúc mạng được lưu trữ bởi bảng
định tuyến trên mọi nút mạng. Mỗi nút mạng chỉ cần một lượng nhỏ thông
tin định tuyến về các nút khác. Nhờ vào bảng định tuyến và các hàm băm

thống nhất (uniform hash function), các nút có thể lưu trữ và lấy các tài
nguyên một cách thuận tiện trên các nút khác nhờ vào khóa của tài nguyên
đó.
Chord, CAN, Kademlia là những ví dụ điển hình cho phương pháp này.
• Tìm kiếm không cấu trúc:

Trái ngược lại với mạng ngang hàng có cấu trúc, mạng ngang hàng không
có cấu trúc không cần duy trì cấu trúc mạng. Địa chỉ và nội dung lưu
trữ trên các nút mạng không có quan hệ với nhau. Mặc dù, các phương
pháp tìm kiếm đã có trong mạng ngang hàng không có cấu trúc là không
đồng nhất (heterogeneous) nhưng hầu hết trong số chúng được thiết kế
chuyên biệt để giải quyết các vấn đề của cơ chế làm ngập. Chúng được chia
thành hai loại: tìm kiếm mù (blind search) và tìm kiếm thăm dò (informed
search).
– Tìm kiếm mù:
Trong các mạng sử dụng phương pháp tìm kiếm này, các nút không
duy trì thông tin về vị trí của các tài nguyên. Lợi ích của phương pháp
này là các nút không mất bất kỳ chi phí nào để duy trì thông tin về
vị trí các tài nguyên và cực kỳ linh hoạt trong môi trường mạng thay
đổi liên tục. Cơ chế làm ngập là cách tiếp cận cơ bản của tìm kiếm
mù mà ở đó các truy vấn được chuyển tới tất cả các peer đã tham gia
vào mạng để xem chúng có chứa tài nguyên được yêu cầu hay không.
Vì sử dụng phương pháp làm ngập nên việc tiêu tốn quá nhiều băng
thông là trở ngại lớn nhất của loại mạng này. Người ta đã đưa ra rất
10


nhiều phương pháp nhằm giảm thiểu lượng băng thông được tiêu thụ
trong các nghiên cứu [10, 11, 14].
– Tìm kiếm thăm dò:

Ngược lại với tìm kiếm mù, phương pháp tìm kiếm thăm dò cho phép
các nút mạng duy trì thông tin về các nút khác trong mạng như cấu
trúc mạng, vị trí của các tài nguyên. Thông thường phương pháp tìm
kiếm thăm dò có hai cơ chế chính đó là: i) đánh chỉ số các nút và ii)
đánh chỉ số tại mỗi nút [26].

1.5

Ưu và nhược điểm của mạng ngang hàng

1.5.1

Ưu điểm

Mạng ngang hàng có rất nhiều ưu điểm tốt hơn so với các loại mạng khác.
Phần dưới đây trình bày một số ưu điểm chính:
• Chia sẻ dữ liệu:

Các peer có thể chia sẻ dữ liệu với nhau một cách dễ dàng. Chúng có thể
chia sẻ các tài nguyên chung như: không gian lưu trữ, băng thông, khả
năng tính toán,... Dữ liệu có thể được chia sẻ hai chiều một cách nhanh
chóng mà không cần sự can thiệp của bất cứ hệ thống nào khác.
• Không có sự kiểm soát của máy chủ tập trung:

Điều này làm giảm hẳn khả năng bị tắc nghẽn cổ chai. Với hệ thống khách–
chủ, khi số lượng yêu cầu phục vụ tăng lên thì việc tắc nghẽn hoàn toàn có
thể xảy ra. Đôi khi, hệ thống không thể làm việc khi (một số) máy chủ bị
hỏng. Các vấn đề này không phải là trở ngại đối với mạng ngang hàng vì
các peer trong mạng giao tiếp trực tiếp với nhau. Thậm chí nếu tắc nghẽn
hình thành thì cũng sẽ nhanh chóng được giải quyết bằng những cách thức

đơn giản và dễ dàng.
11


• Không cần sự quản trị tập trung:

Đôi khi, việc quản trị tập trung cũng có một số lợi ích, ví dụ như theo dõi
các máy tính đã truy cập những tài nguyên nào. Nhưng trong hầu hết các
trường hợp thì sự quản trị tập trung là một hạn chế rất lớn đối với các hệ
thống vì nếu không có việc quản trị tập trung có nghĩa là các tài nguyên sẽ
được lưu trữ tại nhiều nơi trong hệ thống. Do đó, nếu chẳng may một tài
nguyên nào đó bị lỗi sẽ không ảnh hưởng tới các thành phần khác trong
hệ thống.

1.5.2

Nhược điểm

Mô hình mạng ngang hàng giải quyết được rất nhiều hạn chế của mô hình
mạng khách–chủ truyền thống nhưng vẫn tồn tại một số nhược điểm. Tiếp theo,
luận văn sẽ phân tích một số nhược điểm của mô hình mạng ngang hàng:
• Toàn bộ mạng là phi tập trung, điều này cũng gây trở ngại lớn cho người

quản trị mạng. Cụ thể là một người không thể quyết định được cấu hình
của toàn bộ mạng.
• Mức độ bảo mật trong mạng rất kém. Virus, phần mềm gián điệp, phần

mềm độc hại dễ dàng truyền trên hệ thống. Đồng thời cũng gây khó khăn
trong việc kiểm duyệt nội dung của dữ liệu được truyền tải trong mạng.
• Việc phục hồi và sao lưu dự phòng dữ liệu là rất khó khăn và phức tạp. Vì


vậy, mỗi peer phải tự sao lưu dữ liệu của mình.
• Dữ liệu và tài nguyên không được tổ chức tập trung. Chúng được lưu trữ

trên các peer khác nhau và có thể sẽ rất khó khăn trong việc định vị dữ
liệu nếu hệ thống không được tổ chức một cách hợp lý.

12


1.6

Một số vấn đề trong mạng ngang hàng

Khả năng mở rộng, khả năng chịu lỗi, hiệu năng,... là những lợi thế mà mô
hình mạng ngang hàng được cho là tốt hơn so với mô hình mạng khách–chủ.
Tuy nhiên, cũng còn rất nhiều những vấn đề mà mạng ngang hàng cần phải giải
quyết như sau [22]:
• Định tuyến (Routing )

Trong thực tế có rất nhiều phương pháp định tuyến đã và đang được cài
đặt trong các mạng ngang hàng. Ta có thể chia các phương pháp định
tuyến trên mạng ngang hàng thành hai lớp: lớp thứ nhất là các phương
pháp áp dụng với các mạng ngang hàng hoặc là tập trung hoặc được cấu
hình tĩnh; lớp thứ hai là các phương pháp định tuyến áp dụng đối với các
mạng ngang hàng dựa trên nguyên tắc của mạng chồng lấn. Các nút mạng
có thể tùy ý tham gia và rời bỏ mạng một cách tùy ý, thời gian hoạt động
trung bình trong mạng của mỗi nút là tương đối thấp. Cấu trúc của mạng
ngang hàng dựa trên nguyên tắc mạng chồng lấn có thể thay đổi liên tục
theo thời gian. Khi thiết lập một đường đi (route) cho thông điệp thì cũng

không có gì đảm bảo về mặt thời gian đến đích của thông điệp. Do vậy,
định tuyến trong mạng ngang hàng là một vấn đề vô cùng phức tạp. Sau
đây, luận văn trình bày một số vấn đề cần giải quyết tại khâu thiết kế các
thuật toán định tuyến trong mạng ngang hàng [6]:
1. Khả năng mở rộng (Scalability )
Thông thường mạng ngang hàng có hàng ngàn peer tham gia và nó
được mong đợi có thể đáp ứng cho hàng triệu peer hoạt động cùng
lúc. Trong các mạng lớn như vậy, việc sử dụng máy chủ trung tâm để
điều hành hoạt động gây ra rất nhiều các vấn đề về khả năng mở rộng
như: các máy chủ bị quá tải hoặc sinh ra các SPOF. Hơn nữa, trong
các mạng đòi hỏi băng thông liên tục như hội nghị, truyền hình trực
13


tiếp,... các peer cần phải liên kết với hàng xóm thích hợp có đủ băng
thông. Trong trường hợp này, làm thế nào để tìm được hàng xóm thích
hợp trong mạng ngang hàng lớn với chi phí thấp là một thử thách lớn.
Cần phải có các thuật toán xây dựng cấu trúc mạng có khả năng mở
rộng, nhẹ và phân tán cho mục đích này.
2. Khả năng nặc danh (Anonymously )
Thuộc tính này có thể không cần thiết đối với nhiều mạng ngang hàng.
Tuy nhiên, nếu một mạng được thiết kế với khả năng nặc danh thì
phải giải quyết ở bước định tuyến.
3. Độ phức tạp định tuyến (Complexity )
Độ phức tạp định tuyến là số lượng các bước cần thiết để một gói
tin được truyền từ máy này đến máy khác trong trường hợp xấu nhất
(worst case scenario).
• Bảo mật (Security )

Tính chất phân tán tạo ra thêm nhiều thử thách về mặt an ninh hơn so

với mô hình khách–chủ. Vì tập hợp các peer trong mạng ngang hàng thay
đổi liên tục theo thời gian (động) và các peer không tin tưởng lẫn nhau
nên việc đạt được một mức độ bảo mật cao trong mạng ngang hàng khó
khăn hơn so với các mạng không ngang hàng. Các cơ chế bảo mật truyền
thống để bảo vệ dữ liệu và hệ thống khỏi các cuộc xâm nhập và tấn công
như tường lửa không thể bảo vệ cho mạng ngang hàng vì về cơ bản các
peer được phân phối trên toàn cầu và các cơ chế này cũng có thể cản trở
truyền thông giữa các peer. Do đó, một khái niệm bảo mật mới được yêu
cầu phải cho phép các tiến trình tương tác và phân phối trong các mạng
ngang hàng.
• Tin cậy (Reliability )

Một hệ thống đáng tin cậy là một hệ thống có thể được phục hồi khi có lỗi
14


xuất hiện. Các yếu tố được xem xét khi đánh giá độ tin cậy là nhân bản
dữ liệu, phát hiện nút lỗi và phục hồi, thông tin về vị trí của dữ liệu được
lưu trữ ở nhiều nơi để tránh SPOF và các đường dẫn đến dữ liệu luôn sẵn
sàng. Nhân bản dữ liệu làm tăng độ tin cậy bằng việc tăng số lượng và vị
trí các bản sao. Có hai chiến lược nhân bản là nhân bản sở hữu (owner
replication) và nhân bản theo đường đi (path relication). Với nhân bản sở
hữu, khi tìm kiếm thành công, dữ liệu chỉ được lưu trữ duy nhất tại nút
yêu cầu. Trong trường hợp còn lại, khi tìm kiếm thành công, dữ liệu được
lưu tại tất cả các nút từ nút yêu cầu đến nút cung cấp. Mạng ngang hàng
cũng nhân bản và thay thế dữ liệu theo sự phổ biến của chúng để đạt được
hiệu suất thích hợp.
Trong các mạng ngang hàng có cấu trúc, các thông điệp được định tuyến
qua một số ít các bước bằng cách sử dụng trạng thái định tuyến của nút
trước đó. Mạng này sẽ cập nhật trạng thái định tuyến tự động khi các peer

tham gia và rời bỏ mạng nên có thể chuyển thông điệp đến nút đích đúng
ngay cả khi phần lớn các nút hoặc một phần của mạng không hoạt động.
Để đạt được độ tin cậy trong mạng, các peer phải tiêu thụ băng thông
mạng để duy trì trạng thái định tuyến, may mắn là rất nhiều các kỹ thuật
đã được phát triển để giảm lượng băng thông nên các mạng loại này vẫn
phù hợp với điều kiện hoạt động. Với việc tăng khả năng chịu lỗi và độ
tin cậy trong mạng ngang hàng không cấu trúc, việc thêm các liên kết dự
phòng vào hệ thống đã được giải quyết. Theo cách này thì khi một kết nối
bị ngắt sẽ không dẫn đến cả hệ thống bị ngắt kết nối hoặc làm tăng số
bước định tuyến.
• Tính linh hoạt (Flexibility )

Một trong những khía cạnh quan trọng của mạng ngang hàng là khả năng
tự trị của các peer. Chính vì vậy, các peer có thể tham gia và rời bỏ mạng
khi chúng muốn. Các mạng ngang hàng được đặc trưng bởi tính phi tập
15


trung, quy mô lớn và tính động của môi trường mà nó hoạt động. Để giải
quyết bài toán về quy mô và tính động của mạng thì các thuộc tính về khả
năng thích nghi và tự tổ chức cần phải được xem xét một cách cẩn thận
khi xây dựng mạng ngang hàng.
Trong các mạng ngang hàng có cấu trúc chuẩn, định danh tĩnh được gán
cho các peer và các cấu trúc dữ liệu phân phối được xây dựng dựa trên
các định danh này, bởi vậy cấu trúc mạng chồng lấn được quyết định bằng
việc chọn các định danh. Các mạng có cấu trúc dựa trên bảng băm phân
tán tra cứu dữ liệu nhanh chóng và ổn định trong khi các nút tham gia vào
và rời khỏi hệ thống liên tục.
• Cân bằng tải (Load Balancing )


Cân bằng tải là phân bố một cách đồng đều công việc cho các peer trong
mạng. Nếu thực hiện được cân bằng tải trong mạng thì sẽ tối đa hóa thông
lượng bởi vì công việc sẽ được hoàn thành với sự tham gia tất cả các peer
trong mạng [4].
Trong mạng ngang hàng, tra cứu (định vị) là bài toán quan trọng nhất. Một
mạng ngang hàng được đánh giá là tốt nếu thời gian tra cứu nhanh và chính
xác. Bài toán tra cứu được phát biểu đơn giản như sau [9]: A chèn mục dữ liệu
X vào trong hệ thống (mạng) và sau đó B muốn lấy mục dữ liệu X đó, thường

thì không phải lúc nào A cũng kết nối vào trong hệ thống. Câu hỏi đặt ra là làm
thế nào B có thể tìm đúng được nơi đang lưu trữ bản sao của X .

1.7

Một số phương pháp định tuyến trên P2P

Như phân tích ở trên, các phương pháp định tuyến sẽ được chia thành hai
lớp theo cấu trúc của mạng ngang hàng. Sau đây, luận văn sẽ xem xét và phân
tích một số thuật toán định tuyến tiêu biểu trong mạng ngang hàng.
16


Hình 1.2: Mô hình máy chủ trung tâm

1.7.1

Mạng tập trung hoặc được cấu hình tĩnh

Trong phần này, các thuật toán định tuyến thuộc lớp thứ nhất, tức là các
thuật toán định tuyến trên mạng ngang hàng tập trung hoặc được cấu hình tĩnh

sẽ được xem xét và phân tích chi tiết. Về cơ bản, các thuật toán này khá đơn
giản chính vì thế ta dễ dàng nhận ra được các điểm yếu của chúng.
Thông thường, loại mạng này có phạm vi nhỏ với số lượng nút mạng ít.
Phương pháp định tuyến sử dụng Máy chủ trung tâm là một trong những phương
pháp đại diện cho các thuật toán thuộc lớp này.
Phương pháp định tuyến sử dụng máy chủ trung tâm: phương pháp
này duy trì một cơ sở dữ liệu tập trung để ánh xạ tên mục dữ liệu X tới vị
trí của máy đang lưu trữ X như trong Hình 1.2. Tuy nhiên, phương pháp này
không đáng tin và gặp khó khăn khi mở rộng hệ thống đồng thời nó cũng dễ bị
tắc nghẽn cổ chai và dễ dàng bị tấn công vào cơ sở dữ liệu. Mạng ngang hàng
Napster sử dụng phương pháp này.

17


1.7.2

Mạng ngang hàng trên mạng chồng lấn

Mạng chồng lấn xây dựng trên một cấu trúc liên kết ảo bên trên liên kết vật
lý của mạng khác. Các nút mạng tham gia và rời bỏ mạng một cách hoàn toàn
tự động, thời gian hoạt động trung bình của một nút mạng tương đối ngắn.
Cấu trúc của mạng chồng lấn thay đổi liên tục theo thời gian. Ngay cả khi một
đường đi được thiết lập thì cũng chẳng có gì đảm bảo về thời gian đến đích của
thông điệp được truyền trên nó. Do đó, định tuyến trên các loại mạng này gặp
rất nhiều các vấn đề khó khăn. Sau đây là một số thuật toán được cài đặt trên
các loại mạng này.
• Phương pháp định tuyến sử dụng cơ chế làm ngập

Với phương pháp này, nếu B muốn tìm X thì B sẽ phát ra một thông điệp

lan tỏa tới tất cả các nút hàng xóm của B . Các nút hàng xóm sẽ kiểm
tra trong cơ sở dữ liệu cục bộ của mình, nếu tìm thấy X thì sẽ trả lời với
mục dữ liệu này và ngược lại, các nút này sẽ chuyển tiếp thông điệp tới
các hàng xóm của nó một cách đệ quy (xem Hình 1.3). Vì sử dụng phương
pháp làm ngập nên các mạng sử dụng phương pháp này tiêu thụ rất nhiều
băng thông và các yêu cầu có thể bị lặp lại (một số mạng có thể xử lý để
tránh truy vấn lặp). Mạng ngang hàng Gnutella sử dụng phương pháp này.

• Phương pháp định tuyến sử dụng cấu trúc mạng siêu ngang hàng

Để giảm chi phí của thông điệp lan tỏa trong phương pháp làm ngập,
người ta tổ chức các nút trong mạng theo kiểu phân cấp (giống như DNS
đã làm)(Hình 1.4). Việc tìm kiếm sẽ bắt đầu từ nút gốc của mỗi cụm sau
đó nó sẽ chuyển tiếp thông điệp tới các nút khác trong cụm đó. Tuy nhiên,
phương pháp này cũng có những hạn chế như: các nút có bậc cao thì sẽ có
hệ số tải lớn hơn so với các nút lá (hoặc các nút có bậc thấp hơn) và do đó
đòi hỏi cấu hình phần cứng cao và phải được quản lý cẩn thận. Nếu nút
18


Hình 1.3: Phương pháp làm ngập trên mạng chồng lấn

Hình 1.4: Mô hình mạng siêu ngang hàng

gốc hoặc các nút có bậc cao bị hỏng hoặc rời khỏi mạng thì các nút con
của nó cũng không hoạt động được.
• Phương pháp định tuyến theo ngữ nghĩa (Semantic Routing )

Định tuyến theo ngữ nghĩa [6] là một phương pháp định tuyến tập trung
vào bản chất của truy vấn được định tuyến hơn là vào cấu trúc liên kết

mạng. Về cơ bản, định tuyến theo ngữ nghĩa cải thiện phương pháp định
tuyến truyền thống bằng cách sử dụng các nút ưu tiên. Nút ưu tiên là nút
cung cấp các thông tin tốt ở lần trước đó về kiểu dữ liệu được tham chiếu
bởi truy vấn.
19