Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

TIỂU LUẬN MÔN HỌC
MẠNG THẾ HỆ MỚI(NGN)
TÊN ĐỀ
TÀI
MẠNG NGANG HÀNG VÀ ĐỊNH TUYẾN
TRONG MẠNG NGANG HÀNG (P2P)
Học viên 1. LÊ PHƯỚC CHUNG
2. NGUYỄN HUY ANH
GVHD : PGS.TS NGUYỄN HỮU THANH
Chuyên ngành : Kỹ thuật điện tử
Khoá : K26
Đà Nẵng, năm 201
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 1
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
LỜI MỞ ĐẦU
Mạng ngang hàng (tiếng Anh: peer-to-peer network), còn gọi là mạng đồng đẳng, là
một mạng máy tính trong đó hoạt động của mạng chủ yếu dựa vào khả năng tính toán và
băng thông của các máy tham gia chứ không tập trung vào một số nhỏ các máy chủ trung
tâm như các mạng thông thường. Mạng đồng đẳng thường được sử dụng để kết nối các
máy thông qua một lượng kết nối dạng ad hoc. Mạng đồng đẳng có nhiều ứng dụng. Ứng
dụng thường xuyên gặp nhất 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 như điện thoại VoIP.
Một mục đích quan trọng của mạng đồng đẳng là trong mạng tất cả các máy tham
gia đều đóng góp tài nguyên, bao gồm băng thông, lưu trữ, và khả năng tính toán. Do đó
khi càng có nhiều máy tham gia mạng thì khả năng tổng thể của hệ thống mạng càng lớn.
Ngược lại, trong cấu trúc máy chủ-máy khách, nếu số lượng máy chủ là cố định, thì khi
số lượng máy khách tăng lên khả năng chuyển dữ liệu cho mỗi máy khách sẽ giảm xuống

Mạng ngang hàng là một hệ thống phân tán đặc biệt trong tầng ứng dụng, ở đó
mỗi cặp điểm nút có thể giao tiếp với nhau thông qua giao thức định tuyến trọng các tầng
mạng ngang hàng. Mỗi điểm nút giữ 1 đối tượng dữ liệu nào đó có thể là nhạc, ảnh, tài
liệu, vv Mỗi điểm nút có thể truy vấn tới đối tượng nó cần từ các điểm nút khác thông
qua kết nối logic trong tầng mạng ngang hàng.
Overlay network:Là mạng máy tính được xây dựng trên nền của một mạng
khác. Các nodes trong mạng overlay
đượ
c
x
e
m
là nối với nhau bằng liên kết ảo (logical
links), mỗi liên kết ảo có thể bao gồm rất nhiều các liên kết vật lí của mạng nền.
Rất nhiều các mạng P2P được gọi là overlay networks vì nó được xây dựng và hoạt
động trên nền của Internet. VD: Gnutella, Freenet, DHTs ….
Dial-up Internet
cũng là một overlay network trên nền
telephone network.
1.3. So sánh mô hình P2P với mô hình Client/Server:
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 5
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
P2P Cl
ie
nt
/
S
er
ve
r

- Không cần server riêng, các client
chia sẻ tài nguyên. Khi mạng càng
được mở rộng thì khả năng hoạt
động của hệ thống càng tốt.
- Rẻ.
+ Ưu điểm:
- Tốc độ truy cập nhanh.
- Khả năng mở rộng cao.
- Hoạt động với bất kì loại ứng dụng
nào.
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 6
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
+ Nhược
đ
iể
m:
- Chậm.
- Không tốt cho các ứng dụng CSDL.
+ Nhược
đ
iể
m:
- Cần server riêng (nghẽn cổ chai).
- Đắt.
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 7
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
Hình 1.2. Tổng quan đặc tính mạng P2P và mạng Client-Server
1.5. Phân loại mạng ngang hàng
Hai tiêu chí cơ bản để phân loại mạng ngang hàng:
Theo mục đích sử dụng:

máy chủ trung tâm.
Hình 1.3. Mô hình mạng lai ngang hang(Hibrid P2P)
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 9
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
\
Hình 1.3 Mô hình mạng Hibrid P2P cụ thể
Ưu điểm:
 Dễ xây dựng.
 Tìm kiếm file nhanh và hiệu quả.
Nhược điểm:
 Vấn đề luật pháp, bản quyền.
 Dễ bị tấn công.
 Cần quản trị (central server).
Napster là mạng ngang hàng đặc trưng cho hệ thống mạng ngang hàng của thế hệ
thứ nhất, chúng được dùng cho việc chia sẻ các file giữa các người dùng Internet, được
sử dụng rộng rãi, tuy nhiên nhanh chóng bị mất thị trường bởi yếu tố về luật pháp. Khái
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 10
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
niệm và kiến trúc của Napster vẫn còn được sử dụng trong các ứng dụng khác như:
Audiogalaxy, WinMX.
Với Napster, việc tìm kiếm file bị thất bại khi bảng tìm kiếm trên máy chủ vì lý do
nào đó không thực hiện được. Chỉ có các file truy vấn và việc lưu trữ được phân tán, vì
vậy máy chủ đóng vai trò là một nút cổ chai. Khả năng tính toán và lưu trữ của máy chủ
tìm kiếm phải tương xứng với số nút mạng trong hệ thống, do đó khả năng mở rộng mạng
bị hạn chế rất nhiều.
1.5.2. Mạng ngang hàng thuần túy (Pure Peer-to-peer System)
Mạng ngang hàng thuần túy là một dạng khác của thế hệ thứ nhất trong hệ
thống các mạng ngang hàng. Không còn máy chủ tìm kiếm tập trung như trong
mạng Napster, nó khắc phục được vấn đề nút 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 túy lại sử dụng cơ chế

việc định nghĩa các Super-peers.
 Các Super-peer tạo thành một mạng không cấu trúc, có sự khác nhau
giữa Super-peers và Client-peers trong mạng, mỗi Super-peer có nhiều
kết nối đến các Client-peers.
 Mỗi Supper-peer chứa một danh sách các file được cung cấp bởi các
Client-peer và địa chỉ IP của chúng vì vậy nó có thể trả lời ngay lập tức
các yêu cầu truy vấn từ các Client-peer gửi tới.
Ưu điểm:
 Hạn chế việc Flooding các query, làm giảm lưu lượng trong mạng, nhưng
vẫn tránh được hiện tượng nút cổ chai (do có nhiều Super-peers).
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 13
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
 Khắc phục được nhược điểm về sự khác nhau về CPU power,
bandwidth… ở mạng ngang hàng thuần túy, các Super-peer sẽ chịu tải
chính, các nút khác chịu tải nhẹ.
Nhược điểm:
 Mỗi điểm Super-peer trở thành điểm gây lỗi cho nhóm siêu ngang hàng
tương ứng trong trường hợp số lượng Client trong nhóm là rất lớn (tuy
nhiên, nhược điểm này đã được giải quyết bằng việc cải tiến mạng siêu
ngang hàng thông thường, đưa ra khái niệm siêu ngang hàng dư cấp k).
1.5.4 Mạng ngang hàng có cấu trúc (Structured)
Hệ thống mạng ngang hàng không cấu trúc thể hiện nhược điểm: không có gì
đảm bảo tìm kiếm sẽ thành công. Đối với tìm kiếm các dữ liệu phổ biến được chia
sẻ trên nhiều máy, tỉ lệ thành công là khá cao, ngược lại, nếu dữ liệu chỉ được chia
sẻ trên một vài máy thì xác suất tìm thấy là khá nhỏ. Tính chất này là hiển nhiên vì
trong mạng ngang hàng không cấu trúc, không có bất kì mối tương quan nào giữa
một máy và dữ liệu nó quản lý trong mạng, do đó 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ố lượng máy trong mạng càng
lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhược điểm khác của hệ thống
này là do không có định hướng, một yêu cầu tìm kiếm thường được chuyển cho một

Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
 Việc quản lí cấu trúc của topo mạng gặp khó khăn, đặc biệt trong trong
trường hợp tỷ lệ vào/ra mạng của các nút cao.
 Vấn đề cân bằng tải trong mạng.
Sự khác biệt về topology trên mạng overlay và mạng liên kết vật lý dẫn đến thời gian trễ
truy vấn trung bình cao.
1.6. Tìm thong tin quảng bá qua mạng P2P
1 Peer có thể có được 1 bản tin quảng bá bằng 1 trong 3 cách
Không có tin discovery
Discovery trực tiếp
Discovery gián tiếp
Hình 1.7.Peer discovery thong qua catched quảng bá
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 16
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
Hình 1.8.Discover trực tiếp
Hình 1.9 Discovery gián tiếp
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 17
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
Chương 2 : Định tuyến trong các hệ thống P2P thế hệ mới
2.1 Tổng quan định tuyến
2.1.1. Khái niệm
- Định tuyến là 1 quá trình chọn lựa các đường đi trên một mạng máy tính để gửi dữ liệu
qua đó.
- Định tuyến chỉ ra hướng và đường đi tốt nhất từ nguồn đến đích của các gói tin
(packer) thông qua các node trung gian là router.
2.1.2. Nguyên tắc
- Trong hoạt động định tuyến , người ta chia làm hai loại là định tuyến trực tiếp và định
tuyến gián tiếp. Định tuyến trực tiếp là định tuyến giữa hai máy tính nối với nhau vào
một mạng vật lý. Định tuyến gián tiếp là định tuyến giữa hai máy tính ở xa các mạng vật
lý khác nhau nên chúng phải thực hiện thông qua cac Gateway.

thống P2P hỗ trợ tính năng bảng hàm băm phân tán (DHT), trong số đó là Tapestry,
Pastry, Chord và CAN (Content-Addressable Networks). Trong các hệ thống này (còn
gọi là các hệ thống DHT), các file được ràng buộc với các khoá (key).
Hầu như các thuật toán hiện tại ứng dụng trong mạng ngang hàng thế hệ mới
(mạng có cấu trúc) đều định tuyến dựa trên key. Nó nhận một key, và để hồi đáp, chúng
định tuyến một bản tin tới node có trách nhiệm với key ấy. Các key là các chuỗi số có
một độ dài nào đấy. Cácnode là các bộ nhận dạng, lấy từ cùng không gian với các key (có
nghĩa là cùng số lượngdigits). Mỗi node lưu giữ một bảng định tuyến bao gồm một tập
nhỏ các node trong hệ thống.Các thuật toán định tuyến đều cố gắng định tuyến tới node
có key phù hợp và qua ít số hop nhất. Dưới đây là một số thuật toán định tuyến hiện tại:
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 19
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
2.2.2. Định tuyến dựa vào tiền tố (Prefix routing)
Định tuyến dựa vào tiền tố (Prefix routing) - PRR: đây là thuật toán đầu tiên cho
việc tìm kiếm
và
định tuyến của mạng ngang hàng. Bằng cách ánh xạ nhận dạng
đối tượng thành không gian địa
chỉ
của các peers, PRR định tuyến dựa trên key và có
thể trợ giúp các thao tác: đọc, chèn và xóa đối
tượng
lưu trữ trong mạng chồng phủ.
Nguyên lý của thuật toán này là nền tảng cho các thiết kế DHT
sau

này.
PRR là định
tuyến dựa trên hậu tố, là trường hợp đối xứng của định tuyến tiền tố. Định tuyến
hậu

mà
lưu giữ key. Tuy nhiên, Plaxton cũng có một số nhược điểm: yêu cầu hiểu biết
toàn bộ để xây
dựng
mạng chồng; peer gốc của đối tượng là điểm lỗi đơn; không có
sự chèn thêm hoặc xoá bỏ peer;
không

có
sự tránh các điểm tắc nghẽn nóng. Đối với
một hệ thống n node, mỗi node có O(log n) lân cận,
độ
dài đường định tuyến O(log
n) bước
nhảy
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 20
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
2.2.4. Thuật toán Tapetry
Tapestry sử dụng một biến thể của thuật toán Palaxon et al và thêm vào tính năng
động cho các pees trong mạng chồng. Sử dụng định tuyến dựa vào tiền tố, Tapestry sử
dụng thuật toán SHA-1 để băm các địa chỉ node thành các ID biểu diễn theo hệ số 2
b
.
Để hiểu rõ hơn về vấn đề ta sẽ tìm hiểu về thuật toán SHA-1 :
Khởi gán các biến:
H0:=0x67452301
H1:=0xEFCDAB89
H2:=0x98BADCFE
H3:=0x10325476
H4:=0xC3D2E1F0

• X
∨
Y phép toán OR trên bít giữa X và Y
• X
⊕
Y phép toán XOR trên bít giữa X và Y
• X phép toán NOT trên bít X
[ ]
( )
( ) ( )( )
( ) ( ) ( )







≤≤⊕⊕
≤≤∧∨∧∨∧
≤≤⊕⊕
≤≤∧¬∨∧
=
7960 ,
5940 ,
3920 ,
190 ,
,,
tZYX
tZYZXYX

0x5a827999
Hình 2.2 . Bảng Định Tuyến Chứa các Node có ID
Mỗi node lưu giữ một bảng định tuyến gồm log 2
b
(N) hàng và 2
b
cột. Hàng thứ
nhất trong bảng định tuyến chứa các node có ID khác với ID của node đó ở chỉ số thứ
nhất. Hàng thứ hai trong bảng định tuyến chứa các node có ID giống với ID của node đó
ở chữ số thứ nhất nhưng khác ở chữ số thứ hai. Các hàng còn lại của bảng định tuyến
cũng được tổ chức tương tự. Quá trình tìm kiếm được thực hiện bằng cách so sánh lần
lượt các chữ số tiền tố của ID. Ví dụ 4***
⇒
42**
⇒
422*
⇒
4227, quá trình này gọi là
“ánh xạ lân cận”. Bảng định tuyến của một node X được chia thành nhiều mức (log2
b
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 23
Mạng ngang hàng và định tuyến trong mạng ngang hàng (P2P)
(N)), mỗi mức i bao gồm các liên kết (2
b
-1) đến các node có tiền tố giống đến chữ số
thứ i-1 với ID của X. khi một node định tuyến đến node đích nó sẽ đi theo đường đến
node có ID gần giống với ID đích nhất (dựa theo bảng định tuyến). Sau mỗi chặng node
tiếp theo sẽ có mức cao hơn ít nhất là 1, vì vậy sau nhiều nhất là log 2
b
(N) chặng quá

về một vài node khác. Vì bảng định tuyến là phân tán, 1 node sẽ sử dụng hàm băm để giao
tiếp với các node khác. Khi mạng được thiết lập, 1 hệ thống gồm N-node, trong đó mỗi node
chứa thống tin về O(log N) node xung quanh nó, và tìm kiếm các node khác thông qua O(log
N) thông điệp tới các node đó. Chord duy trì thông tin định tuyến khi các node tham gia/rời
khỏi hệ thống. Với một hệ thống có tần suất cao, một node cũng chỉ cần gửi không quá
O(log2 N) thông điệp để định tuyến.
2.2.6.2. Ánh xạ khóa vào một nút trong Chord
Chord ánh xạ các khóa vào các nút, thường sẽ là một cặp key và value. Một value có thể là 1
address, 1 văn bản, hoặc 1 mục dữ liệu. Chord có thể thực hiện chức năng này bằng cách lưu
HVTH: Lê Phước Chung – Nguyễn Huy Anh Trang 25