ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGHIÊN CỨU KỸ THUẬT ĐIỀU KHIỂN TẮC NGHẼN
MẠNG VÀ MÔ PHỎNG,ĐÁNH GIÁ TRÊN NETVVORK
SIMULATOR -2

LUẬN VĂN THẠC SĨ

Người Hướng Dẫn

Hà Nội- 2006 - 1 -
MỤC LỤC

Mục lục 1
Danh mục các từ viết tắt 3
Mở đầu 5
Phần 1: Điều khiển tắc nghẽn mạng 10
Chương 1: Các thuật toán điều khiển tắc nghẽn mạng trên lớp TCP 11
1.1 Cơ chế cửa sổ trượt 12
1.2 Tính toán thời gian phát lại 16
1.2.1 Tính trung bình đơn giản 17
1.2.2 Tính trung bình theo hàm mũ 17
1.3 Quan hệ giữa điều khiển luồng và điều khiển tắc nghẽn trên TCP 18
1.3.1 Dự đoán phương sai RTT 19

3.2.1 Lớp tcp 70
3.2.2 Lớp tcp-sink 71
3.2.3 Lớp link 72
3.2.4 Lớp trace 74
3.3 Các bước xây dựng một chương trình mô phỏng 76
3.4 Khảo sát và đánh giá kết quả mô phỏng 77
Chương 4: Mô phỏng và đánh giá các thuật toán
điều khiển tắc nghẽn trên TCP 80
4.1 Thuật toán Tahoe 81
4.2 Thuật toán Reno 85
4.3 Thuật toán NewReno 93
4.4 Thuật toán Vegas 101
Chương 5: Mô phỏng và đánh giá các thuật toán điều khiển
tắc nghẽn trên Gateway 104
5.1 RED cơ bản 104
5.1.1 So sánh hoạt động của RED với DropTail 105
5.1.2 Sự nhạy cảm của RED với mức độ tải dữ liệu lên mạng 113
5.1.3 Sự nhạy cảm với thông số của RED 115
5.2 RED thích nghi 121
Kết luận 130
Tài liệu tham khảo 134
Phụ lục 136 - 3 -
DANH MỤC CÁC TỪ VIẾT TẮT


Explicit Congestion Notification
Cảnh báo tắc nghẽn trực tiếp
ERD
Early Random Drop
Loại bỏ ngẫu nhiên sớm
EWMA
Exponential Weighted Moving
Average
Trung bình có trọng số hàm mũ
FIFO
First In First Out
Vào trước ra trước
FTP
File Transfer Protocol
Giao thức truyền file
IP
Internet Protocol
Giao thức Internet
MAC
Medium Access Control
Điêu khiển truy cập môi trường
MBPS
Mega Byte Per Second
Triệu byte trong một giây
MIAD
Multiplicative Increase
Multiplicative Decrease
Tăng nhân giảm cộng
MIMD
Mutiplicative Increase


RFC
Request For Comment
Yêu cầu nhận xét
RTO
Retransmission Timer Out
Thời gian truyền lại
RTT
Round Trip Time
Thời gian khứ hồi
SACK
Selective ACKnowledgement
Đáp ứng có lựa chọn
SRTT
Smoothed Round Trip Time
Thời gian khứ hồi đã làm trơn
TCP
Transmission Control Protocol
Giao thức điều khiển truyền dẫn
UW
Usable Window
Cửa sổ có thể truyền - 5 -
MỞ ĐẦU TCP/IP là hệ thống giao thức thống trị trên mạng ngày nay. Là giao
thức lớp giao vận (transport) TCP cung cấp một giao diện giữa lớp ứng dụng

tiêu đó thì mới có thể kiểm soát được tắc nghẽn mạng.
Kiểm soát tắc nghẽn mạng dựa trên TCP gặp rất nhiều khó khăn [34]:
1. IP là giao thức không kết nối, không trạng thái do đó không cung
cấp công cụ gì cho phát hiện tắc nghẽn, và rất ít cho điều khiển
tắc nghẽn.
2. TCP chỉ cung cấp các công cụ cho điều khiển luồng đầu cuối
(end-to-end) và chỉ có thể suy ra sự tắc nghẽn thông qua các
phương pháp gián tiếp (trừ khi sử dụng ECN – Explicit
Congestion Notification [12]). Thêm nữa độ trễ trên mạng có thể
biến đổi nên các điều kiện mạng mà TCP tính ra được có thể
khổng đủ tin cậy.
3. Không có một thuật toán phân tán nào có thể kết nối và phối hợp
hoạt động của được hàng loạt các thực thể TCP. Do đó các thực
thể TCP không thể phối hợp với nhau để duy trì tổng thông lượng
ở một mức nào đó, thay vào đó chúng hoạt động giống như cạnh
tranh các tài nguyên mạng một cách ích kỉ.
Công cụ duy nhất trong TCP liên quan đến kiểm soát tắc nghẽn là cơ chế
điều khiển luồng bằng cửa sổ trượt (sliding-window [34]) và cơ chế điều
khiển lỗi. Hàng loạt giải pháp được đưa ra để sử dụng các cơ chế này cho việc
phát hiện xung đột, tránh xung đột và phục hồi sau tắc nghẽn. Nói chung các
giải pháp ra đời sau thường là nhằm khắc phục các giới hạn của các giải pháp
trước đó và sau một thời gian nghiên cứu, thử nghiệm đã trở thành tiêu chuẩn - 7 -
hoặc khuyến nghị cho TCP. Tahoe là giải pháp cổ điển nhất, bao gồm các cơ
chế nhỏ như khởi động chậm (slow-start), tránh tắc nghẽn (congestion
avoidance- CA) và phát lại nhanh (fast-retransmit). Tahoe sử dụng các ACK
lặp hoặc đồng hồ phát lại (retransmit timer) để xác định sự mất gói tin hay sự
tắc nghẽn trên mạng. Reno [28] cải tiến cơ chế fast-retransmit của Tahoe

Out - FIFO). Các gói tin đến khi bộ đệm đã đầy sẽ lập tức bị loại bỏ. Hàng
loạt gói tin đến từ các TCP nguồn khác nhau có thể bị loại bỏ gần như đồng
thời, do đó hàng loạt TCP sẽ gần như đồng thời thực hiện phát lại và giảm
thông lượng của mình xuống đồng loạt một cách không cần thiết. Do vậy gây
ra hiệu ứng đồng bộ toàn cục (global synchronization) làm giảm hiệu suất
mạng, hơn nữa còn có thể dẫn đến một chu kì đồng bộ mới. Bộ đệm có thể
tăng lên để làm giảm xác suất mất gói tin, tăng thông lượng, nhưng sẽ kéo
theo độ trễ trung bình tăng lên. Mặt khác sự tăng bộ đệm có thể là không giới
hạn được và trở nên bất khả thi. Cơ chế quản lí hàng đợi tích cực (Active
Queue Management - AQM) được đưa ra nhằm giải quyết các vấn đề trên.
Nhiều kĩ thuật được đưa ra như ERD (Early Random Drop)[21], DECbit [27],
IP Source Quench [32], RED (Random Early Detection) [18], trong đó khả
quan nhất là RED. RED loại bỏ gói tin ngay từ khi hàng đợi chưa đầy với xác
suất loại bỏ tỉ lệ với kích thước hàng đợi trung bình. RED được thiết kế với
các mục tiêu chính là tránh tắc nghẽn, tránh đồng bộ toàn cục, cho phép khả
năng truyền burst và giới hạn kích thước hàng đợi trung bình. RED thực hiện
khá tốt các mục tiêu này, nhưng có nhược điểm lớn là khả năng hoạt động phụ
thuộc nhiều vào các thông số hoạt động và mức độ tải dữ liệu lên mạng. Cũng
có nhiều giải pháp được đưa ra để khắc phục yếu điểm này của RED như cơ
chế quản lí từng luồng (per-flow scheduling) [7], RED loại bỏ ưu tiên (RED-
PD)[19], RED thích nghi (Adaptive RED)[16], trong đó RED thích nghi tỏ
ra hiệu quả và đơn giản hơn hẳn. RED thích nghi tự động điều chỉnh một số - 9 -
thông số của RED để phù hợp với điều kiện mạng và đảm bảo vùng hoạt động
xác định cho hàng đợi. RED thích nghi hoạt động tốt hơn RED, và đặc biệt là
nó cho phép thao tác cấu hình đơn giản hơn nhiều.
Nghiên cứu các kĩ thuật trên đòi hỏi một quá trình mô phỏng, kiểm định
rất cẩn thận trước khi đưa thành khuyến nghị hay triển khai thực tế. Network


Điều khiển tắc nghẽn trên mạng có hai phương hướng chính là điều
khiển tắc nghẽn trên lớp TCP và điều khiển tắc nghẽn trên Gateway. Chương
này giới thiệu về một số thuật toán điều khiển tắc nghẽn trên lớp TCP mà đã
khá phổ biến là Tahoe, Reno và Vegas. Do TCP chỉ cung cấp các công cụ cho
việc điều khiển luồng end-to-end, nên các thuật toán này đều dựa trên nền
tảng là cơ chế điều khiển luồng của TCP. Tắc nghẽn trên mạng có thể được
phát hiện thông qua sự kiện mất gói tin, ví dụ nhận được nhiều ACK lặp, quá
thời gian phát lại (timeout) như trong Tahoe và Reno, hoặc cũng có thể được
dự đoán trước nhờ so sánh thông lượng tức thời và thông lượng trung bình
như trong Vegas. Một khi tắc nghẽn được phát hiện (dù chính xác hay không
chính xác), thuật toán điều khiển luồng sẽ giảm thông lượng xuống để đảm
bảo tránh tắc nghẽn và có thể thực hiện việc phát lại gói tin được coi là đã
mất. Mặc dù sự kiện mất gói tin có thể không phải do tắc nghẽn mạng, mà có
thể do mất mát trên đường truyền (gói tin bị lỗi không thể sửa được), tuy
nhiên xác suất mất gói tin do lỗi trên đường truyền chỉ đáng kể với một số
môi trường, đặc biệt là môi trường không dây. Còn trong môi trường mạng
cáp xác suất này rất thấp và có thể được bỏ qua. Khi gói tin bị mất do lỗi trên
đường truyền, TCP chỉ nên phát lại gói tin mất đó mà không cần giảm thông
lượng đi, vì tắc nghẽn chưa hề xảy ra. Sự không phân biệt được giữa gói tin - 12 -
mất do lỗi đường truyền và gói tin mất do tắc nghẽn mạng có thể khiến cho
thông lượng giảm đi một cách không cần thiết. Vì vậy trong môi trường mạng
cáp, ba thuật toán này hoạt động đủ tin cậy, còn trong môi trường không dây
cần một thuật toán khác để có thể đạt được thông lượng tốt hơn. Đã có một số
thuật toán cố gắng giải quết vấn đề này, tuy nhiên trong luận văn này nói
chung và trong chương này nói riêng, sẽ không đề cập đến các thuật toán đó.
Điều khiển luồng TCP thường là dựa trên cơ chế cửa sổ trượt (sliding-

1. Khi một gói tin mới nhận được ACK, biên trái của cửa sổ được
dịch sang phải đến vị trí vượt qua số hiệu gói tin đó. Hoạt động
này được gọi là đóng cửa sổ (closes).
2. Dựa vào ow trong ACK mới nhận được và vị trí biên trái của cửa
sổ, TCP nguồn có thể dịch biên phải của cửa sổ về bên phải sao
cho kích thước cửa sổ bằng với ow. Hoạt động này được gọi là
mở cửa sổ (opens).
3. Cửa sổ bị co lại (shrink) khi biên phải dịch về bên trái. Điều này
xảy ra khi ow mới quá nhỏ, khiến cho tổng của biên trái và ow
(n+1) (n+2) (n+3) (n+4) (n+5) (n+6) (n+7) (n+8) (n+9) (n+10) (n+11)

offered window
(cửa sổ cho phép bởi TCP đích
Usable window
Cửa sổ có thể phát
đã truyền và
đã nhận được
ACK
đã truyền nhưng chưa nhận
được ACK
Có thể truyền mà
không cần đợi ACK
Không thể
truyền cho đến
khi cửa sổ
được dịch sang
phải - 14 -

Truyền các S4, S5, S6
< > ACK S7
< >
Cửa sổ sau S7 ACK S10
< >
Cửa sổ sau S10

- 15 -

Truyền các S11, S12, S13
< >



4/
4
4/1
RDW
RD
W
RDW
S
(1.1)
Trong đó: (giả thiết bỏ qua thời gian nhận và xử lí tại node thu)
-W là kích thước cửa sổ.
-R là tốc độ truyền dữ liệu (transmission) trên kết nối.
-D là độ trễ truyền dẫn (propagation delay).
Có một vài điều cần chú ý ở đây:
- Nếu các luồng TCP được ghép kênh thì R phải giảm đi và S tăng lên. - 16 -
- Nếu luồng TCP đi qua nhiều trạm (hop), D sẽ là tổng các trễ truyền dẫn
trên các hop này cộng trễ trên các router. Thường thì trễ trên router lớn
hơn, đặc biệt là khi xảy ra tắc nghẽn. Khi đó S sẽ bị giảm đi.
- R là tốc độ dữ liệu của kết nối, nên nếu trên đường truyền TCP có một
khúc nào đó có tốc độ thấp hơn R thì sẽ xảy ra nghẹt cổ chai, do đó làm
tăng D và làm S giảm.
- Nếu gói tin bị mất, sẽ xảy ra việc truyền lại, do đó thông lượng thực sẽ
giảm đi.
1.2 Tính toán thời gian phát lại

trễ của K gói tin vừa phát với trọng số như nhau là 1/(K+1):





1
1
)(
1
1
)1(
K
i
iRTT
K
KARTT
(1.2)
Có thể biến đổi lại thành dạng phù hợp cho tính toán hơn :
)1(
1
1
)(
1
)1( 



 KRTT
K

i
i
iKRTTKSRTT

(1.5)
Vì cả  và 1- đều nhỏ hơn 1 nên các giá trị RTT càng cũ (có chỉ số
nhỏ) tương ứng với số mũ lớn thì càng được tính với trọng số nhỏ hơn.
Chú ý rằng  càng bé thì các trọng số có ý nghĩa (lớn một chút) càng ít,
nghĩa là độ trễ dự đoán phụ thuộc chủ yếu vào một ít các độ trễ của các gói tin
mới truyền nhất. Tuy nhiên nó có nhược điểm là thay đổi nhanh nếu mạng có
một thay đổi nhanh.
Sau khi dự đoán độ trễ khứ hồi, chúng ta đặt thòi gian truyền lại lớn
hơn độ trễ này một chút. Lượng thêm vào có thể là một hằng số :
RTO(K+1) = SRTT(K+1) +


Tuy nhiên  lại không tỉ lệ với SRTT. Khi SRTT nhỏ, RTO phụ thuộc
vào  hơn là SRTT. Khi SRTT lớn, giá trị  thêm vào có thể là không đủ.
RFC793 (Request For Comment) đưa ra một cách tính khác như sau:
RTO(K+1)=MIN(UBOUND, MAX(LBOUND,

.SRTT(K+1))) (1.6)
Theo cách này thì RTO tỉ lệ với SRTT và bị giới hạn trong khoảng
{LBOUND,UBOUND}. RFC793 cũng đưa ra khoảng giá trị cho  là
{0.8,0.9} và  là {1.3,2.0}.
1.3 Quan hệ giữa điều khiển luồng và điều khiển tắc nghẽn trênTCP - 19 -
Công cụ duy nhất của TCP mà liên quan đến tắc nghẽn chính là cơ chế

Giá trị đặc trưng của  trong (1.6) là 2. Trong môi trường ổn định, với
phương sai của RTT thấp, công thức này cho RTO cao quá mức cần thiết.
Nhưng trong môi trường không ổn định, giá trị 2 không đủ để chống lại
những sự phát lại không cần thiết. Một cách tiếp cận hiệu quả hơn là dự đoán
sự biến đổi của RTT và sử dụng nó trong tính toán RTO. Tuy nhiên cách tính
độ lệch chuẩn sử dụng các phép bình phương và lấy căn nên không thực sự
thích hợp. Một cách đo sự biến đổi đơn giản hơn là dự đoán độ lệch trung
bình :
MDEV(X) = E[ |X-E[X]| ] ( E[X] là giá trị trung bình của X).
Với các giá trị của RTT, một phép tính trung bình đơn giản có thể được
sử dụng để dự đoán MDEV [34]:
)1(
1
1
)(
1
)(
1
1
)1(
)()1()1(
)1(
1
1
)(
1
)1(
1
1


K
i
(1.7)
Trong cách tính này, cách giá trị RTT cũng như AERR được nhân với
cùng trọng số 1/(K+1). Chúng ta mong muốn các giá trị càng mới thì được
nhân với trọng số càng lớn vì chúng phản ảnh tình trạng hiện tại tốt hơn. - 21 -
Jacobson đề nghị sử dụng cùng kĩ thuật làm trơn bằng hàm mũ như trong tính
toán SRTT. Thuật toán được đưa ra một cách hoàn chỉnh bao gồm :
)1(.)1()1(
)1(.)().1()1(
)()1()1(
)1(.)().1()1(




KSDEVfKSRTTKRTO
KSERhKSDEVhKSDEV
KSRTTKRTTKSERR
KRTTgKSRTTgKSRTT
(1.8)
Dựa trên các thực nghiệm của mình, Jacobson đề nghị các giá trị của g, h
và f là g=0.125, h=0.25 và f=4. Đây cũng chính là các giá trị được dùng gần
đây. RFC2988 thêm một sự cải tiến vào sự tính toán RTO
)]1(.,[)1()1(  KSDEVfGMAXKSRTTKRTO
(1.9)
Trong đó G là giá trị thể hiện độ phân giải của thời gian sử dụng trong

backoff.
1.3.3 Thuật toán Karn [34]
Nếu không xảy ra phát lại, thuật toán Jacobson sẽ không gặp khó khăn.
RTT của mỗi gói tin được đưa vào để tính toán RTO. Tuy nhiên khi có một
gói tin bị timeout và phải phát lại, sau đó nhận được một ACK của nó, có hai
tình huống xảy ra : (1) đây là ACK của gói tin phát lần đầu, trong tình huống
này RTT lớn hơn nhiều so với mong đợi nhưng phản ánh chính xác điều kiện
của mạng ; hoặc (2) đây là ACK của gói tin phát lại. TCP phát không thể
phân biệt hai tình huống này. Nếu là tình huống 1, TCP tính RTT từ lúc phát
lần một cho đến khi nhận được ACK, giá trị này sẽ khá lớn. RTT này sẽ được
sử dụng để tính RTO. Nếu đưa giá trị RTT sai vào thuật toán Jacobson sẽ tạo - 23 -
ra SRTT cao quá mức cần thiết và do đó RTO cũng vậy. Hơn nữa hiệu ứng
này sẽ còn ảnh hưởng đến các chu kì sau. Một cách tiếp cận khác còn tồi tệ
hơn là tính RTT từ khi phát lại đến khi nhận được ACK. Nếu trong thực tế
đây là ACK của lần phát đầu tiên thì RTT sẽ quá nhỏ, tạo ra SRTT và RTO
quá nhỏ. Điều này dẫn đến hiệu ứng phản hồi dương, tạo ra thêm các sự phát
lại và các số đo sai mới.
Thuật toán Karn giải quyết điều này bằng các qui tắc:
1. Không sử dụng RTT đo được của gói tin phát lại để cập nhật SRTT
và SDEV.
2. Dùng công thức (1.10) để tính RTO backoff khi xảy ra phát lại
3. Sử dụng giá trị của RTO backoff cho các gói tin kế tiếp cho đến khi
nhận được ACK của một gói tin chưa bị phát lại.
Sau khi nhận được ACK cho một gói tin mới, thuật toán Jacobson lại
được sử dụng để tính RTO.
1.4 Thuật toán Tahoe [26, 33, 34]
Thuật toán Tahoe được triển khai rộng nhất trên mạng ngày nay. Tahoe