Luận án Nghiên cứu cải tiến cơ chế điều khiển tại các nút mạng

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN KIM QUỐC NGHIÊN CỨU CẢI TIẾN CƠ CHẾ ĐIỀU KHIỂN TẠI CÁC NÚT MẠNG LUẬN ÁN TIẾN SĨ MÁY TÍNH HUẾ - 2015 ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN KIM QUỐC NGHIÊN CỨU CẢI TIẾN CƠ CHẾ ĐIỀU KHIỂN TẠI CÁC NÚT MẠNG CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 62.48.01.01 LUẬN ÁN TIẾN SĨ MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. GS. TS. NGUYỄN THÚC HẢI 2. PGS. TS. VÕ THANH TÚ HUẾ - 2015 i LỜI CAM ĐOAN Tôi xin cam đoan luận án này là công trình nghiên cứu khoa học của tôi và không trùng lặp với bất kỳ công trình khoa học nào khác. Các số liệu trình bày trong luận án đã được kiểm tra kỹ và phản ánh hoàn toàn trung thực. Các kết quả nghiên cứu do tác giả đề xuất chưa từng được công bố trên bất kỳ tạp chí nào đến thời điểm này ngoài những công trình của tác giả. Tp. Huế, ngày 5 tháng 10 năm 2015 Tác giả luận án Nguyễn Kim Quốc ii LỜI CÁM ƠN Trước hết, từ tận đáy lòng, tôi xin bày tỏ lòng tri ân sâu sắc nhất đến Giáo sư, Tiến sĩ Nguyễn Thúc Hải - Viện công nghệ thông tin – Trường Đại học Bách Khoa Hà Nội và Phó giáo sư, Tiến sĩ Võ Thanh Tú – Khoa công nghệ thông tin - Đại học Khoa học đã tận tình hướng dẫn, tạo mọi điều kiện thuận lợi nhất, giúp tôi thực hiện và hoàn thành luận án này. Tôi xin được gửi lời cảm ơn chân thành tới Ban giám đốc Đại học Huế, Ban giám hiệu Trường Đại học Khoa học và Ban lãnh đạo Trường Đại học Nguyễn Tất Thành đã chia sẻ, động viên tôi vượt qua mọi khó khăn để hoàn thành công việc nghiên cứu của mình. Tôi xin trân trọng, biết ơn sâu sắc Quý Thầy Cô trong Khoa công nghệ thông tin - Đại học Khoa học đã tận tâm dạy tôi và tạo điều kiện giúp đỡ tôi trong suốt thời gian tôi tham gia học tập và nghiên cứu khoa học tại Khoa. Tôi xin chân thành cảm ơn các nhà khoa học đã phản biện, đóng góp nhiều ý kiến xây dựng và trao đổi về các vấn đề lý thuyết cũng như thực tiễn để luận án được hoàn thiện. Cuối cùng, tôi xin bày tỏ lời cảm ơn đến vợ và con đã luôn chia sẻ, gánh đỡ những khó khăn cũng như dành những tình cảm, động viên tinh thần không thể thiếu đối với tôi trong suốt quá trình thực hiện luận án này. Tp. Huế, ngày 5 tháng 10 năm 2015 Tác giả luận án Nguyễn Kim Quốc iii MỤC LỤC LỜI CAM ĐOAN ........................................................................................................ i LỜI CÁM ƠN ............................................................................................................ ii MỤC LỤC ................................................................................................................. iii DANH MỤC KÝ HIỆU VÀ VIẾT TẮT .................................................................. ix DANH MỤC HÌNH ẢNH VÀ ĐỒ THỊ .................................................................. xii DANH MỤC BẢNG BIỂU ...................................................................................... xv MỞ ĐẦU ..................................................................................................................... 1 CHƯƠNG 1. KIỂM SOÁT TẮC NGHẼN TRONG MẠNG TCP/IP DỰA TRÊN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TẠI NÚT MẠNG ............................................ 9 1.1. Kiểm soát tắc nghẽn trong mạng TCP/IP ............................................................. 9 1.1.1. Mô hình hoạt động của TCP/IP ...................................................................... 10 1.1.1.1. Mô hình truyền thông trong mạng TCP/IP ................................................ 10 1.1.1.2. Mô hình toán học của TCP/IP ...................................................................... 11 1.1.2. Tắc nghẽn trong mạng TCP/IP ....................................................................... 12 1.1.2.1. Nguyên nhân tắc nghẽn ................................................................................ 13 1.1.2.2. Nguyên lý kiểm soát tắc nghẽn .................................................................... 14 1.1.2.3. Kỹ thuật kiểm soát tắc nghẽn ....................................................................... 14 1.1.3. Kiểm soát tắc nghẽn của giao thức TCP ........................................................ 15 1.1.4. Kiểm soát tắc nghẽn bằng quản lý hàng đợi .................................................. 18 1.1.5. Quản lý hàng đợi tích cực .............................................................................. 19 1.1.5.1. Kiến trúc nút mạng ....................................................................................... 19 1.1.5.2. Kiểm soát tắc nghẽn bằng quản lý hàng đợi tích cực .................................. 20 1.1.5.3. Ưu điểm của quản lý hàng đợi tích cực ....................................................... 21 1.1.6. Kỹ thuật thông báo tắc nghẽn rõ ràng ............................................................ 22 1.2. Phân tích và đánh giá các cơ chế quản lý hàng đợi tích cực ........................... 23 iv 1.2.1. Cơ chế quản lý dựa trên chiều dài hàng đợi ................................................... 24 1.2.1.1. Cơ chế RED ................................................................................................. 24 1.2.1.2. Cơ chế FRED ............................................................................................... 26 1.2.2. Cơ chế quản lý dựa trên tải nạp ...................................................................... 27 1.2.2.1. Cơ chế BLUE ............................................................................................... 27 1.2.2.2. Cơ chế SFB .................................................................................................. 28 1.2.3. Cơ chế quản lý dựa trên chiều dài hàng đợi và tải nạp .................................. 30 1.2.3.1. Cơ chế REM ................................................................................................. 30 1.2.3.2. Cơ chế GREEN ............................................................................................ 32 1.2.4. Đánh giá hiệu năng và phân lớp ứng dụng các cơ chế AQM ........................ 33 1.2.4.1. Đánh giá hiệu năng cơ chế AQM ................................................................. 33 1.2.4.2. Phân lớp ứng dụng các cơ chế AQM ........................................................... 33 1.3. Tình hình ứng dụng logic mờ trong quản lý hàng đợi tích cực ......................... 34 1.3.1. Các cơ chế dùng logic mờ cải tiến RED ........................................................ 34 1.3.1.1. Cơ chế FEM ................................................................................................. 34 1.3.1.2. Cơ chế FCRED ............................................................................................ 35 1.3.2. Các cơ chế dùng logic mờ cải tiến BLUE ...................................................... 35 1.3.2.1. Cơ chế FUZZY BLUE ................................................................................. 35 1.3.2.2. Cơ chế DEEP BLUE .................................................................................... 36 1.3.3. Các cơ chế dùng logic mờ cải tiến REM ........................................................ 36 1.3.3.1. Cơ chế FREM .............................................................................................. 36 1.3.3.2. Cơ chế FUZREM ......................................................................................... 36 1.3.4. Cải tiến cơ chế quản lý hàng đợi dùng điều khiển mờ ................................... 36 1.3.4.1. Cải tiến cơ chế BLUE .................................................................................. 37 1.3.4.2. Cải tiến cơ chế SFB...................................................................................... 37 1.4. Một số tồn tại trong các cơ chế quản lý hàng đợi tích cực ................................ 38 v 1.5. Kết luận chương ................................................................................................ 39 CHƯƠNG 2. CẢI TIẾN CƠ CHẾ QUẢN LÝ HÀNG ĐỢI TÍCH CỰC DỰA TRÊN ĐIỀU KHIỂN MỜ THÍCH NGHI ................................................................. 40 2.1. Cơ sở toán học của logic mờ .............................................................................. 40 2.1.1. Tập mờ ........................................................................................................... 40 2.1.2. Các dạng hàm thuộc của tập mờ .................................................................... 41 2.1.3. Các thông số đặc trưng cho tập mờ ................................................................ 42 2.1.4. Các phép toán trên tập mờ .............................................................................. 43 2.1.5. Luật hợp thành mờ ......................................................................................... 44 2.1.6. Giải mờ ........................................................................................................... 46 2.1.7. Điều khiển mờ ................................................................................................ 47 2.1.7.1. Mô hình điều khiển mờ ................................................................................ 47 2.1.7.2. Hệ mờ Mamdani .......................................................................................... 48 2.1.7.3. Hệ mờ Sugeno .............................................................................................. 49 2.2. Phân tích các cơ chế AQM sử dụng logic mờ .................................................... 49 2.2.1. Phân tích cơ chế FEM .................................................................................... 49 2.2.2. Phân tích cơ chế FUZREM ............................................................................ 52 2.2.3. Một số vấn đề còn tồn tại của cơ chế AQM dùng điều khiển mờ .................. 54 2.3. Xây dựng mô hình điều khiển mờ thích nghi AFC cải tiến AQM ..................... 55 2.3.1. Đề xuất bộ điều khiển mờ thích nghi AFC cải tiến AQM ............................. 55 2.3.1.1. Mô hình điều khiển mờ thích nghi AFC ...................................................... 55 2.3.1.2. Hoạt động của bộ điều khiển mờ thích nghi AFC ....................................... 56 2.3.2. Xác định các biến đầu vào và đầu ra cho AFC .............................................. 57 2.3.3. Xây dựng bộ điều khiển mờ cho AFC ........................................................... 57 2.3.3.1. Hệ số đầu vào ............................................................................................... 57 2.3.3.2. Mờ hóa đầu vào ............................................................................................ 57 vi 2.3.3.3. Hệ luật cơ sở suy diễn mờ ............................................................................ 58 2.3.3.4. Giải mờ đầu ra .............................................................................................. 58 2.3.4. Xây dựng mô hình mẫu cho AFC .................................................................. 59 2.3.5. Xây dựng cơ chế thích nghi cho AFC ............................................................ 59 2.4. Cải tiến cơ chế RED bằng điều khiển mờ thích nghi AFC ............................. 60 2.4.1. Mờ hóa biến đầu vào của FLRED .................................................................. 61 2.4.2. Mờ hóa biến đầu ra của FLRED .................................................................... 63 2.4.3. Xây dựng luật cơ sở suy diễn mờ cho FLRED .............................................. 63 2.4.4. Mặt cong suy diễn của FLRED ...................................................................... 65 2.4.5. Minh họa tính toán đầu ra hệ thống mờ FLRED............................................ 65 2.5. Cải tiến cơ chế REM bằng điều khiển mờ thích nghi AFC ............................. 67 2.5.1. Mờ hóa biến đầu vào của FLREM ................................................................. 67 2.5.2. Mờ hóa biến đầu ra của FLREM .................................................................... 69 2.5.3. Xây dựng luật suy diễn cho FLREM ............................................................. 70 2.5.4. Mặt cong suy diễn của FLREM ..................................................................... 72 2.6. Mô phỏng đánh giá hiệu quả của cơ chế FLRED và FLREM ........................... 73 2.6.1. Cài đặt mô phỏng các cơ chế FLRED và FLREM ......................................... 73 2.6.1.1. Cài đặt chương trình cho các cơ chế FLRED và FLREM ........................... 73 2.6.1.2. Qui trình mô phỏng và đánh giá các cơ chế AQM ...................................... 73 2.6.1.3. Các tiêu chí đánh giá hiệu năng các cơ chế AQM ....................................... 74 2.6.2. Đánh giá độ ổn định các cơ chế FLRED và FLREM .................................... 75 2.6.2.1. Mô hình mạng đơn máy nhận ...................................................................... 75 2.6.2.2. Kiểm soát hàng đợi của các cơ chế FLRED và FLREM ............................. 76 2.6.2.3. Khả năng đáp ứng của các cơ chế FLRED và FLREM ............................... 78 2.6.3. Đánh giá hiệu năng các cơ chế FLRED và FLREM ...................................... 80 2.6.3.1. Mô hình mạng đa máy nhận ......................................................................... 80 vii 2.6.3.2. Đánh giá tỉ lệ mất gói tin của cơ chế FLRED và FLREM ........................... 82 2.6.3.3. Đánh giá mức độ sử dụng đường truyền của cơ chế FLRED và FLREM ... 83 2.7. Kết luận chương ................................................................................................. 84 CHƯƠNG 3. TÍCH HỢP LẬP LUẬN MỜ VỚI MẠNG NƠ-RON NÂNG CAO HIỆU NĂNG QUẢN LÝ HÀNG ĐỢI TÍCH CỰC ................................................. 85 3.1. Tổng quan mạng nơ-ron nhân tạo ...................................................................... 85 3.1.1. Đơn vị xử lý (nơ-ron) ..................................................................................... 86 3.1.1.1. Liên kết trong mạng nơ-ron ......................................................................... 86 3.1.1.2. Quá trình học của mạng nơ-ron ................................................................... 87 3.1.2. Mạng nơ-ron truyền thẳng một lớp ................................................................ 88 3.1.2.1. Mạng Perceptron một lớp............................................................................. 88 3.1.2.2. Quá trình học mạng nơ-ron truyền thẳng một lớp ....................................... 89 3.1.3. Mạng nơ-ron truyền thẳng nhiều lớp ............................................................. 89 3.1.3.1. Thuật toán học lan truyền ngược ................................................................ 89 3.1.3.2. Huấn luyện mạng theo thuật toán lan truyền ngược .................................... 91 3.2. Kết hợp điều khiển mờ với mạng nơ-ron ........................................................... 92 3.2.1. Nền tảng của sự kết hợp ................................................................................. 92 3.2.2. Các mô hình kết hợp ...................................................................................... 93 3.3. Xây dựng mô hình mạng nơ-ron mờ FNN cải tiến AQM .................................. 94 3.3.1. Đề xuất bộ điều khiển mạng nơ-ron mờ FNN cải tiến AQM ........................ 94 3.3.1.1. Mô hình mạng nơ-ron mờ FNN ................................................................... 94 3.3.1.2. Hoạt động của bộ điều khiển nơ-ron mờ FNN ............................................ 95 3.3.2. Xây dựng bộ điều khiển nơ-ron mờ FNN ...................................................... 95 3.3.2.1. Tạo nơ-ron mờ cho FNN .............................................................................. 95 3.3.2.2. Xây dựng mạng nơ-ron mờ FNN ................................................................. 96 3.3.2.3. Huấn luyện mạng nơ-ron mờ FNN .............................................................. 97 viii 3.3.2.4. Chỉnh định tham số hàm thuộc của AFC ..................................................... 98 3.3.3. Thuật toán lan truyền ngược cải tiến IBP ...................................................... 98 3.3.3.1. Chuẩn hóa số liệu đầu vào ra ....................................................................... 99 3.3.3.2. Bổ sung hệ số quán tính ............................................................................... 99 3.3.3.3. Điều chỉnh tốc độ học ................................................................................ 100 3.3.3.4. Thuật toán lan truyền ngược cải tiến.......................................................... 100 3.4. Xây dựng cơ chế quản lý hàng đợi tích cực FNNRED .................................... 101 3.4.1. Cài đặt cơ chế FNNRED .............................................................................. 101 3.4.2. Huấn luyện mạng FNN trong FNNRED ...................................................... 102 3.4.3. Kết quả huấn luyện của FNN trong FNNRED............................................. 102 3.5. Xây dựng cơ chế quản lý hàng đợi tích cực FNNREM ................................... 104 3.5.1. Cài đặt cơ chế FNNREM ............................................................................. 104 3.5.2. Huấn luyện mạng FNN trong FNNREM ..................................................... 105 3.5.3. Kết quả huấn luyện của FNN trong FNNREM ............................................ 105 3.6. Mô phỏng đánh giá hiệu quả của cơ chế FNNRED và FNNREM .................. 107 3.6.1. Đánh giá độ ổn định của cơ chế FNNRED và FNNREM ............................ 107 3.6.1.1. Kiểm soát hàng đợi của cơ chế FNNRED và FNNREM ........................... 107 3.6.1.2. Khả năng đáp ứng của cơ chế FNNRED và FNNREM ............................. 109 3.6.2. Đánh giá hiệu năng của cơ chế FNNRED và FNNREM ............................. 112 3.6.2.1. Đánh giá tỉ lệ mất gói tin của cơ chế FNNRED và FNNREM .................. 112 3.6.2.2. Đánh giá sử dụng đường truyền của FNNRED và FNNREM ................... 113 3.7. Kết luận chương ............................................................................................... 114 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................. 116 DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA LUẬN ÁN ......................... 118 TÀI LIỆU THAM KHẢO ....................................................................................... 119 PHỤ LỤC A ............................................................................................................ 127 PHỤ LỤC B ............................................................................................................ 136 ix DANH MỤC KÝ HIỆU VÀ VIẾT TẮT Ký hiệu Diễn giải tiếng Anh Diễn giải tiếng Việt ACK Acknowledgement Bản tin báo nhận AFC Adaptive Fuzzy Controller Bộ điều khiển mờ thích nghi AIMD Additive-Increase Multiplicative-Decrease Tăng cấp số cộng giảm cấp số nhân ANN Artificial Neural Network Mạng nơ-ron nhân tạo AQM Active Queue Management Quản lý hàng đợi tích cực BLUE BLUE Cơ chế quản lý hàng đợi BLUE BP BackPropagation Lan truyền ngược CE Congestion Experienced Chỉ thị tắc nghẽn CQS Classification Queue Schedular Phân lớp - hàng đợi - lập lịch CWND Congestion Window Cửa sổ tắc nghẽn DT Drop Tail Cơ chế loại bỏ cuối hàng DVP Droping Probability Xác suất loại bỏ gói ECN Explicit Congestion Notification Thông báo tắc nghẽn rõ ràng FCRED Fuzzy Control RED Cơ chế mờ cải tiến RED FIFO First In First Out Vào trước ra trước FIS Fuzzy Inference System Hệ suy luận mờ FL Fuzzy Logic Logic mờ FLC Fuzzy Logic Controller Bộ điều khiển logic m