Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

34
Chương 3
CÁC PHƯƠNG PHÁP ĐIỀU KHIỂN TẮC NGHẼN
3.1 Giới thiệu chương
Trong chương này, chúng ta sẽ hệ thống hóa lại một số phương pháp điều
khiển tắc nghẽn điển hình nhất, phân tích đánh giá chúng dựa trên cơ sở những tiêu
chí đã đề xuất trong chương 2. Đó là các phương pháp điều khiển tắc nghẽn truyền
thống như DECbit, và một vài phương pháp mới như EWA, ETCP, FBA- TCP, QS-
TCP để cải thiện hiệu suất hoạ
t động mạng. Trong đó đặc biệt đi sâu vào phương
pháp điều khiển tắc nghẽn sử dụng TCP phổ biến hiện nay (đặc biệt là trong mạng
Internet) và XCP là ứng cử viên cho mạng dựa trên cơ sở IP sau này.
3.2 Một số phương pháp điều khiển tắc nghẽn truyền thống
3.2.1 DECbit

DECbit là một trong các mô hình điều khiển tắc nghẽn sớm nhất. Phương
pháp này sử dụng phản hồi Nn. Trong DECbit, mạng cung cấp thông tin phản hồi
cho phép phía gởi điều chỉnh lưu lượng vào mạng. Các bộ định tuyến giám sát kích
thước trung bình của hàng đợi trong khoảng thời gian được định nghĩa. Nếu độ dài
trung bình của bộ đệm vượt quá ngưỡng (threshold) thì bộ định tuyến thiết lập mộ
t
bit chỉ dẫn chống tắc nghẽn (gọi là DECbit) trong các gói tin để thông báo sự tắc
nghẽn của mạng. Phía nhận gởi lại bit này trong thông báo nhận được đến phía gởi.
Phía gởi giám sát các bit chỉ dẫn chống tắc nghẽn này để điều chỉnh kích thước của
cửa sổ gởi như sau: Nếu xảy ra tắc nghẽn thì giảm đi theo phép nhân (nhân với
0,875), trong trường hợp ngược lại thì kích th

 Khởi đầu chậm: TCP đi vào mô hình khởi đầu chậm khi bắt đầu kết nối.
Trong suốt quá trình khởi đầu chậm, phía gởi tăng tốc độ gởi theo hàm mũ. Cụ thể,
khi bắt đầu khởi đầu chậm cửa sổ tắc nghẽn thiết lập là 1 đoạn, là MSS khởi tạo bởi
phía gởi trong suốt giai đoạn thiết lập kết nối. Do đó, phía gởi gởi 1 đoạn và đợi cho
tới khi phía nhận xác nhận nó. Một khi ACK đến phía gởi, phía gởi tăng cửa sổ
chống tắc nghẽn của nó bởi 1, gởi 2 đoạn, và đợi ACK tương ứng. Mỗi khi ack đến,
phía gởi có thể gởi 2 đoạn, 4 đoạn, gấp đôi lên dẫn đến tă
ng theo hàm mũ của cửa
sổ chống tắc nghẽn. TCP thoát khỏi khởi đầu chậm khi đoạn bị mất. Khi đó phía
gởi giảm cửa sổ tắc nghẽn đi 1 nửa và đi vào giai đoạn AIMD. Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

36
Cửa sổ
tắc
nghẽn
Thời gian
Khởi đầu
chậm (tăng
theo hàm mũ)
Cửa sổ bằng
1 khi hết thời
gian chở
AIMD
(tăng
tuyến
tính)

3.3.1 EWA (Explicit Window Adaptation) và FEWA (Fuzzy EWA)
Phương pháp EWA [10] (Explicit Window Adaptation) dùng thông báo một
cách rõ ràng đến phía gởi về băng thông còn khả dụng của các đường ra bằng cách
sử dụng cơ chế điều khiển lưu lượng giống như trong TCP để truyền thông tin phản
hồi từ
các bộ định tuyến đến phía gởi.
Sau mỗi khoảng đo i với thời gian tồn tại không đổi phụ thuộc vào băng
thông của tuyến mà router có khả năng EWA được nối, chẳng hạn, 10ms, router
với khả năng EWA đo độ dài hàng đợi hiện thời của nó Q
i
và tính toán độ dài hàng
trung bình hiện thời
i
Q .
i
i
QQ , và độ dài hàng trung bình trước đó
1−i
Q
được dùng
để tính toán cửa sổ gởi mới cho mỗi kết nối TCP đi qua router:
Cửa sổ gởi
(
)
{
}
MSSQBMSS
i
.log.,max
2

⎨
⎧
+
down
up
ωα
ωα
.
(3.2)
với

i
ii
QQQ
128
1
128
127
1
+=
−
(3.3)
Giá trị khởi tạo của hệ số sử dụng
α
được thiết lập là 1, tham số
up
ω
( để
tăng cộng) và
down

hết thời gian. Lý do nằm ở việc tính toán α, nó đặt quá nhiều vào trọng tải trước đó
của bộ định tuyến, vì vậy không thể phản ứng lại đủ nhanh đối với những thay đổi
lớn của các điều kiện tải.
Chính vì hạn chế đó EWA mờ (FEWA – Fuzzy EWA) [10] đ
ã phát triển,
khác với EWA cũ chủ yếu ở việc tính toán α. FEWA sử dụng một bộ điều khiển mờ
để tính α dựa theo giá trị hiện tại và một giá trị gần nhất của bộ đệm bộ định tuyến.
Với các thay đổi này trong việc tính toán phản hồi bên trong bộ định tuyến, hiệu
suất từ đầu cuối đến đầu cuối có thể
đạt được lớn hơn so với EWA.
3.3.2 ETCP (Enhanced TCP)
Ý tưởng của ETCP [10] là sử dụng phản hồi FEWA (dựa trên sự điều khiển
thích ứng lưu lượng-AWND) để tính cửa sổ gởi mới (SWND). ETCP phía gởi
không thực hiện chu trình bắt đầu chậm (slow start) và tránh tắc nghẽn (congestion
avoidance), mà bắt đầu với 1 cửa sổ gởi khởi tạo và cập nhật cửa sổ gởi theo các
cách sau:
- Nếu cửa sổ gởi hiện tại lớn hơn cửa sổ điều khiển lưu lượng thì cửa sổ gởi
mới được thiết lập bằng cửa sổ điều khiển lưu lượng:
AWNDSWND
←
Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

39
- Nếu cửa sổ gởi hiện tại nhỏ hơn cửa sổ điều khiển lưu lượng thì cửa sổ gởi
được tính như sau:
(

Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

40
H_cwnd
H_rtt
H_feedback

Hình 3.2 Header chống tắc nghẽn trong gói dữ liệu/xác nhận XCP
Nếu XCP phía gởi có tốc độ gởi yêu cầu
γ
, giá trị khởi tạo cho H_feedback
trong mào đầu có thể tính toán như sau:

()
/._ cwndrttfeedbackH −=
γ
(3.5)
Trong gói đầu tiên của kết nối XCP, H_feedback được khởi tạo bằng 0, khi
XCP phía gởi có RTT ước lượng hiện thời không hợp lệ trong đường dẫn.
XCP phía nhận sao chép mào đầu chống tắc nghẽn của gói dữ liệu đến sang
xác nhận ACK và gởi xác nhận bao gồm mào đầu chống tắc nghẽn đến XCP phía
gởi. Sau khi xác nhận ACK đến nơi, XCP phía gởi sửa lại cửa sổ chống tắc nghẽn
m


Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

41
Với mỗi kết nối, router duy trì bộ định thời điều khiển được thiết lập xấp xỉ
đến giá trị RTT ước lượng trung bình của XCP phía gởi trên kết nối đó. Sau khi hết
thời gian chờ (time-out) của bộ định thời điều khiển mỗi luồng, EC và FC được
dùng để tính giá trị hiện thời của phản hồi điều khiển chống tắc ngh
ẽn cho luồng
XCP đi qua đường dẫn này. Các thuật toán điều khiển chống tắc nghẽn và điều
khiển bình đẳng của bộ định tuyến XCP có đặc điểm là không đòi hỏi thông tin
trạng thái của mỗi luồng. Thay vào đó, bộ định tuyến khai thác thông tin lưu lượng
tổng bằng cách tích luỹ thông tin từ tất cả các gói truyền qua bộ định tuyến trong
một khoảng thời gian nh
ất định.
Trong phần sau, biểu thức toán học của phép tính EC và FC được trình bày.
 Bộ điều khiển hiệu quả (EC)
Mục đích của bộ điều khiển hiệu quả là tăng tính sử dụng đường truyền trong
khi tối thiểu hóa tốc độ mất gói và hàng đợi ổn định. Nó chỉ xét lưu lượng tổng và
không chú ý đến tính hiệu quả cũng như luồng mà gói có liên quan.
EC tính số byte mà lưu lượng tổng tăng hay giảm theo mong muốn trong
khoảng thời gian điều khiển (RTT trung bình). Phản hồi tổng
φ
(tính theo byte)
được tính trong mỗi khoảng điều khiển:

QSd
β
α

www.4tech.com.vn

42
nghẽn tổng
φ
phải là giá trị âm để giảm số gói tại hàng. Đẳng thức (3.7) đảm bảo
rằng phản hồi chống tắc nghẽn tổng
φ
của đường truyền tỉ lệ với S và –Q.
Để đạt được tính hiệu quả, chúng ta phân bố phản hồi tổng đến từng gói qua
H_feedback. EC chỉ phân phối với trạng thái tổng, nó không quan tâm đến gói nào
có phản hồi và mỗi luồng riêng thay đổi cửa sổ chống tắc nghẽn bao nhiêu. Tất cả
các yêu cầu của EC là lưu lượng tổng phải thay đổi 1 lượng
φ
trong khoảng thời
gian điều khiển. Làm thế nào chúng ta chia phản hồi chính xác giữa các gói (và giữa
các luồng) chỉ ảnh hưởng đến tính bình đẳng, và đó là công việc của bộ điều khiển
bình đẳng.
 Bộ điều khiển bình đẳng XCP
Công việc của bộ điều khiển bình đẳng (FC) là chia nhỏ phản hồi đến các gói
riêng rẻ để đạt được tính bình đẳng. FC dựa vào nguyên lý gi
ống như TCP dùng để
hội tụ đến bình đẳng, gọi là tăng cộng giảm nhân (AIMD). Do đó, chúng ta muốn
tính toán phản hồi trên mỗi gói theo nguyên lý:
- Nếu
φ
>0, lưu lượng của tất cả các luồng tăng giống nhau.
- Nếu
φ
<0, lưu lượng của một luồng giảm tỉ lệ với lưu lượng hiện thời.

npfeedbackH
−
=
_ (3.9)
Trong khoảng điều khiển đơn, p
i
và n
i
được tính toán bằng cách dùng các giá trị Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

43

{
}
∑
+
=
i
ii
p
cwndH
SrttH
d
h
_
._

cwndH
SrttH
p
_
._
.
2
ξ
= (3.12)

iini
SrttHn ._.
ξ
=
(3.13)
Các công thức trên được chứng minh trong [6]. Trong XCP, bộ điều khiển
hiệu quả và bình đẳng được tách riêng. Đặc biệt, bộ điều khiển hiệu quả EC dùng
quy tắc MIMD, tăng mức lưu lượng tỉ lệ với băng thông dự trữ trong hệ thống (thay
vì tăng 1 MSS/RTT/luồng như TCP). Điều này cho phép XCP nhanh chóng có được
băng thông dự trữ dương ngay cả trên đường truyền dung lượng lớ
n. Bộ điều khiển
tính bình đẳng FC dùng quy tắc AIMD, hội tụ đến tính bình đẳng. Do đó, việc tách
cho phép mỗi bộ điều khiển dùng các quy tắc điều khiển thích hợp.
Thông thường, nếu XCP được dùng thì mất gói là rất hiếm. Nhưng nếu mất gói xảy
ra, quá trình phát lại trong XCP phía gởi giống trong TCP.
3.3.3.3 Tính thực tế của XCP
Thực hiện XCP trong hệ thống đầu cuối là tương đối
đơn giản. Chỉ thay đổi
1 ít trong mã nguồn của TCP phía gởi và TCP phía nhận để làm cho chúng có khả
năng XCP. Trang bị router với khả năng XCP khá tốn kém, sự phức tạp của XCP

Mỗi router biên ước lượng tốc độ mỗi luồng cho mọi gói đi qua router biên
trong mạng có khả năng CSFQ. Để tính toán, các router biên cần chứa trạng thái
mỗi luồng. Tốc độ ước lượng mỗi luồng được dùng để dán nhãn gói bằng cách chèn
tốc độ ước lượng vào trong mào đầu gói của mỗi luồng. Router lõi được trang bị với
xếp hàng FIFO và không có chứa trạng thái luồng bất kỳ nào.
Đặc tính này của Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

45
router lõi được gọi là core-stateless. Router lõi thực hiện thuật toán giảm xác suất
cho gói đến dựa vào lưu lượng tổng và thông tin chứa trong nhãn của gói. Mục đích
chính của thuật toán giảm gói theo xác suất là đạt được sự phân bổ băng thông hợp
lý giữa các luồng đi qua router lõi.
Trong phần dưới đây, thuật toán ước lượng tốc độ thực hiện trong router biên
và thuật toán giảm gói thực hiện trong router lõi được nói đến. Nhiều chi ti
ết về
CSFQ, chẳng hạn, giả mã cho thuật toán dùng trong router biên và lõi hay mở rộng
cơ cấu CSFQ cơ bản, có thể tìm thấy trong [8]
 Ước lượng tốc độ mỗi luồng CSFQ trong router biên.
Trong router biên tốc độ ước lượng
i
r
ˆ
của luồng i được cập nhật mỗi khi gói
mới của luồng này đến. Ước lượng tốc độ luồng được thực hiện bằng cách dùng sự
ước lượng dựa trên chuNn hàm mũ. Với
)(k

i
k
i
ˆ
1
ˆ
/
)(
)(
/
)()(
−−
+−=
(3.14)
với
)1()()( −
−=
k
i
k
i
k
i
ttT
và giá trị không đổi K. Mỗi gói của luồng i được dán nhãn
với
i
r
ˆ
cập nhật mới nhất

n
i
i
rC
1
,min
α
(3.17) Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

46
Khi các luồng được đóng gói, A và
α
phải được ước lượng bởi
A
ˆ
và
α
ˆ
. Sau đó tốc
độ lưu lượng tổng được phép của router lõi có thể được ước lượng:

() { }
∑
=
=
n

α
K . Đẳng thức
dạng tương tự được dùng để ước lượng tốc độ lưu lượng tổng
F
ˆ
cho phép bởi
router.
Nếu
CA ≥
ˆ
trong tất cả các khoảng K
c
, đường truyền được giả thiết bị tắc
nghẽn. Nếu
CA ≤
ˆ
trong tất cả các khoảng K
c
, đường truyền giả thiết là không bị tắc
nghẽn.
Giá trị mới cho tốc độ phân bổ bình đẳng ước lượng
α
ˆ
chỉ được tính sau một
khoảng mà trong đó đường truyền được phân loại thành bị tắc nghẽn và không tắc
nghẽn. Nếu đường truyền bị tắc nghẽn thì
α
ˆ
được cập nhật như sau:


phải giới hạn bởi 0.25 giá trị trước đó.

α
ˆ
khi đó được dùng để tính toán xác suất giảm gói của các luồng. Với luồng
i, mỗi bit đang đến bị giảm trong router lõi với xác suất:

⎭
⎬
⎫
⎩
⎨
⎧
−=
i
i
r
P
ˆ
ˆ
1,0max
α
(3.21) Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

47
Nếu các gói trong luồng i bị giảm, tốc độ mới

trong 1 đoạn mạng.
3.3.4.2 FBA-TCP
Phân bổ băng thông hợp lý cho TCP (FBA-TCP) [14] (Fair Bandwidth
Allocation for TCP) là một phương pháp điều khiển lưu lượng TCP dựa trên thông
tin phản hồi về mạng được cung cấp bởi CSFQ
FBA-TCP dùng cơ cấu CSQB miêu tả trong phần trước để cải thiện đ
iều
khiển chống tắc nghẽn trong kết nối TCP. FBA-TCP làm việc như sau: trong router
biên của vùng mạng (trong hình 3.3) FBA-TCP dùng thuật toán giống CSFQ để ước
lượng tốc độ luồng và dán nhãn gói trong luồng với tốc độ luồng ước lượng. Trong
mỗi router biên và lõi trong vùng mạng tốc độ phân bổ bình đẳng được ước lượng
và các gói của luồng bị giảm theo đẳng thức (3.21) nếu nhãn của chúng lớn hơn
phân bổ cân bằ
ng. Chương 3: Các phương pháp điều khiển tắc nghẽn
www.4tech.com.vn

48

Hình 3.4 Kết nối TCP đơn đi qua vùng router có khả năng CSFQ.
Đặc tính mới của FBA-TCP là router biên ở phía nhận của luồng không xoá
nhãn khỏi mỗi gói. Router biên đặt nhãn của gói vào trong mào đầu Ipv4 (hay mào
đầu mở rộng của Ipv6) để truyền trong suốt nhãn này đến TCP phía nhận qua phần
mạng không có khả năng CSFQ. Nếu hệ thống đầu cuối phía nhận của kết nối TCP
nhận gói với nhãn
l
hay tốc độ ước lượng
r

mới này thì nó sẽ truyền yêu cầu QS đi, ngược lại nó sẽ giảm tốc độ dữ liệu đến một
giá trị phù hợp.
Để làm được điều đó bộ
định tuyến cần thiết phải giám sát sự khác nhau của
trọng tải hiện tại và dung lượng sẵn sàng và những yêu cầu QS trong thời gian gần
đây. Khi yêu cầu QS (QS request) tới TCP phía nhận, một đáp ứng QS (QS
response) tương ứng được tạo ra và chèn vào một thông báo nhận được gởi trở về
phía gởi.
Nhận được đáp ứng QS, phía gởi điều chỉnh cửa sổ ch
ống tắc nghẽn khởi tạo
theo tốc độ dữ liệu chỉ ra trong đáp ứng QS. Để tránh lưu lượng bùng phát, phía gởi
tăng dữ liệu từng bước vào cửa sổ khởi tạo. QSTCP đòi hỏi tất cả các bộ định tuyến,
phía gởi và phía nhận hỗ trợ khởi tạo nhanh (QS).
3.4 Đánh giá chung
Các phương pháp này được dùng trong mạng cơ sở IP tương lai dựa vào mức
độ mong mu
ốn tương thích với các phương thức truyền TCP và UDP triển khai hiện
nay trong hệ thống đầu cuối. XCP, chẳng hạn, dường như là phương pháp mạnh
nhất để cải thiện toàn bộ hiệu suất của mạng, ít nhất nếu mạng là mạng tốc độ cao.
Nhưng XCP đòi hỏi đòi hỏi sự thích ứng của phương thức truyền thông trong hệ
thống đầu cuối.
Tương phản với XCP, (F)EWA không cần bất kì sự thay đổi nào trong hệ
thống đầu cuối. Nhưng (F)EWA không mạnh như XCP, cửa sổ gởi của TCP phía
gởi không thể được điều khiển chính xác như XCP.
CSFQ không cung cấp phản hồi rõ cho (TCP) phía gởi. Nó phát triển chủ
yếu để tăng tính bình đẳng giữa các luồng trong (phần) mạng. Do đó, độ gia tăng
hiệu suất khá bị giớ
i hạn. Nhưng FBA-TCP như là sự mở rộng của CSFQ có thể là
ứng cử tiềm năng cho sự cải thiện điều khiển chống tắc nghẽn trong mạng cơ sở IP.
Bất lợi chính của FBA-TCP là các router biên trong phần mạng có khả năng CSFQ