nguyenminhduc.info: Congestion Avoidance and Control

(Bài dịch)

Giới thiệu

Mạng máy tính đã trải qua thời kỳ phát triển bùng nổ trong vài năm gần đây kèm theo đó nhiều vấn đề về tắc nghẽn. Một ví dụ, ta thường thấy cổng mạng hủy 10% gói tin đến vì tràn bộ đệm. Bản điều tra của chúng tôi về các vấn đề này sẽ đưa ra nhiều nguyên nhân nằm trên cách triển khai tầng giao vận (Transport protocol) (chứ không phải chính các giao thức đó). Cách rõ ràng để thực thi một giao thức truyền tải dựa trên cửa sổ (window-based transport protocol) có thể chính xác gây ra phản ứng sai làm tắc nghẽn mạng. Chúng tôi xin đưa ra các ví dụ về phản ứng sai và mô tả một số thuật toán đơn giản để khắc phục tình trạng này. Các thuật toán được bắt nguồn từ ý tưởng đạt được độ tinh cậy của mạng bằng cách buộc cái kết nối ở tầng giao vận tuân theo nguyên tắc 'bảo toàn gói' (packet conservation). Chúng tôi sẽ đưa ra thuật toán xuất phát từ nguyên tắc này và hiệu quả mang lại cho đường truyền trong mạng đang sảy ra tắc nghẽn.

Vào tháng 10 năm 1986, mạng Internet lần đầu tiên trở thành một phần của sự sụp đổ vì tắc nghẽn. Trong thời gian này, Thông lượng từ LBL đến UC Berkeley (các vùng cách nhau 400 thước và 2 hốp IMP) bị rớt từ 32Kbps về 40 bps. Chúng tôi bị mê hoặc bởi hàng ngàn các yếu tố gây nên rớt băng thông và bị thu hút vào một cuộc điều tra về sự việc này. Trong thực tế, chúng tôi băn khoăn nếu 4.3BSD (Berkeley UNIX ) TCP thiếu các phản ứng hoặc nó có thể được điều chỉnh để làm việc tốt hơn trong điều kiện mạng tệ hại. Và câu trả lời đều là "YEAH!"

GETTING TO EQUILIBRIUM: SLOW-START 2

Trong thời gian này, chúng tôi đã triển khai 7 thuật toán vào gói giao thức 4BSD TCP:

(i) round-trip-time variance estimation

(ii) exponential retransmit timer backoff

(iii) slow-start

(iv) more aggressive receiver ack policy

(v) dynamic window sizing on congestion

(vi) Karn’s clamped retransmit backoff

(vii) fast retransmit

Cách tính toán và các bản báo cáo của bước test bản beta cho thấy sản phẩn cuối cùng khá là tốt trong việc xử lý với các điều kiện tắc nghẽn của mạng. Bài bào này là một bản mô tả tóm tắt từ 1-5 và nguồn gốc sau chúng. Thuật toán thứ 6 được phát triển bởi Phil Karn tại Bell Communications Research được mô tả trong mục [16]. Thuật toán thứ 7 sẽ được mô tả sớm trong xuất bản tại RFC.

Thuật toán 1-5 xuất phát từ việc theo dõi: Luồng trên một kết nối (ISO TP-4 hoặc XeroxNS SPP) cần phải tuân theo nguyên tắc 'bảo toàn gói' (packet conservation). Và nếu nguyên tắc được tuân theo, sự sụp đổ do tắc nghẽn sẽ trở thành ngoại lệ hơn là các luật. Thêm nữa, việc điều khiển tắc nghẽn còn bao gồm cả việc tìm kiếm nơi vi phạm việc bảo toàn và sửa chúng. Thuật ngữ 'bảo toàn gói' tương đương với một kết nối cân bằng. Ví dụ như chạy ổn định với trường window cao nhất của gói tin trong việc vận chuyển, lưu lượng của gói thuật ngữ vật lý gọi nó là bảo toàn khi: Một gói mới không được truyền trước khi gói cũ được gửi. Nguyên lý của dòng dữ liệu yêu cầu hệ thống với những thuộc tính trên phải mạnh khi đối mặt với tình trạng tắc nghẽn.

Có 3 khả năng phá vỡ bảo toàn gói:

1. Kết nối không đạt đến trạng thái cân bằng

2. Thiết bị gửi thêm một gói trước khi gói cũ được truyền xong

3. Không thể đạt được trạng thái cân bằng vì giới hạn tài nguyên trên đường truyền.

Trong phần sau đây, chúng tôi sẽ tìm cách xử lý tối ưu tránh những khả năng trên.

Getting to Equilibrium: Slow-start

Lỗi [1] xuất phát từ một kết nối đang bắt đầu hoặc thử kết nối lại sau khi mất một gói tin. Nói cách khác tính bảo toàn là việc thiết bị gửi sử dụng biên nhận ACKs như một chiếc đồng hồ thăm dò để gửi gói tin mới. Kể từ khi thết bị nhận có thể sinh các ACK không nhanh hơn gói tin đi qua mạng, giao thức gọi là ‘tự đếm thời gian' (Hình 1). Hệ thống đồng hồ tự đếm tự động điều chỉnh theo mức tăng giảm băng thông và độ trễ và có một khoảng động rộng (giả sử TCP mở rộng dải từ 800 Mbs kênh Cray đến 1200 bps gói liên kết). Nhưng điều tương tự làm hệ thống tự đếm thời gian ổn định khi nó chạy từ từ - để nhận dữ liệu phải có biên nhận để đếm thời gian các gói nhưng để nhận được biên nhận ACK thì phải có dòng dữ liệu.

Sender: Thiết bị gửi
Receiver: Thiết bị nhận
Pb: biểu thị khoảng cách nhỏ nhất của gói trong phần liên kết chậm nhất của đường mạng (nút thắt cổ chai).
Pr: khoảng cách giữa các gói của mạng bên nhận
As: khoảng cách ACK của mạng thiết bị gửi As = Pb
Ab:
Ar: khoảng cách giữa gói ACK tại thiết bị nhận là Ar=Pr=Pb

Đây là cơ chế mô tả của thiết bị gửi/nhận trong một mạng băng thông rộng kết nối với một mạng chậm hơn, mạng đường dài. Thiết bị gửi chỉ bắt đầu và đã truyền đi một gói chứa trường window, liên tiếp nhau. Gói ACK biên nhận cho đợt gửi đầu tiên được gửi trở lại thiết bị gửi (Ký hiệu bằng đường thẳng đứng ở ống to bên trái phía dưới). Chiều dọc là băng thông, chiều ngang là thời gian. Mỗi một khối đen là một gói. Bandwidth_Time = Bits nên kích thước khối đen tương đương với độ lớn của gói. Số bits không thay đổi đóng vai trò như gói tin đi qua mạng do đó gói tin bị nén thành các đường chiếm băng thông trải dài theo trục thời gian. Thời gian Pb biểu thị khoảng cách nhỏ nhất của gói trong phần liên kết chậm nhất của đường mạng (nút thắt cổ chai). Khi gói tin đi ra khỏi nút thắt, khoảng cách các gói tin không thay đổi bởi vậy khoảng cách giữa các gói của mạng bên nhận Pr = Pb. Nếu thời gian xử lý của thiết bị nhận bằng nhau đối với tất cả các gói tin, thì khoảng cách giữa gói ACK tại thiết bị nhận là Ar=Pr=Pb. Nếu các khe thời gian Pb lớn vừa đủ cho một gói, nó sẽ đủ lớn cho gói ACK bởi vậy khoảng cách giữa các gói ACK được bảo toàn xuốt đường trở về. Vì thế nên khoảng cách ACK của mạng thiết bị gửi As = Pb. Vậy, Nếu gói tin sau đợt gửi đầu tiên chỉ được gửi khi nhận gói tin ACK, khoảng cách gói tin của thiết bị gửi sẽ bằng chính xác thời gian gói tin tại liên kết chậm nhất của đường mạng.

Để bắt đầu đếm, chúng tôi đã phát triển thuật toán slow-start để dần dần tăng lượng dữ liệu truyền đi[2]. Mặc dù chúng tôi hy vọng bằng việc thiết kế như vậy giải thuật sẽ tinh vi hơn, nhưng việc triển khai thì thật đơn giản - Một biến trạng thái mới và 3 dòng code trong thiết bị gửi.

[1] Một luồng cân bằng có nghĩa là bất kỳ thời điểm nào, Tích phân của mật độ gói tin xung quanh vòng gửi/nhận/gửi là một hằng số. Từ khi các gói tin truyền quanh vòng lặp này, Tích phân tiếp tục đủ để thành lập hàm Lyapunov của hệ thống. Một hàm hằng số không đáng kể phù hợp với điều kiện ổn định của Lyapunov vì vậy hệ thống đạt trạng thái ổn định và bất kỳ sự chồng chất hệ thống nào đều ổn định. (Xem [3], Chương 11-12 hoặc [21], Chương 9 về định lý hệ thống ổn định)

[2] Slow-start hơi giống với giải thuật CUTE trong [14]. Thời điểm nghĩ ra thuật toán này chúng tôi không hay biết gì về CUTE nhưng sau đó thì có biết - CUTE được đưa ra trước vài tháng. Khi mô tả thuật toán của chúng tôi vào tháng 1 - 1987, tại cuộc họp tại IETF, chúng tôi gọi nó là soft-start. Cái tên slow-start được đề nghị bởi John Nagle trong một thông điệp gửi đến IETF vào tháng 3 - 1987. Cái tên tỏ ra khá rõ ràng và chúng tôi đặt theo nó.

nguyenminhduc.info

Thứ Sáu, 12 tháng 4, 2013

Congestion Avoidance and Control - V. Jacobson

(Bài dịch)

Không có nhận xét nào:

Đăng nhận xét