Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP --------------------------------------- LUẬN VĂN THẠC SĨ KỸ THUẬT ỨNG DỤNG PHƢƠNG PHÁP GIẢM BẬC MÔ HÌNH TRONG XÂY DỰNG CẤU TRÚC MẠNG QUẢN LÝ VIỄN THÔNG Ngành: KỸ THUẬT ĐIỆN TỬ Mã số: H ọc viên: NG UYỄN ANH TUẤN Ngƣời HD khoa học: PGS TS NGUYỄN HỮU CÔNG THÁI NGUYÊN, 2011 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP --------------------------------------- LUẬN VĂN THẠC SĨ KỸ THUẬT NGÀNH: KỸ THUẬT ĐIỆN TỬ ỨNG DỤNG PHƢƠNG PHÁP GIẢM BẬC MÔ HÌNH TRONG XÂY DỰNG CẤU TRÚC MẠNG QUẢN LÝ VIỄN THÔNG Học viên: NG UYỄN ANH TUẤN Mã số: Ngƣời HD khoa học: PGS TS NGUYỄN HỮU CÔNG Thái Nguyên, 2011 HƢỚNG DẪN K HOA HỌC PGS TS Nguyễn Hữu Công HỌC VIÊN Nguyễn Anh Tuấn KHOA SAU ĐẠI HỌC BGH TRƢỜNG ĐHKTCN Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn LỜI CAM ĐOAN Tôi xin cam đoan các số liệu và kết quả nêu trong Luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ một công trình nào khác Trừ các phần tham khảo đã đƣợc nêu rõ trong Luận văn Tác giả Nguyễn Anh Tuấn Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn LỜI CẢM ƠN Tá c giả xin chân thành cảm ơn Thầy giáo – PGS TS Nguyễn Hữu Công, ngƣời đã hƣớng dẫn và giúp đỡ tận tình từ định hƣớng đề tài, tổ chức thực nghiệm đến quá trình viết và hoàn chỉnh Luận văn Tác giả bày tỏ lòng biết ơn đối với Thạc sỹ Đào Huy Du và các thầy cô trong khoa Điện tử viễn thông phòng Đào tạo , Khoa Sau đại học - Trƣờng Đại học Kỹ thuật Công nghiệp đã tạo điều kiện thuận lợ i để tác giả hoàn thành Luận văn này Do năng lực bản thân còn nhiều hạn chế nên Luận văn không tránh khỏi sai sót, tác giả rất mong nhận đƣợc sự đóng góp ý kiến của các Thầy, Cô giáo, các nhà khoa học và các bạn đồng nghiệp Tác giả Nguyễn Anh Tuấn Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn MỤC LỤC Trang Lời cam đoan Lời cảm ơn Danh mục các bảng biểu Danh mục các hình vẽ PHẦN MỞ ĐẦU 1 Tính cấp thiết của đề tài 1 2 Ý nghĩa của đề tài 1 3 Đối tƣợng, mục đích, phƣơng pháp và nội dung nghiên cứu 2 Chƣơng 1: TỔNG QUAN VỀ QUẢN LÝ HÀNG ĐỢI 3 1 1 Giới thiệu chung 3 1 2 Quá trình truyền dữ liệu trên mạng và vấn đề tắc nghẽn 3 1 2 1 Truyền dữ liệu trên một hệ thống mạng 3 1 2 2 Nghẽn mạng và các nguyên nhân gây nghẽn 7 1 2 3 Cơ chế điều khiển luồng để tránh tắc nghẽn 9 1 3 Sự cần thiết phải quản lý hàng đợi 8 1 3 1 Khái niệm quản lý hàng đợi tích cực AQM 8 1 3 2 Sự cần thiết phải có quản lý hàng đợi tích cực 9 1 4 Tổng kết chƣơng 10 Chƣơng 2 : CÁC PHƢƠNG PHÁP QUẢN LÝ HÀNG ĐỢI 11 2 1 Giới thiệu 11 2 2 Cơ chế thông báo tắc nghẽn 11 2 2 1 Khái niệm chung 2 2 2 Sự đánh dấu trong IP header 11 12 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn 2 2 3 Sự đánh dấu trong TCP header 1 3 2 2 4 Cơ chế hoạt động 1 4 2 3 Cơ chế hủy bỏ sớm ngẫu nhiên RED 15 2 3 1 Mô tả khái quát về thuật toán 15 2 3 2 Giải thuật RED và các tham số 17 2 4 Cơ chế huỷ bỏ sớm ngẫu nhiên theo trọng số WRED 19 2 4 1 Khái quát 19 2 4 2 Cơ chế hoạt động 20 2 4 3 Sự ảnh hƣởng của thông số MPD đến sự hoạt động của WRED 21 2 4 4 Cách cấu hình WRED trong các thiết bị của Cisco 23 Chƣơng 3 : GIẢM BẬC MÔ HÌNH THEO PHƢƠNG PHÁP CÂN BĂNG NỘI 2 5 3 1 Giới thiệu 25 3 2 Phát biểu bài to án giảm bậc mô hình 25 3 3 Phƣơng pháp cân bằng nội của Moore 2 5 3 3 1 Một số ký hiệu toán học 2 5 3 2 2 Tổng quan về đƣa tín hiệu vào của lý thuyết thực hiện tối t h iểu 26 3 3 2 1 Nhắc lại hình học cơ bản 27 3 3 2 2 Đặc điểm của Xc 28 3 3 2 3 Đặc điểm của Xō 29 3 3 3 Phân tích thành phần chính 29 3 3 3 1 Phụ thuộc tuyến tính và xấp xỉ bình phƣơng nhỏ nhất 31 3 3 3 2 Thành phần chính của các ma trận đáp ứng xung 32 3 3 3 3 Tính toán các thành phần độ lớn và thành phần véc tơ 34 3 3 3 4 Tính chất nhiễu loạn của thành phần độ lớn và thành phần véc tơ 35 3 3 4 P hân tích tính điều khiển đƣợc và tính quan sát đƣợc 36 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn 3 3 4 1 Sự liên quan giữa mô hình (F, G, C) và thành phần của eAtB, T A e CT 37 3 3 4 2 Thành phần chính của eAtB, T A e CT 39 3 3 4 3 Giá trị tọa độ không đổi – Dạng bậc 2 41 3 3 4 4 Mô hình cân bằng động học nội cân bằng và chuẩn hóa 42 3 3 4 5 Các tính chất của ổn định tiệm cận, mô hình cân bằng nội 44 3 3 4 6 Tiền đề của giảm bậc mô hình 45 3 3 5 Các công c ụ giảm bậc mô hình 46 3 3 5 1 Giảm bậc bằng cách khử hệ con 47 3 3 5 2 Tính trội nội 49 3 3 5 3 Tính trội nội và các dạng bậc 2 51 3 4 Phát triển phƣơng pháp cân bằng nội của Moore 53 3 4 1 Giảm mô hình 53 3 4 2 Cá c hệ liên tục theo thời gian 55 3 4 3 Hệ thống rời rạc theo thời gian 61 3 5 Thuật toán giảm bậc theo cân bằng nội 67 3 6 Một số ví dụ áp dụng giảm bậc mô hình theo cân bằng nội 69 3 7 Kết luận chƣơng 79 CHƢƠNG 4 : ỨNG DỤNG GIẢM BẬC MÔ HÌN H CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG 4 1 Mở đầu 80 4 2 Cấu trúc hệ thống điều khiển 81 4 2 1 Sơ đồ tổng quát 81 4 2 2 Sơ đ ồ đi ề u khi ể n 81 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn 4 3 Ứ ng d ụ ng gi ả m b ậ c mô hình cho bài toán qu ả n lý hàng đ ợ i tích c ự c A QM 83 4 3 1 Bài toán quản lý hàng đợi 83 4 3 2 Giảm bậc đối tƣợng theo phƣơng pháp cân bằng nội 84 4 3 3 Một số kết quả mô phỏng 87 4 4 Kết luận chƣơng 90 KẾT LUẬN VÀ KIẾN NGHỊ 91 TÀI LIỆU THAM KHẢO 92 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn DANH MỤC CÁC BẢNG BIỂU TT Bảng số Nội dung Trang 1 2 1 Giải thuật WRED 20 2 2 2 Các thông số mặc định của WRED cho các giá trị DSCP khác nhau 22 3 3 1 Tham số của các hệ giảm bậc trong mô hình không gian trạng thái và mô hình hàm truyền của các hệ giảm bậc 71 4 3 2 Tham số của các hệ giảm bậc trong mô hình không gian trạng thái và mô hình hàm truyền của các hệ giảm bậc 76 5 4 1 Mô hình không gian trạng thái và mô hình hàm truyền của các hệ giảm bậc 85 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www lrc-tnu edu vn DANH MỤC CÁC HÌNH VẼ TT Hình số Nội dung Trang 1 1 1 K iến trúc mạng đơn giản 4 2 1 2 Kiến trúc cơ bản của một router 5 3 1 3 Ví dụ về nghẽn mạng 6 4 2 1 ECN Field trong IP header 12 5 2 2 ECN bit trong IP header 13 6 2 3 Cấu trúc TCP Header với 2 cờ CWR và ECE 14 7 2 4 Cấu trúc 2 trƣờng code field và Reserved field của TCP heade 14 8 2 5 Mô hình quản lý hàng đợi dùng thuật toán RED 16 9 2 6 Sơ đồ hoạt động của WRED 20 10 2 7 Cơ chế loại bỏ gói tin của WRED 21 11 2 8 Biểu diễn các trọng số của WRED 22 12 3 1 Các tín hiệu vào ra của hệ thống 27 13 3 2 Sơ đồ không gian trạng thái của hệ thống 28 14 3 3 Hệ thống khi đƣa vào tín hiệu thử x(0) = 0 29 15 3 4 Hệ thống khi đƣa tín hiệu xung đầu vào 32 16 3 5 Phân chia mô hình hệ thống 48 17 3 6 Phân chia mô hình hệ thống thành hệ con trội và hệ con y ếu 48 18 3 7 Tổ chức của mô hình hệ thống 49 19 3 8 Sơ đồ mô phỏng hệ gốc và các hệ giảm bậc trong Simulink 72 20 3 9 Đáp ứng bƣớc nhảy hệ gốc và các hệ giảm bậc 73 21 3 10 Đặc tính tần số hệ gốc và hệ giảm bậc 73 22 3 11 Sơ đồ mô phỏng hệ gốc và các hệ giảm bậc trong Simulink 77 23 3 12 Đáp ứng bƣớc nhảy hệ gốc và các hệ giảm bậc 78 24 3 13 Đặc tính tần số hệ gốc và các hệ giảm bậc 78 25 4 1 Biểu diễn nút cổ chai từ A sang B 81
Trang 1ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
-
LUẬN VĂN THẠC SĨ KỸ THUẬT
ỨNG DỤNG PHƯƠNG PHÁP GIẢM BẬC MÔ HÌNH
TRONG XÂY DỰNG CẤU TRÚC MẠNG
QUẢN LÝ VIỄN THÔNG
Ngành: KỸ THUẬT ĐIỆN TỬ
Mã số:
Người HD khoa học: PGS.TS NGUYỄN HỮU CÔNG
THÁI NGUYÊN, 2011
Trang 2ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
-
LUẬN VĂN THẠC SĨ KỸ THUẬT
NGÀNH: KỸ THUẬT ĐIỆN TỬ
ỨNG DỤNG PHƯƠNG PHÁP GIẢM BẬC MÔ HÌNH
TRONG XÂY DỰNG CẤU TRÚC MẠNG
QUẢN LÝ VIỄN THÔNG
Mã số:
Người HD khoa học: PGS.TS NGUYỄN HỮU CÔNG
HƯỚNG DẪN KHOA HỌC
PGS.TS Nguyễn Hữu Công
HỌC VIÊN
Nguyễn Anh Tuấn
Trang 3LỜI CAM ĐOAN
Tôi xin cam đoan các số liệu và kết quả nêu trong Luận văn
là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ một công trình nào khác Trừ các phần tham khảo đã đƣợc nêu rõ trong Luận văn.
Tác giả Nguyễn Anh Tuấn
Trang 4
LỜI CẢM ƠN
Tác giả xin chân thành cảm ơn Thầy giáo – PGS.TS Nguyễn Hữu Công, người đã hướng dẫn và giúp đỡ tận tình từ định hướng đề tài, tổ chức thực nghiệm đến quá trình viết và hoàn chỉnh Luận văn
Tác giả bày tỏ lòng biết ơn đối với Thạc sỹ Đào Huy Du và các thầy cô trong khoa Điện tử viễn thông phòng Đào tạo, Khoa Sau đại học - Trường Đại học Kỹ thuật Công nghiệp đã tạo điều kiện thuận lợi để tác giả hoàn thành Luận văn này
Do năng lực bản thân còn nhiều hạn chế nên Luận văn không tránh khỏi sai sót, tác giả rất mong nhận được sự đóng góp ý kiến của các Thầy, Cô giáo, các nhà khoa học và các bạn đồng nghiệp
Tác giả
Nguyễn Anh Tuấn
Trang 5
MỤC LỤC
Trang
Lời cam đoan
Lời cảm ơn
Danh mục các bảng biểu
Danh mục các hình vẽ
PHẦN MỞ ĐẦU
1 Tính cấp thiết của đề tài 1
3 Đối tượng, mục đích, phương pháp và nội dung nghiên cứu 2
Chương 1:
TỔNG QUAN VỀ QUẢN LÝ HÀNG ĐỢI 3
1.2 Quá trình truyền dữ liệu trên mạng và vấn đề tắc nghẽn 3
1.2.1 Truyền dữ liệu trên một hệ thống mạng 3
1.2.2 Nghẽn mạng và các nguyên nhân gây nghẽn 7
1.2.3 Cơ chế điều khiển luồng để tránh tắc nghẽn 9
1.3 Sự cần thiết phải quản lý hàng đợi 8
1.3.1 Khái niệm quản lý hàng đợi tích cực AQM 8
1.3.2 Sự cần thiết phải có quản lý hàng đợi tích cực 9
Chương 2:
CÁC PHƯƠNG PHÁP QUẢN LÝ HÀNG ĐỢI 11
2.2 Cơ chế thông báo tắc nghẽn 11
2.2.1 Khái niệm chung
2.2.2 Sự đánh dấu trong IP header
11
12
Trang 62.2.3 Sự đánh dấu trong TCP header 13 2.2.4 Cơ chế hoạt động 14 2.3 Cơ chế hủy bỏ sớm ngẫu nhiên RED 15 2.3.1 Mô tả khái quát về thuật toán 15
2.3.2 Giải thuật RED và các tham số 17 2.4 Cơ chế huỷ bỏ sớm ngẫu nhiên theo trọng số WRED 19
2.4.1 Khái quát 19 2.4.2 Cơ chế hoạt động 20 2.4.3 Sự ảnh hưởng của thông số MPD đến sự hoạt động của WRED 21 2.4.4 Cách cấu hình WRED trong các thiết bị của Cisco 23
Chương 3:
GIẢM BẬC MÔ HÌNH THEO PHƯƠNG PHÁP CÂN BĂNG NỘI 25
3.2 Phát biểu bài toán giảm bậc mô hình 25
3.3 Phương pháp cân bằng nội của Moore 25
3.3.1 Một số ký hiệu toán học 25
3.2.2 Tổng quan về đưa tín hiệu vào của lý thuyết thực hiện tối thiểu 26
3.3.2.1 Nhắc lại hình học cơ bản 27 3.3.2.2 Đặc điểm của Xc 28 3.3.2.3 Đặc điểm của Xō 29 3.3.3 Phân tích thành phần chính 29 3.3.3.1 Phụ thuộc tuyến tính và xấp xỉ bình phương nhỏ nhất 31 3.3.3.2 Thành phần chính của các ma trận đáp ứng xung 32 3.3.3.3 Tính toán các thành phần độ lớn và thành phần véc tơ 34 3.3.3.4 Tính chất nhiễu loạn của thành phần độ lớn và thành phần véc tơ 35
Trang 73.3.4.1 Sự liên quan giữa mô hình (F, G, C) và thành phần của eAtB,
T
A
e CT 37
3.3.4.2 Thành phần chính của eAtB,
T
A
3.3.4.3 Giá trị tọa độ không đổi – Dạng bậc 2 41 3.3.4.4 Mô hình cân bằng động học nội cân bằng và chuẩn hóa 42
3.3.4.5 Các tính chất của ổn định tiệm cận, mô hình cân bằng nội 44 3.3.4.6 Tiền đề của giảm bậc mô hình 45
3.3.5 Các công cụ giảm bậc mô hình 46 3.3.5.1 Giảm bậc bằng cách khử hệ con 47 3.3.5.2 Tính trội nội 49
3.3.5.3 Tính trội nội và các dạng bậc 2 51
3.4 Phát triển phương pháp cân bằng nội của Moore 53 3.4.1 Giảm mô hình 53 3.4.2 Các hệ liên tục theo thời gian 55 3.4.3 Hệ thống rời rạc theo thời gian 61 3.5 Thuật toán giảm bậc theo cân bằng nội 67 3.6 Một số ví dụ áp dụng giảm bậc mô hình theo cân bằng nội 69
CHƯƠNG 4:
ỨNG DỤNG GIẢM BẬC MÔ HÌNH CHO BÀI TOÁN QUẢN LÝ
HÀNG ĐỢI TÍCH CỰC (AQM) TRONG VIỄN THÔNG
4.2 Cấu trúc hệ thống điều khiển 81
Trang 84.3 Ứng dụng giảm bậc mô hình cho bài toán quản lý hàng đợi tích cực
4.3.1 Bài toán quản lý hàng đợi 83 4.3.2 Giảm bậc đối tượng theo phương pháp cân bằng nội 84
Trang 9
DANH MỤC CÁC BẢNG BIỂU
1 2.1 Giải thuật WRED 20
2 2.2 Các thông số mặc định của WRED cho các giá trị DSCP
3 3.1
Tham số của các hệ giảm bậc trong mô hình không gian trạng thái và mô hình hàm truyền của các hệ giảm bậc 71
4 3.2 Tham số của các hệ giảm bậc trong mô hình không gian
trạng thái và mô hình hàm truyền của các hệ giảm bậc 76
5 4.1
Mô hình không gian trạng thái và mô hình hàm truyền của
Trang 10
DANH MỤC CÁC HÌNH VẼ
1 1.1 Kiến trúc mạng đơn giản 4
2 1.2 Kiến trúc cơ bản của một router 5
3 1.3 Ví dụ về nghẽn mạng 6
4 2.1 ECN Field trong IP header 12
5 2.2 ECN bit trong IP header 13
6 2.3 Cấu trúc TCP Header với 2 cờ CWR và ECE 14
7 2.4 Cấu trúc 2 trường code field và Reserved field của TCP heade 14
8 2.5 Mô hình quản lý hàng đợi dùng thuật toán RED 16
9 2.6 Sơ đồ hoạt động của WRED 20
10 2.7 Cơ chế loại bỏ gói tin của WRED 21
11 2.8 Biểu diễn các trọng số của WRED 22
12 3.1 Các tín hiệu vào ra của hệ thống 27
13 3.2 Sơ đồ không gian trạng thái của hệ thống 28
14 3.3 Hệ thống khi đưa vào tín hiệu thử x(0) = 0 29
15 3.4 Hệ thống khi đưa tín hiệu xung đầu vào 32
16 3.5 Phân chia mô hình hệ thống 48
17 3.6 Phân chia mô hình hệ thống thành hệ con trội và hệ con yếu 48
18 3.7 Tổ chức của mô hình hệ thống 49
19 3.8 Sơ đồ mô phỏng hệ gốc và các hệ giảm bậc trong Simulink 72
20 3.9 Đáp ứng bước nhảy hệ gốc và các hệ giảm bậc 73
21 3.10 Đặc tính tần số hệ gốc và hệ giảm bậc 73
22 3.11 Sơ đồ mô phỏng hệ gốc và các hệ giảm bậc trong Simulink 77
23 3.12 Đáp ứng bước nhảy hệ gốc và các hệ giảm bậc 78
