ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
Nguyễn Tuấn Anh
NGHIÊN CỨU MỘT SỐ CƠ CHẾ BẢNG BĂM
PHÂN TÁN TRONG MẠNG NGANG HÀNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2010
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
Nguyễn Tuấn Anh
NGHIÊN CỨU MỘT SỐ CƠ CHẾ BẢNG BĂM
PHÂN TÁN TRONG MẠNG NGANG HÀNG
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Phạm Việt Bình
Thái Nguyên - 2010
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
Cộng hoà xã hội chủ nghĩa Việt Nam
KHOA CÔNG NGHỆ THÔNG TIN
Độc lập – Tự do – Hạnh phúc
***
LỜI CAM ĐOAN
Luận văn thạc sỹ này do tôi nghiên cứu và thực hiện dưới sự hướng dẫn của
Thầy giáo TS. Phạm Việt Bình. Để hoàn thành bản luận văn này, ngoài các tài liệu
tham khảo đã liệt kê, tôi cam đoan không sao chép các công trình nghiên cứu của
người khác.
Thái Nguyên, ngày 13 tháng 10 năm 2010
Ngƣời cam đoan
Nguyễn Tuấn Anh
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
LỜI CẢM ƠN
Trước hết tôi vô cùng biết ơn sâu sắc đến Thầy giáo TS. Phạm Việt Bình đ ã t ậ n
tình hướng dẫn tôi hoàn thành bản luận văn này.
Tôi xin chân thành cảm ơn Ban lãnh đạo Khoa Công nghệ thông tin, tập thể các
thầy, cô giáo trong Khoa cùng toàn thể bạn bè đã đóng góp ý kiến cho bản luận văn của
tôi.
Thái Nguyên, ngày 13 tháng 10 năm 2010
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Mục lục
Danh mục thuật ngữ, từ viết tắt ......................................................................................... 3
Danh mục thuật ngữ, t ừ viết tắt ........................................................................................ 3
Danh mục hình vẽ.............................................................................................................. 3
Danh mục bảng .................................................................................................................. 6
Danh mục thuật toán.......................................................................................................... 6
Lời mở đầu ..................................................................................................................... 7
Chƣơng 1. Khái quát về mạng ngang hàng và bảng băm ........................................... 8
1.1. Khái quát về mạng ngang hàng .................................................................................. 8
1.1.1. Khái niệm mạng ngang hàng .................................................................... 8
1.1.2. Quá trình phát triển của các hệ thống mạng ngang hàng ..................... 10
1.1.3. Phân loại các mô hình mạng ngang hàng ............................................. 14
a) Hệ thống mạng ngang hàng tập trung (Centralized) .......................... 15
b) Các mạng ngang hàng thuần túy (Pure) ............................................. 17
c) Các mạng ngang hàng lai (Hybrid)..................................................... 17
d) Mạng ngang hàng có cấu trúc............................................................. 18
1.1.4. Các lĩnh vực ứng dụng của mạng ngang hàng .............................................. 20
a) Giao tiếp (communication) ................................................................. 20
b) Chia sẻ Files (File sharing) ................................................................ 20
c) Băng thông (Bandwidth....................................................................... 22
d) Không gian lưu trữ (Storage Space) ................................................... 22
e) Các chu trình xử lý (Processor Cycles) ............................................... 25
1.1.5. Các phương pháp đánh giá mạng ngang hàng ...................................... 25
a) Phương pháp phân tích ....................................................................... 25
b) Phương pháp thử nghiệm .................................................................... 26
c) Phương pháp mô phỏng ...................................................................... 26
1.1.6. Các vấn đề đối với mạng mạng ngang hàng hiện nay ............................. 27
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1
1.2. Bảng băm .................................................................................................................. 28
1.2.1. Bảng băm (Hash table) .......................................................................... 28
1.2.2. Bảng băm phân tán - Distributed Hash Table (DHTs) .......................... 28
Chƣơng 2. Một số dạng bảng băm trong mạng ngang hàng ..................................... 31
2.1. Kademlia .................................................................................................................. 32
2.2. Tapestry .................................................................................................................... 34
2.3. Kelips........................................................................................................................ 39
2.4. Chord ........................................................................................................................ 41
Chƣơng 3. Chƣơng trình thử nghiệm .......................................................................... 51
3.1. Bài toán thực tế......................................................................................................... 51
3.2. Khảo sát các simulator mô phỏng mạng overlay ...................................................... 52
3.3. Phần mềm mô phỏng P2PSim .................................................................................. 54
3.3.1. Các bước mô phỏng với phần mềm P2PSim .......................................... 56
3.3.2. Kịch bản mô phỏng ................................................................................ 58
3.3.3. Đánh giá hiệu năng giao thức Chord trong mạng ngang hàng thông
qua các kết quả mô phỏng................................................................................ 58
a) Kết quả mô phỏng ảnh hưởng của Churn rate đến tỷ lệ tìm kiếm lỗi . 58
b) Kết quả mô phỏng ảnh hưởng của số lượng Node đến tỷ lệ tìm kiếm lỗi
................................................................................................................. 62
c) Kết quả mô phỏng ảnh hưởng của RTT đến tỷ lệ tìm kiếm lỗi ............ 65
d) Kết quả mô phỏng các tham số của Chord đối với tỷ lệ tìm kiếm lỗi . 68
Kết luận
................................................................................................................... 71
Tài liệu tham khảo ......................................................................................................... 73
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
Danh mục thuật ngữ, từ viết tắt
Tiếng Anh
Tiếng Việt
Từ viết tắt
Peer-to-peer
Mạng ngang hàng
P2P, P2P
Distributed Hash Table
Bảng băm phân tán
DHTs
Distributed_File_Systems
Hệ thống file phân tán
Peer-to-Peer file sharing
Hệ thống chia sẻ file ngang hàng
Content Distribution Systems Hệ thống nội dung phân tán
Peer
Đồng đẳng trong mạng ngang hàng
Node
Một thiết bị nối mạng (một peer)
Item
Một đơn vị dữ liệu
Structured
Có cấu trúc
Overlay
Mạng được xây dựng trên các mạng khác
Hash table
Bảng băm
Join
Gia nhập (mạng ngang hàng)
Leave
Rời khỏi (mạng ngang hàng)
Failure
Lỗi
Churn rate
Số lượng peer rời khỏi/gia nhập mạng
trong một khoảng thời gian
Danh mục hình vẽ
Hình 1.1. (a) Mô hình Client/Server ................................................................................. 9
Hình 1.1. (b) Mô hình P2P ................................................................................................ 9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
Hình 1.2. Overlay Network Diagram .............................................................................. 10
Hình 1.3. Mô hình centralized directory ........................................................................ 11
Hình 1.4. Mô hình flooding request ................................................................................ 12
Hình 1.5. Mạng ngang hàng tập trung thế hệ thứ nhất (Napster ..................................... 15
Hình 1.6. Mô hình mạng ngang hàng lai (Hybrid) .......................................................... 18
Hình 1.7. Chord Protocol ................................................................................................ 19
Hình 1.8. Ba cấu hình cho các giải pháp Direct Attached Storage ................................. 23
Hình 1.9. Sơ đồ một hệ thống NAS ................................................................................ 24
Hình 1.10. Sơ đồ một Storage Area Network ................................................................. 25
Hình 1.11. Distributed Hash Table .................................................................................. 30
Hình 2.1. Con trỏ của node 3 (0011) trong Kademlia .................................................... 32
Hình 2.2. Minh họa cách chọn bảng định tuyến của một node Tapestry ........................ 35
Hình 2.3. Đường đi của thông điệp từ node 5230 tới node 42AD .................................. 37
Hình 2.4. Ví dụ về Tapestry node publish item .............................................................. 38
Hình 2.5. Ví dụ về Tapestry node tìm kiếm item ............................................................ 39
Hình 2.6. Mạng Kelips trong đó các node phân tán trong 10 nhóm affinity và trạng thái
tại một node cụ thể .......................................................................................................... 40
Hình 2.7 (a) Một mạng Chord với 6 node, 5 item và N=16 ........................................... 43
Hình 2.7 (b) Nguyên tắc chung của bảng routing table .................................................. 43
Hình 2.7 (c) Bảng routing table của node 3 và node 11 .................................................. 43
Hình 2.8. Quá trình một node join vào mạng .................................................................. 48
Hình 2.9 (a) Bảng finger và vị trí của key sau khi node 6 join ....................................... 49
Hình 2.9 (b)Bảng finger và vị trí trí của key sau kho node leave ................................... 49
Hình 3.1 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 10s ............ 59
Hình 3.1 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 10s ........ 59
Hình 3.2 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 60s ............ 60
Hình 3.2 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 60s ........ 60
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
4
Hình 3.3 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 120s .......... 60
Hình 3.3 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 120s ...... 60
Hình 3.4 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 300s.......... 61
Hình 3.4 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 300s ...... 61
Hình 3.5 (a) Kết quả mô phỏng 100Node khoảng thời gian vào/ra mạng là 600s.......... 61
Hình 3.5 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 600s ...... 61
Hình 3.6 (a) Kết quả mô phỏng tổng hợp với 100 node ................................................. 62
Hình 3.6 (b) Kết quả mô phỏng tổng hợp với 1000 node ............................................... 62
Hình 3.7 (a) Kết quả mô phỏng 100 node, khoảng thời gian vào/ra mạng là 300s ........ 63
Hình 3.7 (b) Kết quả mô phỏng 100 node, khoảng thời gian vào/ra mạng là 600s ........ 63
Hình 3.8 (a) Kết quả mô phỏng 250 node, khoảng thời gian vào/ra mạng là 300s ........ 64
Hình 3.8 (b) Kết quả mô phỏng 250 node, khoảng thời gian vào/ra mạng là 600s ........ 64
Hình 3.9 (a) Kết quả mô phỏng 500 node, khoảng thời gian vào/ra mạng là 300s ........ 64
Hình 3.9 (b) Kết quả mô phỏng 500 node, khoảng thời gian vào/ra mạng là 600s ........ 64
Hình 3.10 (a) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 300s .... 64
Hình 3.10 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 600s .... 64
Hình 3.11 (a) Kết quả mô phỏng tổng hợp khoảng thời gian vào/ra mạng là 300s ........ 65
Hình 3.11 (b) Kết quả mô phỏng tổng hợp khoảng thời gian vào/ra mạng là 600s ........ 65
Hình 3.12 (a) Kết quả mô phỏng RTT = 0,5s khoảng thời gian vào/ra mạng là 300s .... 66
Hình 3.12 (b) Kết quả mô phỏng RTT = 0,5s khoảng thời gian vào/ra mạng là 600s .... 66
Hình 3.13 (a) Kết quả mô phỏng RTT = 1s khoảng thời gian vào/ra mạng là 300s ....... 66
Hình 3.13 (b) Kết quả mô phỏng RTT = 1s khoảng thời gian vào/ra mạng là 600s ....... 66
Hình 3.14 (a) Kết quả mô phỏng RTT = 2s khoảng thời gian vào/ra mạng là 300s ....... 67
Hình 3.14 (b) Kết quả mô phỏng RTT = 2s khoảng thời gian vào/ra mạng là 600s ....... 67
Hình 3.15 (a) Kết quả mô phỏng RTT = 3s khoảng thời gian vào/ra mạng là 300s ....... 67
Hình 3.15 (b) Kết quả mô phỏng RTT = 3s khoảng thời gian vào/ra mạng là 600s ....... 67
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
Hình 3.16 (a) Kết quả mô phỏng tổng hợp khoảng thời gian vào/ra mạng là 300s ........ 68
Hình 3.16 (b) Kết quả mô phỏng tổng hợp khoảng thời gian vào/ra mạng là 600s ........ 68
Hình 3.17 (a) Kết quả mô phỏng 100 node, khoảng thời gian vào/ra mạng là 300s ...... 69
Hình 3.17 (b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 300s .... 69
Hình 3.18 (a) Kết quả mô phỏng 100 node, khoảng thời gian vào/ra mạng là 600s ...... 69
Hình 3.18 b) Kết quả mô phỏng 1000 node, khoảng thời gian vào/ra mạng là 600s ...... 69
Hình 3.19 (a) Kết quả mô phỏng tổng hợp 100 node ...................................................... 70
Hình 3.19 (b) Kết quả mô phỏng tổng hợp 1000 node ................................................... 70
Danh mục bảng
Bảng 1.1. So sánh ưu, nhược điểm của hệ thống P2P và Client/Server.......................... 14
Bảng 1.2. Các mô hình P2P ............................................................................................. 15
Bảng 3.1. Trạng thái phát triển của các simulator ........................................................... 53
Bảng 3.2. Đặc điểm của các simulator ............................................................................ 54
Bảng 3.3. Các kịch bản mô phỏng .................................................................................. 58
Bảng 3.4. Các tham số của Chord ................................................................................... 58
Danh mục thuật toán
Thuật toán 2.1. Giả mã tìm node successor của ID n ...................................................... 45
Thuật toán 2.2. Giả mã cho hoạt động join vào mạng của một node .............................. 46
Thuật toán 2.3. Giả mã cho quá trình stabilization ......................................................... 47
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
Lời mở đầu
Khoảng mười năm trở lại đây, thế giới đã chứng kiến sự bùng nổ của Internet
băng thông rộng, cùng với nó là sự phát triển mạnh mẽ của các ứng dụng peer-to-peer.
Với nhiều ưu điểm hứa hẹn như tính hiệu quả, linh hoạt và khả năng mở rộng cao, các
mạng peer-to-peer overlay đã và đang thu hút được nhiều sự quan tâm từ cộng đồng
nghiên cứu. Các mạng peer-to-peer overlay đã phát triển qua ba thế hệ, thế hệ hiện nay
là mạng structured overlay dựa trên khả năng lưu trữ và tìm kiếm dữ liệu hiệu quả của
cơ chế bảng băm phân tán (Distributed Hash Table - DHTs).
DHTs là cơ sở để xây dựng các hệ thống ứng dụng phân tán như distributed file
systems, peer-to-peer file sharing và content distribution systems. Bên cạnh đó là các hệ
thống web caching, multicast, anycast, domain name services, và instant messaging. Các
hệ thống ứng dụng sử dụng DHTs đáng chú ý có BitTorrent, eDonkey...
Các DHTs được thiết kế để làm trong môi trường tương đối ổn định với các peer là
máy tính. Tuy nhiên, vài năm gần đây, các thiết bị nối mạng ngày càng phong phú, đa
dạng như tivi hay các thiết bị wireless như điện thoại, PDA, …. Các thiết bị này kết nối
và rời khỏi mạng sau một thời gian ngắn (churn rate cao) khiến cho thông tin về các
peer trên mạng liên tục thay đổi dẫn đến hiệu năng của các DHTs giảm sút rõ rệt.
Đánh giá và cải thiện hiệu năng của các DHTs trong điều kiện mạng churn rate cao là
bài toán đang rất được quan tâm hiện nay.
Luận văn bao gồm ba phần. Phần thứ nhất tóm tắt lý thuyết chung về mạng
peer-to-peer. Phần thứ hai, luận văn tìm hiểu cơ chế DHTs thông qua một số DHTs nổi
tiếng như Chord, Kademlia, Tapestry, Kelips. Phần thứ ba luận văn văn tiến hành phân
tích, đánh giá hiệu năng của một DHTs cụ thể (Chord DHTs) và căn cứ vào các kết quả
phân tích đó mở ra hướng khắc phục các hạn chế của các DHTs.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
Chƣơng 1.
Khái quát về mạng ngang hàng và bảng băm
1.1. Mạng ngang hàng
1.1.1. Khái niệm mạng ngang hàng
Mạng ngang hàng (Peer – to – Peer, P2P) bắt đầu xuất hiện từ 1999 và đã thu hút
sự quan tâm của giới CNTT trong những năm gần đây. Đặc biệt việc áp dụng các mô
hình P2P trong việc xây dựng những ứng dụng chia sẻ file (file sharing), điện thoại trên
nền Internet (Internet-based telephony) đã đạt được nhiều thành công.
Hiện nay các ứng dụng P2P chiếm khoảng 50% (thậm chí 75%) băng thông trên
Internet.
Cũng giống như các xu hướng đang trong quá trình phát triển khác, hiện nay
chưa có một định nghĩa chính xác về mạng P2P. Dưới đây là một số định nghĩa về P2P:
Theo Oram:
- P2P là một lớp các ứng dụng tận dụng các tài nguyên như bộ nhớ, năng lực xử
lý, nội dung, … tại các điểm cuối trong mạng Internet. Bởi vì truy cập vào các tài
nguyên phân tán này cũng có nghĩa là hoạt động trong một môi trường liên kết không
ổn định và với địa chỉ IP có thể thay đổi, các node P2P phải hoạt động ngoài hệ thống
DNS và có quyền tự trị cao hoặc hoàn toàn tự trị.
- Mạng P2P không có khái niệm máy trạm (client) hay máy chủ (server), mà chỉ
có khái niệm các nốt (peers) đóng vai trò như cả client và server.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
Hình 1.1. (a) Mô hình Client/Server
Hình 1.1. (b) Mô hình P2P
Theo Miller: P2P là một kiến trúc trong đó các máy tính có vai trò và trách
nhiệm như nhau. Mô hình này đối lập với mô hình client/server truyền thống, trong đó
một số máy tính được dành riêng để phục vụ các máy tính khác. P2P có năm đặc điểm:
- Việc truyền dữ liệu và thông tin giữa các peer trong mạng dễ dàng.
- Các peer vừa có thể hoạt động như client vừa có thể hoạt động như server.
- Nội dung chính trong mạng được cung cấp bởi các peer.
- Mạng trao quyền điều khiển và tự trị cho các peer.
- Mạng hỗ trợ các peer không kết nối thường xuyên và các peer không có địa chỉ
IP cố định
Theo P2P Working Group: P2P computing là sự chia sẻ tài nguyên và dịch vụ
bằng cách trao đổi trực tiếp giữa các hệ thống. Tài nguyên và dịch vụ ở đây bao gồm
thông tin, chu kỳ xử lý, không gian lưu trữ. Peer-to-peer computing tận dụng sức mạnh
tính toán của các máy tính cá nhân và kết nối mạng, cho phép doanh nghiệp tận dụng
sức mạnh tổng hợp của các client.
Các định nghĩa về P2P thống nhất ở một số khái niệm: chia sẻ tài nguyên, tự
trị/phân tán, địa chỉ IP động, vai trò vừa là client vừa là server.
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 xem là nối với nhau bằng liên kết ảo (logical links), mỗi liên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
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.
Hình 1.2. Overlay Network Diagram
1.1.2. Quá trình phát triển của các hệ thống mạng ngang hàng
Peer-to-Peer là thuật ngữ tương đối mới trong lĩnh vực mạng và các hệ thống
phân tán. Theo Oram, P2P computing bắt đầu trở thành đề tài được nhiều người quan
tâm từ giữa những năm 2000. Trong khoảng thời gian từ đó đến nay, P2P trải qua vài
thế hệ, mỗi thế hệ được phát triển với những động cơ, mục đích của mình.
Thế hệ thứ nhất
Thế hệ P2P đầu tiên bắt đầu với sự xuất hiện của ứng dụng chia sẻ file Napster.
Napster và các ứng dụng khác trong thế hệ thứ nhất sử dụng mô hình centralized
directory. Đây là mô hình hybrid P2P trong đó hầu hết các peer trong hệ thống có vai
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
trò như nhau, một số peer có vai trò lớn hơn và được gọi là các server.
Hình 1.1 cho thấy một ví dụ về mô hình centralized directory. Trong mô hình
này, các peer muốn chia sẻ file với các peer khác sẽ thông báo với server về các file
này. Khi một peer muốn tìm một file nào đó, nó sẽ gửi yêu cầu đến server, dựa trên các
thông tin đã thu thập được, server sẽ tìm ra các peer chứa file đó và trả kết quả tìm
kiếm cho peer yêu cầu. Kết quả trả về là peer phù hợp dựa trên một số thông số như tốc
độ kết nối, kích thước file, …. Sau khi nhận được kết quả, peer tìm kiếm sẽ trao đổi file
trực tiếp với peer chứa file mà không thông qua server nữa.
Hình 1.3. Mô hình centralized directory
Đóng góp chính của thế hệ thứ nhất là đã đưa ra kiến trúc mạng không xem các
máy tính như client và server mà xem chúng như các máy cung cấp và sử dụng tài
nguyên với vai trò tương đương nhau. Mô hình centralized directory cho phép tìm kiếm
thông tin trong không gian lưu trữ một cách nhanh chóng, tuy nhiên, điểm yếu của của
mô hình này là tính khả mở vì tải trên index server sẽ tăng tuyến tính với số lượng peer.
Đồng thời các hệ thống sử dụng mô hình này, điển hình là Napster còn gặp vấn đề về
bản quyền các tài nguyên.
Thế hệ thứ hai
Thế hệ thứ hai bắt đầu với các ứng dụng như Gnutella, Freenet làm việc mô
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
hình flooded requests. Mô hình này không có bất kỳ server nào, các peer bình đẳng
như nhau. Các hệ thống peer to peer thế hệ thứ hai là các hệ thống peer to peer thuần
túy. Không giống thế hệ thứ nhất, các peer không thông báo về các nội dung chúng
chia sẻ, khi một peer muốn tìm kiếm một file, nó gửi yêu cầu tới các peer kết nối trực
tiếp với nó, nếu các peer đó không tìm thấy file, mỗi peer sẽ gửi yêu cầu tìm kiếm đến
các peer kết nối trực tiếp với nó, quá trình cứ diễn ra như vậy cho đến khi yêu cầu bị
từ chối. Quá trình gửi yêu cầu tìm kiếm đi như vậy gọi là flooding. Hình 1.2 biểu diễn
một mô hình flooding request.
Hình 1.4. Mô hình flooding request
Thế hệ thứ hai xóa bỏ được một số điểm xử lý tập trung trong mạng nhưng tính khả
mở còn kém hơn do mạng sử dụng thuật toán flooding sinh ra quá nhiều traffic.
Thêm nữa, các mạng làm việc theo mô hình này không đảm bảo sẽ tìm được dữ liệu có
trên mạng do phạm vi tìm kiếm bị giới hạn. Một số mạng trong thế hệ thứ hai đưa ra
một số cải tiến. Freenet đưa ra mô hình document routing, trong đó dữ liệu được lưu
trên trên node có id tương tự với id của dữ liệu và các query được chuyển tiếp dựa trên
id của dữ liệu tìm kiếm. Kazza, Gnutella sử dụng khái niệm super peer trong đó một số
node hoạt động như directory service, giảm lượng flooding trong mạng.
Thế hệ thứ ba
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
Sự đơn giản trong giải pháp và khả năng xóa bỏ điểm tập trung, chuyển trách
nhiệm pháp lý về phía người sử dụng cũng như hạn chế về tính khả mở do lưu lượng
quá lớn đã thu hút cộng đồng nghiên cứu về mạng và các hệ thống mở. Bài toán đặt ra
cho cộng đồng nghiên cứu là xây dựng một mạng P2P overlay khả mở không có điểm
điều khiển tập trung. Nỗ lực giải quyết bài toán này là sự xuất hiện của “structured P2P
overlay networks”.
Thế hệ thứ ba được khởi đầu với các dự án nghiên cứu như Chord, CAN, Pastry,
Tapestry và P-Grid. Các dự án này đưa ra khái niệm Distributed Hash Table (DHTs).
Mỗi peer trong hệ thống có một ID thu được từ việc băm các đặc thuộc tính đặc
trưng của peer đó như địa chỉ IP hay public key. Mỗi data item cũng có một ID thu được
theo cách tương tự với các peer. Hash table lưu data dưới dạng cặp key-value. Như vậy,
node ID và cặp key-value được băm vào cùng một không gian ID. Các node sau đó
được nối với nhau theo một topology nào đó. Quá trình tìm kiếm dữ liệu trở thành
quá trình định tuyến với kích thước bảng định tuyến nhỏ và chiều dài đường đi cực
đại. Thế hệ thứ ba đảm bảo xác xuất tìm thấy thông tin cao.
Các DHTs được xây dựng nhằm mục đích cho phép các peer hoạt động như một
cấu trúc dữ liệu phân tán với hai hàm chính Put (key,value) và Get (Key). Hàm Put lưu
dữ liệu tại một peer nào đó sao cho bất kỳ peer nào cũng có thể tìm được bằng hàm Get.
Các hàm này hoàn thành sau khi đi qua một số nhỏ các chặng. Giải pháp DHTs
đảm bảo cho mạng có tính khả mở và khả năng tìm thấy thông tin cao trong khi vẫn
hoàn toàn phân tán. DHT đang được xem như là cách tiếp cận hợp lý cho vấn đề định
vị và định tuyến trong các hệ thống P2P. Cộng đồng nghiên cứu đã đưa ra nhiều DHT
khác nhau. Mỗi DHT hoạt động theo nguyên lý chung và có ưu điểm riêng, Chord với
thiết kế đơn giản, Tapestry và Pastry giải quyết được vấn đề proximity routing, …
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
P2P
Client/Server
- Một mạng ngang hàng cho phép các
- Dữ liệu được lưu trữ ở một Server
node (PCs) đóng góp, chia sẻ nguồn tài
trung tâm, tốc độ cao (Tốc độ truy cập
nguyên với nhau. Tài nguyên riêng rẽ
thường lớn hơn so với mạng P2P).
của các node (ổ cứng, CD-ROM, máy
- Khi một máy client yêu cầu lấy thông
in …. Các nguồn tài nguyên này có thể
tin về thời gian nó sẽ phải gửi một yêu
được truy cập từ bất cứ node nào trong
cầu theo một tiêu chuẩn do server định
mạng.
ra, nếu yêu cầu được chấp nhận thì máy
- Các node đóng vai trò như cả Client (truy
server sẽ trả về thông tin mà client yêu
vấn
cầu.
thông
tin) và Server (cung cấp thông
+ Ƣu điểm:
+ Ƣu điểm:
tin).
-
Không cần server riêng, các client
- Tốc độ truy cập nhanh.
chia sẻ tài nguyên. Khi mạng càng
- Khả năng mở rộng cao.
được mở rộng thì khả năng hoạt
- Hoạt động với bất kì loại ứng
động của hệ thống càng tốt.
dụng nào.
-
Rẻ.
-
Dễ cài đặt và bảo trì.
- Sử dụng được với các ứng dụng
+ Nhƣợc
điểm:
- Thuận
lợi cho việc chia sẽ file, máy
chia sẻ CSDL.
+ Nhƣợc điểm:
- Đáng tin cậy hơn (có server
-riêng).
Cần server riêng (nghẽn cổ chai).
-
in, CD-ROM v.v…
Chậm.
-
Không tốt cho các ứng dụng CSDL.
-- Đắt.
Mức độ an toàn cao nhất.
-
Kém tin cậy.
- Phức tạp trong việc bảo trì, duy trì
Bảng 1.1. So sánh ưu, nhược điểm của hệ thống P2P và Client/Server
hoạt động của mạng.
1.1.3. Phân loại các mô hình mạng ngang hàng
Mạng ngang hàng có thể được phân loại theo mục đích sử dụng như: Chia sẻ file (file
sharing), Điện thoại VoIP (telephony), Đa phương tiện media streaming (audio, video),
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
14
Diễn đàn thảo luận (Discussion forums)… Mạng ngang hàng cũng có thể được phân loại
theo mức độ tập trung của mạng (đối với P2P overlay networks). Hiện nay các hệ thống
mạng ngang hàng có thể được phân loại thành một số nhóm sau:
Bảng 1.2. Các mô hình P2P
a) Hệ thống mạng ngang hàng tập trung (Centralized)
Hệ thống mạng ngang hàng tập trung có đặc điểm là vẫn còn dựa trên một máy
chủ tìm kiếm trung tâm (centralized Peer-to-Peer networks). Cấu trúc Overlay của
mạng ngang hàng tập trung có thể được môtả như một mạng hình sao.
Query
File
download
Hình 1.5. Mạng ngang hàng tập trung thế hệ thứ nhất (Napster
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
15
- Xem thêm -