GI O
TR

V

N

OT O

ỌC QU N

N

N U ỄN VĂN QUỐC

P ÂN TÍC , ÁN
MỘT SỐ

Á

AO T ỨC M N

TRÊN MƠ TR

N

Chun n

ỆU NĂN
P ÂN TÁN

NETWORK S MULATOR

n

K o

ọ m

tn

M số 8 48 01 01

N

n

n TS N U ỄN T

N

T


L

CAM OAN

Tôi xin cam đoan các số liệu và kết quả nghiên cứu trong đề tài là trung
thực, các kết quả nghiên cứu đƣợc thực hiện tại Trƣờng
dƣới sự hƣớng dẫn của TS. Nguyễn Thành


ại học Quy Nhơn

ạt, các tài liệu tham khảo đã

đƣợc trích dẫn đầy đủ, rõ ràng.
Học viên
N u ễn Văn Quố


L

CẢM

N

Trong q trình học tập và hồn thành luận văn, tôi đã nhận đƣợc sự
ủng hộ, giúp đỡ quý báu từ các thầy cô giáo, các đồng nghiệp, bạn bè và
ngƣời thân.
Lời đầu tiên, tơi xin bày tỏ sự kính trọng và biết ơn sâu sắc nhất tới TS.
Nguyễn Thành

ạt - ngƣời đã hƣớng dẫn trực tiếp, tận tình giúp đỡ, động

viên và tạo điều kiện thuận lợi nhất cho tôi trong suốt thời gian thực hiện đề
tài luận văn.
Tôi xin đƣợc cảm ơn sự quan tâm, giúp đỡ, ân cần chỉ bảo và nhiệt tình
giảng dạy của các thầy cô Khoa
nhiên, Trƣờng


ông nghệ thông tin, Khoa Khoa học tự

ại học Quy Nhơn. Những kiến thức mà các thầy cô đã hết

lòng truyền đạt là nền tảng tri thức vững chắc cho chúng tơi trong q trình
học tập cũng nhƣ sau khi ra trƣờng.
uối cùng, tôi xin cảm ơn những ngƣời thân của mình đã ln bên
cạnh, giúp đỡ, động viên và tạo mọi điều kiện để tơi hồn thành luận văn tốt
nghiệp.
Học viên
N u ễn Văn Quố


1

PHẦN MỞ ẦU
1.

Lý o

ọn đề t

Hiện nay, máy tính và mạng toàn cầu đã mang đến những sự phát triển
mạnh mẽ trong tất cả các hoạt động của con ngƣời, hỗ trợ con ngƣời phát
triển xã hội một cách vƣợt bậc so với thời kỳ chƣa có máy tính và mạng
Internet. Với sự phát triển đó, thơng tin là một nguồn tri thức rất quan trọng,
vì thế mà việc lƣu trữ, chia sẻ thông tin rất đƣợc quan tâm.

ể đáp ứng nhu


cầu tiếp thu thông tin mọi lúc mọi nơi, mà thông tin đƣợc lƣu trữ, quản lý ở
khắp mọi nơi trên thế giới.

hính vì thể rất nhiều tổ chức phân bố các chi

nhánh trên nhiều vị trí ở các thành phố, các quốc gia khác nhau, để đáp ứng
nhu cầu cung cấp thông tin cho địa phƣơng và quốc gia ngay tức thì.

o đó

việc quản lý các thơng tin địi hỏi tính chính xác, liên tục, và đồng bộ giữa các
bộ phận, các cơ sở khác nhau, việc quản lý thông tin, dữ liệu của tổ chức
không chỉ tập trung tại một chi nhánh duy nhất mà cần đƣợc quản lý tại tất cả
các chi nhánh, và đặc biệt các thơng tin, dữ liệu này phải có mối liên hệ logic
với nhau thơng qua mạng máy tính. Việc quản lý thông tin, dữ liệu theo kiểu
truyền thống, hay tập trung nhƣ trƣớc đây sẽ không giải quyết đƣợc vấn đề
nêu trên, để đảm bảo tính liên tục, nhanh chóng, chính xác cho mọi hoạt động
lƣu trữ, chia sẻ thơng tin cần phải có một giải pháp tồn diện cho các vấn đề
về tổ chức và kinh tế, sự liên kết các cơ sở dữ liệu đang tồn tại, sự phát triển
mở rộng, giảm tổng chi phí tìm kiếm, tin cậy và tính sẵn sàng.

ó chính là

mạng phân tán, khác với mạng truyền thống, mạng phân tán có khả năng làm
đƣợc những việc mà mạng khác không làm đƣợc, đáp ứng đƣợc yêu cầu là
thông tin đƣợc liên tục, liền mạch, chính xác nhƣng khơng làm q tải nơi lƣu
trữ thơng tin. [5]
Ngày nay mơ phỏng là phƣơng pháp chính để đánh giá và phân tích
hiệu suất của các hệ thống trƣớc khi áp dụng vào thực tế là một điều cần thiết,



2

việc tìm hiểu về mạng phân tán và mơ phỏng các giao thức phổ biến trên
mạng phân tán nhƣ hord, Tapestry, Kelips, Kademlia trên môi trƣờng mạng
giả lập nhƣ Network Simulator 2 (NS2), Oversim, P2PSim để nghiên cứu
cách các giao thức hoạt động, đánh giá hiệu năng, phân tích dữ liệu từ đó đƣa
ra đƣợc ƣu khuyết điểm của từng giao thức, và chọn ra đƣợc giao thức phù
hợp nhất cho từng trƣờng hợp cụ thể để áp dụng vào thực tế. [1]
Qua đó, chúng ta thấy đƣợc tầm quan trọng cũng nhƣ sự những nhu cầu
cho nghiên cứu, phân tích đánh giá mạng phân tán và các giao thức trên môi
trƣờng mạng phân tán.
Từ những lý do ở trên, chúng tơi chọn đề tài “P ÂN TÍC ,
Á

ỆU NĂN

MƠ TR

N

Mụ đ

2.

MỘT SỐ

AO T ỨC M N

ÁN


P ÂN TÁN TRÊN

NETWORK S MULATOR”
n

ên ứu

Tìm hiểu và nghiên cứu, đánh giá cách phân bổ và tìm kiếm thơng tin, hiệu
năng của các giao thức mạng phân tán từ đó đƣa ra cái nhìn chi tiết nhất về ƣu
khuyết điểm của các giao thức trên mạng phân tán .
ố t ợn v p ạm v n

3.

ên ứu

ối tƣợng nghiên cứu: Một số giao thức trên mạng phân tán.

-

- Phạm vi nghiên cứu: Mạng phân tán trên môi trƣờng mạng giả lập.
4.

P

ơn p

pn


ên ứu

Phƣơng pháp nghiên cứu tài liệu: Qua nguồn tài liệu đã đƣợc xuất bản,
ban hành, các bài báo đã đăng trên các tạp chí khoa học, các tài liệu liên quan
đến vấn đề đang nghiên cứu trên Internet.
Phƣơng pháp thực nghiệm: Tiến hành phân tích thiết kế giao thức, mơ
phỏng giao thức phân tán, và thiết lập các giao thức trên môi trƣờng mạng giả
lập để đánh giá, so sánh các giao thức tìm kiếm và phân bổ thơng tin trên
mạng phân tán.


3

Ýn

5.

ĩ k o

ọ v n

ĩ t ự t ễn

Mang lại các tổng hợp, đánh giá, phân tích mạng phân tán, giao thức
phân tán đƣợc mô phỏng trên môi trƣờng mạng giả lập. Mang tới cái nhìn chi
tiết nhất về mạng phân tán, giao thức mạng phân tán, hiệu năng, phân bổ và
lƣu trữ thơng tin, tìm kiếm và đề xuất, từ đó nhận ra ƣu khuyết điểm để nâng
cao, hồn thiện hơn mạng phân tán và những thành phần liên quan.
Hiện nay nhu cầu về mạng phân tán đang rất lớn, với các phân tích
đánh giá này thì việc nhìn nhận tốt hơn về mạng phân tán cũng nhƣ các giao

thức chạy trên môi trƣờng mạng phân tán sẽ giúp tạo ra các giao thức mới tối
ƣu, cải thiện mạng phân tán để đáp ứng đƣợc các nhu cầu mới trong sự phát
triển ngày càng tiến bộ của khoa học kỹ thuật.
Kết ấu ủ luận văn

6.

ể thực hiện đề tài một cách hệ thống, ngoài phần mở đầu, kết luận, tài liệu
tham khảo, luận văn có cấu trúc 3 chƣơng nhƣ sau:
Chương 1: Một số kiến thức lý thuyết cơ sở về mạng phân tán.
hƣơng này sẽ tìm hiểu về tổng quan về lý thuyết mạng máy tính,
mạng phân tán, các giao thức trên mạng phân tán.
Chương 2: Mô tả, phân tích giao thức phân tán.
Trong chƣơng này, tìm hiểu các giao thức cụ thể về khái niệm, mô tả,
chi tiết từng thành phần của các giao thức.
Chương 3: Mô phỏng, đánh giá giao thức phân tán.
Trong chƣơng này sẽ nêu rõ các phƣơng pháp phân tích, giới thiệu các
cơng cụ mô phỏng mạng và tiến hành mô phỏng các giao thức lên môi trƣờng
mạng ảo, để tiến hành phân tích, đánh giá về hiệu năng, tìm kiếm của các giao
thức.


4

C
1.1 TỔN

N

TỔNG QUAN LÝ THUYẾT


QUAN VỀ M NG MÁY TÍNH

1.1.1 Mạn m

tn

Ngày nay, khoa học và kỹ thuật đã đạt đƣợc những thành tựu to lớn.
Nhờ sự phát triển của kỹ thuật số, kỹ thuật phần cứng và công nghệ phần
mềm đã và đang đem lại cho ngƣời sử dụng các dịch vụ mới đa dạng và
phong phú hơn, nhất là trong lĩnh vực truyền thông mà tiêu biểu là mạng máy
tính.
Mạng máy tính là mạng viễn thơng kỹ thuật số cho phép các node
mạng chia sẻ tài nguyên. Trong các mạng máy tính, các thiết bị máy tính trao
đổi dữ liệu với nhau bằng các kết nối (liên kết dữ liệu giữa các node). Các liên
kết dữ liệu này đƣợc thiết lập qua cáp mạng nhƣ dây hoặc cáp quang hoặc
phƣơng tiện không dây nhƣ Wi-Fi. Các node mạng có khả năng khởi động,
định tuyến và chấm dứt dữ liệu, đƣợc xác định bởi các địa chỉ mạng và bao
gồm tất cả các thiết bị (máy tính cá nhân, điện thoại, máy chủ, bộ định tuyến,
chuyển mạch,…) có thể kết nối với nhau trực tiếp hoặc gián tiếp đƣợc hỗ trợ
bởi các giao thức truyền thông mạng (network protocol). Mạng máy tính có
thể giúp con ngƣời truy cập vào số lƣợng lớn các ứng dụng và dịch vụ có thể
có do những ngƣời khác chia sẻ. [5]
Hệ thống mạng máy tính với những ƣu điểm nhƣ tăng tốc độ tìm kiếm
và download dữ liệu, dễ dàng trong việc giao lƣu trao đổi thông tin giữa
ngƣời và ngƣời, nối liền khoảng cách…đã và đang có nhiều ứng dụng trong
tất cả các lĩnh vực, nhất là trong thông tin liên lạc.
1.1.2 Mạng ngang hàng peer – to – peer
Mơ hình mạng ngang hàng (Peer-to-Peer Network) hay mạng ngang
hàng là một cấu trúc đƣợc tạo nên bởi các máy tính liên kết với nhau, vai trị

của mỗi máy tính là nhƣ nhau, mỗi máy tính là một phần (peer) và duy trì sự


5

tồn tại của mạng ngang hàng mà không cần đến máy chủ hay các phần mềm
máy chủ.

Hình 1. 1: Mơ ìn k

ủv n n

n P2P

1.1.2.1 Phân loại P2P
Tùy vào sự phân quyền, cách thức trao đổi, thu nhận tài nguyên của các
máy tính trong mạng, để chia P2P làm hai loại kiến trúc chính.
Mạn P2P t uần tú là mơ hình thể hiện chính xác bản chất của mạng
P2P nhất, vì nó hồn tồn khơng có máy chủ trung tâm quản lý mạng mà mọi
máy tính đều có vai trị vừa là khách, vừa là chủ và khơng hề có các máy định
tuyến hoặc trung tâm định tuyến mà các máy tự định tuyến với nhau. Mọi
máy tính đều cân bằng về chức năng, các máy là các node (hay gọi là
servant).

ác mạng P2P thuần túy có thể kể đến nhƣ: Gnutella, Freenet,

Kademlia…


6


Hình 1. 2 Mạn P2P t uần tú

Kiến trúc này có khả năng mở rộng mạng nhanh, chịu lỗi hệ thống cao,
và mọi máy tính đều có tính tự chủ độc lập. Nếu có vấn đề xảy ra nhƣ một vài
node bị lỗi thì khơng gây ra lỗi tồn mạng và có thể dễ dàng bù đắp bằng các
node mới tham gia vào. ũng chính vì P2P thuần túy khơng có máy chủ trung
tâm để định tuyến nên tốc độ phát hiện thông tin chậm, dịch vụ không đƣợc
đảm bảo, và hành vi của hệ thống khó có thể ghi nhận đƣợc. [2]
Mạn P2P l

ép Sẽ có một máy chủ trung tâm dùng để lƣu trữ

thông tin của các máy khác, làm nhiệm vụ trả lời các truy vấn thông tin trong
mạng.

ác máy khách có vai trị lƣu trữ thơng tin, tài nguyên đƣợc chia sẻ,

cung cấp các thông tin chia sẻ tài nguyên của nó cho máy chủ. iểm khác biệt
nữa so với P2P thuần là có sử dụng các trạm định tuyến để xác định địa chỉ
IP của các máy khách. ó hai kiểu mạng lai ghép: mạng lai ghép với chỉ số
hóa tập trung, tức là có một máy chủ trung tâm bảo trì các chỉ số của dữ liệu
hoặc tài liệu hiện tại đang đƣợc chia sẻ bởi các máy khách, mỗi máy khách
giữ gìn một kết nối tới máy chủ trung tâm để gửi các yêu cầu, kiến trúc này
thƣờng đƣợc sử dụng trong mạng Napster. Hệ thống này tuy đơn giản nhƣng
hoạt động hiệu quả, tìm kiếm thơng tin nhanh, tồn diện và đảm bảo kết quả
tìm kiếm. Tuy vậy nó rất dễ bị lỗi và sụp đổ khi máy chủ trung tâm bị lỗi hoặc


7


bị tấn cơng, kích thƣớc cơ sở dữ liệu và khả năng đáp ứng yêu cầu là có giới
hạn trong phạm vi các máy tham gia mơ hình mạng này.

Discovery
server

data exchange
Hình 1. 3 Mạn l

v

ỉ số ó tập trun

Kiểu thứ hai là mạng lai ghép với chỉ số hóa phân tán, có một máy chủ
trung tâm đăng kí đƣợc sử dụng cho cả hệ thống và tạo điều kiện để dễ dàng
khám phá các node có trong mạng. ó một vài node đƣợc xem là quan trọng
hơn với các node cịn lại (super node), làm nhiệm vụ bảo trì các chỉ số cho
thông tin chia sẻ bởi tất cả các node mà đƣợc kết nối với nó và đƣợc ủy quyền
từ máy chủ trung tâm để thực hiện tìm kiếm trong phạm vi các node đã có kết
nối với super node. [2]
data exchange
Super
node
Super
node

Hình 1. 4 Mạn l

v


ỉ số p ân t n

1.1.2.2 Mạng P2P khơng có cấu trúc và có cấu trúc
ựa vào cấu trúc liên kết giữa các nút mạng trong mạng P2P ta có thể
phân loại thành 2 loại. [2]
Mạng P2P khơng có cấu trúc là mạng trong đó các liên kết giữa các nút
mạng đƣợc thiết lập một cách ngẫu nhiên, không theo một quy luật nào. Mỗi


8

máy tính mới tham gia vào mạng rất dễ dàng, nhƣng khi tìm kiếm thơng tin
thì hệ thống này khơng thể đảm bảo thành cơng cao vì khơng có mối tƣơng
quan nào giữa một node và dữ liệu của nó đang lƣu trữ. Mỗi lần một node cần
thơng tin, vì khơng có định hƣớng, nên u cầu sẽ đƣợc gửi ngẫu nhiên tới
một số node trong mạng, số lƣợng node càng lớn, khả năng tìm thấy càng cao
nhƣng sẽ làm tốn rất nhiều băng thông mạng. Napster,

nutella, Fasttrack và

e onkey2000 là những mạng đại diện cho kiểu P2P khơng có cấu trúc này.
Mạng P2P có cấu trúc khắc phục đƣợc nhƣợc điểm của mạng P2P
khơng có cấu trúc bằng cách sử dụng hệ thống

HT ( istributed Hash Table

– ảng băm phân tán). Hệ thống định nghĩa liên kết giữa các nút mạng theo
thuật toán cụ thể, xác định chặt chẽ mỗi node sẽ chịu trách nhiệm đối với
phần dữ liệu chia sẻ trong mạng. Khi tìm kiếm và lấy thơng tin, dữ liệu sẽ

đƣợc nhanh chóng hiệu quả hơn khi đã có một định tuyến rõ ràng.

hord,

CAN, Kademlia, Pastry và Tapestry là các đại diện cho kiểu mạng P2P có cấu
trúc này.
1.1.2.3 Cơ chế tìm kiếm trong hệ thống mạng P2P
ách tìm kiếm ở các thế hệ mạng P2P rất khác nhau, với cấu trúc tập
trung ở thế hệ thứ nhất đến thế hệ thứ hai với cơ chế ngập lụt và cuối cùng là
thế hệ thứ ba mới nhất dựa vào bảng băm phân tán.
Tìm kiếm với chỉ số hóa tập trung và kho chứa đƣợc sử dụng trong
mạng lai ghép, máy khách kết nối với máy chủ trung tâm để đƣợc định tuyến
tới nơi mà máy khách yêu cầu có dữ liệu là tốt nhất và khi đó hai máy khách
trực tiếp trao đổi với nhau mà không cần máy chủ. [3]
Làm ngập lụt các câu hỏi (Flooding broadcast of queries) đƣợc sử dụng
trong mạng P2P thuần, để tìm kiếm thơng tin cần, một node gửi thơng tin tới
tất cả các node mà nó kết nối, cứ nhƣ thế yêu cầu này đƣợc gửi đi cho đến khi
nhận đƣợc trả lời từ node có chứa thơng tin mà node yêu cầu cần.


9

Mơ hình định tuyến dựa trên bảng băm phân tán (Routing model) là
cách tìm kiếm tiên tiến nhất đƣợc sử dụng trong mạng P2P thuần. Mỗi tài
nguyên sẽ băm tên và nội dung để tạo ra một I , sau đó sẽ đƣợc lƣu trữ ở một
node mà có I gần với I

của tài nguyên đó. Khi một node khác có u cầu,

thì chỉ việc băm tên của tài ngun đó và gửi thơng tin đến tất cả các node

hàng xóm trong bảng định tuyến của mình đến khi nhận đƣợc trả lời từ node
đang lƣu giữ tài nguyên.
1.1.2.4 Các ứng dụng của P2P
ó rất nhiều các ứng dụng dựa trên nền tảng P2P, trong số đó tiêu biểu
nhƣ: Giao tiếp (communication), chia sẻ file (file sharing), băng thông
(bandwidth), không gian lƣu trữ (storage), các chu trình xử lý (processor
cycles). Hiện tại mạng chúng ta sử dụng đều dựa trên nền tảng P2P này, đó
thực sự là một phát minh vĩ đại nhất của loài ngƣời.
1.1.3 Giao thức
Giao thức giao tiếp hay cịn gọi là giao thức truyền thơng, giao thức
liên mạng, giao thức tƣơng tác, giao thức trao đổi thông tin (tiếng Anh là
communication protocol) - trong công nghệ thông tin gọi tắt là giao thức
(protocol), tuy nhiên, tránh nhầm với giao thức trong các ngành khác - là một
tập hợp các quy tắc chuẩn dành cho việc biểu diễn dữ liệu, phát tín hiệu,
chứng thực và phát hiện lỗi dữ liệu - những việc cần thiết để gửi thơng tin qua
các kênh truyền thơng, nhờ đó mà các máy tính (và các thiết bị) có thể kết nối
và trao đổi thông tin với nhau.

ác giao thức truyền thông dành cho truyền

thơng tín hiệu số trong mạng máy tính có nhiều tính năng để đảm bảo việc
trao đổi dữ liệu một cách đáng tin cậy qua một kênh truyền thơng khơng hồn
hảo. ác giao thức có thể đƣợc thực hiện bằng phần cứng, phần mềm hoặc kết
hợp cả hai.[3]


10

1.2 M N


P ÂN TÁN

1.2.1 Tổng quan
Mạng phân tán ( istributed Network) là mạng tập hợp các máy tính
độc lập không phụ thuộc lẫn nhau đƣợc kết nối với nhau có chức năng và dữ
liệu trải rộng trên các trạm (máy tính) giao tiếp với nhau bằng các giao thức
phân tán, có khả năng phối hợp với nhau, chia sẻ tài nguyên hoặc thực hiện
một nhiệm vụ chung. Mỗi máy tính hoạt động độc lập và giao tiếp với ngƣời
dùng nhƣ một hệ thống tồn vẹn. [4]
Vì các lý do khác nhau, chủ yếu do ngƣời dùng phân tán (địa lý) và dữ
liệu phân tán (địa lý) nên việc thúc đẩy phát triển một mạng có tính mở, khả
chuyển, co dãn, thay đổi phạm vi linh hoạt (quy mơ), tính sẵn dùng cao, ngay
cả khi một phần hệ thống bị lỗi.

ặc biệt do sự phát triển không ngừng của

các thiết bị di dộng và siêu di động đã tạo ra các mạng kết nối vô cùng lớn với
khả năng xử lý gấp nhiều lần, vì vậy các phần mềm phân tán và mạng phân
tán đƣợc phát triển do các nhu cầu ứng dụng, tích hợp các ứng dụng riêng rẽ
đang có để phát triển thêm, sử dụng các nguồn tài ngun đang có nhƣ lƣới
tính tốn, quản lý dữ liệu có sẵn, đều có khả năng tích hợp vào mạng phân tán
mà không cần phải xây dựng lại từ đầu nhờ vào nền tảng chi phí và hiệu năng
của máy tính và truyền thơng hiện tại. [4]
Nhƣng đi kèm với những thuận lợi đã có thì vẫn có những khó khăn
nhất định khi phát triển mạng phân tán. Vì có vơ số phần cứng, phần mềm
hồn tồn khơng giống nhau tham gia, nên việc giao tiếp khó khăn, một phần
chịu ảnh hƣờng từ đƣờng truyền mạng (băng thông, tỉ lệ lỗi truyền, tính sẵn
dùng trong giờ cao điểm) nên việc truyền dữ liệu chƣa chắc thành công, các
ràng buộc về thứ tự sự kiện (các kiểu đồng bộ khác nhau) và ràng buộc về
topology truyền thông (trao đổi thông điệp) của ứng dụng nên việc phát triển

khó khăn hơn các hệ thống mạng thông thƣờng.


11

ụ thể hơn, trong quy trình phát triển mạng phân tán, có các câu hỏi
thƣờng khơng có một câu trả lời tồn vẹn và đầy đủ từ đó dẫn tới với dự tính
sai chi phí, nguồn lực, thời gian. Từ đó dẫn tới việc phát triển mạng phân tán
thất bại, gia tăng chi phí và thời gian phát triển. Ví dụ nhƣ các thành phần có
khả năng tƣơng tác với nhau hay khơng, nếu có thì ở mức độ nào, và ảnh
hƣởng thế nào tới kiến trúc chung của hệ thống? [6]. Việc che dấu ngƣời dùng
về sự phân tán thực hiện ở mức nào, một phần hay toàn bộ? Từ đó ảnh hƣởng
nhƣ thế nào tới kiến trúc và các kĩ thuật có liên quan? Nếu một hệ thống hỏng
có làm cả hệ thống hỏng hay khơng? Nếu muốn hệ thống có độ chịu lỗi cao
thì phải thực hiện những gì? Và cịn rất nhiều các câu hỏi có liên quan tới hiệu
năng hoạt động, đồng bộ giữa các thành phần, đảm bảo tính sẵn dùng và dễ
dàng thêm hoặc loại bỏ một thành phần mà không làm ảnh hƣởng tới tính bảo
mật của hệ thống. [4]
1.2.2 C

t

n p ần ủ

ệ phân tán

Hệ phân tán gồm hai thành phần chính, có thể nêu cụ thể nhƣ sau:
Phần cứng hệ phân tán: ao gồm các máy chủ và các hệ thống máy con
đƣợc đặt ở những vị trí khác nhau và kết nối với nhau qua mạng máy tính.
Phần mềm hệ phân tán: sẽ gồm 3 hệ thống sau:

 DOS (Distributed Operating Systems) - Hệ điều hành phân tán: Hệ điều
hành gắn chặt với hệ thống phần cứng (máy đa vi xử lý hoặc máy tính
đồng bộ).
 NOS (Network Operating Systems) - Hệ điều hành mạng: cài đặt trên
máy tính cục bộ. ung cấp dịch vụ cục bộ cho các máy tính khác.
 Middleware: ài đặt các dịch vụ cơ bản để thực hiện, phát triển các ứng
dụng.
1.2.3 K ến trú

ủ

ệ t ốn p ân t n

Kiến trúc của hệ thống phân tán bao gồm các thành phần:
 Multicomputer ( a máy tính): ác node tính tốn riêng biệt kết nối với
nhau qua một mạng máy tính. Mỗi node có tài nguyên riêng (bộ vi xử


12

lý, bộ nhớ lƣu trữ,…) liên lạc với nhau qua mạng, và các node này có
thể đồng nhất hoặc khơng đồng nhất với nhau về kiến trúc vật lý.


istributed Opera System (Hệ điều hành phân tán): kiến trúc chứa các
dịch vụ quan trọng: bộ nhớ phân tán dùng chung, phân công tác vụ giữa
các bộ vi xử lý, đồng bộ giữa các node, có tính trong suốt cao. Một số
hệ điều hành phân tán nhƣ: Amoeba, Plan 9, horus, Mungi.

Hình 1. 5 K ến trú


ệ t ốn p ân t n

 Middleware: ó giao diện lập trình phân tán độc lập với hệ điều hành,
có khả năng tăng tính trong suốt (che dấu tính khơng đồng nhất), cung
cấp các dịch vụ cơ bản để đồng nhất hoạt động giữa các node.

Hình 1. 6 K ến trú M

lew re


13

1.2.4

u, k u ết đ ểm
Với những nội dung đƣợc nêu ở trên, việc mạng phân tán có những ƣu

điểm và khuyết điểm là điều hiển nhiên, đƣợc nêu nhƣ sau:
Ƣu điểm đầu tiên của mạng phân tán đó chính là chi phí, việc sử dụng
các thành phần đã có sẵn, từ đó phát triển thêm thì thu đƣợc tỷ lệ giá/hiệu
năng tốt hơn. Tiếp theo, hiệu năng tốt chính là do sử dụng kết hợp khả năng
lƣu trữ và xử lý của nhiều node, có thể đạt đƣợc mức độ hiệu năng vƣợt ra
ngồi tầm của các máy tính trung tâm. Với khả năng mở rộng cao, các tài
nguyên nhƣ khả năng lƣu trữ và xử lý có thể đƣợc tăng theo cấp số cộng.

i

cùng với đó là độ tin cậy cao do các thành phần luôn luôn đƣợc bổ sung, thay

thế, khi một node trong mạng hỏng thì hệ thống vẫn có thể tiếp tục hoạt động
bình thƣờng. uối cùng, nó có tính phân tán cố hƣu vì một số ứng dụng web,
phần mềm đã có tính phân tán một cách tự nhiên, từ đó chỉ việc phát triển
thêm, khơng cần phải nâng cấp hoặc bổ sung gì. [3]
i kèm với các ƣu điểm đã có, mạng phân tán cũng có một số khuyết
điểm cố hữu vẫn cần phải giải quyết trong tƣơng lai nhƣ việc bảo mật mạng
phân tán dễ bị xâm phạm hơn do bao gồm nhiều thành phần, mà mỗi thành
phần đều có đặc tính khác nhau, từ đó dễ bị tổn thƣơng hơn mạng tập trung.
ồng thời, do việc giao tiếp thực hiện qua mạng, khi đó có một số điều ảnh
hƣởng tới hệ thống nhƣ băng thông, độ ổn định của đƣờng truyền mạng, thêm
vào đó là các thành phần mới của mạng khơng hề có phần cứng đồng bộ
giống nhau một trăm phần trăm nên việc sai khác sẽ diễn ra, ảnh hƣởng tới hệ
thống, tệ hơn có thể gây thất bại cho hệ thống.

ồng nghĩa với việc độ phức

tạp của phần mềm chạy trên hệ thống là rất cao, khó hơn so với phần mềm
truyền thống, dẫn tới chi phí phát triển cao, khả năng bị lỗi cao hơn.


14

1.3 DHT – Bản băm p ân t n
1.3.1 Tổng quan DHT
DHT (Distributed Hash Table –

ảng băm phân tán) đƣợc sử dụng ở

thế hệ thứ ba của mạng P2P, tức là mạng P2P có cấu trúc.


HT là lớp các hệ

thống phân tán phi trung tâm mà cung cấp một dịch vụ tra cứu tƣơng tự nhƣ
một bảng băm: các cặp (key, value) đƣợc lƣu trữ trong

HT, và một node

mạng có tham gia bất kỳ có thể lấy đƣợc giá trị có quan hệ với một khóa cho
trƣớc một cách hiệu quả, với độ tin cậy cao, khả mở (Scalable) và có khả
năng chịu lỗi. Trách nhiệm bảo quản ánh xạ từ khóa tới giá trị đƣợc phân tán
giữa các node, sao cho một thay đổi tại một tập hợp các node tham gia chỉ gây
ra rắc rối tối thiểu.

iều này cho phép dùng

HT cho số lƣợng rất lớn các

node mạng và liên tục xử lý đƣợc các sự kiện các node vào và ra khỏi mạng
và các thất bại. Ngoài ra

HT cịn hỗ trợ ba thao tác: chèn, tìm kiếm và xóa

các cặp (key, value). [5]
Trong

HT, key đƣợc tính ra từ value, tất cả các key đều nằm trên

cùng không gian địa chỉ, để xác định node nào lƣu cặp (key, value) đó thì mỗi
node phải có một I


trong khơng gian địa chỉ giống nhƣ không gian địa chỉ

của key. Khi đó, một node gửi thơng điệp u cầu lƣu dữ liệu tới các node
khác thông quan routing table (bảng định tuyến). Q trình chuyển tiếp thơng
điệp qua mạng cho đến khi gặp đƣợc node có I gần với I của value nhất thì
lúc này cặp (key, value) sẽ đƣợc lƣu tại đây. Tƣơng tự nhƣ vậy, để tìm một
value thì node cần tìm dữ liệu sẽ gửi đi thơng điệp tìm kiếm qua mạng, đến
khi có node chứa value đó hồi đáp và trả dữ liệu cho node tìm kiếm.
HT tạo nên cơ sở hạ tầng cho việc xây dựng các dịch vụ phức tạp
hơn, chẳng hạn nhƣ các hệ thống file phân tán, chia sẻ file trong mạng đồng
đẳng, hệ thống phân phối nội dung (content distribution), web cache có tính
hợp tác, multicast, anycast, dịch vụ tên miền và instant messaging. ác mạng


15

phân tán nổi tiếng sử dụng

HT bao gồm

itTorrent distributed tracker,

eDonkey network, Storm botnet, YaCy, và Coral Content Distribution
Network. HT đƣợc sử dụng trong rất nhiều mạng để phân tán nội dung, chia
sẻ tài nguyên, nền tảng cho truyền thông an toàn.
nhƣ:

hord,

HT hỗ trợ các giao thức


AN, Kademlia, Pastry, Tapestry, Kelips. Nó đƣợc sử dụng

trong rất nhiều mạng để phân tán nội dung, chia sẻ tài nguyên, nền tảng cho
truyền thông an tồn. [5]
1.3.2 ặc tính của DHT:
Ngƣợc lại với hệ thống P2P không cấu trúc, mỗi HT của node sẽ quản
lý một số lƣợng nhỏ các tham khảo tới các node khác.

HT cho phép hoạt

động phân tán, không nhất thiết duy trì một server trung tâm để điều khiển
hoạt động của mạng P2P. ũng vì vậy, các ứng dụng P2P sử dụng HT là các
ứng dụng P2P thuần nhất.
Tức là có O(log N) các tham khảo, ở đây N mơ tả số node có trong hệ
thống.

ằng việc ánh xạ các node và các mục dữ liệu vào trong một không

gian địa chỉ chung, việc định tuyến tới một node để dẫn đến các mục dữ liệu
trong node có trách nhiệm với dữ liệu này.
ác câu truy vấn đƣợc định tuyến qua một số lƣợng nhỏ các node để tới
node đích. ởi vì một tập nhỏ tham khảo sẽ đƣợc mỗi node quản lý, một mục
dữ liệu có thể đƣợc xác định vị trí bởi việc định tuyến thơng qua O(log N)
các bƣớc. Node khởi tạo u cầu tìm kiếm có thể là bất kỳ trong HT.
ằng việc phân tán các chỉ số nhận dạng của node và mục dữ liệu gần
nhƣ khắp hệ thống, tải để cho việc thu nhận các mục sẽ đƣợc cân bằng đều
nhau giữa tất cả các node. Hệ thống vẫn hoạt động tốt với ngay cả những
lƣợng node (hằng trăm, hàng nghìn node) và lƣu lƣợng trên mạng cực kì lớn.
ởi vì khơng một node nào đóng vai trị khác nhau trong hệ thống, nên

sự hình thành các điểm nóng hay tắc nghẽn có thể tránh đƣợc. Ngoài ra, sự


16

dời đi hay rút khỏi (còn gọi là churn) của một node đƣợc xem nhƣ là khơng
có ảnh hƣởng tới chức năng của

HT.

o đó,

HT đƣợc xem nhƣ là có khả

năng đứng vững, chống lại lỗi ngẫu nhiên và tấn công trên diện rộng.
Một chỉ mục phân tán cung cấp một câu trả lời dứt khoát về kết quả.
Nếu một mục dữ liệu đƣợc lƣu trữ trong hệ thống, HT đảm bảo rằng dữ liệu
đó đƣợc tìm thấy. Và việc định tuyến, lấy dữ liệu nhanh và có thể hồn thành
trong thời gian ngắn (tỉ lệ logarit).
Một công nghệ chủ chốt đƣợc sử dụng để đạt đƣợc những kết quả nhƣ
bất kỳ node nào chỉ cần liên hệ với một vài node trong hệ thống, vì thế chỉ
cần một số lƣợng hạn chế các cơng việc cần làm mỗi khi có sự thay đổi thành
viên trong mạng. Một vài thiết kế

HT có khả năng loại bỏ những node có

thể gây nguy hiểm cho mạng và cho phép có thể dấu tên.

uối cùng


HT

phải giải quyết những vấn đề của hệ thống phân tán truyền thống nhƣ cân
bằng tải, tính tồn vẹn của dữ liệu…
1.3.3 Cấu trúc của DHT
ấu trúc của một

HT có thể đƣợc phân thành một số thành phần

chính:
 Một khơng gian khóa (keyspace) trừu tƣợng, chẳng hạn tập các xâu
kích thƣớc 160-bit.
 Một phƣơng án phân hoạch khơng gian khóa (keyspace partitioning)
chia tách sở hữu khơng gian khóa này giữa các node thành viên.
 Một mạng overlay kết nối các node, cho phép chúng tìm node chủ của
một khóa nào đó trong khơng gian khóa.
Một khi các thành phần này đƣợc lắp ráp vào đúng chỗ, một tình huống
điển hình của việc sử dụng

HT cho việc lƣu trữ và lấy dữ liệu nhƣ sau. Giả

sử khơng gian khóa là một tập các xâu 160-bit.

ể lƣu trữ một file với

filename và data cho trƣớc vào HT, thực hiện băm SHA-1 cho filename, tạo


17


một khóa k kích thƣớc 160-bit, và thơng điệp put(k,data) đƣợc gửi tới một
node bất kì tham gia HT. Thơng điệp này đƣợc gửi chuyển tiếp từ node này
tới node khác qua mạng overlay cho đến khi nó đến đƣợc node duy nhất chịu
trách nhiệm cho khóa k theo nhƣ quy hoạch khơng gian khóa đã quy định, cặp
(k,data) sau đó đƣợc lƣu trữ tại node này. Từ đó, một node bất kì có thể lấy
nội dung của file bằng cách lại thực hiện hàm băm cho filename để lấy khóa k
và u cầu một node

HT bất kì tìm dữ liệu đƣợc liên hệ với khóa k bằng

một thơng điệp get(k). Thông điệp này sẽ lại đƣợc định tuyến theo mạng
overlay để tới đƣợc node chịu trách nhiệm cho khóa k, node này sẽ trả lời
bằng data đƣợc lƣu trữ tại đó. [21]
1.3.3.1 Phân hoạch khơng gian khóa
a số các

HT dùng một dạng hàm băm ổn định (consistent hashing)

để ánh xạ từ khóa tới các node. Kĩ thuât này sử dụng một hàm δ(k1,k2) định
nghĩa một khái niệm trừu tƣợng là khoảng cách từ khóa k1 tới khóa k2, khái
niệm này không liên quan đến khoảng cách địa lý hay độ trễ mạng. Mỗi node
đƣợc gán một khóa đơn, gọi là định danh của node (I ). Một node với I i sở
hữu tất cả các khóa mà i là I gần nhất theo hàm khoảng cách δ.
Ví dụ Chord coi các khóa nhƣ là các điểm trên một đƣờng tròn, còn
δ(k1,k2) là độ dài cung tròn nối từ k1 tới k2 theo chiều kim đồng hồ. Khơng
gian khóa trịn này đƣợc phân thành các cung liền nhau, trong đó các điểm
mút là định danh của các node. Nếu i1 và i2 là hai I liên tiếp, thì node với I
i2 sở hữu tất cả các khóa nằm giữa i1 và i2.
onsistent hashing có tính chất quan trọng rằng việc xóa hay thêm một
node chỉ làm thay đổi tập khóa thuộc sở hữu các node có I liền đó, và không

ảnh hƣởng đến tất cả các node khác.

o mỗi thay đổi về sở hữu thƣờng

tƣơng ứng với một loạt các di chuyển tốn kém về băng thông khi các đối
tƣợng đƣợc lƣu tại node này chuyển sang node khác, việc tối thiểu hóa các


18

hoạt động tái tổ chức nhƣ vậy là cần thiết cho việc hỗ trợ có hiệu quả tần xuất
cao của hiện tƣợng node đến và đi. [21]
1.3.3.2 Mạng Overlay.
Mỗi node lƣu trữ một tập các liên kết tới các node khác (danh sách
hàng xóm hoặc bảng định tuyến). ác liên kết này tạo nên mạng overlay. Một
node lựa chọn danh sách hàng xóm của mình theo một cấu trúc nhất định,
đƣợc gọi là topo mạng.
Tất cả các topo

HT đều có một biến thể nào đó của tính chất quan

trọng nhất: với khóa k bất kì, một node hoặc có I sở hữu k hoặc có liên kết
tới một node ở gần k hơn, theo khái niệm khoảng cách không gian khóa đƣợc
định nghĩa ở trên. Khi đó, có thể dễ dàng định tuyến một thông điệp tới chủ
sở hữu của một khóa k bất kì bằng thuật tốn tham lam (thuật tốn khơng nhất
thiết tối ƣu tồn cục) sau đây: tại mỗi bƣớc, gửi chuyển tiếp thơng điệp tới
hàng xóm có I gần k nhất. Khi khơng có hàng xóm nào nhƣ vậy là khi ta đã
đến đƣợc node gần nhất - chủ sở hữu của khóa k theo định nghĩa ở trên. Kiểu
định tuyến này đôi khi đƣợc gọi là định tuyến theo khóa (key based routing).
HT cung cấp các dịch vụ lƣu trữ, tìm kiếm dữ liệu chỉ đơn giản thơng qua

hai hàm chèn (insert) và tìm kiếm (lookup).

Hình 1. 7: C

ứ năn

n

ủ bản băm p ân t n – DHT


19

1.3.4 Cơ sở bảng DHT
1.3.4.1 Quản lý dữ liệu phân tán.
Một

HT quản lý dữ liệu bằng việc phân tán nó qua một số node và

thực hiện một mơ hình định tuyến mà cho phép node tìm kiếm đạt hiệu quả
dựa trên một mục dữ liệu xác định đƣợc chỉ ra vị trí. Ngƣợc với tìm kiếm
“ngập lụt” trong hệ thống khơng cấu trúc, mỗi một node trong

HT sẽ có

trách nhiệm với một khoảng các thành viên của các mục dữ liệu. Ngồi ra,
mỗi node lƣu trữ một cái nhìn từng phần trong tồn bộ hệ thống phân tán mà
ở đó thực sự phân tán các thông tin định tuyến. ựa trên thơng tin này, thủ tục
tìm định tuyến tiêu biểu sẽ trải qua nhiều node, lấy đích ở gần mỗi một node,
cho đến khi node đích đƣợc tìm thấy. [21]

o đó, HT cho phép một chiến lƣợc thực hiện tiên phong để thu nhận
dữ liệu bằng cấu trúc tìm kiếm khơng gian và cung cấp một mơ hình định
tuyến trƣớc. Trong việc so sánh, thông tin định tuyến trong hệ thống khơng
cấu trúc chẳng có liên quan gì đến vị trí của các mục dữ liệu xác định mà chỉ
phản ánh sự kết nối giữa các node. ác kết quả của chiến lƣợc tác động trở
lại trong các câu truy vấn bằng việc làm “ngập lụt” các yêu cầu thông qua
mạng bởi vì việc định tuyến khơng thể trực tiếp tìm kiếm tới node đích. Với
một hệ thống trung tâm, chiến lƣợc tìm kiếm bị ẩn, việc định tuyến một truy
vấn là khơng cần thiết khi thủ tục tìm kiếm tự nó đƣợc hạn chế với một hệ
thống đơn.
1.3.4.2 Định địa chỉ trong DHT.
HT giới thiệu không gian địa chỉ mới vào trong dữ liệu bằng việc ánh
xạ. Không gian địa chỉ tiêu biểu bao gồm một số lớn các giá trị nguyên,…
HT thu đƣợc chỉ số phân tán bằng việc chuyển một phần liền kề của không
gian địa chỉ tới mỗi node thành viên để đƣa ra một giá trị từ không gian địa


20

chỉ, phép tốn chính đã đƣợc cung cấp bởi một hệ thống HT là một hàm tìm
kiếm, thí dụ để xác định node có vai trị đối với giá trị này. [20]

Hình 1. 8 Một k ơn

đến 65 535 C

n đị
k ôn

Hƣớng tiếp cận


ỉ tu ến t n v
n đị

trị số n u ên từ 0

ỉ l p ân vùn tron số 8 peer

HT khác nhiều trong việc làm thế nào để quản lý và

phân vùng không gian địa chỉ. Trong hầu hết các trƣờng hợp, các mơ hình này
tự thêm vào các giải thích về địa lý của khơng gian địa chỉ. Một ví dụ đơn
giản, tất cả các phép tốn trong khơng gian địa chỉ có thể đƣợc hiện modul
với số các thành viên trong vòng tròn.
Trong một hệ thống

HT, mỗi mục dữ liệu đƣợc thiết kế là một I ,

một giá trị duy nhất trong không gian địa chỉ. Giá trị này có thể đƣợc lựa
chọn một cách tự do bởi ứng dụng, nhƣng nó thơng thƣờng nhận đƣợc từ
chính dữ liệu của nó thơng qua một hàm băm chống và trạm, chẳng hạn nhƣ
SHA-1, thí dụ, chỉ số I
hay file nhị phân.

o đó,

của một file có thể là kết quả của việc băm tên file
HT có thể lƣu trữ file đó tại node tƣơng ứng với

phần chia của không gian địa chỉ mà chứa chỉ số đó.

ác giao diện ứng dụng

HT đƣợc rút từ sự kiện của chúng và đƣa ra

đơn giản nhƣng có hoạt động chung.

ựa trên chức năng tìm kiếm, hầu hết

HT thực hiện một không gian lƣu trữ nhƣ là một bảng băm. o đó, hàm put
chấp nhận một I và dữ liệu tùy ý (giá trị băm của file name và file content)
đƣợc lƣu trữ dữ liệu đó (trên node tƣơng ứng với I đó). hỉ số I này và dữ
liệu thơng thƣờng đƣợc tham khảo từ cặp (key, value). Tƣơng ứng, hàm get


21

thu nhận dữ liệu liên quan với một I cụ thể. Với giao diện chung này và mơ
hình định địa chỉ đơn giản, HT có thể đƣợc sử dụng cho các ứng dụng rộng
lớn và đa dạng. ác ứng dụng tự kết hợp tùy ý ngữ nghĩa với các định dạng
ID ví dụ việc băm các từ khóa tìm kiếm, chỉ số cơ sở dữ liệu, vị trí địa lý, thƣ
mục phân cấp tên nhị phân. o đó, các ứng dụng khác nhau nhƣ các hệ thống
file phân tán, cơ sở dữ liệu phân tán, và các hệ thống định tuyến đã đƣợc phát
triển trên HT. [20]
Hầu hết các hệ thống HT cố gắng trải rộng tải của các thông điệp định
tuyến và dữ liệu lƣu trữ trên các node thành viên một cách bằng nhau. Tuy
nhiên, có ít nhất ba nguyên nhân mà tại sao một số node trong hệ thống có thể
thực hiện tải cao hơn các node còn lại: một node quản lý một phần chia lớn
của không gian địa chỉ, một node tƣơng ứng với một phần chia không gian địa
chỉ với một số lƣợng lớn các mục dữ liệu, hay một một node quản lý các mục
dữ liệu của các node thành viên thông dụng. Trong hồn cảnh này, thì thêm

vào các mơ hình cân bằng tải có thể giúp cho việc tải đƣợc đồng đều trên tất
cả các node.
Ví dụ, một node có thể truyền tƣơng ứng một phần khơng gian địa chỉ
của nó tới các node cịn lại, hay nhiều node có thể quản lý cùng một không
gian địa chỉ.
1.3.4.3 Định tuyến
Việc định tuyến là chức năng chính của

HT.

ựa trên thủ tục định

tuyến, các thơng điệp với I đích của nó đƣợc truyền tới node

HT mà quản

lý I đích. o đó, thuật tốn tìm kiếm của HT sẽ xử lý các vấn đề tìm kiếm.
ác hệ thống

HT đang tồn tại thực hiện một hƣớng tiếp cận đa dạng

cho định tuyến. Tuy nhiên, về nguyên lý cơ bản là mỗi node đƣợc cung cấp
với một số tầm nhìn hữu hạn trong tồn bộ hệ thống bằng việc lƣu trữ trên nó
một số giới hạn các đƣờng link đến các node khác. Khi một node nhận đƣợc


22

một thơng điệp cho một địa chỉ I đích trong trƣờng hợp nó khơng có địa chỉ
đó, thì nó sẽ chuyển thơng điệp đó tới một trong những node mà nó biết. Q

trình xử lý này đƣợc lặp lại tuần hồn đến khi node đích đƣợc tìm thấy.
Việc lựa chọn node nhảy kế tiếp đƣợc xác định bởi thuật toán định
tuyến và mơ hình định tuyến. Một hệ mét tiêu biểu là node gần: các thông
điệp luôn đƣợc chuyển tới node quản lý số lƣợng các I gần nhất với đích của
I của thơng điệp. Ý tƣởng là, chẳng hạn nhƣ một mơ hình định tuyến tin cậy
một thơng điệp tới đích của nó với số bƣớc nhảy nhỏ. Thì rõ ràng, nó là một
thử thách để thiết kế các thuật tốn định tuyến và các ma trận.

o đó, thơng

tin các node lỗi và định tuyến lỗi đƣợc giới hạn hay ít xung đột trong q
trình định tuyến chính xác và co dãn hệ thống.
1.3.4.4 Lưu trữ dữ liệu
ó hai phƣơng pháp lƣu trữ dữ liệu trong HT, trong

HT có sử dụng

lƣu trữ trực tiếp, dữ liệu sẽ đƣợc sao chép nên trên node tƣơng ứng của nó.

(a) Lƣu trữ trực tiếp
Hình 1. 9

p

(b) Lƣu trữ gián tiếp
ơn p

p l u ữ l ệu tron D T

Ƣu điểm của mô hình này là dữ liệu đƣợc lƣu trữ trực tiếp vào hệ thống

P2P và node đó thêm vào nó rồi sau đó rời khỏi

HT mà node đó khơng có

dữ liệu trở thành không tồn tại. Nhƣợc điểm là quá tải trong việc lƣu trữ và
băng thông của mạng. Khi một node có thể bị lỗi, dữ lệu cần phải đƣợc
chuyển tới các node khác để tăng khả năng tồn tại. Thêm vào đó, với các dữ
liệu lớn thì một số lƣợng lớn không gian lƣu trữ cho các node.