điều khiển tắc nghẽn trên mạng ngang hàng có cấu trúc

I

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRẦN TRỌNG TẤN

ĐIỀU KHIỂN TẮC NGHẼN TRÊN MẠNG

NGANG HÀNG CÓ CẤU TRÚC

LUẬN VĂN THẠC SĨ

HÀ NỘI - 2011

II

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRẦN TRỌNG TẤN

ĐIỀU KHIỂN TẮC NGHẼN TRÊN MẠNG

NGANG HÀNG CÓ CẤU TRÚC

Ngành: Công nghệ Thông tin

Chuyên ngành: Truyền dữ liệu và mạng máy tính

Mã số: 60 48 15

LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Hoài Sơn

HÀ NỘI - 2011

III

Mục lục

Mở đầu ..................................................................................................................... 1

Chương 1. Tổng quan .............................................................................................. 3

1.1. Mạng ngang hàng......................................................................................... 3

1.1.1. Mức độ phân tán .................................................................................... 3

1.1.2. Cấu trúc mạng........................................................................................ 5

1.2. Mạng ngang hàng có cấu trúc....................................................................... 6

1.2.1. Đặc điểm của DHT ................................................................................ 7

1.2.2. Cấu trúc hệ thống................................................................................... 7

1.3. Mạng Chord .................................................................................................. 9

1.3.1. Mô hình của Chord .............................................................................. 10

1.3.2. Tìm kiếm trong mạng Chord ............................................................... 11

1.3.3. Quá trình tham gia và ổn định mạng ................................................... 14

Chương 2. Vấn đề điều khiển tắc nghẽn trong mạng ngang hàng có cấu trúc ...... 16

2.1. Tắc nghẽn và tầm quan trọng của việc điều khiển tắc nghẽn trong mạng

ngang hàng có cấu trúc ...................................................................................... 16

2.2. Phân tích quá trình sụp đổ do tắc nghẽn trong mạng ngang hàng có cấu trúc

............................................................................................................................ 17

2.2.1. Khái quát.............................................................................................. 17

2.2.2. Định nghĩa............................................................................................ 17

2.2.3. Các mô hình......................................................................................... 19

2.2.4. Tổng tải đến O..................................................................................... 19

2.2.5. Ví dụ với một triệu nút ........................................................................ 22

2.2.6. Phân tích các trạng thái tiệm cận của A............................................... 22

2.2.7. Kết luận................................................................................................ 25

Chương 3. Các nghiên cứu về điều khiển tắc nghẽn trên DHT............................. 26

3.1. Phương pháp CSCC.................................................................................... 26

3.2. Phương pháp BPCC.................................................................................... 27

3.3. Phương pháp Marking ................................................................................ 28

3.4. Phương pháp định tuyến thích nghi............................................................ 31

Chương 4. Điều khiển tắc nghẽn sử dụng phương pháp thay đổi bảng định tuyến

................................................................................................................................ 34

4.1. Đề xuất phương pháp.................................................................................. 34

4.2. Nội dung chi tiết ......................................................................................... 34

4.2.1. Phát hiện tắc nghẽn.............................................................................. 34

4.2.2. Xử lý trong trường hợp có tắc nghẽn................................................... 35

4.2.3. Xử lý khi hết tắc nghẽn........................................................................ 36

4.3. Ví dụ minh họa ........................................................................................... 37

4.4. Nhận xét về phương pháp........................................................................... 39

5. Mô phỏng và kết quả ......................................................................................... 41

5.1. Mô phỏng.................................................................................................... 41

5.1.1. Chương trình mô phỏng....................................................................... 41

IV

5.1.2. Các thay đổi đã áp dụng....................................................................... 44

5.2. Kết quả........................................................................................................ 45

5.2.1. So sánh với mô hình Chord chuẩn....................................................... 45

5.2.2. Đánh giá hiệu năng khi tiến hành tùy chỉnh các tham số và cải tiến

phương pháp .................................................................................................. 47

6. Kết luận và hướng phát triển ............................................................................. 50

V

Danh mục hình ảnh

Hình 1: Mạng ngang hàng phân tán hoàn toàn........................................................ 4

Hình 2: Mạng ngang hàng phân tán một phần......................................................... 4

Hình 3: Mạng ngang hàng lai .................................................................................. 5

Hình 4: Bảng băm phân tán – DHT......................................................................... 7

Hình 5: Mô hình vòng Chord với khóa có chiều dài 6 bit..................................... 11

Hình 6: Quá trình tìm kiếm đơn giản trên Chord .................................................. 12

Hình 7: Bảng finger của nút 8................................................................................ 13

Hình 8: Giả mã của phương pháp tìm kiếm cải tiến.............................................. 13

Hình 9: Quá trình tìm kiếm khóa 54 trên nút 8 ..................................................... 14

Hình 10: (a) tải đến các nút tạo bởi P0, (b) Tải tới và rời khỏi nút................... 18

Hình 11: Thông lượng đạt được so sánh với tốc độ truy vấn cho hệ thống DHT với

một triệu nút trong hai trường hợp tắc nghẽn M1 và M2. Mạng DHT sụp đổ khi

tải tới đạt đến giá trị xopt......................................................................................... 22

Hình 12: Phương pháp CSCC................................................................................ 26

Hình 13: Phương pháp BPCC................................................................................ 28

Hình 14: Mạng DHT với 8 nút. ............................................................................. 31

Hình 15: Truy vấn thông thường trên mạng Chord (m=8).................................... 37

Hình 16: Bảng định tuyến ban đầu của nút P8 ....................................................... 38

Hình 17: Bảng định tuyến của nút P8 khi xảy ra tình trạng tắc nghẽn trên nút P42.

................................................................................................................................ 38

Hình 18: Truy vấn được thay đổi đường đi khi áp dụng giải pháp chống tắc nghẽn

................................................................................................................................ 38

Hình 19: Mô hình mạng mô phỏng........................................................................ 41

Hình 20: Mô hình lớp Node................................................................................... 42

Hình 21: Biểu đồ số lượng gói tin bị loại bỏ khi áp dụng và không áp dụng việc

điều khiển tắc nghẽn .............................................................................................. 45

Hình 22: Biểu đồ thể hiện số gói tin trung bình phải sử dụng với mỗi truy vấn

thành công.............................................................................................................. 46

Hình 23: Ảnh hưởng của việc thay đổi giá trị xác định mức độ tắc nghẽn mềm của

nút........................................................................................................................... 47

Hình 24: Ảnh hưởng của số lượng nút được khôi phục bảng định tuyến lên hiệu

năng của hệ thống .................................................................................................. 48

Hình 25: Hiệu năng của hệ thống thay đổi khi cải tiến phương pháp điều khiển tắc

nghẽn...................................................................................................................... 48