Tài liệu ứng dụng đại số gia tử cho bài toán quản lý hàng đợi tích cực trên mạng tcp ip

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP LÊ THẾ HỢP ỨNG DỤNG ĐẠI SỐ GIA TỬ CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRÊN MẠNG TCP/IP LUẬN VĂN THẠC SĨ KỸ THUẬT VIỄN THÔNG THÁI NGUYÊN - 2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP LÊ THẾ HỢP ỨNG DỤNG ĐẠI SỐ GIA TỬ CHO BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRÊN MẠNG TCP/IP Chuyên ngành: Kỹ thuật viễn thông Mã số: 8.52.02.08 LUẬN VĂN THẠC SĨ KỸ THUẬT VIỄN THÔNG KHOA ĐIỆN TỬ NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN PHƯƠNG HUY THÁI NGUYÊN - 2020 LỜI CAM ĐOAN Tên tôi là: Lê Thế Hợp Sinh ngày: 13/03/1984 Học viên lớp cao học CHK20KTĐT - Trường Đại học Kỹ thuật Công nghiệp Đại học Thái Nguyên. Hiện đang công tác tại: Trường Cao Đẳng nghề công nghệ và nông lâm Đông Bắc Xin cam đoan: Đề tài “Ứng dụng đại số gia tử cho bài toán quản lý hàng đợi tích cực trên mạng TCP/IP” do Thầy giáo TS. Nguyễn Phương Huy hướng dẫn là công trình nghiên cứu của riêng tôi. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng như nội dung trong đề cương và yêu cầu của thầy giáo hướng dẫn. Nếu sai tôi hoàn toàn chịu trách nhiệm trước hội đồng khoa học và trước pháp luật. Thái Nguyên, ngày 10 tháng 5 năm 2020 Tác giả luận văn Lê Thế Hợp 1 LỜI CẢM ƠN Sau một thời gian nghiên cứu và làm việc nghiêm túc, được sự động viên, giúp đỡ và hướng dẫn tận tình của Thầy giáo hướng dẫn TS. Nguyễn Phương Huy, luận văn với đề tài “Ứng dụng đại số gia tử cho bài toán quản lý hàng đợi tích cực trên mạng TCP/IP” đã hoàn thành. Tôi xin bày tỏ lòng biết ơn sâu sắc đến: Thầy giáo hướng dẫn TS. Nguyễn Phương Huy đã tận tình chỉ dẫn, giúp đỡ tôi hoàn thành luận văn này. Trường Đại học công nghệ Kỹ thuật công nghệp và đặc biệt là các Thầy, cô trong Khoa Điện tử đã giúp đỡ tôi trong quá trình học tập cũng như thực hiện luận văn. Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động viên, khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn thành luận văn này. Thái Nguyên, ngày 28 tháng 3 năm 2020 Tác giả luận văn Lê Thế Hợp 2 MỤC LỤC LỜI CAM ĐOAN.................................................................................................. 1 LỜI CẢM ƠN ....................................................................................................... 2 MỤC LỤC ............................................................................................................. 3 DANH MỤC CÁC TỪ VIẾT TẮT ...................................................................... 5 DANH MỤC CÁC HÌNH ẢNH ........................................................................... 7 DANH MỤC CÁC BẢNG BIỂU ......................................................................... 8 MỞ ĐẦU ............................................................................................................... 1 CHƯƠNG 1 BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRÊN MẠNG TCP/IP ....................................................................................................... 5 1.1.Mạng TCP/IP và bài toán điều khiển tắc nghẽn .............................................. 5 1.1.1. Truyền số liệu trên mạng TCP/IP................................................................ 5 1.1.2. Các giải thuật điều khiển tắc nghẽn theo giao thức TCP ............................ 7 1.2.Quản lý hàng đợi theo phương pháp truyền thống (thụ động)...................... 11 1.3.Quản lý hàng đợi tích cực ............................................................................. 12 1.3.1. Khái niệm quản lý hàng đợi tích cực ........................................................ 12 1.3.2. Phân loại các phương pháp quản lý hàng đợi tích cực ............................. 13 1.4.Hiện trạng nghiên cứu và các phương pháp tiếp cận bài toán AQM trong các nghiên cứu trước đây. .......................................................................................... 14 1.4.1. Các phương pháp AQM dựa trên chiều dài hàng đợi ............................... 14 1.4.2. Quản lý hàng đợi tích cực dựa trên tốc độ lưu lượng đến ........................ 18 1.4.3. Các giải thuật AQM dựa trên sự kết hợp giữa độ dài hàng đợi và kiểm soát lưu lượng đến ...................................................................................................... 21 1.5.Một số vấn đề lớn còn tồn tại đối với bài toán AQM ................................... 23 CHƯƠNG 2 ĐẠI SỐ GIA TỬ VÀ ỨNG DỤNG TRONG ĐIỀU KHIỂN..... 26 2.1.Đại số gia tử .................................................................................................. 26 2.1.1. Dẫn nhập ................................................................................................... 26 2.1.2. Định nghĩa đại số gia tử ............................................................................ 28 2.2.Các đại lượng đo trên đại số gia tử ............................................................... 30 3 2.2.1. Các hàm đo ................................................................................................ 31 2.2.2. Định lượng đại số gia tử ............................................................................ 32 2.3.Lập luận xấp xỉ dựa trên đại số gia tử và giải bài toán suy luận xấp xỉ bằng nội suy ................................................................................................................. 35 2.4.Chuyển điều khiển mờ sang điều khiển dùng đại số gia tử .......................... 36 2.4.1. Điều khiển mờ kinh điển ........................................................................... 36 2.4.2. Điều khiển sử dụng đại số gia tử............................................................... 37 CHƯƠNG 3 ỨNG DỤNG ĐẠI SỐ GIA TỬ TRONG BÀI TOÁN CẢI TIẾN GIẢI THUẬT REM_AQM ................................................................................. 38 3.1.Nhắc lại giải thuật REM................................................................................ 38 3.2.Bộ điều khiển gia tử cho bài toán cải tiến giải thuật REM ........................... 39 3.2.1. Lựa chọn các thành phần đại số gia tử đối với các biến vào/ra. ............... 40 3.2.2. Xây dựng mô hình toán học cho mối quan hệ vào – ra của bộ điều khiển HA ....................................................................................................................... 41 3.2.3. Tính toán giá trị định lượng ngữ nghĩa cho các nhãn ngôn ngữ của các biến ...................................................................................................................... 43 3.3.Mô phỏng và đánh giá giải thuật HAC-REM với mạng đa tắc nghẽn.......... 46 3.3.1. Lựa chọn các tham số mô phỏng .............................................................. 46 3.3.2. Cấu trúc mạng mô phỏng .......................................................................... 47 3.3.3. Ảnh hưởng của lưu lượng tải và tốc độ đáp ứng ...................................... 48 3.3.4. Ảnh hưởng của trễ đến các phương pháp AQM ....................................... 50 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .......................................................... 52 TÀI LIỆU THAM KHẢO ................................................................................... 55 4 DANH MỤC CÁC TỪ VIẾT TẮT Ký hiệu ACK AIMD Tiếng Anh Tiếng Việt Acknowledgement Bản tin báo nhận Additive– Increase MultiplicativeDecrease Tăng cộng giảm nhân AQM Active Queue Management ARED Adaptive Random Early Detection AVQ Adaptive Virtual Queue CE Congestion Experienced Chỉ thị tắc nghẽn Congestion Window Cửa sổ tắc nghẽn DT Drop Tail Cơ chế loại bỏ cuối hàng DP Droping Probability Xác suất loại bỏ gói Explicit Congestion Notification Thông báo tắc nghẽn rõ ràng Expert System Hệ chuyên gia CWND ECN ES FIFO FL Quản lý hàng đợi tích cực Phát hiện sớm ngẫu nhiên thích nghi Giải thuật hàng đợi ảo thích nghi Hàng đợi phục vụ theo kiểu First In First Out vào trước ra trước Fuzzy Logic Logic mờ Fuzzy Logic Controller Bộ điều khiển logic mờ FS Fuzzy system Hệ mờ HA Hedge Algebras Đại số gia tử Đại số gia tử Hedge Algebras Controller Bộ điều khiển đại số gia tử FLC HAC HAC-REM IP Hedge Algebras Controller Random Exponential Marking Internet Protocol for Giải thuật đánh dấu ngẫu nhiên theo hàm mũ ứng dụng gia tử Giao thức Internet 5 Phần mềm mô phỏng mạng NS2 Network Simulator 2 PI Proportional Integral Bộ điều khiển tích phân tỷ lệ PH Packet Header Mào đầu gói tin QL Queue Limit Giới hạn hàng đợi QoS Quality of Service Chất lượng dịch vụ RED Random Early Discard Loại bỏ ngẫu nhiên sớm REM Random Exponential Marking RTP Realtime Protocol RTT Round Trip Time SC Soft computing Network Simulator 2 Đánh dấu ngẫu nhiên theo hàm mũ Giao thức thời gian thực Thời gian cho một chu trình của gói tin Kỹ thuật tính toán mềm TCP Transport Control Protocol TQL Target Queue Length UDP User Data Protocol Giao thức điều khiển truyền tải Chiều dài hàng đợi tham chiếu Giao thức dữ liệu người sử dụng 6 DANH MỤC CÁC HÌNH ẢNH Hình 1.1. Kiến trúc mạng đơn giản. ..................................................................... 5 Hình 1.2. Hiện tượng Time out ............................................................................. 7 Hình 1.3. Nguyên lý cửa sổ tắc nghẽn .................................................................. 8 Hình 1.4. Nguyên lý của việc lặp lại ba bản tin báo nhận .................................... 9 Hình 1.5. Thuật toán khởi đầu chậm, truyền lại nhanh và khôi phục nhanh [16] ............................................................................................................................. 10 Hình 1.6. Phân loại các phương pháp quản lý hàng đợi tích cực ....................... 14 Hình 1.7. Giải thuật RED truyền thống [11] ....................................................... 16 Hình 1.8. Giải thuật RED với “gentle option” .................................................... 17 Hình 2.1. Tính mờ của giá trị ngôn ngữ .............................................................. 33 Hình 2.2. Lập luận xấp xỉ với đại số gia tử ......................................................... 35 Hình 3.1. Vị trí bộ điều khiển sử dụng gia tử cho bài toán REM AQM ............. 39 Hình 3.2. Sơ đồ mô tả hệ thống điều khiển sử dụng HA .................................... 40 Hình 3.3. Sreal của bộ điều khiển HA................................................................... 45 Hình 3.4. Cấu trúc mạng đa tắc nghẽn ................................................................ 47 Hình 3.5. Kích thước hàng đợi của các phương pháp AQM khi N=800 luồng .. 48 Hình 3.6. Tỷ lệ mất gói và hiệu suất sử dụng tuyến của các giải thuật AQM khi lưu lượng tải 250-800 ......................................................................................... 49 Hình 3.7. Trễ trung bình và biến thiên độ trễ khi tăng lưu lượng từ 250-800 .... 50 Hình 3.8. Kích thước hàng đợi của các phương pháp AQM khi RTT=200 ms .. 51 Hình 3.9. Các tham số mạng khi RTT thay đổi từ 30, 120, 200 ms ................... 51 7 DANH MỤC CÁC BẢNG BIỂU Bảng 3.1. Các tham số của REM ........................................................................ 38 Bảng 3.2. Tham số mờ của đại số gia tử cho các biến Pr (kT ) , Pr (kT  T ) , DP ... 41 Bảng 3.3. Mối quan hệ dấu của các gia tử và các phần tử sinh .......................... 41 Bảng 3.4. Hệ luật mờ cho bài toán REM AQM .................................................. 42 Bảng 3.5. Tham số mờ của đại số gia tử cho các biến Pr (kT ) , Pr (kT  T ) và DP 43 Bảng 3.6. Giá trị định lượng ngữ nghĩa của các biến ......................................... 44 8 MỞ ĐẦU 1. Tính khoa học và cấp thiết của đề tài Sự bùng nổ nhu cầu thông tin của khách hàng cùng với xu hướng hội nhập trên một nền mạng chung duy nhất TCP/IP đã và đang đặt ra những thách thức to lớn cho mạng truyền thông hiện tại. Khách hàng ngày càng đòi hỏi sự đa dạng về số lượng dịch vụ cũng như sự hoàn thiện trong chất lượng dịch vụ. Do đó, trên mạng lõi TCP/IP, các bài toán quản lý mạng truyền thông như định tuyến, quản lý tài nguyên, quản lý chất lượng, điều khiển lưu lượng mạng…cho các loại hình dịch vụ khác nhau cũng cần phải được đáp ứng một cách tức thời, đồng bộ, hiệu quả và thông minh. Một trong các bài toán kể trên chính là quản lý hàng đợi tích cực (Active Queue Management – AQM) tại các router trên mạng TCP/IP. Mục đích của bài toán này là căn cứ vào tình trạng hiện tại của hàng đợi hoặc/và tốc độ của các nguồn lưu lượng đến để đưa ra cơ chế chủ động loại bỏ gói tin của các luồng lưu lượng đến theo một cách thức phù hợp sao cho luôn duy trì chiều dài trung bình (hoặc tức thời) của hàng đợi ở một mức đặt trước phù hợp. Việc ổn định chiều dài của hàng đợi sẽ làm cho một số thông số hoạt động của mạng TCP/IP như tỷ lệ mất gói, hiệu suất sử dụng tuyến, trễ trung bình và biến thiên độ trễ dao động trong một phạm vi hợp lý. Điều này sẽ vừa đảm bảo không gây tắc nghẽn trên mạng, vừa tạo điều kiện cung cấp và duy trì một cách tốt nhất chất lượng dịch vụ (Quality of Service –QoS) của các luồng lưu lượng đến khác nhau. Để giải quyết bài toán AQM, ba phương pháp truyền thống được biết đến là quản lý hàng đợi dựa trên chiều dài hàng đợi (đại diện tiêu biểu là giải thuật loại bỏ gói ngẫu nhiên sớm - Random Early Discard - RED), quản lý hàng đợi dựa trên tốc độ lưu lượng đến (mà đại diện là giải thuật Blue) và quản lý hàng đợi dựa trên sự kết hợp cả chiều dài và tốc độ lưu lượng đến (điển hình là giải thuật đánh dấu ngẫu nhiên theo hàm mũ - Random Exponential Marking REM). 1 Gần đây, nhằm nâng cao hiệu quả của bài toán AQM, ngoài ba thuật toán tiêu biểu kể trên, đã có rất nhiều phương pháp khác được công bố. Các công trình này xoay quanh việc sửa đổi RED, Blue, REM hoặc kết hợp các phương pháp. Các kết quả thu được đã phần nào đáp ứng được yêu cầu của bài toán AQM. Tuy nhiên, các phương pháp này vẫn cần được cải tiến sao cho vừa đơn giản hóa khi thực hiện, vừa nâng cao tính thông minh trong việc duy trì độ dài hàng đợi trung bình trong điều kiện động học của mạng luôn thay đổi, vừa đảm bảo tính công bằng trong việc loại bỏ gói đối với các luồng lưu lượng đến. Các nhược điểm cố hữu trên của các bài toán AQM truyền thống sẽ được khắc phục khi áp dụng các thành tựu đạt được của lĩnh vực khoa học máy tính mà cụ thể là trí tuệ nhân tạo nhằm bổ sung khả năng học, khả năng ra quyết định thông minh của hệ thống. Một trong các công cụ thường được sử dụng chính là logic mờ. Việc áp dụng logic mờ cho các giải thuật AQM đã có nhiều tác giả nghiên cứu trong những năm gần đây. Mục đích của việc áp dụng logic mờ là nhằm đơn giản hóa việc thiết kế các giải thuật AQM dựa trên một mức độ sai số cho phép. Đại số gia tử là một hướng tiếp cận tương đương với logic mờ (do người Việt phát minh). Thậm chí, trong một số bài toán thực tế, chất lượng của bộ điều khiển sử dụng đại số gia tử cho kết quả tốt hơn do ưu điểm ở việc đảm bảo mối quan hệ thứ tự giữa các giá trị ngôn ngữ xuất hiện trong hệ luật của suy luận. Từ các phân tích trên, được sự hướng dẫn của Thầy giáo TS. Nguyễn Phương Huy, học viên đề xuất đề tài luận văn tốt nghiệp là “ Ứng dụng đại số gia tử cho bài toán quản lý hàng đợi tích cực trên mạng TCP/IP”. 2. Tổng quan tình hình nghiên cứu Năm 2001, Athuraliya, Li, Low, và Yin (2001) đề xuất một giải thuật AQM gọi là đánh dấu ngẫu nhiên theo hàm mũ - REM. Ý tưởng chính cho việc thiết kế giải thuật này là ổn định hóa cả tốc độ đầu vào xung quanh dung lượng của liên kết và chiều dài hàng đợi xung quanh một giá trị mục tiêu nhỏ. 2 Logic mờ được áp dụng trong viễn thông từ rất sớm do những kết quả hấp dẫn đạt được khi áp dụng logic mờ trong nhiều lĩnh vực. Tuy nhiên, việc áp dụng logic mờ cho các giải thuật AQM chỉ được đề xuất trong những năm rất gần đây. Mục đích của việc áp dụng logic mờ là nhằm đơn giản hóa việc thiết kế các giải thuật AQM dựa trên một mức độ sai số cho phép. Đã có rất nhiều tác giả đã đề xuất cải tiến các giải thuật AQM truyền thống dựa trên lý thuyết điều khiển mờ [7] [15] Đặc biệt, dựa trên giải thuật REM, một bộ điều khiển tự thích nghi gọi là FUZREM được thiết kế trong [18] tự động điều chỉnh các quy tắc cho REM. Đại số gia tử là một hướng tiếp cận tương đương với logic mờ. Trong một số bài toán cụ thể, đại số gia tử đã chứng minh tính ưu việt hơn so với logic mờ do việc đảm bảo trật tự của các giá trị ngôn ngữ xuất hiện trong hệ luật của suy luận [4] [8] . Tuy nhiên, đến thời điểm hiện tại, chưa có công trình nghiên cứu nào trên thế giới áp dụng đại số gia tử cho bài toán AQM. 3. Mục tiêu, đối tượng và phạm vi nghiên cứu của đề tài Mục tiêu nghiên cứu: Mục tiêu của đề tài là chứng minh khả năng ứng dụng mô hình tính toán có sử dụng đại số gia tử cho bài toán AQM theo thuật toán REM trên mạng TCP/IP. Về mặt bản chất chính là xây dựng giải thuật điều khiển trên router (sử dụng đại số gia tử) chủ động loại bỏ gói tin để duy trì chiều dài hàng đợi ở một ngưỡng phù hợp dựa trên thông tin về chiều dài hàng đợi và tốc độ của luồng thông tin đến. Giải thuật điều khiển này sẽ phải được chứng minh hiệu quả trong việc nâng cao chất lượng mạng TCP/IP. Đối tượng và phạm vi nghiên cứu: Đánh giá hiệu quả của thuật toán cải tiến thu được thông qua công cụ mô phỏng NS2 trên một tôpô mạng TCP/IP phù hợp được cộng đồng quốc tế công nhận. 3 4. Phương pháp luận nghiên cứu - Phương pháp nghiên cứu lý thuyết: Tổng hợp, nghiên cứu các tài liệu về TCP/IP, các giải thuật AQM, logic mờ, đại số gia tử và ứng dụng trong điều khiển. - Phương pháp nghiên cứu thực nghiệm: Sau khi nghiên cứu lý thuyết, phát biểu thuật toán, đưa ra giải pháp xử lý; cài đặt phần mềm mô phỏng dùng công cụ NS2; So sánh và đánh giá các kết quả đạt được so với các phương pháp khác. - Phương pháp trao đổi khoa học: Thảo luận, xemina, lấy ý kiến chuyên gia, công bố các kết quả nghiên cứu trên tạp chí khoa học. 4 CHƯƠNG 1 BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRÊN MẠNG TCP/IP 1.1. Mạng TCP/IP và bài toán điều khiển tắc nghẽn 1.1.1. Truyền số liệu trên mạng TCP/IP Hình 1.1. Kiến trúc mạng đơn giản. Trên mạng TCP/IP, thông tin muốn gửi đi được chia thành các đơn vị dữ liệu nhỏ gọi là gói tin. Ngoài việc gửi đi các gói tin, phía phát đồ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à đặt nó ở đầu của mỗi gói tin (Packet Header - PH). Mỗi một PH chứa địa chỉ nguồn để định rõ địa chỉ nơi gửi gói đó. PH cũng chứa địa chỉ IP đích là nơi mà gói tin phải chuyển đến. Các bộ định tuyến sẽ dùng địa chỉ đích này để xác định đích đến của gói tin và thực hiện công việc chuyển gói tin đến đúng địa chỉ. Khi có nhiều gói tin từ nhiều nguồn khác nhau cùng đến bộ định tuyến 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á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 bộ định tuyến 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 đó. Nếu tốc độ chuyển các gói tin đi của bộ định tuyến lớn hơn tốc độ các gói tin đến thì sau một khoảng thời gian nào đó hàng đợi sẽ trở nên rỗng. Ngược lại, nếu tốc độ chuyển các gói tin đi nhỏ hơn tốc độ 5 các gói tin đến bộ định tuyến thì sau một khoảng thời gian hàng đợi sẽ đầy và hiện tượng tắc nghẽn xảy ra [11] , [16] . Một cách cách tổng quát có thể định nghĩa tắc nghẽn như sau: “Trong quá trình hoạt động, mạng có thể rơi vào trạng thái không đủ khả năng đáp ứng các chỉ tiêu chất lượng cho các kết nối đã được thiết lập hay cho một yêu cầu kết nối mới do sự biến đổi bất thường, không dự đoán được của dòng lưu lượng cùng với tình trạng lỗi của các phần tử mạng” [16] . Các gói tin đi vào và đi ra các bộ định tuyến trên mạng TCP/IP thường dưới dạng cụm từ một hoặc nhiều nguồn khác nhau. Các hàng đợi bên trong sẽ giúp các bộ định tuyến lưu trữ các cụm gói tin này cho đến khi chúng được chuyển đi. Khi các cụm gói tin đến đến vượt quá kích thước của hàng đợi thì sẽ xảy ra tình trạng tắc nghẽn. Các gói đến sau sẽ bị loại bỏ. Như vậy, tắc nghẽn trên mạng TCP/IP xảy ra khi lưu lượng từ nhiều tuyến đổ dồn về một tuyến và tuyến này không có khả năng xử lý hết được. Tắc nghẽn cũng xảy ra ngay bên trong bản thân bộ định tuyến tại mạng lõi của mạng khi các nút mạng nhận được nhiều lưu lượng hơn so với thiết kế của nó. Khi mạng xảy ra tắc nghẽn nếu không được xử lý kịp thời sẽ gây ra các hậu quả nghiêm trọng: các gói tin không được xử lý kịp, không chuyển được đến đầu cuối người nhận, gây ùn tắc trong mạng, mạng không hoạt động được trong thời gian dài và như vậy không thể truyền tải được dữ liệu, các thành phần có thể bị hư hỏng. Do đó, vấn đề quan trọng là phải điều khiển được tắc nghẽn trong mạng. Để làm được điều này, việc tăng chiều dài hàng đợi không phải là giải pháp tốt vì khi tăng kích thước bộ đệm đồng nghĩa với việc tạo ra trễ lớn và làm ảnh hưởng đến QoS của các dịch vụ thời gian thực trên mạng TCP/IP. Chính vì vậy, mạng TCP/IP cần phải có một cơ chế loại bỏ gói tin một cách phù hợp để loại bỏ tắc nghẽn khi nó đã xảy ra hoặc lý tưởng hơn là phòng tránh tắc nghẽn khi nó chưa kịp xảy ra. 6 1.1.2. Các giải thuật điều khiển tắc nghẽn theo giao thức TCP 1.1.2.1. Giao thức TCP Giao thức điều khiển truyền tải - Transmission Control Protocol (TCP) là một giao thức truyền thông từ đầu cuối đến đầu cuối cho phép thiết lập một liên kết trực tiếp giữa nguồn và đích. Đặc điểm chính của giao thức này là xác minh kết quả nhận dữ liệu ở đầu thu bằng cách sử dụng cơ chế báo nhận. Nếu gói tin bị mất, bên phát sẽ gửi lại gói tin một lần nữa. Do đó, TCP sẽ đảm bảo truyền tải toàn vẹn thông tin. TCP là một giao thức chung, không phụ thuộc vào mạng được sử dụng. Chính vì vậy, để đạt được thông lượng tối đa, TCP sẽ từng bước điều chỉnh hoạt động cho đến khi đạt đến thông lượng giới hạn thông qua các cơ chế hoạt động của nó. 1.1.2.2. Một số thuật ngữ Để làm rõ hơn hoạt động của giao thức TCP, báo cáo sử dụng một số thuật ngữ sau đây: + Hình 1.2. Hiện tượng Time out Bản tin báo nhận (Acknowledgement - ACK): Là một thông điệp được gửi bởi bên nhận để thông báo cho bên gửi biết số gói tin đã thu được đúng. Nếu bên gửi không nhận được ACK có nghĩa là các gói dữ liệu bị mất, kết quả là bên gửi phải phát các gói dữ liệu mất một lần nữa (Hình 1.2). 7 Timeout: Liên quan đến thời gian chờ đợi một báo nhận. Bộ đếm thời gian sẽ bắt đầu khi một gói tin được gửi đi. Khi hết thời gian chờ đợi mà chưa nhận được ACK, bên gửi sẽ giả định là gói tin đã bị mất và truyền lại. Bộ đệm: Là một vùng nhớ truy xuất ngẫu nhiên được sử dụng để lưu trữ dữ liệu tạm thời. Khi gói tin đến đầu thu, chúng sẽ được lưu vào bộ đệm để chờ xử lý. Tắc nghẽn: Là một hiện tượng bão hòa, xảy ra khi lưu lượng truy cập quá lớn. Ví dụ khi bộ đệm nhận được số gói dữ liệu nhiều hơn so với khả năng của mình, hoặc khi chuyển tiếp dữ liệu từ một mạng dung lượng cao tới một mạng có dung lượng thấp hơn. Tắc nghẽn sẽ dẫn đến mất mát dữ liệu. Cửa sổ tắc nghẽn (Congestion Window - cwnd): Là một biến trạng thái của TCP nhằm giới hạn số lượng gói dữ liệu mà một giao thức TCP có thể gửi khi chưa nhận được một ACK. Số lượng gói số liệu được gửi trong thực tế sẽ là giá trị nhỏ nhất của cwnd và kích thước cửa sổ nhận mà bên thu đã đề nghị. Thời gian cho một chu trình của gói tin (Round Trip Time - RTT): Là thời gian cần thiết để một gói tin đạt đến đích cộng với thời gian của ACK cho gói tin này. Nó tương ứng với thời gian trao đổi của một segment giữa bên gửi và bên nhận. Hình 1.3. Nguyên lý cửa sổ tắc nghẽn 8 Hiện tượng lặp lại ba bản tin báo nhận: Hiện tượng này xảy ra khi một gói tin bị mất trong quá trình truyền tải. Theo cơ chế của TCP, các gói tin đến tiếp vẫn làm cho bên nhận gửi các ACK chứa số hiệu của gói tin cuối cùng chính xác nhận được. Do vậy, số thứ tự gói trước gói bị mất sẽ được gửi cho đến khi gói bị mất được truyền lại và nhận chính xác. Khi bên gửi thu được 3 ACK giống nhau, nó sẽ gửi lại các gói tin bị mất (xem Hình 1.4). Hình 1.4. Nguyên lý của việc lặp lại ba bản tin báo nhận 1.1.2.3. Các giải thuật tránh tắc nghẽn trên mạng TCP/IP Giải thuật tránh tắc nghẽn trên mạng TCP/IP được phát triển nhằm điều chỉnh tốc độ của các luồng lưu lượng sao cho càng gần với "giới hạn truyền tải" càng tốt để truyền tải tối đa thông tin và tránh tắc nghẽn mạng. Giả thuyết cơ bản của giải thuật này là coi việc một gói tin bị mất tương đương với tình trạng tắc nghẽn. Nguyên tắc của giải thuật là điều khiển tốc độ của từng nguồn theo trạng thái lưu lượng. Nguyên tắc này khá đơn giản. Khi bắt đầu hoạt động, mỗi nguồn tăng dần tốc độ lưu lượng. Sự gia tăng này sẽ diễn ra liên tục cho đến khi xảy ra mất gói tin. Điều này có nghĩa là tắc nghẽn được phát hiện ở một nơi nào đó trong mạng. Do vậy, nguồn lưu lượng phải giảm tốc độ đủ để thoát khỏi tình trạng tắc nghẽn. Đây chính là điểm cơ bản của các giải thuật điều khiển tắc nghẽn “tăng cộng giảm nhân” (Additive Increase Multiplicative DecreaseAIMD) trên mạng TCP/IP [12] . 9 Để cải thiện khả năng hoạt động của giao thức TCP, một số giải thuật đã được thêm vào trong các phiên bản TCP khác nhau (Tahoe, Reno, Vegas, New Reno, Santa Cruz...). Trong đó, TCP New Reno là giao thức được sử dụng rộng rãi nhất trong thời gian gần đây. Các giải thuật cải tiến hoạt động của TCP (Hình 1.5) bao gồm: Hình 1.5. Thuật toán khởi đầu chậm, truyền lại nhanh và khôi phục nhanh [16] Giải thuật khởi đầu chậm và tránh tắc nghẽn [16] : Gồm hai pha khởi đầu chậm và tránh tác nghẽn. Ban đầu, TCP hoạt động ở pha khởi đầu chậm. Mục đích là để có được một ngưỡng dự đoán tắc nghẽn. Bắt đầu pha khởi đầu chậm, TCP thiết lập cwnd =1. Mỗi khi nhận được một ACK, cwnd sẽ tăng lên một đơn vị (nhưng không vượt quá cửa sổ nhận mà bên thu thông báo). Do vậy, cwnd sẽ tăng lên theo hàm mũ cho tới khi đạt đến ngưỡng khởi đầu chậm (Ssthresh) thì chuyển sang pha tránh tắc nghẽn. Trong giai đoạn tránh tắc nghẽn, TCP sẽ điều chỉnh cwnd=cwnd +1/cwnd mỗi khi nhận được một ACK cho đến khi việc mất gói xảy ra. Khi phát hiện mất gói, nguồn phát sẽ đặt Ssthresh = cwnd/2, truyền lại các gói tin bị mất và trở về pha khởi đầu chậm bằng cách đặt lại cwnd bằng 1. Giải thuật truyền lại nhanh [16] : Mục đích là để khôi phục hoạt động của TCP hiệu quả hơn từ việc mất gói. Khi nhận được hai bản tin báo nhận giống nhau, TCP xem như đây là trường hợp lặp lại ba bản tin báo nhận và đường truyền đã bị tắc nghẽn. Thay vì mất thời gian chờ đợi Timeout, nguồn sẽ giảm tốc độ và truyền lại các gói tin bị mất. 10