Tài liệu Nghiên cứu kĩ thuật điều khiển tắc nghẽn mạng và mô phỏng, đánh giá trên network simulator 2

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGHIÊN CỨU KỸ THUẬT ĐIỀU KHIỂN TẮC NGHẼN MẠNG VÀ MÔ PHỎNG,ĐÁNH GIÁ TRÊN NETVVORK SIMULATOR -2 LUẬN VĂN THẠC SĨ Hà Nội- 2006 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGHIÊN CỨU KỸ THUẬT ĐIỀU KHIỂN TẮC NGHẼN MẠNG VÀ MÔ PHỎNG,ĐÁNH GÍA TRÊN NETVNORK SIMULATOR -2 Luậm Văn Thạch Sỹ : Kỹ Thuật Điện Tử-Viễn Thông Mã số: 2.07.00 Người Hướng Dẫn Hà Nội- 2006 -1- MỤC LỤC Mục lục .......................................................................................................... 1 Danh mục các từ viết tắt ................................................................................. 3 Mở đầu ........................................................................................................... 5 Phần 1: Điều khiển tắc nghẽn mạng ............................................................. 10 Chương 1: Các thuật toán điều khiển tắc nghẽn mạng trên lớp TCP ............ 11 1.1 Cơ chế cửa sổ trượt ........................................................................... 12 1.2 Tính toán thời gian phát lại ............................................................... 16 1.2.1 Tính trung bình đơn giản........................................................... 17 1.2.2 Tính trung bình theo hàm mũ ................................................... 17 1.3 Quan hệ giữa điều khiển luồng và điều khiển tắc nghẽn trên TCP .... 18 1.3.1 Dự đoán phương sai RTT .......................................................... 19 1.3.2 Exponential RTO backoff .......................................................... 21 1.3.3 Thuật toán Karn ....................................................................... 22 1.4 Thuật toán Tahoe ............................................................................. 23 1.4.1 Kĩ thuật slow-start..................................................................... 23 1.4.2 Kĩ thuật Congestion Avoidance ................................................. 25 1.4.3 Kĩ thuật fast retransmit ............................................................. 28 1.5 Thuật toán Reno ............................................................................... 29 1.5.1 Kĩ thuật fast recovery ................................................................ 30 1.5.2 Thuật toán NewReno ................................................................ 32 1.6 Thuật toán Vegas .............................................................................. 32 1.6.1 Cơ chế phát lại mới ................................................................... 34 1.6.2 Cơ chế Congestion Avoidance ................................................... 36 1.6.3 Thay đổi cơ chế slow-start ........................................................ 37 Chương 2: Các thuật toán điều khiển tắc nghẽn mạng trên Gateway ............ 40 2.1 Random Early Detection .................................................................. 42 2.1.1 Thuật toán RED ........................................................................ 44 2.1.2 Tính toán kích thước hàng đợi trung bình ................................. 47 2.1.3 Tính toán xác xuất loại bỏ gói tin .............................................. 51 -2- 2.1.4 Ưu nhược điểm của RED .......................................................... 53 2.2 RED thích nghi (Adaptive RED) ........................................................ 54 2.2.1 Thuật toán RED thích nghi........................................................ 55 2.2.2 Khoảng giới hạn của các thông số ........................................... 59 2.2.3 Ưu nhược điểm của RED thích nghi .......................................... 62 Phần 2: Mô phỏng và đánh giá.................................................................... 64 Chương 3: Giới thiệu về chương trình mô phỏng mạng NS-2 ....................... 65 3.1 Tổng quan về NS-2 ............................................................................ 66 3.2 Một số lớp đối tượng trong NS-2 ....................................................... 68 3.2.1 Lớp tcp ...................................................................................... 70 3.2.2 Lớp tcp-sink .............................................................................. 71 3.2.3 Lớp link..................................................................................... 72 3.2.4 Lớp trace .................................................................................. 74 3.3 Các bước xây dựng một chương trình mô phỏng ............................... 76 3.4 Khảo sát và đánh giá kết quả mô phỏng ............................................ 77 Chương 4: Mô phỏng và đánh giá các thuật toán điều khiển tắc nghẽn trên TCP............ 80 4.1 Thuật toán Tahoe .............................................................................. 81 4.2 Thuật toán Reno ................................................................................ 85 4.3 Thuật toán NewReno ......................................................................... 93 4.4 Thuật toán Vegas............................................................................. 101 Chương 5: Mô phỏng và đánh giá các thuật toán điều khiển tắc nghẽn trên Gateway ........... 104 5.1 RED cơ bản ..................................................................................... 104 5.1.1 So sánh hoạt động của RED với DropTail............................... 105 5.1.2 Sự nhạy cảm của RED với mức độ tải dữ liệu lên mạng .......... 113 5.1.3 Sự nhạy cảm với thông số của RED......................................... 115 5.2 RED thích nghi ................................................................................ 121 Kết luận ...................................................................................................... 130 Tài liệu tham khảo ...................................................................................... 134 Phụ lục ....................................................................................................... 136 -3- DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt ACK AIAD AIMD AQM CA CD CWND ECN ERD EWMA FIFO FTP IP MAC MBPS MIAD MIMD NAM NS OPNET OW RED REDPD Tiếng Anh ACKnowledgement Additive Increase Additive Decrease Additive Increase Mutiliplicative Decrease Active Queue Manegement Congestioin Avoidance Collision Detection Congestion WiNDow Explicit Congestion Notification Early Random Drop Exponential Weighted Moving Average First In First Out File Transfer Protocol Internet Protocol Medium Access Control Mega Byte Per Second Multiplicative Increase Multiplicative Decrease Mutiplicative Increase Mutiplicative Decrease Network AniMator Network Simulator OPtimized Network Evaluation Tool Offered Window Random Early Detection Random Early Detection with Preferential Dropping Tiếng Việt Đáp ứng Tăng cộng giảm cộng Tăng cộng giảm nhân Tổ chức hàng đợi tích cực Tránh tắc nghẽn Ph¸t hiÖn xung ®ét Cửa sổ tắc nghẽn Cảnh báo tắc nghẽn trực tiếp Loại bỏ ngẫu nhiên sớm Trung bình có trọng số hàm mũ Vào trước ra trước Giao thức truyền file Giao thức Internet Điêu khiển truy cập môi trường Triệu byte trong một giây Tăng nhân giảm cộng Tăng nhân giảm nhân Mô tả hành vi động của mạng Chương trình mô phỏng mạng Công cụ thử nghiệm mạng đã tối ưu (tên phần mềm) Cửa sổ bên đích cho phép Phát hiện sớm ngẫu nhiên Phát hiện sớm ngẫu nhiên với loại bỏ ưu tiên -4- RFC RTO RTT SACK SRTT TCP UW Request For Comment Retransmission Timer Out Round Trip Time Selective ACKnowledgement Smoothed Round Trip Time Transmission Control Protocol Usable Window Yêu cầu nhận xét Thời gian truyền lại Thời gian khứ hồi Đáp ứng có lựa chọn Thời gian khứ hồi đã làm trơn Giao thức điều khiển truyền dẫn Cửa sổ có thể truyền -5- MỞ ĐẦU TCP/IP là hệ thống giao thức thống trị trên mạng ngày nay. Là giao thức lớp giao vận (transport) TCP cung cấp một giao diện giữa lớp ứng dụng và lớp mạng mà qua đó các ứng dụng có thể sử dụng các dịch vụ mạng với chất lượng dịch vụ (QoS) mong muốn. Chất lượng dịch vụ được xác định dựa vào một loạt thông số như thông lượng, tốc độ mất gói tin, hiệu suất sử dụng mạng, độ trễ, độ công bằng (fairness).... Các thông số này không chỉ phụ thuộc vào cấu trúc vật lí của mạng, mà còn phụ thuộc nhiều vào cách thức tổ chức hoạt động của các thành phần của mạng. Các thuật toán cổ điển như DropTail trên Gateway [3,18] hay Tahoe [25] trên TCP đã được triển khai rất rộng trên mạng do tính đơn giản và khá hiệu quả của chúng. Tuy nhiên yêu cầu ngày càng cao về chất lượng dịch vụ như thông lượng truyền dẫn cao, độ trễ thấp, hiệu suất sử dụng mạng cao,... đã khiến cho các thuật toán cổ điển này ngày càng không đáp ứng được yêu cầu. Mặt khác chúng còn gây ra nhiều vấn đề lớn làm hạn chế chất lượng dịch vụ. Đặc biệt hiện tượng tắc nghẽn mạng xảy ra tại các Gateway khi tổng thông lượng truyền đến quá cao làm ảnh hưởng đến một loạt yếu tố quyết định chất lượng dịch vụ như tăng độ trễ, tăng tốc độ mất gói tin, giảm hiệu suất mạng, giảm thông lượng truyền tin, tính công bằng không được bảo đảm,... Độ trễ tăng lên không chỉ gây mất thời gian chờ đợi cho người dùng mà còn sẽ làm cho mạng không thể đáp ứng được một số loại dịch vụ yêu cầu mà độ trễ phải được giới hạn (delay-limited) như thoại. Tốc độ mất gói tin tăng lên làm tăng sự lãng phí tài nguyên mạng vì một gói tin bị mất có nghĩa là hàng loạt tài nguyên đã dùng để truyền nó trở thành vô ích. .v.v. Chính vì vậy mà yêu cầu về kiểm soát tắc nghẽn mạng ngày càng trở nên quan trọng và trở thành chủ đề nghiên cứu, mô phỏng, thử -6- nghiệm và ứng dụng trong nhiều năm gần đây. Các cơ chế kiểm soát hay điều khiển tắc nghẽn mạng có thể phân ra hai hướng chính : điều khiển tắc nghẽn dựa trên TCP và điều khiển tắc nghẽn dựa trên Gateway. Mục tiêu cơ bản nhất của mọi cơ chế điều khiển tắc nghẽn mạng là nhằm hạn chế lượng dữ liệu đưa lên mạng ở mức mà mạng có thể truyền được. Chỉ khi đạt được mục tiêu đó thì mới có thể kiểm soát được tắc nghẽn mạng. Kiểm soát tắc nghẽn mạng dựa trên TCP gặp rất nhiều khó khăn [34]: 1. IP là giao thức không kết nối, không trạng thái do đó không cung cấp công cụ gì cho phát hiện tắc nghẽn, và rất ít cho điều khiển tắc nghẽn. 2. TCP chỉ cung cấp các công cụ cho điều khiển luồng đầu cuối (end-to-end) và chỉ có thể suy ra sự tắc nghẽn thông qua các phương pháp gián tiếp (trừ khi sử dụng ECN – Explicit Congestion Notification [12]). Thêm nữa độ trễ trên mạng có thể biến đổi nên các điều kiện mạng mà TCP tính ra được có thể khổng đủ tin cậy. 3. Không có một thuật toán phân tán nào có thể kết nối và phối hợp hoạt động của được hàng loạt các thực thể TCP. Do đó các thực thể TCP không thể phối hợp với nhau để duy trì tổng thông lượng ở một mức nào đó, thay vào đó chúng hoạt động giống như cạnh tranh các tài nguyên mạng một cách ích kỉ. Công cụ duy nhất trong TCP liên quan đến kiểm soát tắc nghẽn là cơ chế điều khiển luồng bằng cửa sổ trượt (sliding-window [34]) và cơ chế điều khiển lỗi. Hàng loạt giải pháp được đưa ra để sử dụng các cơ chế này cho việc phát hiện xung đột, tránh xung đột và phục hồi sau tắc nghẽn. Nói chung các giải pháp ra đời sau thường là nhằm khắc phục các giới hạn của các giải pháp trước đó và sau một thời gian nghiên cứu, thử nghiệm đã trở thành tiêu chuẩn -7- hoặc khuyến nghị cho TCP. Tahoe là giải pháp cổ điển nhất, bao gồm các cơ chế nhỏ như khởi động chậm (slow-start), tránh tắc nghẽn (congestion avoidance- CA) và phát lại nhanh (fast-retransmit). Tahoe sử dụng các ACK lặp hoặc đồng hồ phát lại (retransmit timer) để xác định sự mất gói tin hay sự tắc nghẽn trên mạng. Reno [28] cải tiến cơ chế fast-retransmit của Tahoe thành hồi phục nhanh (fast-recovery) và đạt được sự cải tiến tốt khi không có quá một gói tin trong cùng một cửa sổ dữ liệu bị mất. Tuy nhiên hiệu quả có thể giảm đi khi có nhiều hơn một gói tin trong cùng một cửa sổ dữ liệu bị mất, hay chính xác hơn là có nhiều hơn một gói tin bị mất trước khi fast-retransmit được khởi động. NewReno [17] là một cải tiến của Reno nhằm giải quyết tình huống trên. Tuy nhiên hiệu quả vẫn có thể giảm đi rất nhiều khi quá nhiều gói tin trong cùng cửa sổ dữ liệu bị mất, thậm chí hoạt động không bằng Tahoe trong một vài trường hợp. Khác với tính chất reactive (phản ứng lại) của các thuật toán trên, tính chất mà TCP phải làm mất gói tin thì mới xác định được điều kiện của mạng, Vegas [4,5] là một thuật toán proactive (chủ động), cho phép TCP dự đoán được điều kiện tắc nghẽn của mạng mà không cần làm mất gói tin. Vegas dựa vào sự so sánh thông lượng tức thời và thông lượng trung bình để dự đoán điều kiện tắc nghẽn mạng và cho phép TCP hoạt động hiệu quả hơn, duy trì giai đoạn CA dài hơn, tăng thông lượng và giảm tốc độ gói tin mất. Các thuật toán trên chỉ cần thay đổi TCP nguồn mà không thay đổi gì đến TCP đích. SACK [28] là một thuật toán cần sự thay đổi cả ở TCP đích tạo ra SACK - và TCP nguồn - phản ứng với SACK. SACK có thể hoạt động tốt ngay cả khi có nhiều gói tin trong cùng cửa sổ bị mất. Veno [36,37] là sự kết hợp của Vegas và Reno để thích hợp với môi trường mạng không dây môi trường mà tỉ lệ gói tin mất do lỗi khá cao. Ngoài ra còn có một số thuật toán khác như Westwood, Westwood+[30] ,... cũng đã được đưa ra. -8- Các thuật toán trên chạy trên TCP đã cải thiện rất tốt khả năng kiểm soát tắc nghẽn mạng cũng như nâng cao chất lượng dịch vụ. Nhưng kiểu Gateway DropTail vẫn còn hạn chế nhiều đến sự kiểm soát tắc nghẽn cũng như gây ra một số hiện tượng không tốt khác. Gateway DropTail sử dụng một bộ đệm hữu hạn làm hàng đợi và hoạt động kiểu vào trước - ra trước (First In First Out - FIFO). Các gói tin đến khi bộ đệm đã đầy sẽ lập tức bị loại bỏ. Hàng loạt gói tin đến từ các TCP nguồn khác nhau có thể bị loại bỏ gần như đồng thời, do đó hàng loạt TCP sẽ gần như đồng thời thực hiện phát lại và giảm thông lượng của mình xuống đồng loạt một cách không cần thiết. Do vậy gây ra hiệu ứng đồng bộ toàn cục (global synchronization) làm giảm hiệu suất mạng, hơn nữa còn có thể dẫn đến một chu kì đồng bộ mới. Bộ đệm có thể tăng lên để làm giảm xác suất mất gói tin, tăng thông lượng, nhưng sẽ kéo theo độ trễ trung bình tăng lên. Mặt khác sự tăng bộ đệm có thể là không giới hạn được và trở nên bất khả thi. Cơ chế quản lí hàng đợi tích cực (Active Queue Management - AQM) được đưa ra nhằm giải quyết các vấn đề trên. Nhiều kĩ thuật được đưa ra như ERD (Early Random Drop)[21], DECbit [27], IP Source Quench [32], RED (Random Early Detection) [18],... trong đó khả quan nhất là RED. RED loại bỏ gói tin ngay từ khi hàng đợi chưa đầy với xác suất loại bỏ tỉ lệ với kích thước hàng đợi trung bình. RED được thiết kế với các mục tiêu chính là tránh tắc nghẽn, tránh đồng bộ toàn cục, cho phép khả năng truyền burst và giới hạn kích thước hàng đợi trung bình. RED thực hiện khá tốt các mục tiêu này, nhưng có nhược điểm lớn là khả năng hoạt động phụ thuộc nhiều vào các thông số hoạt động và mức độ tải dữ liệu lên mạng. Cũng có nhiều giải pháp được đưa ra để khắc phục yếu điểm này của RED như cơ chế quản lí từng luồng (per-flow scheduling) [7], RED loại bỏ ưu tiên (REDPD)[19], RED thích nghi (Adaptive RED)[16],... trong đó RED thích nghi tỏ ra hiệu quả và đơn giản hơn hẳn. RED thích nghi tự động điều chỉnh một số -9- thông số của RED để phù hợp với điều kiện mạng và đảm bảo vùng hoạt động xác định cho hàng đợi. RED thích nghi hoạt động tốt hơn RED, và đặc biệt là nó cho phép thao tác cấu hình đơn giản hơn nhiều. Nghiên cứu các kĩ thuật trên đòi hỏi một quá trình mô phỏng, kiểm định rất cẩn thận trước khi đưa thành khuyến nghị hay triển khai thực tế. Network Simulator (NS) [13,23] là một công cụ mô phỏng mạng rất mạnh và phù hợp cho công việc này. NS dựa trên ngôn ngữ lập trình hướng đối tượng (objectoriented) là C++ và ngôn ngữ lập trình kịch bản (script) là OTcl để thực hiện các chương trình mô phỏng hướng đối tượng và hướng sự kiện (evenoriented). Trải qua nhiều phiên bản, tới nay đã là NS2-30, NS tích hợp sẵn rất nhiều thí nghiệm mô phỏng mạng, tạo điều kiện cho những người đi sau có thể xây dựng hoặc lặp lại các thí nghiệm một cách dễ dàng hơn. NS2 nay đã trở thành sự bảo đảm về công cụ mô phỏng cho các thí nghiệm về mạng. Trong luận văn này trước hết sẽ nghiên cứu, tìm hiểu về một số kĩ thuật tránh tắc nghẽn mạng nêu trên, sau đó sẽ tiến hành mô phỏng trên NS2 để khảo sát và khẳng định lại những gì tìm hiểu, nghiên cứu được. - 10 - PHẦN 1 ĐIỀU KHIỂN TẮC NGHẼN MẠNG - 11 - CHƢƠNG 1 CÁC THUẬT TOÁN ĐIỀU KHIỂN TẮC NGHẼN MẠNG TRÊN LỚP TCP Điều khiển tắc nghẽn trên mạng có hai phương hướng chính là điều khiển tắc nghẽn trên lớp TCP và điều khiển tắc nghẽn trên Gateway. Chương này giới thiệu về một số thuật toán điều khiển tắc nghẽn trên lớp TCP mà đã khá phổ biến là Tahoe, Reno và Vegas. Do TCP chỉ cung cấp các công cụ cho việc điều khiển luồng end-to-end, nên các thuật toán này đều dựa trên nền tảng là cơ chế điều khiển luồng của TCP. Tắc nghẽn trên mạng có thể được phát hiện thông qua sự kiện mất gói tin, ví dụ nhận được nhiều ACK lặp, quá thời gian phát lại (timeout) như trong Tahoe và Reno, hoặc cũng có thể được dự đoán trước nhờ so sánh thông lượng tức thời và thông lượng trung bình như trong Vegas. Một khi tắc nghẽn được phát hiện (dù chính xác hay không chính xác), thuật toán điều khiển luồng sẽ giảm thông lượng xuống để đảm bảo tránh tắc nghẽn và có thể thực hiện việc phát lại gói tin được coi là đã mất. Mặc dù sự kiện mất gói tin có thể không phải do tắc nghẽn mạng, mà có thể do mất mát trên đường truyền (gói tin bị lỗi không thể sửa được), tuy nhiên xác suất mất gói tin do lỗi trên đường truyền chỉ đáng kể với một số môi trường, đặc biệt là môi trường không dây. Còn trong môi trường mạng cáp xác suất này rất thấp và có thể được bỏ qua. Khi gói tin bị mất do lỗi trên đường truyền, TCP chỉ nên phát lại gói tin mất đó mà không cần giảm thông lượng đi, vì tắc nghẽn chưa hề xảy ra. Sự không phân biệt được giữa gói tin - 12 - mất do lỗi đường truyền và gói tin mất do tắc nghẽn mạng có thể khiến cho thông lượng giảm đi một cách không cần thiết. Vì vậy trong môi trường mạng cáp, ba thuật toán này hoạt động đủ tin cậy, còn trong môi trường không dây cần một thuật toán khác để có thể đạt được thông lượng tốt hơn. Đã có một số thuật toán cố gắng giải quết vấn đề này, tuy nhiên trong luận văn này nói chung và trong chương này nói riêng, sẽ không đề cập đến các thuật toán đó. Điều khiển luồng TCP thường là dựa trên cơ chế cửa sổ trượt (slidingwindow). Để có thể sử dụng cơ chế này cho điều khiển tắc nghẽn, một số cơ chế gồm thành phần khác được bổ sung thêm vào như đảm bảo khả năng dự đoán tắc nghẽn, tránh tắc nghẽn cũng như phục hồi lại sau tắc nghẽn. Mỗi thuật toán có cách thức khác nhau, nhưng cũng có những điểm chung như slow-start, fast retransmit, và timeout... Trong chương này trước hết sẽ giới thiệu sơ qua về cơ chế cửa sổ trượt cũng như cách tính toán thời gian phát lại (retransmission timer), sau đó tìm hiểu chi tiết hơn cách thức chung của việc sử dụng cơ chế điều khiển luồng vào việc điều khiển tắc nghẽn. Phần cuối của chương sẽ đi vào chi tiết từng thuật toán trước khi so sánh ưu nhược điểm của chúng với nhau. 1.1 Cơ chế cửa sổ trƣợt Cơ chế cửa sổ trượt cho phép TCP phát một lúc hàng loạt gói tin trước khi dừng lại và đợi (stops and waits) ACK. Điều này khiến cho tốc độ truyền tin cao hơn vì nguồn tin không phải đợi ACK cho từng gói tin. Chúng ta xem xét cơ chế này qua hình 1.1. Trong hình 1.1, cửa sổ đề nghị mà TCP đích cho phép (offered window:ow) là 8 gói tin, đã có 5 gói tin được phát mà chưa nhận được ACK. TCP nguồn dựa vào hai đại lượng trên để tính ra usable window(uw)=3, là số - 13 - gói tin có thể phát tiếp mà không cần đợi ACK. Các gói tin có số thứ hiệu nhỏ hơn n+3 đã truyền đi trước đó và đã nhận được ACK, nghĩa là đã được phía thu nhận tốt. Các gói tin có số hiệu từ n+8 đến n+10 có thể được phát liên tiếp ngay. Khi cửa sổ dịch sang phải, TCP nguồn có thể phát các gói tin có số hiệu lớn hơn n+10. offered window (cửa sổ cho phép bởi TCP đích Usable window Cửa sổ có thể phát ...(n+1) (n+2) (n+3) (n+4) (n+5) (n+6) (n+7) (n+8) (n+9) (n+10) (n+11) ... đã truyền và đã nhận được ACK đã truyền nhưng chưa nhận được ACK Có thể truyền mà Không thể không cần đợi ACK truyền cho đến khi cửa sổ được dịch sang phải Hình 1.1: Cửa sổ trượt Các biên trái và biên phải của cửa sổ có thể thay đổi tùy theo các ACK nhận được. Có ba khả năng dịch chuyển của cửa sổ: 1. Khi một gói tin mới nhận được ACK, biên trái của cửa sổ được dịch sang phải đến vị trí vượt qua số hiệu gói tin đó. Hoạt động này được gọi là đóng cửa sổ (closes). 2. Dựa vào ow trong ACK mới nhận được và vị trí biên trái của cửa sổ, TCP nguồn có thể dịch biên phải của cửa sổ về bên phải sao cho kích thước cửa sổ bằng với ow. Hoạt động này được gọi là mở cửa sổ (opens). 3. Cửa sổ bị co lại (shrink) khi biên phải dịch về bên trái. Điều này xảy ra khi ow mới quá nhỏ, khiến cho tổng của biên trái và ow - 14 - nhỏ hơn giá trị biên phải cũ. Tuy nhiên cửa sổ chỉ có thể co lại nếu uw còn lớn hơn 0. Hình 1.2 : Một quá trình truyền tin đơn giản 1 1024 1025 2048 2049 3072 3073 4096 4097 5120 5121 6144 6145 7168 Cửa sổ sau gói tin (S) 2 Truyền các S4, S5, S6 <----------------------------------------> ACK S7 <-------------------------> Cửa sổ sau S7 ACK S8 <----------> Cửa sổ sau S8 Truyền S9 <----------> ACK S10 <----------> Cửa sổ sau S10 7169 8192 - 15 - Truyền các S11, S12, S13 <----------------------------------------> ACK S14 <-------------------------> Cửa sổ sau S14 ............................... Hình 1.3 : Các hoạt động của cửa sổ trượt trong ví dụ truyền tin trong hình 1.2 Để hiểu rõ hơn về hoạt động của cửa sổ trượt, chúng ta xem xét một thí dụ truyền tin đơn giản. Giản đồ thời gian của quá trình truyền được thể hiện trong hình 1.2. Sự thay đổi cửa sổ tương ứng được thể hiện trong hình 1.3. Thông lượng truyền tin trong khi sử dụng cơ chế cửa sổ trượt phụ thuộc không chỉ vào tốc độ kết nối, độ trễ trên kết nối, mà còn phụ thuộc nhiều vào kích thước của cửa sổ. [34] đã chỉ ra phương pháp tính toán và thu được kết quả của thông lượng chuẩn hóa S (tỉ số giữa thông lượng thực với tốc độ truyền tin của kết nối) trên một kết nối trực tiếp giữa TCP nguồn và TCP đích như sau :  14W S    RD W  RD / 4 W  RD / 4 (1.1) Trong đó: (giả thiết bỏ qua thời gian nhận và xử lí tại node thu) -W là kích thước cửa sổ. -R là tốc độ truyền dữ liệu (transmission) trên kết nối. -D là độ trễ truyền dẫn (propagation delay). Có một vài điều cần chú ý ở đây: - Nếu các luồng TCP được ghép kênh thì R phải giảm đi và S tăng lên. - 16 - - Nếu luồng TCP đi qua nhiều trạm (hop), D sẽ là tổng các trễ truyền dẫn trên các hop này cộng trễ trên các router. Thường thì trễ trên router lớn hơn, đặc biệt là khi xảy ra tắc nghẽn. Khi đó S sẽ bị giảm đi. - R là tốc độ dữ liệu của kết nối, nên nếu trên đường truyền TCP có một khúc nào đó có tốc độ thấp hơn R thì sẽ xảy ra nghẹt cổ chai, do đó làm tăng D và làm S giảm. - Nếu gói tin bị mất, sẽ xảy ra việc truyền lại, do đó thông lượng thực sẽ giảm đi. 1.2 Tính toán thời gian phát lại Một điểm quan trọng trong TCP là thời gian truyền lại (Retransmission timer - RTO). Giá trị này nếu quá thấp sẽ dẫn đến nhiều sự phát lại quá sớm, nghĩa là không cần thiết, khiến cho dung năng của mạng bị lãng phí. Hơn nữa có thể tạo ra hiệu ứng hồi tiếp dương trên mạng – tắc nghẽn dẫn đến nhiều phát lại hơn, điều này lại làm tăng thêm trạng thái tắc nghẽn trên mạng. Mặt khác, RTO nếu quá cao sẽ dẫn đến tình huống không phản ứng kịp với sự mất gói tin. Thường thì RTO được đặt lớn hơn độ trễ khứ hồi (round-trip delay RTT). Tuy nhiên giá trị RTT bị biến đổi khi các điều kiện của mạng thay đổi. Do đó nếu RTO được đặt cố định (dựa trên các điều kiện của mạng) có thể sẽ ảnh hưởng lớn đến thông lượng và tắc nghẽn nếu giá trị không phù hợp với trạng thái tức thời của mạng. Một phương pháp khác là biến đổi cho thích hợp với trạng thái của mạng tại thời điểm đó, thường là lấy trung bình trong một khoảng thời gian trở về trước. Có một số vấn đề khiến cho giá trị này không thực sự đúng : - TCP đích có thể không gửi ACK ngay lập tức. TCP thường sử dụng ACK lũy tích hơn. - 17 - -Nếu một gói bị truyền lại và sau đó TCP nguồn nhận được ACK của gói tin đó, nó không thể phân biệt được ACK của lần truyền trước hay lần truyền sau. - Điều kiện mạng có thể thay đổi đột ngột. Tuy nhiên đây vẫn là phương pháp khả quan nhất. Chúng ta sẽ xem xét kĩ hơn về phương pháp này. Phương pháp này dự đoán RTT hiện tại thông qua độ trễ của một số gói tin được truyền mới nhất, sau đó đặt thời gian truyền lại lớn hơn trễ khứ hồi dự đoán một chút. Có hai phương pháp tính RTT như sau: 1.2.1 Tính trung bình đơn giản Đối với phương pháp này, độ trễ khứ hồi được tính bằng trung bình độ trễ của K gói tin vừa phát với trọng số như nhau là 1/(K+1): ARTT ( K  1)  1 K 1  RTT (i) K  1 i 1 (1.2) Có thể biến đổi lại thành dạng phù hợp cho tính toán hơn : ARTT( K  1)  K 1 ARTT( K )  RTT( K  1) K 1 K 1 (1.3) 1.2.2 Tính trung bình theo hàm mũ Đối với phương pháp này, độ trễ của gói tin phát càng mới thì càng được tính với trọng số lớn. Điều này phù hợp hơn vì các độ trễ càng mới thì càng phản ánh chính xác điều kiện tức thời của mạng hơn. Công thức tính trong phương pháp này như sau: SRTT(K+1) = SRTT(K) + (1-)RTT(K+1) (1.4) - 18 - Trong đó  là một giá trị nằm trong khoảng {0,1}. Có thể phân tích công thức này thành dạng: K 1 SRTT ( K  1)  (1   )  i 1 RTT ( K  2  i ) (1.5) i 1 Vì cả  và 1- đều nhỏ hơn 1 nên các giá trị RTT càng cũ (có chỉ số nhỏ) tương ứng với số mũ lớn thì càng được tính với trọng số nhỏ hơn. Chú ý rằng  càng bé thì các trọng số có ý nghĩa (lớn một chút) càng ít, nghĩa là độ trễ dự đoán phụ thuộc chủ yếu vào một ít các độ trễ của các gói tin mới truyền nhất. Tuy nhiên nó có nhược điểm là thay đổi nhanh nếu mạng có một thay đổi nhanh. Sau khi dự đoán độ trễ khứ hồi, chúng ta đặt thòi gian truyền lại lớn hơn độ trễ này một chút. Lượng thêm vào có thể là một hằng số : RTO(K+1) = SRTT(K+1) +  Tuy nhiên  lại không tỉ lệ với SRTT. Khi SRTT nhỏ, RTO phụ thuộc vào  hơn là SRTT. Khi SRTT lớn, giá trị  thêm vào có thể là không đủ. RFC793 (Request For Comment) đưa ra một cách tính khác như sau: RTO(K+1)=MIN(UBOUND, MAX(LBOUND, .SRTT(K+1))) (1.6) Theo cách này thì RTO tỉ lệ với SRTT và bị giới hạn trong khoảng {LBOUND,UBOUND}. RFC793 cũng đưa ra khoảng giá trị cho  là {0.8,0.9} và  là {1.3,2.0}. 1.3 Quan hệ giữa điều khiển luồng và điều khiển tắc nghẽn trênTCP