Tài liệu Ứ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

ĐẠ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: NGUYỄ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: NGUYỄN ANH TUẤN Mã số: Ngƣời HD khoa học: PGS.TS NGUYỄN HỮU CÔNG HƢỚNG DẪN KHOA HỌC HỌC VIÊN PGS.TS. Nguyễn Hữu Công Nguyễn Anh Tuấn KHOA SAU ĐẠI HỌC BGH TRƢỜNG ĐHKTCN Thái Nguyên, 2011 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 11 2.2.2. Sự đánh dấu trong IP header 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 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.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 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 3.3.4. Phâ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 T A 3.3.4.1. Sự liên quan giữa mô hình (F, G, C) và thành phần của eAtB, e CT T 37 A 3.3.4.2. Thành phần chính của eAtB, 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ÌNH 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 AQM 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 90 4.4 Kết luận chƣơng 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ố 1 2.1 2 2.2 Nội dung Trang Giải thuật WRED 20 Các thông số mặc định của WRED cho các giá trị DSCP khác nhau. 22 Tham số của các hệ giảm bậc trong mô hình không gian 3 3.1 4 3.2 trạng thái và mô hình hàm truyền của các hệ giảm bậc 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 76 Mô hình không gian trạng thái và mô hình hàm truyền của 5 4.1 các hệ giảm bậc Số hóa bởi Trung tâm Học liệu – ĐHTN 85 http://www.lrc-tnu.edu.vn DANH MỤC CÁC HÌNH VẼ TT Hình số Nội dung 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 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 Số hóa bởi Trung tâm Học liệu – ĐHTN Trang http://www.lrc-tnu.edu.vn 28 4.2 Sơ đồ hệ thống điều khiển AQM 82 29 4.3 Đáp ứng h(t) hệ gốc và các hệ giảm bậc 86 30 4.4 Đặc tính biên tần hệ gốc và hệ giảm bậc 87 31 4.5 32 4.6 33 4.7 34 4.8 Gói tín hiệu đầu ra (đỏ) bám tín hiệu yêu cầu (xanh) của hệ điều khiển gốc Tín hiệu điều khiển mờ (đỏ) và tín hiệu sai số (xanh) của hệ gốc bậc 3 Gói dữ liệu đầu ra tiệm cận vói gói dữ liệu yêu cầu q0=200 Tín hiệu điều khiên mờ (đỏ) và tín hiệu sai số (xanh) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn 88 88 89 89 Luận văn thạc sỹ kỹ thuật 1 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công MỞ ĐẦU 1. Đặt vấn đề Mạng viễn thông đƣợc coi là cơ sở hạ tầng truyền thông của hiện tại và tƣơng lai, cho phép tích hợp tất cả các dịch vụ lên trên nền một hệ thống phƣơng tiện truyền thông duy nhất. Một trong các vấn đề đƣợc quan tâm nghiên cứu hiện nay là việc xây dựng nên phƣơng pháp để giải quyết các bài toán điều khiển lƣu lƣợng thông minh trên mạng viễn thông hiện tại. Nhằm giải quyết đƣợc vấn đề tránh tắc nghẽn và tối ƣu hoá thời gian truyền nhận các gói dữ liệu thông qua các router trên mạng. Quản lý hàng đợi nút lõi trên mạng lõi là các dòng lƣu lƣợng tổ hợp. Tại nút lõi, tốc độ dòng lƣu lƣợng tổ hợp đến nó phải đƣợc ƣớc lƣợng để làm cơ sở đƣa ra các quyết định điều khiển. Trễ truyền làm giảm độ chính xác của việc tính toán ƣớc lƣợng tốc độ lƣu lƣợng, thậm chí có thể làm cho thuật toán điều khiển trở nên mất ổn định. Việc ƣớc lƣợng lƣu lƣợng đƣợc thực hiện dựa trên các thông tin giám sát đƣợc cũng nhƣ các số liệu quá khứ và các kết quả dự báo trƣớc đó. Thuật toán điều khiển sẽ duy trì giá trị độ dài xếp hàng tại bộ đệm xung quanh giá trị cân bằng mong muốn. Việc ứng dụng phƣơng trình trạng thái mô tả các đặc trƣng của phần tử đại diện trong mạng viễn thông hiện đại dƣới dạng các hệ thống có động học cần đƣợc quản lý, điều khiển và hệ động học phải đƣa ra tín hiệu điều khiển. Hiển nhiên chất lƣợng điều khiển, vận hành của các phần tử mạng càng cao khi mô hình toán học có khả năng mô tả càng chính xác các động học thực tế xảy ra trong hệ thống. Nhƣng để đáp ứng đòi hỏi đó kết quả của các quá trình mô phỏng là các mô hình toán học phức tạp có bậc rất cao, gây nhiều phiền phức trong khi nắm bắt về hệ thống cũng nhƣ khó khăn nhằm thỏa mãn tính hội tụ, nhu cầu theo thời gian thực, Để điều khiển hệ thống theo thời gian thực thì chúng ta cần phải tìm cách tăng tốc độ tính toán của hệ điều khiển Với các lý do trên đề tài đề xuất việc xây dựng cấu trúc TMN nhằm quản lý các hàng đợi mạng động học xảy ra trên mạng viễn thông. Từ đó tìm giải phảp để đơn giản hóa cấu trúc TMN cụ thể là sử dụng phương pháp giảm bậc mô hình, đồng thời nghiên cứu ảnh hƣởng của TMN đối với hiệu năng và chất lƣợng dịch vụ của mạng viễn thông. 2. Mục tiêu nghiên cứu Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 2 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công Mục đích của luận văn là nghiên cứu và ứng dụng phƣơng pháp giảm bậc mô hình đối với bài toán quản lý lƣu lƣợng mạng để xây dựng cấu trúc mạng TMN theo góc độ lý thuyết hệ thống. Đồng thời từ cấu trúc TMN xây dựng đánh giá hiệu năng và chất lƣợng dịch vụ của mạng viễn thông. 3. Nội dung nghiên cứu - Đánh giá tổng quát về các phƣơng pháp giảm bậc mô hình. - Nghiên cứu giảm bậc mô hình theo phƣơng pháp cân bằng nội. - Bài toán quản lý hàng đơi AQM trong TMN - Áp dụng phƣơng pháp giảm bậc mô hình theo phƣơng pháp cân bằng nội vào bài toán quản lý hàng đợi tại các nút mạng trong TMN 4. Ý nghĩa khoa học và thực tiễn a. Ý nghĩa khoa học: - Giảm bậc mô hình áp dụng theo phƣơng pháp cân bằng nội sẽ giúp giảm độ phức tạp của thuật toán điều khiển, giảm thông tin thừa, tăng tốc độ xử lý. - Xây dựng đƣợc bài toán quản lý ứng dụng giảm bậc mô hình để đánh giá các tác động trong mạng viễn thông. b. Ý nghĩa thực tiễn: Áp dụng bài toán này để xây dựng cấu trúc mạng TMN cho các mạng viễn thông cụ thể. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 3 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công CHƢƠNG 1 TỔNG QUAN VỀ QUẢN LÝ HÀNG ĐỢI 1.1 Giới thiệu chung Ngày nay, với sự bùng nổ và phát triển nhanh chóng của mạng Internet nhƣ hiện nay, hàng triệu chiếc máy tính trên thế giới đã có thể kết nối với nhau để chia sẻ tài nguyên lẫn nhau. Ở một mức độ khác, Internet bao gồm nhiều máy tính chuyên dụng đƣợc gọi là các router đƣợc sử dụng làm cầu nối trung gian chuyển tải dữ liệu giữa các hệ thống với nhau. Và những router này đƣợc kết nối với nhau bởi các mối liên kết truyền thông. Trong một mạng máy tính lớn nhƣ vậy, nhiều hệ thống có thể đang sử dụng mạng cùng một lúc. Và hiện tƣợng quá tải hay tắc nghẽn mạng xuất hiện khi những hệ thống này đồng thời truyền dữ liệu nhiều hơn mức mà các chƣơng chình chuyển vận có thể thực hiện đƣợc. Để giải quyết vấn đề này, ngƣời ta phải sử dụng những giải thuật phát hiện và điều khiển sự tắc nghẽn trong mạng. Việc sử dụng các cơ chế điều khiển tắc nghẽn sẽ giúp các hệ thống cùng chia sẻ cơ sở hạ tầng mạng tốt hơn. 1.2 Quá trình truyền dữ liệu trên mạng và vấn đề tắc nghẽn 1.2.1 Truyền dữ liệu trên một hệ thống mạng Nhƣ đã nói ở phần mở đầu, các máy tính nối mạng với nhau để nhằm liên kết, chia sẻ dữ liệu với nhau. Khi một hệ thống nào đó muốn gửi dữ liệu đến một hệ thống khác, nó sẽ chia các khối dữ liệu đó thành từng mảnh dữ liệu nhỏ gọi là gói tin(packet). Hệ thống gửi đi này đồng thời đóng gói những thông tin điều khiển việc chuyển vận gói tin đó vào một đầu mục của gói (packet header) và đặt nó ở đầu của mỗi gói. Trong một mạng IP, mỗi một packet header chứa địa chỉ nguồn để định rõ địa chỉ nơi gửi gói đó. Packet header cũng chứa địa chỉ IP đích ( destination IP address) nơi mà gói tin phải chuyển đến. Địa chỉ đích này sẽ dùng để các bộ định tuyến xác định địa chỉ đích của gói tin đó và thực hiện công việc chuyển nó đến đúng địa chỉ đó. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 4 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công Trong nhiều trƣờng hợp, không phải lúc nào thiết bị phát và thiết bị thu cũng đƣợc nối trực tiếp với nhau mà chúng phải thông qua các bộ định tuyến trung gian nhƣ ví dụ trong Hình 1.1. Trong những trƣờng hợp này, thiết bị gửi sẽ gửi gói tin đó cho bộ định tuyến mà nó đƣợc nối trực tiếp tới. Khi đó, bộ định tuyến này sẽ sử dụng địa chỉ đích (địa chỉ nơi nhận) của gói nhƣ một chìa khóa để tìm kiếm dữ liệu thông tin lộ trình của nó cho một quyết định chuyển tiếp nó đi. Nếu bộ định tuyến này và thiết bị thu đƣợc kết nối trực tiếp với nhau thì nó sẽ chuyển gói tin đến thẳng thiết bị thu. Nếu không phải đƣợc nối trực tiếp, bộ định tuyến này sẽ chuyển gói tin đến một bộ định tuyến khác mà nó biết đƣợc qua quá trình phân tích thông tin lộ trình ở trên. Quá trình nhƣ vậy đƣợc lặp lại cho đến khi gói tin đƣợc chuyển đến một bộ định tuyến đƣợc kết nối trực tiếp với thiết bị thu và đƣợc chuyển đến đích đến cuối cùng. Hình 1.1: Kiến trúc mạng đơn giản. Các phƣơng thức quản lý hàng đợi tích cực. Trong một hệ thống mạng, một bộ định tuyến (router) thƣờng có nhiều giao diện mạng gắn với những mối liên kết khác nhau nhƣ trong Hình 1.2 . Những liên kết này dùng để kết nối với các bộ định tuyến khác hay kết nối với các mạng con (subnetwork ). Một mạng con thông thƣờng bao gồm một hay nhiều những hệ thống kết thúc ( end system ). Khi một gói tin đƣợc chuyển tới router, nó sẽ sử dụng địa chỉ nơi nhận và dữ liệu thông tin lộ trình của gói tin để xác định liên kết đầu ra cho gói Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 5 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công tin đó. Khi có nhiều gói tin từ nhiều nguồn khác nhau cùng đến router với một lộ trình đầu ra giống nhau thì chỉ có duy nhất một gói tin đƣợc đáp ứng còn các gói tin còn lại bị đẩy vào một hàng đợi tại mối liên kết đầu ra mà chúng yêu cầu. Khi nhịp độ đến router của các gói tin nhƣ vậy tăng lên, chúng sẽ tiếp tục đƣợc đƣa vào hàng đợi đó. Thông thƣờng, hàng đợi này sẽ đƣợc duy trì với cơ chế FIFO ( first in first out) . Với cơ chế này thì những gói tin đến sau sẽ đƣợc xếp vào cuối hàng đợi. Nếu mức độ chuyển các gói tin đi của router lớn hơn mức độ các gói tin khác đến router thì sau một khoảng thời gian nào đó hàng đợi sẽ trở lên rỗng. Còn ngƣợc lại, nếu mức độ chuyển các gói tin đi nhỏ hơn mức độ các gói tin khác đến router thì sau một khoảng thời gian hàng đợi sẽ đầy. Khi đó, router sẽ phải loại bỏ các gói tin theo một cơ chế nào đó, nếu không hiện tƣợng tắc nghẽn sẽ xảy ra. [1] Hình 1.2: Kiến trúc cơ bản của một router 1.2.2 Nghẽn mạng và các nguyên nhân gây nghẽn Khi có quá nhiều gói tin trong mạng ( hay một phần của mạng ) làm cho hiệu năng của mạng giảm đi vì các nút mạng không còn đủ khả năng lƣu trữ, xử lý, truyền đi, chúng bắt đầu bị mất các gói tin dẫn đến sự tắc nghẽn trong mạng. Để tránh sự tắc nghẽn, trong các mạng sử dụng giao thức TCP cho phép giảm lƣu lƣợng truyền khi xảy ra tắc nghẽn bằng cách sử dụng kỹ thuật khởi động chậm (slow-start) và giảm cửa sổ tắc nghẽn theo cấp số nhân. Các bộ định tuyến theo dõi độ dài hàng đợi và sử dụng các tín hiệu điều khiển để thông báo với các máy tính rằng đã xảy ra tắc nghẽn. TCP duy trì một cửa sổ gọi là cửa sổ tắc nghẽn dùng để giới hạn lƣợng dữ liệu ở mức ít hơn kích thƣớc vùng đệm của nơi nhận khi Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 6 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công xảy ra sự tắc nghẽn. Kích thƣớc cửa sổ đƣợc tính nhƣ sau: Kích thƣớc đƣợc phép=min(Kích thƣớc gói tin,kích thƣớc cửa sổ tắc nghẽn) Khi bị mất một gói tin, giảm kích thƣớc cửa sổ tắc nghẽn đi một nửa (cho tới khi chỉ còn kích thƣớc của một gói tin). Với những gói tin vẫn còn nằm trong cửa sổ đƣợc phép, nhƣợng bộ bằng cách gia tăng bộ đếm thời gian truyền lại theo hàm mũ. Quá trình khởi động chậm làm giảm luồng gói tin truyền qua các nút mạng nhƣng đồng thời giải phóng đƣợc các gói tin còn tồn ở hàng đợi. [2] Hình 1.3: Ví dụ về nghẽn mạng 1.2.3 Cơ chế điều khiển luồng để tránh tắc nghẽn Nhƣ đã nói sơ lƣợc ở trên, điều khiển luồng là quá trình điều khiển gói báo nhận hoặc điều chỉnh kích thƣớc cửa sổ trƣợt. Việc sử dụng cửa sổ trƣợt có kích thƣớc thay đổi là hỗ trợ việc điều khiển tốc độ truyền dữ liệu cũng nhƣ là việc truyền đáng tin cậy. Để tránh việc nhận nhiều gói tin hơn khả năng lƣu trữ, nơi nhận sẽ gửi đi thông báo cửa sổ nhỏ hơn và ngƣợc lại. Trƣờng hợp xấu nhất, nơi nhận sẽ gửi thông báo cửa sổ có kích thƣớc là zero để ngƣng tất cả việc truyền dữ liệu. Nhƣng việc nhiều lần ngƣng truyền với những đợt ngắn do tràn hàng đợi tạm thời là không cần thiết, điều này làm tăng sự dao động thông lƣợng. Vì vậy, cần có cơ chế điều khiển hợp lý giữa luồng gói tin đến và cơ chế xử lý tại nút nhận thích hợp. Thông thƣờng, các điểm đầu cuối thƣờng không nhận biết sự tắc nghẽn và tại sao chúng xảy ra. Bởi vì tắc nghẽn là do sự trì hoãn gia tăng, nên hầu hết các phần Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 7 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công mềm giao thức sử dụng bộ đếm thời gian và truyền lại. Vấn đề này gọi là sự sụp đổ do nghẽn mạch. Giải quyết toàn diện vấn đề này rất phức tạp, liên quan đến nhiều tầng giao thức khác nhau và nhiều dịch vụ khác nhau. Thông thƣờng, việc điều khiển sự tắc nghẽn đƣợc thực hiện qua 3 bƣớc sau: Bƣớc 1: Làm chủ hệ thống để phát hiện khi nào xảy ra và xảy ra ở đâu. Khi xác định đƣợc tắc nghẽn ở đâu, lúc đó bƣớc thứ 2 sẽ đƣợc thực hiện. Bƣớc 2: Chuyển thông tin đến những nút mạng ( router) khác mà ở đó có thể tiến hành giải quyết đƣợc công việc đồng thời thông báo tắc nghẽn ( ECN : Explicit Congestion Notification ) cho các router khác. Tất nhiên, các gói tin phụ sẽ làm tăng tải vào thời điểm nhiều tải không cần thiết. Một phƣơng pháp khác là máy chủ hay router gửi các gói tin thăm dò để biết rõ ràng về sự tắc nghẽn. Thông tin có thể đƣợc sử dụng chỉ lƣu thông quanh khu vực có sự cố. Bƣớc 3: Khi nhận đƣợc thông tin về sự tắc nghẽn, máy chủ có những hành động thích hợp để giảm sự tắc nghẽn nhƣ: Sắp xếp lại tuyến đƣờng truyền tin, hạn chế không cho truyền gói tin vào những đƣờng xảy ra tắc nghẽn, … Các phƣơng pháp có thể hoạt động ở trạm nguồn hoặc ở trạm đích. Hoạt động ở trạm nguồn: Bao gồm gói tin đƣợc gửi đi, trở lại từ điểm tắc nghẽn báo cho nguồn hoặc nguồn suy đoán về sự tồn tại của tắc nghẽn bằng việc quan sát thời gian cần thiết cho sự báo nhận đi trở lại. Hoạt động ở trạm đích: Sự hiện diện của tắc nghẽn có nghĩa là tải( tạm thời) lớn hơn lƣợng tin ( một phần hệ thống ) có thể quản lý. Hai giải pháp có thể thực hiện để giải quyết là tăng tài nguyên ( lƣợng thông tin có thể lƣu trữ) hoặc giảm tải. Tuy nhiên, đôi khi không thể tăng khả năng tài nguyên lên đƣợc hoặc nếu tăng thì chỉ tăng đến một giới hạn nhất định. Cách duy nhất để tác động sự tắc nghẽn là giảm tải. Để giảm tải có thể phủ nhận dịch vụ với nơi sử dụng, giảm bớt dịch vụ từ các trạm gửi đến hoặc cải tiến giao thức điều khiển phù hợp, cải tiến cơ chế xử lý gói tin tại hàng đợi của các nút mạng trung tâm theo một trật tự ƣu tiên phù hợp. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 8 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công 1.3 Sự cần thiết phải quản lý hàng đợi 1.3.1 Khái niệm quản lý hàng đợi tích cực AQM (Active Queue Managament) Quản lý hàng đợi tích cực ( AQM ) là một cơ chế phát hiện sự tắc nghẽn trong hệ thống mạng. Những giải thuật quản lý hàng đợi tích cực chạy bên trong những bộ định tuyến và phát hiện sự tắc nghẽn phôi thai điển hình bằng cách theo dõi chiều dài hàng đợi tức thời hay chiều dài hàng đợi trung bình. Khi kích thƣớc hàng đợi trung bình vƣợt quá một ngƣỡng nhất định nhƣng vẫn còn ít hơn khả năng xử lý của hàng đợi, những giải thuật quản lý hàng đợi tích cực xem xét sự tắc nghẽn trên mối liên kết và thông báo trở lại cho những hệ thống bằng cách thả một số gói tin chuyển đến bộ định tuyến. Các giải thuật AQM có thể cũng đặt một bit vào header của một gói tin nào đó rồi chuyển nó về phía thiết bị nhận của gói đó sau khi sự tắc nghẽn đƣợc phát hiện. Khi thiết bị thu nhận đƣợc gói tin đã đƣợc đánh dấu này, nó sẽ gửi trở lại bên phát gói tin đó một bit khác trong phiên làm việc giữa nó và bên phát. Khi bên phát nhận đƣợc tín hiệu này, nó sẽ giảm bớt tín hiệu truyền dữ liệu . Quá trình đặt một bit đặc biệt trong header của gói tin bởi những giải thuật AQM và việc chuyển gói tin đã đƣợc đánh dấu đó đến bên nhận gọi là sự đánh dấu (mark) . Gói tin chứa bit đặc biệt trong quá trình trên gọi là gói tin đƣợc đánh dấu. Những hệ thống trải qua việc bị đánh dấu hoặc bị mất mát gói tin sẽ giảm nhịp độ truyền dữ liệu để giải toả sự tắc nghẽn và ngăn việc tràn hàng đợi. Mục tiêu quan trọng nhất của các giải thuật AQM là ngăn ngừa sự tắc nghẽn trƣớc khi nó thực sự xuất hiện. Nhƣ vậy, việc sử dụng hiệu quả các giải thuật quản lý hàng đợi sẽ đem lại những hiệu quả đó là: giảm bớt sự mất mát các gói tin, đạt đƣợc một lƣu lƣợng truyền dữ liệu cao và một độ trễ hàng đợi thấp. Điều này thật sự là một cải thiện rất tốt cho những ứng dụng tƣơng tác nhƣ duyệt Web hay các cuộc hội thoại trực tiếp. Một mục tiêu quan trọng khác của quản lý hàng đợi tích cực là quản lý tắc nghẽn với yêu cầu ngăn ngừa sự đồng bộ hoá toàn cục ( global synchronization ) bằng sự ngẫu nhiên trong quyết định đánh dấu hay loại bỏ gói tin. Khi một sự tắc Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn Luận văn thạc sỹ kỹ thuật 9 Hướng dẫn KH: PGS.TS Nguyễn Hữu Công nghẽn đƣợc nghi ngờ trên một mối liên kết nào đó, đa số những giải thuật quản lý hàng đợi không đánh dấu hay loại bỏ gói tin một cách một cách tất định mà là ngẫu nhiên. Xác suất đánh dấu hay loại bỏ của một gói tin đƣợc chuyển đến thông thƣờng phụ thuộc vào độ ƣớc tính của sự tắc nghẽn trên mối liên kết. [1] 1.3.2 Sự cần thiết phải có quản lý hàng đợi tích cực Kỹ thuật truyền thống để quản lý chiều dài hàng đợi là thiết lập một giá trị chiều dài cực đại cho mỗi hàng đợi, những gói tin( packet ) đƣợc chấp nhận đƣa vào hàng đợi cho đến khi hàng đợi đạt giá trị max, sau đó sẽ loại bỏ những gói tin đƣợc chuyển đến tiếp theo cho đến khi hàng đợi đƣợc giảm bớt bởi các gói đã đƣợc truyền đi. Kỹ thuật này đƣợc gọi là “Drop Tail” ( Khi hàng đợi full nó sẽ loại bỏ những gói tin ở cuối hàng đợi). Phƣơng pháp này có 2 hạn chế: + lock out ( khoá): Trong một số trƣờng hợp, gói tin cuối cho phép một kết nối đơn hoặc vài luồng dữ liệu độc quyền xếp hàng ngăn ngừa các kết lối khác trong cùng hàng đợi. Hiện tƣợng “lock out” là kết quả của sự đồng bộ hoá hay các hiệu ứng thời gian khác. + full queue (hàng đợi đầy ): Kỹ thuật Drop Tail cho phép duy trì hàng đợi ở nguyên trạng thái trong suốt thời gian dài cho đến khi có các tín hiệu tắc nghẽn ( các tín hiệu tắc nghẽn này đƣợc truyền qua các gói tin bị loại bỏ khi hàng đợi đầy). Điều này rất quan trọng trong việc giảm bớt kích thƣớc hàng đợi dừng và đây là điều quan trọng nhất trong mục đích quản lý hàng đợi. Giả thiết đơn giản đó là có một sự cân bằng đơn giản giữa độ trễ ( delay ) và lƣu lƣợng. Nếu hàng đợi đầy hoặc gần đầy, dẫn đế burst làm cho nhiều gói tin đƣợc loại bỏ. Điều này có thể dẫn đến một sự đồng bộ hóa ở phạm vi lớn các gói tin đến sau, làm cho lƣu lƣợng toàn bộ quá trình giảm. Full Queue gây lên trạng thái không ổn định trong hàng đợi. Một cơ chế quản lý hàng đợi tích cực có thể đem lại những ƣu điểm sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn