- cwnd (Congestion window) là cửa sổ phát hiện tại được xác lập

- rwnd (receive window) là cửa sổ thu cho phép.

Thì w được xác định là:

w = min{cwnd, rwnd}

Giai đoạn tránh tắc nghẽn (Congestion Avoidance): Giả sử tại thời điểm (t) cơ chế bắt đầu chậm phát hiện có sự nghẽn mạng. Khi đó một giá trị ngưỡng được thiết lập là:

ssth(t) = w(t)/2

Giá trị của cwnd được thiết lập lại là:

w(t) = 1

Tại đây cơ chế bắt đầu chậm được thực hiện như sau: Tại thời điểm (t+1) cứ mỗi Segment hồi đáp ACK được nhận thì giá trị cwnd sẽ được cập nhật theo công thức:

w(t+1) = w(t) + 1 cho đến khi giá trị của w => ssth(t) thì bắt đầu tăng tuyến tính. Giả sử tại thời điểm (t+1) có w=>ssth(t) thì w(t+1)) được cập nhật theo công thức:

.

Như vậy cơ chế bắt đầu chậm có 2 giai đoạn là giai đoạn tăng theo hàm mũ và giai đoạn tránh tắc nghẽn. Giai đoạn 1 kết thúc khi TCP phát hiện mất Segment và chuyển sang giai đoạn 2 là giai đoạn tránh tắc nghẽn. Trong giai đoạn tránh tắc nghẽn sử dụng kỹ thuật tăng theo hàm mũ và kỹ thuật tăng tuyến tính. Khi phát hiện có Segment bị mất nó đặt w=1 và trở lại chu trình của nó.

- Cơ chế phát lại nhanh (Fast Retransmission): Trong trường hợp trạm phát nhận được hơn 3 Segment ACK trùng lặp số hiệu thì sự mất Segment đã xảy ra. Nếu chờ cho đến khi Segment đó bị Time out để tiến hành phát lại thì số gói tin trên mạng sẽ tăng lên rất nhiều dễ dẫn đến nghẽn mạng. TCP sử dụng cơ chế phát lại nhanh để khắc phục tình trạng này. Khi nhận được 3 Segment ACK trùng lặp số hiệu thì TCP thực hiện như sau:

Đặt lại ngưỡng ssth: ssth = w/2

Cập nhật lại w: w = 1

phát lại Segment bị mất theo yêu cầu của bên nhận.

- Cơ chế phục hồi nhanh (Fast Recovery): Khi nhận 3 segment ACK trùng lặp số hiệu, cơ chế phục hồi nhanh thực hiện như sau:

Đặt lại ngưỡng ssth: ssth = w/2

Cập nhật lại cwnd: w = ssth

TCP phiên bản ban đầu chỉ sử dụng cơ chế cửa sổ trượt, bắt đầu chậm còn với TCP hiện tại sử dụng 5 cơ chế trên (TCP Tahoe đóng góp cơ chế phát lại nhanh, TCP Reno đóng góp cơ chế khôi phục nhanh) để truyền dữ liệu giữa các máy tính với nhau một cách tin cậy.

* Kết thúc kết nối

Để kết thúc kết nối TCP thực hiện quá trình bắt tay 4 bước và chiều của kết nối là độc lập với nhau. Khi một bên muốn kết thúc nó gửi một segment có cờ FIN được bật và khi bên kia nhận được Segment này nó sẽ gửi lại một Segment ACK hồi đáp. Vì vậy một quá trình kết thúc kết nối sẽ có 2 cặp Segment được trao đổi giữa 2 máy tính. Trong quá trình kết thúc có thể tồn tại dạng một bên đã kết thúc việc gửi chỉ còn nhận Segment.

1.5 Một số cải tiến của TCP

Có rất nhiều phương pháp cải tiến TCP, nhưng trong nội dung giới hạn của luận văn chúng tôi chỉ chú ý đến việc điều khiển kích thước cửa sổ để tăng hiệu năng của mạng. Như trên đã nói, kích thước cửa sổ càng lớn thì hiệu năng của mạng càng được nâng cao, nhưng thời gian cần cho việc tăng kích thước cửa sổ lại tỉ lệ thuận với RTT, xác suất lỗi và độ lớn của thông lượng đường truyền. Các phiên bản cải tiến TCP nhằm vào điều khiển kích thước cửa sổ nhưng có các chiến thuật khác nhau được đề xuất là TCP Reno và TCP Vegas [9] [10] [15] [19]. Trong đó TCP Reno được sử dụng nhiều cho TCP hiện nay.

1.5.1 TCP Reno

Để điều khiển truyền thông TCP Reno sử dụng hầu hết các cơ chế điều khiển như: Cơ chế cửa sổ trượt, cơ chế bắt đầu chậm, cơ chế tránh tắc nghẽn, cơ chế phát lại nhanh và cơ chế phục hồi nhanh [4][7][12][21]. Thuật toán của TCP Reno nhu sau:

Ban đầu khi một kết nối được thiết lập thì TCP Reno đặt ngưỡng của cửa sổ phát có độ lớn tối đa và cwnd bằng 1 Segment.

Tại thời điểm (t+1) thì chỉ xảy ra ở 1 trong các trường hợp sau:

* Trường hợp 1: Trạm phát nhận được Segment hồi đáp ACK (Truyền nhận thành công):

Nếu w

Sử dụng cơ chế bắt đầu chậm:

Kích thước cửa sổ được cập nhật: w(t+1) = w(t) + 1

Ngoài ra (Cho trường hợp w>ssth)

Tăng kích thước w theo tuyến tính:

Kích thước cửa sổ được cập nhật: w(t+1) = w(t) +

* Trường hợp 2: Trạm phát nhận 3 Segments ACK hồi đáp trùng lặp số hiệu:

Sử dụng cơ chế phát lại nhanh và phục hồi nhanh:

Đặt lại ngưỡng: ssth = w(t)/2

Kích thước cửa sổ được cập nhật: w(t+1) = ssth

* Trường hợp 3: Khi phát hiện có Segment bị Time Out

Đặt lại ngưỡng: ssth = w(t)/2

Kích thước cửa sổ được cập nhật: w(t+1) = 1

Sử dụng cơ chế bắt đầu chậm

Như vậy TCP Reno điều khiển cửa sổ phát bằng cách nhận thông tin từ Segment hồi đáp ACK và Segment bị Time Out. Hình 1.13 mô tả cơ chế hoạt động của TCP Reno [21]

Sự cải tiến của TCP Reno ở đây là sau khi sử dụng cơ chế phát lại nhanh nó sử dụng cơ chế phục hồi nhanh. Như vậy TCP Reno đã tận dụng được đường truyền, cho nên thông lượng trên đường truyền tăng lên một cách đáng kể.

1.5.2 Các yếu tố ảnh hưởng và hạn chế của TCP

- Các yếu tố ảnh hưởng:

Các cơ chế điều khiển truyền thông của TCP cho thấy thời gian để đường truyền đạt đến thông lượng tối đa phụ thuộc vào: kích thước của cửa sổ tắc nghẽn và kích thước của cửa sổ nhận, thời gian khứ hồi của các Segments (RTT), xác suất lỗi hay là sự mất các Segment và thông lượng của đường truyền. Rõ ràng tốc độ thay đổi của kích thước cửa sổ phụ thuộc vào RTT, nếu RTT càng lớn thì thời gian cần thiết để cập nhật kích thước cửa sổ càng dài. Số gói tin lỗi hoặc mất càng nhiều thì thời gian đạt đến thông lượng tối đa của đường truyền càng dài. Thông lượng của đường truyền càng lớn thì thời gian đạt đến thông lượng tối đa càng dài.

Đặc biệt đối với mạng không dây với đặc tính xác suất lỗi và các gói tin bị mất cao do nhiễu của sóng điện từ, do sự di chuyển qua lại giữa các ô (cell). TCP vẫn xem đây là sự nghẽn mạng do đó sử dụng các cơ chế truyền thông của nó sẽ làm giảm hiệu suất đường truyền một cách đáng kể [5].

- Hạn chế của TCP:

Mặc dù các cơ chế điều khiển truyền thông của TCP rất linh hoạt nhưng còn một số hạn chế như sau:

+ Không tận dụng hết khả năng của đường truyền, đặc biệt là với đường truyền với thông lượng lớn

+ Với những đường truyền có độ trễ lớn và bất đối xứng thi TCP tỏ ra kém hiệu quả

+ Chưa có khả năng nhận biết sự nghẽn mạng với lỗi bit do đường truyền.

+ Thời gian để đạt được thông lượng tối đa của đường truyền còn dài.

Chương 3: Điều khiển lưu thông mạng Internet

Việc truyền dữ liệu trong mạng phụ thuộc nhiều yếu tố, trong đó có chiến lược cấp phát tài nguyên của mạng (đường truyền, bộ nhớ đệm...). Nếu khả năng tài nguyên có hạn và chiến lược cấp phát không thích nghi với trạng thái luôn thay đổi của mạng thì dễ dẫn đến tình trạng, dữ liệu dồn về một trạm nào đó của mạng, gây nên tắc nghẽn do khả năng tài nguyên của trạm không đáp ứng nổi. Trong khi đó, tài nguyên của một số trạm nào đó có hiệu suất sử dụng thấp do rất ít dữ liệu được chuyển qua nó.

Để tránh các tình trạng trên cần thiết phải có một cơ chế kiểm soát luồng dữ liệu áp dụng cho toàn mạng, tức là điều khiển lưu thông trên mạng [59]. Nếu có tắc nghẽn xảy ra phải tiến hành điều khiển tắc nghẽn (congestion control) để giải quyết tắc nghẽn đưa mạng về trạng thái bình thường.

3.1 Điều khiển tắc nghẽn Để điều khiển tắc nghẽn cần phải phân tích một số nguyên nhân gây ra tắc nghẽn như sau: - Thời gian chờ xử lý, xếp hàng vào hàng đợi quá lớn. Nếu luồng các gói tin đột ngột bắt đầu đến từ 3 hay 4 đường vào và tất cả đều cần ra cùng một đường nên hàng đợi sẽ bị đầy (do phải lưu gói tin, phải tạo các bảng định tuyến,... ). Nếu khả năng xử lý của các nút yếu hay nói cách khác các CPU tại các router xử lý chậm các yêu cầu sẽ dẫn đến tắc nghẽn.

- Bộ đệm ở các hàng đợi quá nhỏ. Nếu bộ nhớ không đủ dung lượng để lưu chúng thì một số gói tin sẽ bị mất. Việc tăng dung lượng bộ nhớ đệm lên sẽ có ích, nhưng Nagle(1987) cho rằng nếu các router có lượng nhớ không xác định thì sự tắc nghẽn chẳng tốt hơn tí nào mà ngược lại trở nên xấu đi do số bản sao được gửi tăng lên, làm tăng lượng thông tin ở nơi nhận tin [18].

Tần suất lỗi mạng cao và độ trễ lớn. Đối với mạng cố định, việc mất gói tin do lỗi đường truyền hiếm khi xảy ra. Mất gói tin đồng nghĩa với việc xảy ra tắc nghẽn ở các nút (router) trong mạng. Cơ chế điều khiển chống tắc nghẽn của TCP sẽ căn cứ vào sự kiện mất gói và kiểm tra trễ quá time-out để xác định tắc nghẽn trong mạng. TCP không có khả năng phân biệt giữa mất gói do đường truyền hay mất gói do tắc nghẽn, mỗi khi xảy ra các hiện tượng trên TCP giảm tốc độ truyền. Điều đó không còn phù hợp với truyền thông di động vì hiệu suất đường truyền sẽ bị hạ thấp. Một vấn đề khác có tính không đồng nhất giữa mạng di động và mạng cố định là tốc độ truyền kênh di động thấp hơn nhiều so với mạng cố định [35]. Vì vậy, phần truy cập vô tuyến sẽ luôn là chỗ nghẽn cổ chai đối với một kết nối giữa thuê bao di động và một đầu cuối ở mạng cố định. Ngoài ra, hiệu ứng băng thông không đối xứng cũng có tác động lớn đến truy nhập Internet. Băng thông theo hướng từ máy cố định tới máy di động thường lớn hơn nhiều băng thông theo chiều ngược lại. Hiệu ứng này làm cho trễ theo hai chiều truyền khác nhau.

Trên hình biểu thị sự thay đổi lưu lượng của TCP. Khi máy chủ truyền các gói tin vào mạng con. Trong vòng lượng thông tin có thể truyền tốt thì các gói tin này sẽ được truyền đi, ngoại trừ vài gói tin bị hỏng do lỗi truyền và số gói tin được truyền đi tương ứng với số gói tin chuyển đến. Tuy nhiên, khi số lượng gói tin tăng lên, những router không còn khả năng điều chỉnh, đánh mất chúng. Điều này có khuynh hướng làm cho vấn đề trầm trọng hơn khi lượng lưu thông quá cao, sự truyền bị phá bỏ hoàn toàn và hầu như không có gói tin nào được truyền đi.

Nguyên lý điều khiển tắc nghẽn

Nhiều vấn đề trong hệ thống phức tạp như mạng máy tính có thể được xem xét dựa trên quan điểm của lý thuyết điều khiển. Phương pháp này dẫn đến việc chia tất cả các cách giải quyết thành 2 nhóm: vòng mở và vòng đóng.

Giải quyết vòng mở là cố gắng giải quyết vấn đề bằng việc thiết kế tốt về bản chất để chắc chắn không xảy ra sự cố ở điểm đầu tiên. Ở một hệ thống đang vận hành sự điều khiển của chúng không được thực hiện. Tiến hành điều khiển vòng mở bao gồm việc quyết định khi nào có thể nhận lượng tin mới, quyết định khi nào loại bỏ gói tin và loại bỏ gói nào, sau đó lên quyết định trình tự ở các điểm khác nhau trong mạng. Như vậy, các quyết định này đã không xem xét đến tình trạng lưu hành của mạng.

Giải quyết vòng đóng dựa vào khái niệm chính là vòng phản hồi, đây là phương pháp gồm 3 bước khi áp dụng vào điều khiển sự tắc nghẽn:

Bước 1: Làm chủ hệ thống để phát hiện xảy ra khi nào và ở đâu. Đây là điều tất yếu phải thực hiện để phát hiện tắc nghẽn có xảy ra hay không, nếu tồn tại thì xảy ra khi nào, ở đâu để có biện pháp khắc phục. 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ơi (router) mà ở đó có tiến hành giải quyết được công việc bằng cách chuyển thông tin báo tắc nghẽn cho các router khác hay là để router phát hiện tắc nghẽn gửi cho router nguồn. 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.

Ngoài ra, cũng còn có những khả năng khác.

Ví dụ: Sử dụng một bit hoặc một trường được lưu tại mọi gói tin để những router bất cứ lúc nào cũng nhận được thông báo dù xảy ra tắc nghẽn ở mức nào. Khi router phát hiện tình trạng tắc nghẽn này, nó sẽ đưa thông tin vào các trường ở gói tin sắp chuyển đi báo cho các nơi tiếp theo.

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õ 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ó nhiều phương pháp điều khiển tắc nghẽn, các phương pháp có thể hoạt động ở nguồn hoặc ở đích.

Hoạt động ở 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 xung quanh như là thời gian cần thiết cho sự báo nhận đi trở lại.

Hoạt động ở đích: Sự hiện diện của tắc nghẽn có nghĩa tải (tạm thời) là 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: 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ể sử dụng:

-Phủ nhận dịch vụ với nơi sử dụng, giảm bớt dịch vụ một vài nơi hoặc tất cả các nơi sử dụng.

-Có kế hoạch về nhu cầu nơi sử dụng theo phương pháp có thể dự đoán được.

-Để hạn chế tắc nghẽn phải thiết kế tốt hệ thống để chắc chắn không xảy ra tình trạng tắc nghẽn ở thời điểm ban đầu. Nếu sau đó xảy ra tắc nghẽn thì phải có những phản ứng nhận biết tắc nghẽn xảy ra ở đâu và thông báo để giải quyết.

3.2 Các giải pháp tránh tắc nghẽn

Để giải quyết tránh tắc nghẽn trong quá trình truyền thông trên mạng, chúng ta cần phải nghiên cứu các biện pháp xử lý tại các nút mạng và tại các trạm đầu cuối.

3.2.1 ở các nút mạng

Việc giải quyết bài toán xếp hàng tại bộ đệm của các nút mạng là rất quan trọng trong quá trình điều khiển lưu thông từ đầu cuối đến đầu cuối, chủ yếu các gói tin bị dồn tại các nút mạng trung tâm, nên cần phải có các giải pháp sắp xếp tại hàng đợi để nhanh chóng giải phóng các gói tin một cách cân bằng và hợp lý đối với các dịch vụ khác nhau, đáp ứng tốt yêu cầu của người sử dụng. ở nút mạng có các tổ chức hàng đợi như là: FIFO, PQ, classe-based, WFQ, RED...

+ Hàng đợi FIFO (First In First Out): phục vụ theo nguyên tắc gói tin vào trước được truyền đi trước. Đây là thuật toán được sử dụng rộng rãi, không phân biệt giữa các gói tin có yêu cầu chất lượng dịch vụ khác nhau. Nếu các gói tin đến và hàng đợi đã đầy thì gói tin bị huỷ bỏ, ta gọi là huỷ bỏ phần đuôi (DropTail).

+ Hàng đợi ưu tiên (PQ: Priority Queue): Các bộ định tuyến thực hiện nhiều hàng đợi FIFO, mỗi hàng đợi có một độ ưu tiên riêng để đảm bảo các gói tin cần được ưu tiên xử lý trước, tránh khả năng bị huỷ bỏ. Các gói tin có độ ưu tiên cao được truyền trước các gói tin có độ ưu tiên thấp hơn.

+ Hàng đợi classe-based: hàng đợi FIFO có thể xảy ra vấn đề có hàng chờ mãi không được phục vụ và bị tràn gói tin đến. Để khắc phục nhược điểm này, các gói tin bên trong mỗi hàng đợi được truyền theo nguyên tắc FIFO, còn các hàng đợi khác nhau sẽ được truyền theo nguyên tắc vòng tròn (Round Robin: RR ) hay còn gọi là hàng đợi cân bằng (Fair Queuing: FQ). Số các gói tin được truyền từ mỗi lớp hoặc băng thông dành cho mỗi lớp trong mỗi vòng là đã được xác định bởi thuộc tính của lớp đó. Như vậy, thuật toán đảm bảo cho mỗi lớp sẽ nhận một phần nào đó của băng thông liên kết.

Tuy nhiên, trong một lớp sẽ không cân bằng đối với các gói tin có kích thước nhỏ phải chờ đợi một thời gian dài trước những gói có dung lượng lớn hơn. Trong trường hợp này thì thuật toán điều độ không hợp lý.

+ Hàng đợi cân bằng trọng số (WFQ: Weight Fair Queue): WFQ dùng nhiều hàng đợi để tách biệt các luồng và cấp lượng băng thông như nhau vào mỗi luồng. Hay sự cấp phát băng thông cân bằng được định nghĩa là các luồng trong cùng một lớp có dung lượng nhỏ thì được cấp phát băng thông toàn bộ theo yêu cầu, những thời điểm có mật độ các luồng cao sẽ được chia sẻ băng thông để sử dụng. Điều này ngăn chặn trường hợp một ứng dụng nào đó, ví dụ như FTP tiêu thụ tất cả lượng băng thông khả dụng. WFQ đảm bảo rằng tất cả các hàng đợi không thiếu băng thông và lưu lượng nhận được dịch vụ có thể dự báo. Các luồng dữ liệu cỡ nhỏ nhận dịch vụ ưu tiên, truyền toàn bộ tải được cấp của nó theo một cách hợp lý. Các luồng dữ liệu cỡ lớn chia sẻ khả năng còn lại, nhận lấy lượng băng thông bằng nhau hay một phần nào đó. Hiện nay một số Cisco router đang dùng thuật toán WFQ cho giao tiếp có tốc độ nhỏ hơn 2Mbps.

Thuật toán này cho phép băng thông được chia sẻ một cách công bằng, không sử dụng danh sách truy cập hay các tác vụ quản lý tốn nhiều thời gian khác. Việc cân bằng hiện đang chịu sự chi phối của 6 cơ cấu: IP ưu tiên (IP Precedence), thông báo nghẽn tường minh tiến trong Frame-Relay (FECN: Frame Relay forward explicit congestion notification), thông báo nghẽn tường minh quay lui trong Frame-Relay (BECN: Frame Relay backward explicit congestion notification), RSVP, IP RTP Priority, IP RTP Reserve.

+ Hàng đợi Deficit Round Robin (DRR): cung cấp ưu tiên cho lưu lượng thời gian thực như VoIP, các gói IP được ánh xạ sang các hàng đợi khác nhau căn cứ vào các bit ưu tiên. Tất cả các hàng đợi đều phục vụ theo kiểu xoay vòng (RR), ngoại trừ một hàng đợi ưu tiên được dùng để kiểm soát lưu thoại. DRR hỗ trợ tương tự như WFQ nhưng cho các giao tiếp tốc độ cao.

Quản lý hàng đợi tránh tắc nghẽn

Như đã thảo luận trên, FIFO, FQ, WFQ, PQ, DRR [41] quản lý sự cố tắc nghẽn và ưu tiên hoá lưu lượng là điều quan trọng nhất. Còn vấn đề tránh tắc nghẽn được giải quyết bằng bài toán tương tự nhưng ở góc độ hoàn toàn khác. Thay vì kiểm soát các nghẽn đang tồn tại, tránh tắc nghẽn tiến hành các hoạt động ngăn chặn tắc nghẽn trước khi nó xảy ra. Có hai phương pháp cơ bản:

Gói tin kiểm tra tắc nghẽn (Choke Packets): Khi đường truyền đã ở ngưỡng tắc nghẽn, router gửi Choke Packet trở lại trạm nguồn để thông báo tình trạng này và trạm nguồn sẽ giảm lưu lượng để tránh tắc nghẽn. Nếu hết tắc nghẽn (không có Choke Packets gửi đến) trạm nguồn lại tăng lưu lượng gửi. Cụ thể như sau: Căn cứ các bộ đệm bị đầy, sắp tràn router đặt DECbit (a binary congestion bit) trong gói tin để dự báo tắc nghẽn. Trạm đích sao bit này vào ACK và gửi về trạm nguồn. Trạm nguồn hiệu chỉnh tốc độ gửi dữ liệu để tránh tắc nghẽn. Nếu hơn 50% gói tin có DECbit, trạm nguồn giảm cửa sổ tắc nghẽn (congestion window: cwnd) 0,875 lần giá trị trước. Nếu nhỏ hơn 50% gói tin có DECbit, trạm nguồn tăng cửa sổ tắc nghẽn cwnd lên 1. Tăng 1, giảm 0,875 làm cho cơ chế điều chỉnh ổn định.

RED (Random Early Detection): ý tưởng giống như DECbit là router có chương trình quản lý độ dài hàng đợi và khi kiểm tra thấy sắp xảy ra tắc nghẽn thì thông báo cho trạm nguồn hiệu chỉnh cửa sổ tắc nghẽn. Điểm khác ở đây là RED thông báo cho trạm nguồn về tắc nghẽn bằng cách cho rơi sớm gói tin, như vậy trạm nguồn nhận biết thông qua "time out", hoặc "duplicate ACK" và trạm nguồn giảm tốc độ phát với hy vọng không phải hủy bỏ nhiều gói tin sau đó. Xác suất rơi gói tin sớm phụ thuộc độ dài trung bình hàng đợi và hai ngưỡng minth, maxth [28]. Vì vậy RED rất hữu dụng trong các mạng TCP tốc độ cao để tránh nghẽn.

1 Cơ chế quản lý hàng đợi RED

Một trong những lý do của tỷ lệ mất gói tin cao nữa là sự bất lực của mạng. Để sớm phát hiện tắc nghẽn và hỗ trợ báo tắc nghẽn cho trạm nguồn, tổ chức chuẩn IETF khuyến cáo nên dùng quản lý hàng đợi tích cực (RED/ECN) tại Router trên mạng Internet [28].

Bộ định tuyến cài đặt RED sử dụng hai giá trị là chặn trên và chặn dưới để đánh dấu các vị trí trong hàng đợi: minth và maxth như hình 3.11. Hoạt động của RED được mô tả bởi ba quy tắc để xác định vị trí của mỗi gói tin gửi đến:

- Nếu số lượng gói tin trong hàng đợi nằm giữa các giá trị minth và maxth thì hủy bỏ gói tin một cách ngẫu nhiên tùy theo một hàm xác suất p.

- Nếu hàng đợi chứa ít hơn minth gói tin thì thêm gói tin mới vào hàng đợi và xác suất hủy bỏ là 0.

- Nếu hàng đợi chứa nhiều hơn maxth gói tin thì hủy bỏ những gói tin mới và xác suất hủy bỏ là 1.

Để cho RED hoạt động tốt thì phải chọn các giá trị minth, maxth và hàm xác suất p như thế nào cho phù hợp. Giá trị minth phải đủ lớn để đảm bảo rằng liên kết dữ liệu được sử dụng với hiệu suất cao. Giá trị maxth phải lớn hơn minth, ít nhất là phải gấp đôi. Nếu không thì RED cũng gây ra những ảnh hưởng như "cắt bớt phần đuôi". Mô hình được thể hiện như sau:

Mặc dù mô hình tuyến tính là cơ sở của phép tính xác suất cho RED, cần phải có những hiệu chỉnh để tránh tình trạng phản ứng "quá vội". Sở dĩ cần có những thay đổi là bởi vì giao thông trên mạng có thể là theo từng "đợt", và gây ra những dao động quá nhanh của hàng đợi trong bộ định tuyến. Nếu RED sử dụng một mô hình tuyến tính đơn giản, những gói tin đến sau trong mỗi đợt sẽ bị gán xác suất cao cho khả năng phải loại bỏ (bởi vì chúng đến khi hàng đợi đã có nhiều gói tin). Tuy nhiên, bộ định tuyến không nên huỷ bỏ những gói tin này một cách không cần thiết, bởi vì làm như thế sẽ tác động xấu đến hiệu suất của TCP. Nếu gặp một đợt (các gói tin) ngắn, ít có khả năng bị loại bớt gói tin, bởi vì hàng đợi chưa bị đầy. Dĩ nhiên, RED không thể tạm hoãn việc huỷ bỏ vô thời hạn bởi vì một đợt dài sẽ làm đầy hàng đợi, kết quả chẳng khác nào chiến lược "cắt bớt phần đuôi", và sẽ gây ra ảnh hưởng đến toàn bộ Internet.

Làm thế nào RED có thể gán một xác suất huỷ bỏ cao hơn khi hàng đợi bị đầy mà không phải huỷ bỏ gói tin của mỗi đợt? Câu trả lời thuộc về một kỹ thuật được vay mượn từ TCP: thay vì sử dụng kích thước thật của hàng đợi tại thời điểm đó, RED tính kích thước hàng đợi trung bình có hệ số , và sử dụng kích thước trung bình này để xác định xác suất. Giá trị của được cập nhật mỗi khi có gói tin gửi đến theo phép gán sau :

:= (1 - ) * + * k (3.1)

Với là hệ số hay là trọng số hàng đợi,( 0 1)

k: kích thước hàng đợi hiện hành.

Nếu giá trị của đủ nhỏ, thì giá trị trung bình sẽ có khuynh hướng ít thay đổi, và sẽ ít bị ảnh hưởng đối với những đợt ngắn (ví dụ: = 0,002).

Cùng với những phương trình để xác định , RED còn bao gồm những chi tiết khác mà chúng ta đã ít chú ý. Lấy ví dụ, các phép tính trong RED có thể được thực hiện vô cùng hiệu quả với việc chọn các hệ số là lũy thừa của 2. Thời gian cần để chuyển gói tin IP đi là tỷ lệ thuận với kích thước của nó, nên sẽ hợp lý hơn khi đo hàng đợi theo byte thay vì theo gói tin IP, làm như thế sẽ chỉ đòi hỏi những thay đổi nhỏ đến những phương trình cho p và . Việc đo kích thước hàng đợi theo byte ảnh hưởng đến xác suất bị loại bỏ của các gói tin có kích thước khác nhau. Những gói tin IP nhỏ (ví dụ, những gói tin chuyển tải dữ liệu cho việc kết nối từ xa) sẽ có xác suất bị loại bỏ thấp hơn những gói tin IP lớn (ví dụ: những gói tin chuyển dữ liệu của dịch vụ truyền tệp tin). Một kết quả tích cực của việc sử dụng kích thước là khi những gói báo nhận (ACK) di chuyển trên một con đường bị tắc nghẽn, chúng sẽ có xác suất bị loại bỏ thấp hơn. Và kết quả là, nếu một gói tin (lớn) đến được, thì TCP nơi gửi sẽ nhận được báo nhận và sẽ tránh được việc truyền lại không cần thiết các gói tin lớn.

Chi tiết thuật toán điều khiển của RED được thể hiện cụ thể như sau:

Các tham số vào:

maxth: là giới hạn của ngưỡng kích thước hàng đợi cực đại,

minth: là giới hạn của ngưỡng kích thước hàng đợi cực tiểu

maxp: xác suất rơi cực đại

: là trọng số hàng đợi trong đoạn [0,1], 0 1.

Thuật toán RED có 2 phần chính: Ước tính kích thước hàng đợi trung bình và quyết định các gói tin đến có bị rơi hay không?

(1) Ước tính kích thước hàng đợi trung bình

RED/ECN tính toán kích thước hàng đợi trung bình dựa trên sự di chuyển của trọng số theo hàm mũ trung bình:

If hàng đợi là không rỗng then

:= (1 - ) * + * k

else

:= ( 1 - )f(time - q-time) *

( k: kích thước hàng đợi hiện hành.

time: thời gian hiện tại

q_time: thời điểm hàng đợi bắt đầu rỗi )

(2) Phần quyết định gói tin rơi

Trong phần này của thuật toán RED/ECN quyết định hoặc là rơi gói tin hoặc là không rơi gói tin đến. Đó là thuật toán cải tiến hiệu năng cho những luồng báo nhận, khi kích thước hàng đợi trung bình biến đổi từ min¬th đến max¬th, các giá trị sẽ bị rơi với một xác suất trong khoảng 0 đến maxp. Nghĩa là:

If minth 

xác suất các gói tin đến bị rơi là:

pb( )= = (3.2)

Từ đó suy ra xác suất số các gói tin đến được đích là:

pa( )= pb( )/(1-count*pb( ) )

(count: là số các gói tin đã đến được bộ định tuyến mà sau đó bị rơi)

If maxth  then

các gói tin đến sẽ bị rơi hay pb( )= 1.

If

các gói tin đến sẽ không bị rơi hay pb( )= 0

Khi các gói tin bị mất ở hàng đợi tức là có dấu hiệu bộ đệm bị tràn. Vì vậy ECN có thể nhận ra tắc nghẽn thông qua việc mất gói tin, giúp ích cho việc nâng cao hiệu năng mạng.

3.2.2 Những cơ chế điều khiển của TCP

Khi một kết nối được thiết lập, độ lớn cửa sổ truyền ban đầu là thấp, sau đó tăng dần lên nhằm tránh tắc nghẽn. Quá trình sẽ tăng liên tục cho đến khi w đạt đến giá trị tối đa, tức là khi gặp lỗi hay khi nhận được gói báo nhận ACK yêu cầu phát lại, hay quá thời gian chờ tối đa cho phép. Khi đó, độ lớn cửa sổ phát sẽ được giảm và quá trình truyền lại bắt đầu một chu kỳ mới [7].

Việc tránh tắc nghẽn có thể căn cứ vào thời gian khứ hồi gói tin RTT (Round trip time: thời gian bắt đầu phát gói dữ liệu cho đến khi nhận được trả lời) hoặc lượng dữ liệu đưa vào mạng để biết tắc nghẽn sắp xảy ra nếu không can thiệp [21].

Nếu hàng đợi bộ định tuyến (Router) đang tăng, thời gian đợi tăng và RTT tăng, căn cứ vào RTT hiện tại sẽ biết được tắc nghẽn sắp xảy ra. Xác định RTT trung bình, nếu RTTht > RTTtb thì giảm cwnd(1/8). Ngược lại thì tăng cửa sổ tắc nghẽn cwnd lên một gói cực đại.

Cơ chế bắt đầu chậm (Slow-start):

Lúc khởi động ta không thể gửi toàn bộ số liệu ứng với cửa sổ quy định (advertised window) vì sợ các router trên mạng không thể nhận kịp số gói dữ liệu tối đa ồ ạt và dẫn đến tắc nghẽn. Nhưng ngược lại, không thể tăng tuyến tính, vì như thế sẽ qua lâu và cần tăng nhanh đến cửa sổ tắc nghẽn, nhờ cơ chế bắt đầu chậm nó tăng theo lũy tiến chứ không phải tuyến tính. Lúc bắt đầu phát với cnwd=1, mỗi khi nhận được thông báo trả lời ACK (báo nhận), cwnd được tăng thêm gấp đôi (1, 2, 4, 8, 16...) cho đến khi xuất hiện tình trạng tắc nghẽn dữ liệu, thể hiện qua việc gia tăng giá trị thời gian trễ RTT. Giai đoạn khởi động chậm kết thúc khi cửa sổ w đạt đến ngưỡng nhất định.

Ảnh hưởng của thuật toán Slow-Start

Có hai vấn đề quan tâm khi sử dụng thuật toán Slow-Start với mạng tốc độ cao và độ trễ lớn là:

Thuật toán dò tìm băng thông theo kiểu Slow-Start có thể mất rất nhiều thời gian để đạt tốc độ cực đại, đặc biệt trong môi trường trễ lớn. Với mạng vệ tinh tốc độ Gbit/s với RTT khoảng 0,5s cần 29 RTT hay 14,5s để khởi tạo thành công. Như vậy, toàn bộ giải thông sẽ không được tận dụng hết ngay và trong phần lớn thời gian băng thông của mạng sẽ bị lãng phí. Gần đây IETF cũng đã xem xét tới việc cho phép TCP có thể phát nhiều hơn một segment (các đề nghị gần đây cho phép phát từ 2- 4 segment) tại thời điểm bắt đầu khởi tạo thuật toán Slow-Start. Nếu còn dung lượng trên đường truyền, thay đổi này sẽ làm giảm bớt thời gian khoảng 3 lần RTT.

Vấn đề thứ hai là sự nhầm lẫn giữa tắc nghẽn mạng và lỗi do đường truyền. TCP không phân biệt được hai lỗi này và nó cho rằng khi bị mất gói có nghĩa là do mạng tắc nghẽn. Do thuật toán dò tìm là tuyến tính hơn là luỹ thừa, giả sử nếu xuất hiện các segment bị lỗi ngay từ đầu thì thời gian cần thiết để đạt tốc độ tối đa là rất dài [41].

Cải thiện Slow-Start là tạo cho router gần phía kết nối vệ tinh gửi trả tín hiệu báo nhận ACK. Vì vậy Router phải có bộ đệm cho các segment dữ liệu để đề phòng trường hợp phải phát lại, cơ chế này cần sử dụng kiểu đường truyền đối xứng (ít có trên Internet) và có thể bị ảnh hưởng do lỗi.

Cơ chế tránh tắc nghẽn (Congestion Avoidance)

TCP phát với MaxWindow w = min {cwnd, rwnd}, trong đó

cwnd: Congestion window: xác lập trên cơ sở mức tắc nghẽn thấy được trên mạng

rwnd: Receive window: cửa sổ thu cho phép

Khi có hiện tượng tắc nghẽn, thể hiện ở time-out hoặc Duplicated ACK, đặt giá trị cửa sổ w/2 (không nhỏ hơn 2 đơn vị gói dữ liệu) lưu giữ trong trường ssthresh và đặt cwnd=1 đơn vị gói dữ liệu (giảm theo cấp số nhân để thoát nhanh tránh tắc nghẽn).

Khi nhận được thông báo ACK (giảm tắc nghẽn)

Nếu cwnd

Nếu cwnd = ssthresh thuật toán tránh tắc nghẽn được thực hiện: giá trị cwnd được tăng 1/cwnd với mỗi thông báo ACK nhận được (tăng tuyến tính để không rơi lại vào tắc nghẽn).

Cơ chế phát lại nhanh (Fast Retransmission)

TCP thực hiện phát một gói dữ liệu khi nhận được thông báo NAK (thu sai) hoặc được đồng hồ quản lý phát lại được kích hoạt (time-out). Nếu chờ time-out mới phát lại gây ra số gói phát lại nhiều (hoặc đòi hỏi bộ đệm phía thu lớn để giữ tạm các gói sai số thứ tự), điều đó dễ gây ra tắc nghẽn. Cơ chế phát lại nhanh cho phép phát lại không cần chờ time-out, trong trường hợp nhận được hơn ba thông báo ACK lặp lại (duplicated ACK), nghĩa là có gói dữ liệu bị mất, cần phát lại [61].

Hình 1.9: Cơ chế truyền lại nhanh dựa trên duplicate ACKs

Cơ chế phục hồi nhanh (Fast Recovery)

Như trên, khi time-out là bắt đầu lại "Slow Start", quá trình "Slow Start" là không cần thiết. Ta có thể bắt đầu ngay quá trình tuyến tính từ threshold lúc time-out (phục hồi nhanh).

Khi time-out hoặc nhận được ba thông báo ACK lặp lại, trạm phát thiết lập

ssthresh = cwnd/2 (không nhỏ hơn hai đơn vị gói dữ liệu) và phát lại gói dữ liệu mất, tăng cwnd = cwnd + 3*smss.

Điều này cho phép tăng "nhân tạo" cửa sổ phát cwnd tương ứng ba gói dữ liệu như được nhận trong bộ đệm của trạm nhận.

Với mỗi thông báo ACK lặp lại, tăng cwnd = cwnd + 1*smss, tương ứng với một gói dữ liệu được phát vào mạng.

Thực hiện phát một gói dữ liệu, nếu thoã mãn: w = min {cwnd, rwnd}. Sau khi nhận được thông báo trả lời ACK không bị lặp lại, nghĩa là một gói dữ liệu mới đã được nhận đúng, thực thể TCP thiết lập lại giá trị cwnd được giữ trong trường ssthresh và thực hiện việc phát bình thường trở lại với qui tắc:

w = min {cwnd, rwnd}

Cơ chế phục hồi nhanh tránh cho lưu lượng dữ liệu trong kết nối TCP không bị thay đổi đột ngột và đảm bảo thông lượng dữ liệu đạt được phù hợp với bối cảnh thực tế: việc phát, thu có lỗi.

Thuật toán phát lại và phục hồi nhanh có 2 nhược điểm:

Việc phỏt lại cỏc gúi bị lỗi dẫn đến phỏt lại gúi dữ liệu đó được phát thành công trước đó và khi thuật toỏn này khụng thành cụng phải chờ time-out để phỏt lại, khi đó độ lớn cửa sổ phỏt bằng 1.

Vỡ vậy, thay vỡ chờ time-out ta dựng ngay thuật toỏn phỏt lại giống như trong giai đoạn khởi động chậm .

Trong mạng khụng đối xứng băng thụng đường truyền có độ chờnh lệch lớn giữa kờnh số liệu và kờnh ACK (tớnh khụng đối xứng sẽ tăng lên khi truyền theo 2 hướng), kích thước và thời gian truyền giữa gói ACK và gói dữ liệu làm ảnh hưởng đến hiệu suất trao đổi dữ liệu TCP, tốc độ kờnh phỏt phụ thuộc vào sự thay đổi nhịp của gúi xỏc nhận ACK (ACK clock). Như vậy, khi ACK bị mất, thiết bị phát sẽ rơi và trạng thái chờ phỏt làm cho độ trễ đường truyền tăng lờn. Vấn đề này được giải quyết theo 2 hướng như sau:

-Kỹ thuật quản lý kờnh xỏc nhận ACK, trong đó đặc biệt là kỹ thuật nộn tiờu đề và giảm tần số phỏt của ACK [32].

-Kỹ thuật điều khiển tần suất phỏt ACK nhằm tối ưu hoá quá trỡnh truyền phỏt dữ liệu trờn kờnh phỏt [43].

Mô hình TCP/IP đã được nghiên cứu và phát triển trên mạng Internet trong một thời gian dài, Internet được xem như là một môi trường không đồng nhất, cần có những cơ chế điều khiển tắc nghẽn để giảm những sai sót không đáng có. Ví dụ như, một trạm nguồn TCP có thể điều khiển tốc độ các gói tin lưu thông trên đường truyền thông qua cơ chế điều chỉnh cửa sổ hoặc giảm luồng các gói tin đến bằng cách điều chỉnh gói báo nhận ACK để đáp ứng với những thay đổi của mạng nhằm mục đích tăng công suất mạng.

Trước đây, việc nghiên cứu hiệu năng, chiến lược điều khiển mạng lưu thông hầu như tập trung chủ yếu về một mặt, như yêu cầu về mục đích hiệu quả hoặc nghiên cứu hiệu năng hợp nhất trong một lĩnh vực cụ thể. Ví dụ: mô tả mối quan hệ giữa số lượng gói tin đưa vào và độ trễ, tốc độ đến và thời gian xử lý, quản lý hàng đợi, giao thức điều khiển, nhưng nó chỉ xét đến mạng hàng đợi liên kết đơn và với giả sử bộ đệm là vô hạn, vì vậy các tính toán không thể đánh giá đầy đủ đối với chiến lược điều khiển mạng.

3.4 Phân tích những cải tiến đã được đề xuất cho TCP

Khi có sự mất cân bằng tài nguyên, như khi tốc độ các gói tin đến cao mà tốc độ xử lý tại hàng đợi của máy tính trung tâm thấp (nguyên nhân tăng độ trễ, phải truyền tải lại), làm giảm hiệu năng. Hoặc sau phục hồi hệ thống, các máy trạm đồng thời truy cập đến máy trung tâm làm tăng tải, nên phải có chiến lược đồng bộ hiện tượng quá tải phù hợp. Trong giao thức TCP cũng đã có những cơ chế điều khiển luồng cũng như kiểm soát lỗi, nhưng trong môi trường mạng bất đối xứng đã tỏ ra kém hiệu quả. Vì vậy, các nhà nghiên cứu Internet đã đề nghị những cơ chế để cải tiến TCP [41], [59] như sau:

+ Tăng kích thước cửa sổ với một tốc độ không phụ thuộc RTT: tức là cần phải tính toán sao cho RTT nhỏ. Tuy nhiên, điều này không tạo điều kiện dễ dàng cho việc chọn tốc độ tăng kích thước cửa sổ để mạng hoạt động tốt trên phạm vi rộng của RTT. Nếu tốc độ tăng là nhỏ hơn so với tốc độ hiện tại thì các liên kết sẽ chậm, còn nếu tốc độ là quá nhanh thì số gói tin mất sẽ lớn khi có nhiều liên kết đang hoạt động và RTT sẽ lớn.

+ Điều chỉnh kích thước cửa sổ theo độ trễ lúc không có lỗi: tập trung vào việc so sánh RTT với RTT cực tiểu dựa trên số gói tin chuyển đi được. Ý tưởng ở đây là tăng độ đo RTT theo kích thước hàng đợi trong bộ định tuyến. Khó khăn trên thực tế là việc ước lượng RTT theo thời gian đợi tại thời điểm bắt đầu của một kết nối. Nếu tất cả trạm nguồn sử dụng cơ chế này thì sẽ giảm nguy cơ tắc nghẽn.

+ Đánh dấu các gói tin ở bộ định tuyến khi có dấu hiệu tắc nghẽn cho đến khi gói tin rơi (ECN: thông báo rõ tắc nghẽn) để cho trạm nhận gửi thông báo ngược lại đi theo các gói ACK. Cơ chế này rất được ưu chuộng, vì nó dùng để ra hiệu cho trạm nguồn hạ thấp kích thước cửa sổ và thực hiện việc truyền lại các gói tin hỏng.

+ Cải tiến bộ định tuyến có các chương trình hỗ trợ cho việc thông báo rõ tốc độ truyền tin xác định, nên bộ định tuyến phức tạp hơn. Một đề xuất là đánh dấu nhãn gói tin nếu nó có khả năng gây ra lỗi mất gói tin trong tương lai. Điều đó có nghĩa là, khi các gói tin đến, bộ định tuyến phải dự báo về gói tin này, hoặc là sẽ bị rơi hoặc là gói tin đó sẽ đến sau. Sự quyết định phải dựa trên tải hiện hành của bộ định tuyến.

+ Xây dựng cơ chế điều khiển lỗi cho những liên kết nhiều lỗi.

Đây là 5 đề xuất chính để cải thiện lưu thông trên mạng. Tuy nhiên mỗi phương pháp có những ưu và khuyết điểm riêng dựa trên mô hình cài đặt.

Vì vậy, trong chương này, chúng tôi chỉ đi sâu phân tích những giải pháp có tác động mạnh trong điều khiển tắc nghẽn, đặc biệt là các phương pháp tránh tắc nghẽn hữu dụng trong môi trường bất đối xứng về băng thông, tỷ lệ gói tin được truyền và độ trễ. Cụ thể như sau:

- Xử lý nhanh các gói tin đến tại nút mạng, dựa trên chiến lược quản lý hàng đợi thích hợp và cải tiến giao thức ở đầu cuối cho các mô hình mạng đáp ứng với hiệu suất cao.

- Có thể tăng, giảm thời gian đáp ACK để điều chỉnh lưu lượng gói tin đến. Đo các tham số mạng liên quan và theo dõi quá trình thực hiện dựa trên sơ đồ hình 3.1, đặt tầng quan sát tại máy trạm để theo dõi chu kỳ của các quá trình thực hiện trên mạng [37]. Dùng Timer để biết được gói tin cần bao lâu để được báo nhận của RTT từ khi bắt đầu yêu cầu gói tin đến cho đến lúc nhận được đáp ứng trả lời. Đồng thời, ghi lại biến cố xảy ra (dựa vào trình tự ACK) như là hiện tượng mất gói tin.

- Thiết kế hệ thống phải đảm bảo lưu lượng truyền tối đa nhưng không dẫn đến tắc nghẽn, không để xảy ra hiện tượng thắt nút do sự chênh lệch tốc độ trong thiết kế mạng Intranet. Đặc biệt xử lý tốc độ cao tại vị trí các nút mạng trung tâm qua kết nối bộ định tuyến truyền đi Internet để thực hiện hiệu suất tốt hơn.

3.6.2 Các giải pháp cải tiến điều khiển ACK

Cơ chế điều khiển được xét đến ở đây là quá trình điều khiển gói báo nhận ACK 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ợ điều khiển tốc độ truyền dữ liệu cũng như truyền dữ liệu đá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 đi thông báo cửa sổ có kích thước là zero để ngưng tất cả việc truyền. 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. Trong trường hợp này, điều khiển gói báo nhận ACK hợp lý giữa luồng gói tin đến và cơ chế xử lý hàng đợi tích cực tại nút nhận trung tâm là hiệu quả hơn.

Kỹ thuật lọc gói ACK và điều khiển tắc nghẽn ACK

Để giảm bớt ACK trên đường truyền và giải phóng hàng đợi, người ta sử dụng Kỹ thuật lọc gói ACK (ACK filter: AF), tức là loại bỏ bớt các gói ACK của cùng một kết nối, tích luỹ số thứ tự của các gói ACK đến trước vào ACK sau cùng. Khi có hiện tượng tắc nghẽn xẩy ra thì ta dùng cơ chế điều khiển tắc nghẽn đối với các gói ACK (ACK Congestion Control: ACC) của TCP tại bộ đệm hàng đợi máy nhận. ACC có 2 thành phần:

Cơ chế báo hiệu kênh ACK bị tắc nghẽn và cơ chế trả lời của bên nhận.

ACC có thể dùng thuật toán RED để phát hiện sớm tắc nghẽn tiềm ẩn (khả năng vượt quá ngưỡng) có thể xảy ra bằng cách tính toán kích thước trung bình của hàng đợi trong khoảng thời gian ngay trước đó, khi đó một gói ACK hay gói tin sẽ được đánh dấu bit ECN (Explicit Congestion Notification: Báo tắc nghẽn) trong trường Options của TCP. Như vậy khi nhận gói ACK có ECN, bên gửi sẽ giảm tần suất phát gói tin và khi nhận gói tin có ECN bên nhận làm chậm việc phát ACK [43].

Kỹ thuật trễ ACK

Tại mỗi thiết bị nhận người ta duy trì một hệ số động DelAck gọi là hệ số giữ chậm (hay trễ) ACK nhằm xác định số gói tin tương ứng với một gói ACK. Khi một gói ACK có đánh dấu ECN, giá trị DelAck được nhân lên nhiều lần nên làm giảm số gói ACK trên đường truyền sẽ dẫn đến sự giảm tần suất phát gói tin. Trạm nhận truyền ít nhất 1 gói ACK cho mỗi cửa sổ phát của trạm phát. Nếu không trạm phát sẽ rơi vào trạng thái chờ cho đến khi gói ACK được phát miễn cưỡng theo nhịp đồng hồ phát của trạm nhận. Giao thức TCP có cơ chế DelAck gọi là TCP_DelAck.

Kỹ thuật tái tạo ACK

Nếu chuỗi ACK được phát đi ở kênh tốc độ chậm thì ta sử dụng phương pháp tái tạo gói ACK (ACK Reconstruction:AR) bằng cách tạo ra các gói ACK "giả" cung cấp cho trạm phát theo một tốc độ không đổi làm giá trị cửa sổ phát tăng lên phù hợp trên mỗi kênh phát. Nghĩa là mỗi AR có một tham số ngưỡng ack_thresh, quyết định số ACK được thêm vào.

3.7 Điều khiển lưu lượng trong mạng TCP cải tiến và các cải tiến của cơ chế quản lý hàng đợi tại nút mạng

3.7.1 Điều khiển lưu lượng trong TCP

Như chúng ta đã phân tích ở trên, TCP điều khiển tần suất truyền bằng cách giới hạn số gói báo nhận ACK được truyền. Một cách lý tưởng khi không có sự mất mát dữ liệu do tắc nghẽn trên đường truyền thì độ lớn của cửa sổ phát càng lớn càng tốt. Khi một kết nối được thiết lập, độ lớn cửa sổ truyền ban đầu là thấp, sau đó tăng dần lên nhằm tránh tắc nghẽn. Quá trình sẽ tăng liên tục cho đến khi W đạt đến giá trị tối đa, tức là khi gặp lỗi hay khi nhận được gói lặp báo nhận ACK yêu cầu phát lại hay quá thời gian chờ tối đa (time-out) cho phép. Khi đó, độ lớn cửa sổ phát sẽ được giảm và quá trình truyền lại bắt đầu một chu kỳ mới [65].

Nếu gói báo nhận ACK đến trước thời điểm cho phép (time-out), độ lớn cửa sổ phát tăng lên 1 với mỗi gói báo nhận ACK nhận được và quá trình lặp lại cho đến khi W bằng giá trị ngưỡng hay gặp lỗi.

Gọi W(t) là số gói tin tối đa cho phép phát tại thời điểm t hay độ lớn cửa sổ phát thời điểm t. Trong pha khởi động chậm, độ lớn cửa sổ phát tăng nhanh theo hàm mũ. Khi độ lớn cửa sổ phát tăng vượt quá giá trị ngưỡng (threshold) đặt trước, giá trị W(t) sẽ tăng tuyến tính và theo công thức:

W(t) = W(t) + 1/W(t) và chuyển sang pha tránh lỗi.

Như vậy độ lớn cửa sổ phát sẽ tăng lên 1 sau khi phát hết các gói dữ liệu trong cửa sổ phát, nghĩa là W(t) càng lớn thì tốc độ tăng càng chậm và kéo dài cho đến khi gặp lỗi. Ví dụ: Giả sử ngưỡng ban đầu bằng 8 gói dữ liệu, độ lớn cửa sổ phát bằng 1, tăng nhanh và sau 3 lần truyền, giá trị này đạt ngưỡng đặt trước và chuyển sang giai đoạn tăng tuyến tính. Giả sử khi w(t) = 12 lỗi xảy ra, khi đó giá trị ngưỡng được đặt bằng 6 và w(t) = 1.

3.7.2 Hoạt động TCP_Tahoe

Giao thức điều khiển tắc nghẽn TCP_Tahoe là giao thức TCP kết hợp với ba cơ chế "bắt đầu chậm", "tránh tắc nghẽn" và "phát lại nhanh". Đặc trưng của TCP_Tahoe là khi phát hiện mất gói dữ liệu thông qua việc nhận 3 gói ACK lặp lại, trạm gửi phát lại gói dữ liệu bị mất đặt cwnd bằng 1 gói dữ liệu và khởi động quá trình "bắt đầu chậm". Cơ chế "phát lại nhanh" khôi phục chờ "time-out", cho phép tăng đáng kể thông lượng và hiệu suất sử dụng kênh kết nối TCP. Hoạt động của TCP_Tahoe như sau:

3.7.3 Hoạt động TCP_Reno

TCP_Reno là cải tiến tiếp của TCP_Tahoe, ở đây sau "phát lại nhanh" là "hồi phục nhanh" (giảm cwnd xuống còn một nửa), chứ không phải là "bắt đầu chậm" (cwnd=1). Như vậy tránh được "đường ống" khỏi bị rỗng sau khi phát lại nhanh và cần quá trình "bắt đầu chậm" để đổ đầy đường ống.

Theo chuẩn TCP_Reno khi độ lớn cửa sổ phát đặt về 1, giá trị ngưỡng threshold bằng W(t)/2, ta thấy trong giai đoạn này cửa sổ phát tăng rất chậm nhưng giảm rất nhanh theo cấp số nhân.

Khi dữ liệu bị mất hay quá thời gian chờ ACK, TCP_Reno đặt lại cửa sổ phát bằng 1, sử dụng cơ chế phát lại nhanh (Fast retransmission) và khôi phục nhanh (Fast recovery), trạm gửi sẽ đi vào giai đoạn khôi phục nhanh (xét trường hợp một gói lỗi) sau khi nhận được một giá trị ngưỡng của số báo nhận ACK lặp bằng 3. Khi số báo nhận lặp đạt đến ngưỡng trạm gửi sẽ phát lại 1 gói dữ liệu, sau đó giảm cửa sổ tắc nghẽn cwnd xuống còn một nửa. Sau đó cứ mỗi lần nhận được 1 ACK, trạm gửi lại gửi đi 1 gói dữ liệu.

Thuật toán TCP_Reno

B1: Khi nhận được gói báo nhận ACK

If W(t)= Threshold then

W(t+t):=W(t)+1; // giai đoạn khởi động chậm

Else

W(t+t):=W(t)+1/W(t), // giai đoạn tăng tuyến tính

B2: Khi nhận được 3 gói lặp ACK

Threshold:=W(t)/2;

W(t):=W(t)/2;

Thực hiện thuật toán phát và phục hồi nhanh

B3: Khi quá thời gian cho phép

Threshold:=W(t)/2;

W(t)=1;

Trong quá trình truyền khi gặp lỗi thì giá trị ngưỡng thay đổi theo công thức:

Threshold = max(Flight size/2, 2*SMSS),

trong đó Flight size là số gói tin đã gửi nhưng chưa nhận ACK. SMSS là độ lớn tối đa gói tin gửi.

So với TCP_Tahoe, TCP_Reno cải thiện đáng kể hiệu năng về thông lượng nếu chỉ có nhiều nhất là 1 gói dữ liệu bị loại trong các gói dữ liệu của một cửa sổ. Tuy nhiên, hiệu năng của TCP_Reno sẽ giảm trầm trọng nếu trong một cửa sổ có trên một gói dữ liệu bị loại.

TCP_NewReno là cải tiến tiếp của TCP_Reno để cải thiện hiệu năng trong trường hợp cửa sổ có trên một gói dữ liệu bị loại.

Trong TCP_Reno, các gói ACK cục bộ (partial ACK) giải phóng TCP khỏi trạng thái "phục hồi nhanh", nếu có nhiều gói dữ liệu bị mất trong một cửa sổ thì phải chờ time_out để phát lại.

Trong TCP_NewReno, các ACK cục bộ nhận được không đưa TCP ra khỏi quá trình "phục hồi nhanh", mà được xem như là tín hiệu thông báo rằng gói dữ liệu ngay tiếp sau gói dữ liệu được xác nhận đã bị mất và phải được truyền lại. Như vậy, khi có nhiều gói dữ liệu bị mất từ một cửa sổ TCP_NewReno có thể phục hồi không cần chờ đến time_out, bằng cách phát lại một gói dữ liệu đã mất cho mỗi RTT, cho đến khi tất cả các gói dữ liệu bị mất từ cửa sổ này đã được truyền lại. TCP_NewReno giữ nguyên trong "phục hồi nhanh" cho đến khi tất cả gói dữ liệu được gửi đi từ khi bắt đầu thực hiện "phục hồi nhanh" được báo nhận hết.

3.7.4 Thuật toán TCP_SACK

Gần đây, IETF đã đưa vào áp dụng những mở rộng mới đối với giao thức TCP gọi là phương pháp ACK có lựa chọn (SACK: Selective ACK). Phương pháp này cho phép TCP có thể báo nhận ACK các dữ liệu nhận được mà không theo thứ tự. Do vậy, SACK có hai ưu điểm chính là:

Trước hết nó tăng hiệu quả của việc truyền lại TCP bằng cách giảm chu kỳ truyền lại và kỹ thuật SACK cho phép TCP truyền lại nhiều gói tin bị mất trong 1 chu kỳ. Người ta đã chứng minh được TCP_SACK cho phép nâng cao hiệu năng của hệ thống trong trường hợp trễ lớn. Nhưng giao thức TCP_SACK có nhược điểm là:

- Đòi hỏi phải sửa đổi giao thức ở cả hai phía thu và phát.

- Do TCP không phân biệt được lỗi do truyền dẫn, nên trong trường hợp lỗi lớn hiệu năng TCP giảm một cách đáng kể và bắt đầu giảm cửa sổ tắc nghẽn phía phát.

Trong TCP_SACK (Selective Acknowledgement TCP), mỗi gói dữ liệu có chứa một trường tuỳ chọn SACK, trường này gồm một số khối SACK, mỗi khối chứa các thông tin về một khối dữ liệu đã được nhận, nhưng không đúng thứ tự bên nhận chứa trong bộ đệm. Việc bổ sung tuỳ chọn SACK vào TCP không làm thay đổi cơ chế điều khiển tắc nghẽn bên trong của TCP, TCP_SACK vẫn bảo toàn được các đặc tính của Tahoe và Reno TCP trong trường hợp có các gói dữ liệu đến không đúng số thứ tự, nó chỉ sử dụng cơ chế phát lại khi bị hết giờ như giải pháp cuối cùng.

TCP_SACK khác TCP_Reno là khi thực hiện "phục hồi nhanh", nó duy trì một biến được gọi là pipe, biểu diễn ước lượng số gói dữ liệu đã gửi vào mạng nhưng chưa có báo nhận. Trạm gửi chỉ gửi dữ liệu mới hoặc phát lại khi ước lượng nói trên nhỏ hơn cwnd. Biến pipe sẽ tăng một mỗi khi trạm gửi phát đi một gói dữ liệu mới hoặc phát lại một gói dữ liệu cũ, nó được giảm đi một khi trạm gửi nhận một gói ACK lặp với một tuỳ chọn SACK và báo rằng dữ liệu mới đã được nhận đúng tại trạm nhận.

Trong trường hợp một cửa sổ có không quá một gói dữ liệu bị loại, hoạt động của TCP_SACK cũng giống Reno và NewReno. TCP_SACK khác TCP_Reno khi nhiều gói dữ liệu trong một cửa sổ bị loại. TCP_SACK có hiệu năng cao hơn NewReno vì NewReno chỉ có thể phát lại nhiều nhất là một gói dữ liệu bị loại hoặc trong mỗi khoảng thời gian khứ hồi RTT, gây ra sự trễ lớn trong việc phát lại các gói dữ liệu bị loại tiếp theo trong cùng cửa sổ.

3.7.5 TCP Vegas

Trong báo cáo, họ cho rằng TCP Vegas có thể đạt được thông lượng cao hơn từ 37% đến 71% so với TCP Reno trên Internet. Sự phát lại các segments của nó chỉ bằng từ 1/5 đến 1/2 của TCP Reno và cho rằng sự cải tiến thông lượng trên đường truyền là làm sao giảm được các gói tin bị mất và giảm sự phát lại các gói tin. Năm 1995 Ahn và các đồng sự đó kiểm nghiệm TCP Vegas trờn SunOS 4.1.3 và cho chỳng cạnh tranh trờn mạng diện rộng và trờn internet [9]. Họ tuyờn bố TCP Vegas đạt dược thông lượng cao, giảm sự phỏt lại và thời gian trung bỡnh của RTT ngắn hơn TCP Reno, bởi vỡ TCP Vegas giữ dữ liệu ớt trờn mạng. Cựng thời gian đó một số nhà nghiên cứu chú ý sự thực thi của TCP Vegas với hàng đợi RED trên Gateway. Họ báo cáo rằng TCP Vegas sử dụng hàng đợi RED có kết quả tốt hơn hàng đợi Droptail. Trong khoảng thời gian hơn 10 năm trở lại đây có nhiều nghiên cứu về TCP Vegas. Trong các tài liệu của mỡnh, cỏc tỏc giả đều chỉ ra những ưu điểm và các khuyết điểm của TCP Vegas. Khuyết điểm lớn nhất của TCP Vegas là nếu có sự cạnh tranh trên đường truyền giữa TCP Vegas và các phiên bản TCP khác thỡ TCP Vegas tỏ ra kộm cạnh tranh, từ đó họ đưa ra các cải tiến để khắc phục các nhược điểm của nó.

Hiện nay TCP Vegas vẫn chưa được sử dụng rộng rói trờn Internet, vỡ vẫn cũn một số hạn chế nhất định trong việc xác định các tham số ảnh hưởng trong từng thời điểm nhất định, để tăng hiệu quả đường truyền, đây là vấn đề mở mà các nhà nghiên cứu rất quan tâm.

Thuật toán điều khiển của TCP Vegas

í tường then chốt của TCP Vegas là ngăn ngừa các segments bị mất trong quá trỡnh truyền thụng và trỏnh tắc nghẽn mạng. TCP Vegas điều khiển kích thước cửa sổ tắc nghẽn bằng cách theo dừi cỏc RTT (Round Trip Time). RTT là thời gian được tính từ khi một segment được gửi đi từ trạm phát đến trạm nhận, cho đến khi trạm phát nhận được segment hồi đáp ACK, chứa thông tin về segment đó đó được nhận thành công. Nếu thời gian của các RTT được theo dừi tăng, thỡ TCP Vegas nhận biết mạng sắp bị tắc nghẽn và thực hiện cơ chế tránh tắc nghẽn. Nếu thời gian của cỏc RTT giảm thỡ TCP Vegas nhận biết mạng được khai thông và TCP Vegas thực hiện cơ chế tăng kích thước cửa sổ để tận dụng thông lượng của đường truyền. Trong quá trỡnh điều khiển truyền thông, TCP Vegas sử dụng các cơ chế : Cơ chế cửa sổ trượt, cơ chế bắt đầu chậm, tránh tắc nghẽn, phát lại nhanh, phục hồi nhanh và cơ chế điều khiển truyền thông của nó. Cơ chế bắt đầu chậm được TCP Vegas sử dụng khi bắt đầu một kết nối. Cơ chế phát lại nhanh và phục hồi nhanh được thực hiện khi nó nhận được 1 hoặc 3 segments ACK trùng lặp số hiệu. Thuật toán TCP Vegas thực hiện như sau:

Ký hiệu: D: là thời gian RTT được theo dừi d: là giá trị nhỏ nhất của các RTT được theo dừi

 và  là cỏc trị hằng, t và (t+1) là cỏc thời gian thực hiện. Đặt:

Thuật toán điều khiển của TCP Vegas :

Trong pha bắt đầu chậm TCP Vegas ước tính diff và so sánh nó với 1 ngưỡng ó (thường chọn bằng 1) nếu diff

Ảnh hưởng của các tham số trong thuật toán TCP Vegas

TCP Vegas dựa vào sự quan sát các RTT để điều khiển truyền thông. Các tham số như: độ trễ d của đường truyền, độ trễ D của cỏc RTT (D = d + thời gian trễ trên bộ đệm) và việc thiết lập cỏc giỏ trị ỏ, õ. Các tham số trên có ảnh hưởng lớn đến việc điều khiển truyền thông của TCP Vegas trên mạng.

Trong một mạng chỉ dựng TCP Vegas thỡ thụng lượng tăng, khả năng tránh tắc nghẽn tốt, tỷ lệ mất gói tin giảm, nhưng khi mạng có sự tham gia của TCP Reno thỡ khả năng cạnh tranh của nó tỏ ra kém hơn TCP Reno. Dễ thấy điều này qua thuật toán của nó.

Cỏc hằng số ỏ, õ thường được chọn là 1 và 3 (hoặc là 2 và 4). TCP Vegas tăng kích thước cửa sổ lên 1 khi . Tỷ số luôn dương và thường nhỏ hơn 1. Do vậy khi cửa sổ của nó đủ lớn, lưu lượng trên đường truyền cao, độ trễ của các RTT tăng (Do thời gian chờ của các segments trên hàng đợi tăng) thỡ khả năng tăng kích thước cửa sổ rất khó xảy ra vỡ khi đó . Nếu lớn hơn õ TCP Vegas sẽ giảm kích thước cửa sổ xuống 1. Điều này cho thấy TCP Vegas tăng hoặc giảm kích thước cửa sổ linh hoạt, dựa vào sự quan sát độ trễ của các RTT và cách thiết lập trị số cho các hằng ỏ, õ. Trong trường hợp dung lượng đường truyền nhỏ, độ trễ của đường truyền thấp, chiều dài hàng đợi hạn chế, khả năng xử lý tại hàng đợi chậm, khả năng nghẽn mạng có thể xảy ra. Nếu mạng chỉ sử dụng giao thức TCP Vegas thỡ thụng lượng đường truyền được nâng cao rừ rệt nhờ kớch thước cửa sổ luôn được giữ ở mức cao. Rừ ràng TCP ra đời nhằm đáp ứng những hạn chế về tài nguyên phần cứng của mạng.

TCP Reno tăng kích thước cửa sổ cho đến khi phát hiện sự mất các segments, bất chấp RTT có tăng hay không. Với cơ chế như vậy nên khi TCP Vegas tham gia truyền thông cùng với TCP Reno thỡ khả năng chiếm giữ đường truyền và hàng đợi của TCP Reno nhiều hơn. TCP Vegas khó có cơ hội tăng kích thước cửa sổ, do độ trễ trên hàng đợi tăng, trị số của ỏ, õ thiết lập nhỏ, làm số lượng các segments trên mạng của TCP Vegas giảm.

Để tạo sự công bằng và tăng thông lượng trên mạng người ta có thể tăng năng lực phần cứng như: tăng bộ đệm tại các Router và tăng tốc độ xử lý tại cỏc Routers, hoặc cải tiến thuật toỏn của TCP Vegas. Người ta thường cải tiến thuật toán kết hợp với việc cải tiến cách quản lý hàng đợi để giảm bớt segment bị mất và giảm thời gian chi phí cho việc xử lý, hoặc thiết lập giỏ trị cỏc hằng số ỏ, õ một cách phù hợp. Giá trị ban đầu của ỏ, õ ảnh hưởng rất lớn đến sự cạnh tranh của TCP Vegas. Nếu các giá trị này được thiết lập đủ lớn một cách phù hợp, sao cho khi TCP Reno tăng kích thước cửa sổ thỡ TCP Vegas cũng tăng kích thước cửa sổ, cho đến giới hạn của sự cạnh tranh thỡ cú thể làm tăng thông lượng trên đường truyền và tăng sức cạnh tranh của TCP Vegas trên mạng.

Một số nghiên cứu đó chỉ ra cỏc thiếu sút của TCP Vegas. Từ đó đó cú một số cải tiến TCP Vegas nhằm khắc phục cỏc thiếu sút, tăng năng lực cạnh tranh của TCP Vegas và nâng cao chất lượng truyền thông. Các cải tiến của TCP Vegas đều nhằm vào việc cải tiến cách quản lý hàng đợi sao cho có thời gian D là nhỏ nhất trên đường truyền và thiết lập các giá trị ỏ, õ.

3 Ảnh hưởng của tham số ỏ và õ

Trong thuật toán TCP Vegas độ trễ của các RTT được sử dụng để điều khiển truyền thông, tuy nhiên việc thiết lập các giá trị đầu tiên cho ỏ và õ có ảnh hưởng lớn đến việc cạnh tranh của TCP Vegas với TCP Reno trong mạng.Trong các phiên bản cải tiến của TCP Vegas các giá trị ban đầu của ỏ và õ thường được thiết lập là 1 và 3.

Trong trường hợp mạng có thông lượng đường truyền lớn, hàng đợi tại các Router nhỏ, nếu một nguồn TCP Vegas tham gia truyền thông vào lúc đường truyền đó tồn tại cỏc segments của cỏc nguồn khỏc đang tham gia truyền thông thỡ cơ hội để các segment của nguồn này tham gia vào hàng đợi là rất nhỏ. Hơn nữa gía trị của d được lấy là giá trị nhỏ nhất của độ trễ RTT trước đó. Nếu giá trị này được lấy rất nhỏ so với RTT hiện tại thỡ tỷ số rất nhỏ, do vậy hiệu số lớn, có thể lớn hơn õ, do đó Vegas sẽ giảm kích thước cửa sổ trong lúc nó cần phải tăng, để tận dụng thông lượng đường truyền.

Trong trường hợp đường truyền đó đạt mức bóo hũa nếu trị số ỏ, õ được thiết lập quá lớn thỡ nú sẽ tăng kích thước cửa sổ trong lúc nó cần phải giảm để tránh nguy cơ nghẽn mạng.

Khi trong mạng cú sự cạnh tranh giữa TCP Vegas và TCP Reno thỡ giỏ trị ban đầu của ỏ,õ ảnh hưởng rất lớn đến năng lực cạnh tranh của TCP Vegas. TCP Reno tăng kích thước cửa sổ bất chấp độ trễ của RTT có tăng hay không, do vậy tỷ lệ thông lượng trên đường truyền và trong hàng đợi của nó cao hơn so với TCP Vegas. Nếu giá trị ban đầu của ỏ, õ đủ lớn một cỏch phự hợp thỡ TCP Vegas cú thể tăng kích thước cửa sổ trong pha tránh tắc nghẽn để cạnh tranh tốt với TCP Reno.

Từ sự nhận xột trờn qua cỏc mụ hỡnh mạng cú sử dụng TCP Vegas chỳng tụi thiết lập cỏc kịch bản mụ phỏng và tăng các giá trị ỏ và õ cho đến khi thông lượng trên mạng đạt giá trị cao nhất. Các kết quả được ghi nhận và thống kê cho từng trường hợp mô phỏng. Khi tăng ỏ, õ đến 1 giá trị thích hợp không những làm tăng sức cạnh tranh trên mạng của TCP Vegas, mà cũn làm cho thụng lượng trên mạng cũng được tăng lên.