Xem mẫu
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Khảo sát giải thuật điều khiển tắc nghẽn cho luồng
TCP
Nguyễn Xuân Khánh
Khoa Viễn Thông II,
Học Viện Công Nghệ Bưu Chính Viễn Thông
Email: xuankhanh@ptithcm.edu.vn
Abstract— TCP (Transmisssion Control Protocol) mang hầu hết lưu trữ gói truyền tại hàng đợi đầu ra của router tạm thời có
các lưu lượng trên Internet, vì thế hiệu năng của Internet phụ thể bị tràn và gây ra tình trạng mất gói (mất segment TCP).
thuộc rất lớn vào TCP thực hiện như thế nào khi truyển qua Mặc dù, một nguyên nhân khác gây ra hiện tượng mất gói
Internet, nhất là hiệu quả của giải thuật điều khiển tắc nghẽn mà cũng có thể do lỗi sai truyền dẫn nhưng hiện nay lý do chính
TCP sử dụng. Bài báo này khào sát một số giải thuật điều khiển
là vẫn do tình trạng tắc nghẽn trên mạng (hiện nay mạng sử
tắc nghẽn thông dụng dùng trong các hệ điều hành window và
Linux như TCP-Tahoe, TCP-Reno, TCP-NewReno, BIC-TCP và dụng phương tiện truyền dẫn quang rộng rãi nên lỗi truyển dẫn
CUBIC. Trong từng giải pháp, các cơ chế điều khiển cửa sổ tắc thấp).
nghẽn sử dụng các hàm khác nhau được phân tích và so sánh Luồng TCP qua mạng Internet thường đi qua nhiều đường
dựa vào mức độ tận dụng tài nguyên mạng của từng giải pháp.
truyền, liên kết có tốc độ khác nhau. Do đó, tốc độ truyền
Keywords- TCP, Điều khển tắc nghẽn, giải thuật tránh tắc segment trên toàn bộ tuyến được xác định bởi liên kết có tốc
nghẽn, Khởi động chậm . độ thấp nhất. Tắc nghẽn có thể xảy ra ở phía phát của liên kết
này (hàng đợi đầu ra) khi có nhiều segment trong nhiều kết nối
I. GIỚI THIỆU TCP đồng hiện hành cùng tới với tốc độ nhanh hơn tốc độ
Các giải thuật điều khiển tránh tắc nghẽn trong TCP nhằm truyển trên liên kết này. Trong tình huống này, số lượng gói
giải quyết vấn đề sử dụng tài nguyên mạng một cách hiệu quả, trong hàng đợi đầu ra này tăng dần lên cho đến khi bộ đệm
công bằng và giảm thiểu sự mất gói xảy ra. Mỗi kết nối TCP sẽ đầy và xảy ra hiện tượng gói bị loại bỏ. Điều này cũng ảnh
phản ứng với hiện tượng này bằng cách điều chỉnh tải đưa vào hưởng đến các ACK liên quan đến những gói đã mất và như
mạng sao cho vẫn đảm bảo được ở một mức độ hợp lý chất vậy nó có một ảnh hưởng đáng kể đến tổng thời gian truyền
lượng kết nối TCP, giảm thiểu mức độ tắc nghẽn xảy ra trên một bản tin.
mạng và ảnh hưởng của nó. Bên cạnh đó, các giải thuật này Để giảm khả năng xảy ra mất segment, mỗi host TCP phát có
còn đảm bảo sự công bằng trong việc sử dụng tài nguyên mạng một thủ tục điều khiển tắc nghẽn cho mỗi kết nối TCP, thủ tục
giữa các kết nối. Tuy nhiên trong bài báo này chỉ đề cập đến này sử dụng tốc độ đến của các ACK trong một kết nối để ổn
góc độ điều chỉnh mức độ phát của bên phát thông qua điều định tốc độ đưa segment vào Internet. Bên cạnh thủ tục điều
chỉnh cửa sổ tắc nghẽn khiển lưu lượng dùng cửa sổ trượt, mỗi kết nối TCP cũng có
một biến cửa sổ tắc nghẽn Wc kết hợp với thủ tục điều khiển
Phần còn lại của bài báo được tổ chức như sau: trong phần tắc nghẽn này. Mỗi kết nối đều phải duy trì cả 2 biến này và
II, miêu tả về các hoạt động cơ bản trong điều khển tắc nghẽn. chỉ có thể thực hiện truyền một segment trong kết nối khi cả 2
Phần III, IV và V giới thiệu các giải pháp TAHOE, RENO, cửa số này đều trong trạng thái mở (con hạn mức truyền).
NEWRENO. Phần VI và VI giới thiệu các giải thuật cho mạng
tộc độ cao và độ trễ lớn BIC-TCP và CUBIC. Phần VIII cung Như trên đã trình bày, thủ tục điều khiển tắc nghẽn có tác
cấp các kết quả mô phỏng và phân tích lý thuyết. Cuối cùng, là dụng khi xảy ra trường hợp mạng nặng tải và trạng thái luồng
kết luận bài báo trong phần IX. segment được điều khiển chính bởi cửa sổ tắc nghẽn Wc. Còn
trong trường hợp mạng có tải nhẹ thì nó được điều khiển chính
II. ĐIỀU KHIỂN TẮC NGHẼN TRONG TCP bởi cửa sổ phát Ws. Tuy nhiên, một kết nối TCP khi bắt đầu
Cơ chế điều khiển lưu lượng của TCP nhằm tránh hiện tượng truyền do chưa nhận các ACK nên TCP phát không biết được
quá tải/tắc nghẽn ở phía TCP nhận khi tốc độ TCP phát cao mức độ tải hiện hành của mạng. Nên để ngăn tránh việc truyền
hơn tốc độ xử lý ở TCP nhận. Tuy nhiên, nó không giải quyết một khối lượng lớn các segment (lên đến kích thước cửa sổ
được tình trạng tắc nghẽn trên đường truyển khi luồng TCP Ws cực đại đã thỏa thuận giữa 2 đầu phát và nhận) thì kích
được truyền qua mạng (ví dụ Internet). Hiện tượng tắc nghẽn thước của sổ tắc nghẽn Wc được thiết lập ban đầu là 1
trên mạng gây ra do một router hay một gateway trên con segment. Do kích thước Wc tính theo đơn vị byte nên giá trị
đường đi của luồng TCP bị tắc nghẽn trong khoản thời gian tải ban đầu này sẽ bằng với kích thước segment lớn nhất MSS
nặng. Trong khoản thời gian tắc nghẽn này, các bộ đệm dùng (Maximum Segment Size) đã được thỏa thuận giữa 2 đầu thu
phát của kết nối TCP vào lúc thiết lập kết nối.
ISBN: 978-604-67-0635-9 51
51
- HộiHội
Thảo Quốc
Thảo GiaGia
Quốc 2015
2015vềvềĐiện
ĐiệnTử,
Tử,Truyền
TruyềnThông và Công
Thông và CôngNghệ
NghệThông
ThôngTinTin (ECIT
(ECIT 2015)
2015)
Thủ tục điều khiển cửa sổ tắc nghẽn thực hiện khi TCP phát Trong trường hợp mạng có tải nhẹ - có nghĩa là không có liên
bắt đầu pha truyền dữ liệu của một kết nối bằng cách gởi một kết nào trên con đường qua mạng bị tắc nghẽn - thì luồng
segment với kích thước MSS. Sau đó nó khởi tạo một bộ định segment trên kết nối được điều khiển chính bởi Ws miễn sao
thời phát lại RTO (Retransmission TimeOut) cho segment này Wc luôn lớn hơn Ws cực đại. Trong trạng thái này tất cả các
và chờ nhận ACK cho segment này. Nếu thời gian định thời segment được truyền với một độ biến động trễ và độ trễ tương
phát lại hết hạn thì nó sẽ phát lại segment này. Nếu nó nhận đối là hằng số. Tuy nhiên, khi số lượng kết nối trên mạng tăng
được ACK trước thời hạn này thì Wc được tăng lên 2 segment dẫn đến mức độ lưu lượng tăng đến một mức bắt đầu xảy ra
với kích thước mỗi segment là MSS. TCP phát sau đó có thể mất gói thì thủ tục điều khiển tránh tắc nghẽn trên mỗi kết nối
phát 2 segment và mỗi ACK nhận được cho các segment này sẽ bắt đầu điều chỉnh cửa sổ Wc của kết nối sao cho phản ánh
Wc được tăng lên 1 segment (MSS byte). Do đó, TCP phát được mức độ tắc nghẽn.
bây giờ có thể phát 4 segment và cứ tiếp tục như thế Wc sẽ
Khi xảy ra mất gói thủ tục điểu khiển tắc nghẽn ở TCP phát sẽ
tăng theo qui luật hàm mũ. Mặc dù, Wc tăng nhanh như vậy,
phản ứng lại bằng cách điều chỉnh Wc (giảm Wc) tùy vào
nhưng pha này vẫn được gọi là khởi đầu chậm (slow start) vì
trường hợp cụ thể phát hiện ra sự mất gói do nhận được các
nó được tăng từ 1 segment. Việc tăng này được tiếp tục cho
ACK nhân bản hay hết thời hạn của bộ định thời phát lại
đến khi có một sự hết hạn thời gian phát lại của một segment
bị mất, hoặc TCP phát nhận được một ACK nhân bản (nhiều Trường hợp thứ nhất : phát hiện ra mất gói khi nhận được các
ACK giống nhau xác nhận cho cùng một segment), hoặc đạt ACK nhân bản. Việc nhận được ACK nhân bản cho thấy ở
đến mức cao hơn mức ngưỡng SST (Slow Start Threshold). host đích vẫn nhận được các segment. Do đó mức độ tắc
Với mỗi kết nối TCP, SST được thiết lập 64 kbyte. Tuy nghẽn có thể được giả định là nhẹ và vào lúc nhận được ACK
nhiên, trong ví dụ hình 1 giá trị này được giả định ban đầu là nhân bản thứ 3 liên quan đến segment bị mất (thủ tục fast
32 kbyte và nếu MSS là 1 kbyte thì nó bằng với 32 segment. retransmit) thì kích thước của Wc sẽ được giảm phân nữa và
a)
Wc thủ tục tránh tắc nghẽn được thực hiện bắt đầu từ giá trị này.
3 nhân bản
(segment/kbyte)
ACK đầu tiên Thủ tục này được gọi là khôi phục nhanh (fast recovery).
Trong ví dụ trong hình 1 (a) , vào lúc nhận ACK nhân bản thứ
64
3, segment bị mất được phát lại và Wc được thiết lập lại bằng
phân nữa - 32 kbyte - giá trị hiện hành (64 kbyte). Sau đó Wc
được tăng trở lại theo như thủ tục tránh tắc nghẽn. Tuy nhiên,
3 nhân bản
ACK thứ 2
Wc =
khi đạt đến 34 segment (34 kbyte) một segment thứ 2 bị mất
SST= 32
32 34 (giả sử do nhận được ACK nhân bản ACK thứ 3 lần 2) làm
cho Wc lại bị thiết lập lại phân nữa là 17 segment và thủ tục
16 SST= 17 tránh tắc nghẽn lại khởi động lại. Lần này ở giá trị Wc=17
8
segment.
4
2
5 10 20 30 37 40 50
RTT
Trường hợp thứ hai : mất gói được nhận ra do quá hạn bộ định
b) thời phát lại RTO. trong trường hợp này được giả định là mức
Wc
(segment/kbyte)
độ tắc nghẽn xảy ra đến nổi không có segment nào thuộc kết
RTO đầu tiên
nối có thể đi qua mạng. Như ví dụ trong hình 1(b), khi bộ định
64
thời phát lại hết hạn (RTO), Wc được thiết lập lại 1 segment
RTO thứ 2
bất chấp giá trị hiện hành của nó là bao nhiêu và thủ tục slow
start được khởi động lại. Như vậy, khi mức độ tắc nghẽn đạt
đến mức làm quá hạn bộ định thời phát lại thì luồng segment
32 SST= 32
được điều khiển chính bằng Wc
RTO thứ 3
16
8 III. GIẢI PHÁP TCP-TAHOE
4
2
5 10 20 30 40 50
RTT
Hình 1. Điều chỉnh cửa sổ tắc nghẽn : a) Vào lúc nhận các TCP Tahoe là một trong những giải pháp điều khiển tắc nghẽn
ACK nhân bản ; b) Vào lúc hết hạn bộ định thời phát lại RTO trong TCP có sớm nhất do V. Jacobson đề xuất [3]. Giải pháp
này dựa trên đặc tả RFC 793 (TCP chuẩn) và bao gồm một số
Giả sử Wc đạt đến SST cho thấy đường truyền không bị tắc giải thuật được chia thành 3 nhóm : Khắc phục vấn đề ước
nghẽn và do đó thủ tục sẽ bước vào giai đoạn 2. Trong giai lượng thời hạn phát lại (RTO), Tăng cường nhận diện sự mất
đoạn 2 thay vì Wc tăng 1 segment, thì nó chỉ tăng 1/Wc gói nhanh hơn và Các giải thuật tránh tắc nghẽn (CA-
segment cho mỗi ACK nhận được. Như vậy, giai đoạn này Congestion Avoidance) và khởi động chậm (SS-Slow Start).
Wc sẽ tăng 1 segment khi nhận được một tập Wc ACK. Pha
này được gọi là pha tránh tắc nghẽn và trong pha này việc tăng Cải tiến đầu tiên : Nếu giá trị RTO được ước lượng quá cao thì
Wc mang tính cộng. Giai đoạn này tiếp tục cho đến khi Wc viện nhận ra sự mất gói sẽ quá bảo toàn và hiệu suất của các
đạt được đến một mức ngưỡng thứ 2 – trong ví dụ này là 64 luồng TCP riêng biệt có thể suy giảm nghiêm trọng. Trong
kbyte – thì Wc sẽ được duy trì không đổi ở giá trị này. trường hợp ngược lại, khi giá trị RTO được ước lượng không
52
52
- HộiHội
Thảo Quốc
Thảo QuốcGia
Gia2015
2015về
vềĐiện
Điện Tử,
Tử, Truyền
Truyền Thông vàCông
Thông và CôngNghệ
Nghệ Thông
Thông Tin Tin (ECIT
(ECIT 2015)
2015)
đúng mức thì cơ chế phát hiện lỗi có thể gây ra tình trạng phát không đáng kể (
- HộiHội
Thảo Quốc
Thảo Gia
Quốc 2015
Gia 2015về
vềĐiện
ĐiệnTử,
Tử,Truyền
TruyềnThông và Công
Thông và CôngNghệ
NghệThông
ThôngTinTin (ECIT
(ECIT 2015)
2015)
b trong hình 3), hiệu suất của giải thuật SS trong một khoản Nhận ra mất gói
thời gian dài rất thấp. Giới hạn mạng
Cửa sổ tắc nghẽn
Giải thuật thứ hai trong nhóm này là tránh tắc nghẽn CA. Mục
đích của giải thuật này nhằm cải tiến hiệu suất của TCP trong
trường hợp tài nguyên mạng giới hạn, có khả năng xảy ra hiện
tượng cổ trai truyền dẫn. So với giải thuật khởi động chậm thì
giải thuật này dè dặt nhiều hơn trong đáp ứng cho những gói
ACK nhận được và với việc nhận ra mất gói. Nếu tất cả các
gói đã được giao thành công trong khoản thời gian RTT thì Thời gian
SS SS CA SS
thay vì nhân đôi cửa sổ tắc nghẽn như trong giai đoạn SS thì
giải thuật CA chỉ tăng 1 (tăng cộng). Và khi có sự mất gói xảy
ra, thay vì khởi động lại với kích thước 1 gói thì cửa sổ tắc Hình 5. Biến động cửa sổ tắc nghẽn của tổ hợp 2 giải thuật SS
nghẽn chỉ đơn giản giảm phân nữa so với kích thước hiện và CA
hành (ngay trước khi sự mất gói xảy ra). Theo phân tích của
Jacobson [3] để đạt được mạng không có tắc nghẽn thì việc IV. GIẢI PHÁP TCP RENO
giảm phân nữa cửa sổ tắc nghẽn bởi các luồng riêng biệt là đủ. Trong TCP Tahoe, việc giảm cửa sổ tắc nghẽn về 1 khi có sự
Cách giảm có tính nhân này giống như hành vi hàm mũ khi mất gói xảy ra là một việc khá hà khắc và trong một vài
nhiều gói liên tiếp bị mất (trạng thái tắc nghẽn kéo dài). Theo trường hợp có thể dẫn đến sự suy giảm độ thông xuất nghiêm
như trong hình 4, Giải thuật CA này đúng là có hiệu quả trong trọng. Ví dụ, với tỉ lệ mất gói 1% có thể gây ra sự suy giảm
thời gian dài nhưng bù lại thì thời gian tìm ra tài nguyên mạng đến 75% độ thông xuất của một luồng TCP chạy giải thuật
của nó lại chậm do tốc độ tăng kích thước cửa sổ của nó mang Tahoe [4]. Để giải quyết vấn đề này, Jacobson đã đưa ra khái
tính dè dặt. niệm về sự khác biệt giữa những sự kiện tắc nghẽn nhẹ và tắc
nghẽn nghiêm trọng và đồng thời đã hiệu chỉnh lại các giải
thuật khởi động chậm và tránh tắc nghẽn.
Nhận ra mất gói
Cửa sổ tắc nghẽn
Sự nhận ra mất gói thông qua thời hạn phát lại RTO cho thấy
Giới hạn mạng
trong một khoản thời gian nhất định (ví dụ RTO-RTT) một sự
kiện tắc nghẽn nghiêm trọng nào đó đã ngăn cản việc truyền
bất kỳ gói nào trên mạng. Vì vậy, bên phát TCP sẽ áp dụng
chính sách bảo toàn thiết lập lại cửa sổ tắc nghẽn tới một giá
trị tối thiểu.
Một cách khác có thể nhận ra mất gói bằng các ACK nhân
Thời gian bản. Giả sử bên phát TCP nhận được 4 ACK, ACK đầu tiên
xác nhận cho gói dữ liệu mới nào đó, 3 ACK còn lại là các bản
copy chính xác của ACK đầu tiên. Các ACK nhân bản cho
Hình 4. Biến động cửa sổ tắc nghẽn và hiệu quả của giải thuật
thấy những gói nào đó đã bị lỗi. Tuy nhiên, sự hiện diện của
tránh tắc nghẽn CA
mỗi gói ACK (bao gồm ACK nhân bản) cho biết một gói dữ
liệu đã đến đích thành công. Hơn nữa, phía phát bên cạnh việc
Giải thuật TCP Tahoe gồm cả 2 giải thuật SS và CA hoạt động
nhận ra mất gói nó cũng quan sát khả năng của mạng trong
riêng biệt. Nó tổ hợp cả khám phá nhanh tài nguyên mạng
việc phân phối dữ liệu. Như vậy, trong trường hợp này trạng
(SS) và hiệu suất dài hạn (CA). Để chuyển giữa 2 pha giải
thái của mạng có thể được xem là bị tắc nghẽn nhẹ, và phản
thuật này, một mức ngưỡng ssthresh được định nghĩa. Mức
ứng với sự kiện mất gói có thể lạc quan hơn. Trong TCP
ngưỡng này xác định kích thước cực đại của cửa sổ tắc nghẽn
Reno, phản ứng lạc quan này là sử dụng giải thuật khôi phục
trong pha khởi động chậm SS, và nếu có bất kỳ sự mất gói xảy
nhanh FR (Fast Recovery).
ra thì ssthreh được điều chỉnh về phân nữa kích thước cửa sổ
tắc nghẽn hiện hành. Khi nằm trong giai đoạn của giải thuật
Ý định của FR là giảm phân nữa cửa sổ tắc nghẽn và thực hiện
SS và có một sự mất gói được nhận biết thì bản thân cửa sổ
thăm dò tài nguyên mạng cho đến khi lỗi được khắc phục. Hay
luôn thiết lập lại ở giá trị tối thiểu (=1). Ngay khi giá trị cửa sổ
nói một cách khác, bên phát nằm trong trạng thái khôi phục
tắc nghẽn thấp hơn ssthreh, pha SS được thực hiện. Khi cửa sổ
nhanh cho đến khi nó nhận được gói ACK không nhân bản.
lớn hơn mức ngưỡng này, giải thật CA được sử dụng. Đây là
Các giai đoạn của giải thuật được minh họa trong hình 6. Các
gọi là chu trình SS-CA (hình 5)
kích thước cửa sổ tắc nghẽn trong các trạng thái khác nhau
được biểu thị bởi các đoạn bên trên các đường trạng thái, và
các mũi tên biểu thị kích thước cửa sổ hiệu lực hay số lượng
gói đang được chuyển tiếp.
54
54
- HộiHội
Thảo Quốc
Thảo QuốcGia
Gia2015
2015về
vềĐiện
Điện Tử,
Tử,Truyền
Truyền Thông vàCông
Thông và CôngNghệ
Nghệ Thông
Thông TinTin (ECIT
(ECIT 2015)
2015)
Sự chuyển từ trạng thái 1 sang trạng thái 2 biểu thị sự giảm Kết quả những biến động cửa sổ tắc nghẽn lý thuyết của TCP
việc sử dụng tài nguên mạng dùng chính sách giảm gấp bội. Reno biểu diễn trong hình 7. So với nững biến động của TCP
Sau khi giảm phân nữa (Wc/2), giải thuật không chỉ phát lại Tahoe, bằng cách thay các giai đoạn khởi động chậm SS sau
gói dữ liệu chưa được xác nhận cũ nhất mà còn’thổi phồng’ mỗi sự kiện mất gói bằng các giai đoạn phát lại nhanh FR
cửa sổ theo số lượng gói ACK nhân bản (trang thái 2 sang ngắn hơn, TCP Reno đạt hiệu quả trong trạng thái ổn định cải
trạng thái 3). Như chúng ta đã biết, một ACK sẽ chỉ thị ít nhất thiện đáng kể.
một gói dữ liệu đã được giao thành công. Như vậy, nếu chúng
ta muốn duy trì một số lượng gói không đổi đang được chuyển Thực ra, Việc khôi phục từ một sự mất gói đơn sẽ luôn hoàn
tiếp, chúng ta phải thổi phồng cửa sổ tắc nghẽn để mở một vị thành trong một RTT. Tuy nhiên, hiệu suất được cải thiện
trí gởi dữ liệu mới (trạng thái 4). Nếu không có sự tăng này thì không chỉ bởi rút ngắn giai đoạn khôi phục, mà còn bởi việc
các gói dữ liệu mới không thể được gởi trước khi lỗi được cho phép truyền dữ liệu trong giai đoạn khôi phục
khắc phục, và số lượng gói đang được chuyển tiếp có thể giảm
nhiều hơn mong đợi. V. GIẢI PHÁP TCP NEWRENO
Dữ liệu đã Dữ liệu đã phát chờ Dữ liệu được Một trong những điểm yếu của giải thuật FR trong TCP Reno
được ACK ACK đệm chờ phát
sẽ bộc lộ khi nhiều gói mất xảy ra trong một sự kiện tắc nghẽn
Wc
Ngay trước khi đơn lẽ. Điều này làm giảm đáng kể hiệu năng của TCP Reno
Trạng thái 1 nhận ra mất gói
trong những môi trường tải nặng. Khi một một sự kiện tắc
Wc/2 Ngay sau khi nghẽn đơn lẽ (đột biến lưu lượng trong một khoản thời gian
nhận ra mất gói
Trạng thái 2 ngắn) gây ra mất nhiều gói dữ liệu. Phản ứng giảm phân nữa
Wc/2+#dup Wc “phình ra” theo số lượng cửa số tắc nghẽn của FR đột nhiên chuyển thành một sự giảm
Trạng thái 3
ACK nhân bản nhận được
cửa cổ tắc nghẽn theo quy luật hàm mũ mang tính thận trọng.
Wc/2+#dup
Các ACK nhân bản có thêm Sự mất gói đầu tiên gây ra giải thuật bắt đầu vào giai đoạn
Trạng thái 4 làm Wc “phình ra” thêm khôi phục và giảm phân nữa cửa sổ tắc nghẽn. sau đó nếu
Wc/2 nhận được một ACK không nhân bản thì giải thuật sẽ kết thúc
Trạng thái 5
Sau khi khôi phục thành công qua trình khôi phục. Tuy nhiên, các sự mất tiếp theo sẽ gây ra
cửa sổ tắc nghẽn tiếp tục giảm thêm nữa theo cùng một cơ chế
Dữ liệu tồn đọng không được phép phát lại vào và thoát trạng thái khôi phục như trường hợp mất gói đầu
Số lượng dữ liệu mới được phép gởi đi do tiên trong chuỗi mất gói này.
cửa sổ tắc nghẽn “xã hơi”
Số lượng dữ liệu tới đầu nhận thành công,
suy ra từ các ACK nhân bản nhận được
Kích thước cửa sổ tắc
nghẽn là tổng của 2 thành
Theo một ý nghĩa nào đó, việc phản ứng theo quy luật hàm mũ
Số lượng gói đang chuyển tiếp phần này này đối với nhiều sự mất gói là mong muốn của các giải thuật
tránh tắc nghẽn với mục đích giảm sự tiêu thụ tài nguyên
Hình 6. Các trạng thái tiêu biểu của FR mạng trong những tình trạng tắc nghẽn nghiêm trọng. Nhưng
sự mong muốn này dựa trên giả định các trạng thái tắc nghẽn
Trong trạng thái cuối cùng (trạng thái 5), khi một gói ACK độc lập nhau và trong ví dụ trên thì điều này không đúng. Có
không nhân bản được nhận, chúng ta muốn khôi phục lại hoạt khả năng cao tất cả sự mất gói trong nhóm dữ liệu ban đầu
động tránh tắc nghẽn với phân nữa cửa sổ tắc nghẽn ban đầu. (những gói dữ liệu còn tồn đọng vào lúc xảy ra sự mất gói)
Với xác suất cao, các ACK không nhân bản này sẽ xác nhận được gây ra bởi cùng một sự kiện mất gói đơn lẽ. Như vậy,
việc giao thành công tất cả các gói dữ liệu tồn đọng suy luận các sự mất gói thứ hai, thứ ba trong ví dụ trên nên được xử lý
từ các ACK nhân bản nhận được trước đây. Ở thời điểm này, như là một yêu cầu phát lại dữ liệu chứ không phải như là
việc giảm cửa số tắc nghẽn tới Wc/2 (giá trị ngay trước khi những chỉ báo tắc nghẽn. Hơn nữa, việc giảm cửa sổ tắc nghẽn
vào giai đoạn khối phục -trang thái 2) là một cách thức tin cậy không đảm bảo sẽ giải phóng tài nguyên mạng ngay tức thời
và đơn giản để đảm bảo mục tiêu thoát trạng thái khôi phục do tất cả gói dữ liệu được phát trước khi giảm cửa sổ vẫn đang
nhanh FR. được chuyển tiếp. Vì vậy, trước khi kích thước cửa sổ tắc
nghẽn mới có hiệu lực, ta không nên áp dụng thêm bất kỳ
Nhận ra mất gói
chiến lược giảm nào nữa. Điều này có thể hiểu là việc giảm
cửa sổ tắc nghẽn không nên thường xuyên hơn một lần trong
Cửa sổ tắc nghẽn
Giới hạn mạng
khoản thời gian độ trễ lan truyền một chiều hay xấp xỉ RTT/2.
ssthresh Floyd et al. [7] đưa ra một sự cải tiến đơn giản giải thuật khôi
phục nhanh FR. Sự cải tiến này nhằm giải quyết sự không
tường minh của các sự kiện tắc nghẽn bằng cách trì hoãn việc
thoát khỏi giai đoạn khôi phục cho tới khi tất cả các gói dữ
Thời gian
SS FR CA liệu trong giới hạn cửa sổ tắc nghẽn ban đầu (ngay khi tắc
nghẽn xảy ra) được xác nhận. Giải thuật NewReno bổ sung
Hình 7. Những biến động cửa sổ tắc nghẽn của TCP Reno thêm một biến trạng thái đặc biệt để nhớ số thứ tự của gói dữ
55
55
- HộiHội
Thảo Quốc
Thảo QuốcGia
Gia2015
2015về
vềĐiện
Điện Tử,
Tử,Truyền
Truyền Thông vàCông
Thông và CôngNghệ
Nghệ Thông
Thông TinTin (ECIT
(ECIT 2015)
2015)
liệu sau cùng được gởi đi trước khi vào trạng thái khôi phục BIC-TCP (Binary Increase Congestion Control – TCP) mở
nhanh FR. Giá trị này giúp phân biệt giữa ACK nội bộ (ACK rộng NewReno thêm một một giai đoạn hội tụ nhanh RC
cho các gói tồn đọng) và ACK cho dữ liệu mới. Việc nhận (Rapid Convergence). Trong giai đoạn này, BIC-TCP sử dụng
được một ACK cho gói dữ liệu mới có nghĩa là tất cả các gói cách thức tìm kiếm nhị phân để khám phá nhanh kích thước
được gởi trước khi nhận ra lỗi đã được giao thành công và bất cửa sổ tắc nghẽn tối ưu (giá trị tương ứng với tài nguyên mạng
kỳ một sự mất gói mới nào sẽ chỉ báo một sự kiện tắc nghẽn khả dụng) bằng cách xem sự nhận biết mất gói như là một chỉ
mới. Một ACK nội bộ xác nhận sự khôi phục từ chỉ một lỗi sai báo cửa sổ tắc nghẽn có kích thước qua mức.
đầu tiên và chỉ báo thêm nhiều sự mất gói trong bó gói đầu
tiên.
Wmax
Cửa sổ tắc nghẽn
Dữ liệu đã Dữ liệu đã phát chờ Dữ liệu được
được ACK ACK đệm chờ phát
XX
Wc
Ngay trước khi
Trạng thái 1 nhận ra mất gói Giới hạn mạng
Wc/2 Ngay sau khi Wmin
Trạng thái 2 nhận ra mất gói
#dup+Wc/2 Phát lại gói mất . Mỗi ACK
nhân bản ‘thổi phồng’ Wc
Trạng thái 3
Thời gian
#dup+Wc/2-ACK ACK nội bộ làm giàm cwnd,
các gói trước khi nhận
Trạng thái 4
Hình 9. Tìm kiếm nhị phân để đạt kích thước cửa sổ tối ưu.
#dup+Wc/2-ACK Phát lại gói bị mất ( ). Wc vẫn
duy trì không đổi
Trạng thái 5
Trong khi mạng giao các gói dữ liệu thành công (bên phát
#dup+Wc/2-ACK
Các ACK nhân bản chỉ làm
nhận được ACK trong khoảng RTT) cửa sổ tắc nghẽn được
Trạng thái 6 Wc “phình ra” thêm cập nhật đến điểm giữa (giá trị trung bình) trong dãy tìm kiếm
Wc/2 giữa kích thước cửa sổ tối thiểu Wmin (không có sự mất gói
Thoát trạng thài khôi phục và làm
Trạng thái 7 giảm Wc khi nhận được trong khoản RTT) và kích thước cửa sổ cực đại Wmax (giá trị
có sự mất gói xảy ra). Khi có một chỉ báo giao dữ liệu thành
X Mất gói do sự kiện tắc nghẽn thấp công (nhận được ACK không nhân bản) thì Wmin được tăng
Nhận ra mất gói (3 ACK nhân bản) lên giá trị cửa sổ trước đó (gía trị cửa sổ khi mạng không có
Phát lại gói tắc nghẽn). Sau khi cửa sổ tăng đến điểm giữa, nếu mạng
ACK không nhân bản
không có mất gói xảy ra thì có nghĩa rằng mạng có thể xử lý
nhiều lưu lượng hơn và như vậy có thể thiết lập điểm giữa là
Số lượng dữ liệu tới đầu nhận thành công,
biết được từ các ACK nhân bản nhận được
Kích thước cửa sổ tắc
nghẽn là tổng của 2 thành
một giá trị Wmin mới. và thực hiện một sự tìm kiếm khác với
Số lượng gói đang chuyển tiếp phần này giá trị Wmin và Wmax mới. Ngay khi nhận ra mất gói ( ví dụ
nhận được 3 ACK nhân bản) thì Wmax được thiết lập bằng gía
trị cửa sổ hiện hành (giá trị khi mạng có tắc nghẽn) và vào giai
Hình 8. Các trạng thái của giải thuật khôi phục nhanh FR của đoạn khôi phục nhanh như trong NewReno. Với cách thực
TCP NewReno hiện này, cửa sổ tăng rất nhanh khi kích thước cửa sổ hiện
Hình 8 minh họa sự biến động kích thước cửa sổ tắc nghẽn hành cách xa giá trị tương ứng với dung lượng của đường
trong NewReno. Tương tự với giải thuật Reno, việc nhận bất truyền (giá trị xảy ra mất gói trước đó). Còn nếu gần với giá trị
kỳ các gói ACK nhân bản đều chỉ kích khởi việc ‘thổi phồng’ này thì nó sẽ giảm chậm mức độ tăng kích thước . Mức độ
cửa sổ tắc nghẽn (các trạng thái 3,4,6) . Một ACK nội bộ cho tăng cửa sổ nhỏ nhất ở điểm bảo hòa và số lượng quá mức của
biết chính xác về phần nào đó dữ liệu đã được giao thành nó vượt qua điểm bảo hòa với sự mất gói rất nhỏ. Toàn bộ
công. Như vậy, phản ứng với ACK nội bộ chỉ là một sự giảm hàm phát triển cửa sổ này đơn giản là một hàm logarit lõm.
bớt cửa sổ tắc nghẽn (trạng thái 4) và một sự phát lại gói dữ Hàm lõm này giữ cho cửa sổ tắc nghẽn ở điểm bảo hòa lâu và
liệu chưa được xác nhận kế tiếp (trạng thái 5). Cuối cùng, cân bằng hơn nhiều so với các hàm tuyến tính và hàm lồi (các
việc thoát khỏi giai đoạn khôi phục nhanh FR chỉ có thể thực hàm này có mức tăng cửa sổ lớn nhất ở điểm bảo hòa và như
hiện khi bên phát nhận được một ACK cho gói dữ liệu mới vậy gây ra sự quá mức lớn nhất về kích thước cửa sổ ở thời
và kèm theo đó là việc giảm kích thước cửa sổ hoàn toàn. điểm mất gói xảy ra. Đặc tính này giúp cho BIC-TCP rất ổn
định.
VI. GIẢI PHÁP BIC-TCP
Tuy nhiên, việc tăng đến điểm giữa có thể tăng quá nhiều
trong một RTT, vì thế nếu khoảng cách giữa điểm giữa và
Wmin hiện hành lớn hơn một hằng số cố định nào đó Smax thì
BIC-TCP sẽ tăng cửa sổ theo Smax. Nếu không có sự mất gói
xảy ra ở kích thước cửa sổ cập nhật này, thì kích thước cửa sổ
này trở thành giá trị Wmin mới. Tiến trình này tiếp tục cho
56
56
- HộiHội
Thảo Quốc
Thảo QuốcGia
Gia2015
2015về
vềĐiện
Điện Tử,
Tử,Truyền
Truyền Thông vàCông
Thông và CôngNghệ
Nghệ Thông
Thông TinTin (ECIT
(ECIT 2015)
2015)
đến khi độ tăng cửa sổ này ít hơn một hằng số nhỏ Smin nào VII. GIẢI PHÁP CUBIC
đó và lúc này kích thước cửa sổ được thiết lập tới giá trị cực
đại hiện hành (Wmax). Như thế, sau khi thực hiện giảm cửa sổ CUBIC là một biến thể của BIC-TCP. Tên gọi của giải thuật
do tắc nghẽn, hàm phát triển cửa sổ này sẽ hầu như phù hợp này xuất phát từ hàm phát triển cửa sổ của nó là một hàm
với một hàm tuyến tính (giai đoạn tăng cộng) theo sau bởi một cubic. Dạng của hàm này rất giống với hàm phát triển cửa sổ
hàm logarithmic (giai đoạn tìm kiếm nhị phân). của BIC-TCP. CUBIC sử dụng hàm cubic theo thời gian trôi
qua từ sự kiện tắt nghẽn mới nhất. Trong khi hầu hết các giải
Nếu kích thước cửa sổ tăng quá giá trị cực đại, kích thước cửa thuật sử dụng hàm tăng lồi khi có sự kiện mất gói xảy ra, mức
số cân bằng phải lớn hơn giá trị cực đại hiện hành và một giá độ tăng cửa sổ là luôn luôn tăng, CUBIC sử dụng cả 2 giai
trị cực đại mới được thiết lập. BIC-TCP vào một giai đoạn đoạn lõm và lồi của hàm CUBIC.
mới gọi là thăm dò giá trị cực đại. Giai đoạn thăm do cực đại
sử dụng một hàm phát triển cửa sổ đối xứng chính xác với sự Chi tiết của hoạt động của CUBIC như sau. Khi có sự mất gói
phát triển trong giai đoạn tăng cộng và tìm kiếm nhị phân. xảy ra CUBIC thiết lập Wmax bằng kích thước cửa sổ nơi sự
Hình-10a biểu diễn hàm phát triển này trong giai đoạn thăm kiện mất gói xảy ra và thực hiện giảm kích thước cửa sổ theo
dò giá trị cực đại. Trong quá trình thăm dò, kích thước cửa sổ bội số với hệ số β ( hằng số giảm kích thước cửa sổ), thực hiện
ban đầu phát triển chậm để tìm giá trị cực đại cận kề, và sau giai đoạn khôi phục nhanh thông thường và phát lại của TCP.
một khoản thời gian phát triển chậm mà không tim thấy giá trị Sau đó nó vào giai đoạn tránh tắc nghẽn, bắt đầu tăng cửa sổ
cực đại mới (không có sự mất gói xảy ra) thì nó đoán giá trị dùng giai đoạn lõm của hàm cubic. Hàm cubic được thiết lập
cực đại mới nằm xa vị trí hiện hành và nó chuyển sang tăng có giai đoạn bằng phẳng của nó ở Wmax, như vậy hàm lõm sẽ
nhanh hơn bằng cách chuyển sang tăng cộng. Trong quá trình phát triển tiếp tục cho tới khi kích thước cửa sổ bằng Wmax.
này kích thước cửa sổ được tăng với mức tăng cố định. BIC- Giải thuật tiếp tục chuyển sang phần lồi của hàm cubic và bắt
TCP có hiệu năng tốt là nhờ sự tăng chậm quanh giá trị Wmax đầu giai đoạn phát triển cửa sổ lồi. Cách điều chỉnh cửa sổ này
và tăng tuyến tính trong quá trình tăng công và thăm dò giá trị (lõm và sau đó lồi) cải thiện giao thức và độ ổn định của mạng
cực đại. nhưng vẫn duy trì sự tận dụng mạng cao [8]. Điều này là do
Tăng
cộng
Tìm kiếm kích thước cửa sổ duy trì hầu như là hằng số, hình thành một
nhị phân
sự bình ổn quanh giá trị Wmax nơi mà được xem như hiệu quả
sử dụng mạng cao nhất và trong trạng thái ổn định, hầu hết
Wmax những mẫu kích thước cửa sổ của CUBIC là gấn với Wmax,
như vậy nó đẩy mạnh việc tận dụng mạng cao và ổn định giao
thức.
Thăm dò cực đại
Hàm phát triển cửa sổ CUBIC sử dụng hàm sau :
a) Hàm phát triển cửa số BIC-TCP
𝑊𝑊(𝑡𝑡) = 𝐶𝐶(𝑡𝑡 𝑡 𝑡𝑡)3 + 𝑊𝑊𝑊𝑊𝑊𝑊𝑊𝑊 (4)
Trạng thài ổn định
C: là một thông số CUBIC
t : thời gian trôi qua từ sự giảm kích thước cửa sổ gần
Wmax nhất
K : khoản thời gian hàm W(t) tăng W đến Wmax khi
Thăm dò cực đại không có thêm sự mất gói xảy ra
Wmax : Kích thước cửa sổ tắc nghẽn ngay trước khi nhận
ra sự kiện mất gói gần nhất
b) Hàm phát triển cửa số CUBIC
Hình 10. Các hàm phát triển cửa sổ BIC-TCP và CUBIC K được tính theo công thức sau ;
BIC-TCP đạt được tính linh hoạt tốt trong mạng tốc độ cao, 3 Wmaxβ
công bằng giữa các luồng và ổn định do sự dao động cửa sổ K= √ (5)
C
thấp. Tuy nhiên, hàm phát triển của nó có thể vẫn quá mạnh β : Hệ số giảm bội số
đối với TCP., đặc biệt trong trường hợp mạng tốc độ chậm và
có RTT nhỏ. Hơn nữa nhiều giai đoạn khác nhau (tăng nhị Vào lúc nhận một ACK trong giai đoạn tắc nghẽn, CUBIC
phân, tham dò giá trị cực đại, Smax và Smin) của quá trình tính toán tốc độ phát triển cửa sổ trong giai đoạn RTT kế dùng
điều khiển cửa sổ làm tăng độ phức tạp khi thực hiện giao thức công thức (4). Nó thiết lập W(t+RTT) như là giá trị mục tiêu
và phân tích hiệu năng của nó. Để giải quyết những vần đề dự kiến của cửa sổ tắc nghẽn. Giả sử kích thước cửa sổ tắc
này, CUBIC đã được giới thiệu như là một biến thể của BIC- nghẽn hiện hành là Wc. Phụ thuộc vào giá trị của Wc, CUBIC
TCP với sự điều khiển cửa sổ đơn giản và tăng cường tình thực hiện trong 3 phương thức khác nhau. Đầu tiên, nếu Wc
công bằng giữa các luồng TCP trong việc sử dụng tài nguyên nhỏ hơn kích thước cửa sổ mà TCP chuẩn đạt được ở thời
mạng khi có tắc nghẽn xảy ra điểm t sau sự kiện mất gói gần nhất, thì CUBIC nằm trong mô
57
57
- HộiHội
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
hình TCP. Ngược lại, nếu Wc thấp hơn Wmax, thì CUBIC chỉ thị bởi một RTO, giải thuật khởi động chậm (SS) và Wc
năm trong vùng lõm, và nếu Wc lớn hơn Wmax thì CUBIC được thiết lập về một segment.
nằm trong vùng lồi. Đồ thị trong hình-13 biểu diễn biến động của kích thước cửa
sổ tắc nghẽn trong ngữ cảnh Reno. Trong giải thuật Reno khi
Khi nhận được một ACK trong giai đoạn tránh tắc nghẽn, tắc nghẽn xảy ra thì giải thuật khôi phục nhanh (FR) được
CUBIC sẽ kiểm tra xem giao thức có nằm trong vùng TCP thực hiện nên Wc không thiết lập lại ở giá trị 1 segment như
hay không. Để trả lời câu hỏi này, đầu tiên phải phân tích kích trong Tahoe mà được thiết lập giá trị 3 segment (4886 byte ).
thước cửa sổ của TCP theo thời gian trôi qua t . Kích thước
cửa sổ trung bình của giải thuật tăng công giảm bội số AIMD
(sử dụng trong TCP chuẩn Reno) với hệ số cộng α, hệ số nhân
β và xác suất mất gói p được tính theo công thức sau.
1 α 2−β 1
x√ x x (6)
RTT 2 β p
Kích thước cửa sổ trung bình của TCP với α = 1 và β = 0,5 là
1 3 1
x√ x (7)
RTT 2 p
Hình-12 biến động cửa sổ tắc nghẽn của giải thuật Tahoe
Như vậy để phương trình (6) giống với (7) thì α phải bằng
3β/2-β . Nếu TCP tăng cửa sổ lên α trong khoảng RTT thí kích
thước cửa sổ theo thời gian trôi qua t sẽ là
β t
Wtcp(t) = Wmax(1 − β) + 3 x (8)
2−β RTT
Nếu Wc nhỏ hơn Wtcp(t), thì giao thức nằm trong phương
thức TCP và Wc được thiết lập giá trị Wtcp(t) mỗi lần nhận
được ACK
VIII. KẾT QUẢ
Hình-13 Biến động cửa sổ tắc nghẽn của giải thuật Reno
Mô phỏng được thực hiện trên một mạng giả lập gồm 2 subnet Trong ngữ cảnh Cubic độ mất gói trong mạng Internet vẫn là
(HN và HCMC) và mạng Internet. Subnet HCMC bao gồm 0,5% những độ trễ lan truyền một chiều được thiết lập 100ms
một FPT server kết nối vào mạng Internet thông qua một (mạng độ trễ cao, ví dụ vệ tinh). Hình-14 biểu diễn sự biến
Router . Tương tự, subnet HN gồm một Client và Router_HN động cửa sổ tắc nghẽn của giải thuật Cubic, kết quả cho thấy
kết nối vào Internet. Luồng lưu lượng trong mô phỏng là hàm cubic được thể hiện qua những vùng lõm hoặc lõm và lồi
luồng FPT truyền qua giao thức TCP từ FPT server đến Client.
Với các giải thuật điều khiển tắc nghẽn khác nhau thì sự biến
động kích thước cửa sổ khác nhau thể hiện tương tự như trong
các phần trên đã trình bày. Vùng lõm Cả 2 vùng
lõm và lồi
Internet
Router Client
Ftp Server Router
Subnet HCMC Subnet HN
Hình-11 Mô hình mạng giả lập Hình-14 Biến động cửa sổ tắc nghẽn của giải thuật Cubic
Mô phỏng gồm 3 ngữ cảnh Tahoe, Reno và Cubic tương ứng IX. KẾT LUẬN
với 3 giải thuật trong phần III,IV và VII. Trong 2 ngữ cảnh
Bài báo đã khảo sát và mô phỏng một số giải thuật điều khiển
Tahoe và Reno, giá trị các thông số SST=64000 và xác suất
tắc nghẽn phổ biến cho luồng TCP dùng trong các hệ điều hành
mất gói trên mạng Internet là 0.5% . Kết quả như sau :
window và linux .
Đồ thị trong hình-12 biểu diễn sự biến động của kích thước
cửa sổ tắc nghẽn trong ngữ cảnh Tahoe. Khi tắc nghẽn được
58
58
- Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015)
LỜI CÁM ƠN [5] S. Floyd and T. Henderson, “RFC2582 – The NewReno modification to
TCP’s fast recovery algorithm,“ RFC, 1999.
Nghiên cứu này được tài trợ bởi Học Viện Công Nghệ Bưu
[6] Alexander Afanasyev, Neil Tilley, Peter Reiher, and Leonard Kleinrock,
Chính Viễn Thông với mã số đề tài 02-HV-2015-RD_VT2. “ Host-to-Host Congestion Control for TCP,“ IEEE Communication
Surveys & Tutorial, Vol.12, No. 3, 2010.
TÀI LIỆU THAM KHẢO
[7] S. Floyd,T. Henderson, A. Gurtov and Y. Nishida, “RFC6582 – The
[1] J.Postel, “ RFC 793- Transmission Control Protocol “, RFC, 1981. NewReno modification to TCP’s fast recovery algorithm,“ RFC, 2012.
[2] S. Floyd,T. Henderson and A. Gurtov, “RFC3782 – The NewReno [8] Cai, H., eun, D., Ha, S., Rhee, I., and xu, L., “Stochastic ordering for
modification to TCP’s fast recovery algorithm,“ RFC, 2004. internet congestion control and its applications,“ In proceedings of IEEE
[3] V. Jacobson, “ Congestion avoidance and control, ” ACM INFOCOM, 2007
SIGCOMM,pp. 314-329, 1988. [9] Peng Yang, Wen Luo, Lisong Xu, Jitender Deogun, and Ying Lu , “TCP
[4] V. Jacobson, “ Modified TCP congestion avoidance algorithm,“ email to Congestion Avoidance Algorithm Identification,“ 31st International
the end2end list, 4/1990 Conference on Distributed Computing System, 2011
59
59
nguon tai.lieu . vn
