Luận Văn Nghiên cứu về cơ chế lập lịch của mạng ngang hàng P2P

MỤC LỤC


LỜI CẢM ƠN i

MỤC LỤC ii

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT iv

DANH MỤC CÁC BẢNG

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ vii

MỞ ĐẦU 1

Chương 1 TỔNG QUAN VỀ MẠNG NGANG HÀNG 2

1.1 KHÁI NIỆM MẠNG NGANG HÀNG 2

2.1.1 Giới thiệu 2

2.1.2Định nghĩa P2P: 4

2.1.3 Khái niệm peer (Peer) 5

2.1.4 Cách phân loại peer trong mạng ngang hàng 6

2.1.5 Mạng chồng phủ 7

1.2 Phân loại mạng ngang hàng 7

1.2.1 Mạng ngang hàng không có cấu trúc 8

1.2.2 Mạng ngang hàng có cấu trúc 14

1.3 Đặc điểm của mạng ngang hàng 15

1.3.1 So sánh mô hình P2P với mô hình truyền thống Client/Server 16

1.3.2 Các ưu thế của mạng ngang hàng 17

1.3.3 Các vấn đề cần xem xét trong mạng ngang hàng 17

1.3.4 Tiềm năng phát triển của mạng ngang hàng 18

1.4 Ứng dụng của mạng ngang hàng 18

1.41 Chia sẻ tài liệu 19

1.4.2 Ứng dụng phân tán tính toán 19

1.4.3 Ứng dụng hợp tác 19

1.4.4 Ứng dụng lớp nền 19

1.5 Kết luận chương 1 20

Chương 2 CÁC CƠ CHẾ LẬP LỊCH TRONG MẠNG NGANG HÀNG 21

2.1 LẬP LỊCH TRONG MẠNG NGANG HÀNG CHIA SẺ TẬP TIN (P2P FILE SHARING) 21

2.1.1 Đặt vấn đề 21

2.1.2 Mô hình truyền thông 22

2.1.2 Lập lịch trong mạng P2P streaming 40

Chương 3 ĐÁNH GIÁ HIỆU NĂNG CỦA CÁC THUẬT TOÁN LẬP LỊCH 55

3.1 HIỆU NĂNG CỦA CÁC THUẬT TOÁN TRONG MẠNG P2P CHIA SẺ TẬP TIN 55

3.1.1 Đặt vấn đề 55

3.1.2 Mô phỏng các cơ chế lập lịch 56

3.2 Đánh giá hiệu năng của các cơ chế lập lịch đối với mạng P2P streaming 60

3.2.1 Cơ chế lập lịch peer tối ưu 60

3.2.2 Cơ chế lập lịch chunk tối ưu 60

3.2.3 Đánh giá hiệu năng các cơ chế lập lịch bằng chương trình mô phỏng 61

KẾT LUẬN 70

KIẾN NGHỊ VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO 71

TÀI LIỆU THAM KHẢO 72

PHỤ LỤC


DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ


Hình 1.1: Hệ thống mạng 3

Hình 1.2: Mô hình Client/Server 4

Hình 1.3: Mô hình P2P 5

Hình 1.4: Mô hình mạng chồng phủ 7

Hình 1.5: Phân loại mạng P2P 8

Hình 1.7: Mạng ngang hàng thuần túy (Gnutella 4.0, FreeNet) 11

Hình 1.8: Node mạng tham gia vào mạng Gnutella và tìm kiếm file 11

Hình 1.9: Mạng ngang hàng lai ghép 14

Hình 1.10: Cấu trúc dạng vòng 15

Hình 2.1: Mạng kết nối hoàn thiện với việc cấp phát băng thông không đối xứng 23

Hình 2.2: Ma trận sở hữu và đồ thị mạng luồng của nó 35

Hình 2.3: Luồng cực đại và lịch trình truyền dẫn 36

Hình 2.4: Dồ thị luồng cực đại có trọng số và lịch trình truyền dẫn của nó 38

Hình 2.5: Trao đổi các block giữa hai peer trong các hệ thống P2P chia sẻ file 41

Hình 2.6: Trao đổi block giữa 2 peer trong hê thống P2P live streaming 41

Hình 2.7: Trao đổi block giữa 2 peer trong hệ thống P2P VoD 42

Hình 2.8: Lập lịch Pull-based 43

Hình 2.9: Lập lịch RUc 46

Hình 2.10: Lập lịch LUc 46

Hình 2.11: Lập lịch RUp 47

Hình 2.12: Lập lịch MDp 48

Hình 2.13: Lập lịch ELp 48

Hình 2.14: Lập lịch LUc/MDp và LUc/Rup 50

Hình 2.15: Lập lịch RUc/RUp và RUc/MDp 50

Hình 2.16: Lập lịch ELp/RUc 51

Hình 2.18: Sự khác nhau giữa các cơ chế lập lịch peer trước 53

Hình. 3.2 so sánh hiệu năng của các thuật toán lập lịch với kích cỡ file thay đổi (peer size = 10, pi = 2, qi = 3, xác suất của 1 và 0 bằng nhau) 57

Hình. 3.3 So sánh hiệu năng của các thuật toán lập lịch với kích cỡ peer thay đổi (kích thước file = 100, pi = 2, qi = 3, xác suất của số 1: số 0 = 1:2) 58

Hình. 3.4 Hiệu suất so sánh các thuật toán lập lịch đại diện với thay đổi kích thước file (peer size = 10, pi = 2, qi = 3, xác suất của số 1: số 0 = 1:2) 10 59

Hình 3.5 Mô hình uniform với lập lịch chunk trước 64

Hình 3.6 Mô hình uniform với lập lịch peer trước 65

Hình 3.7 Mô hình 3-class với lập lịch chunk trước 66

Hình 3.8 Mô hình 3-class với lập lịch peer trước 67

Hình 3.9 Mô hình free-rider với lập lịch chunk trước 68


MỞ ĐẦU


Như chúng ta đều biết, hầu như mọi dịch vụ mà Internet cung cấp ngày nay đều dựa trên mô hình client/server. Nói chung, mô hình client/server có rất nhiều điểm ưu việt như là mọi xử lý sẽ nằm trên server do đó sẽ tránh cho clients những tính toán nặng nề.

Tuy nhiên, khi mà Internet phát triển với tốc độ chóng mặt như ngày nay thì mô hình client/server có một nhược điểm lớn đó là khi số lượng client tăng đến một mức độ nào đó thì nhu cầu về tải và băng thông tăng lên dẫn đến việc máy chủ không có khả năng cung cấp dịch vụ cho các máy khách thêm vào.

Để giải quyết vấn đề trên và còn nhiều vấn đề khác của mô hình client/server, công nghệ mạng ngang hàng P2P (peer to peer) được tin tưởng sẽ là lời giải cho các vấn đề trên. 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 P2P. 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ó nhiều ứng dụng như 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, P2P streaming do đó các mạng P2P đã và đang thu hút được nhiều sự quan tâm từ cộng đồng nghiên cứu đặc biệt là nghiên cứu về mặt hiệu năng sử dụng của mạng P2P.

Những ưu thế của mạng ngang hàng P2P đã thu hút rất nhiều người sử dụng dẫn đến việc nghẽn mạng, giới hạn băng thông đứng trước tình hình này việc nghiên cứu về cơ chế lập lịch của mạng ngang hàng P2P là một trong những thách thức cũng như một trong những thành công mang lại hiệu quả cao cho việc sử dụng mạng ngang hàng P2P này.

Trong khuôn khổ của luận văn sẽ đi nghiên cứu lần lượt các chương sau:

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

Chương 2: Các cơ chế lập lịch trong mạng ngang hàng

Chương 3: Đánh giá hiệu năng của các cơ chế lập lịch