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 chuẩn hàm mũ. Với )(k
i
t và )(k
i
llần lượt là thời gian đến (arrival
time) và độ dài gói k của luồng i. Sau đó, i
r
ˆ được cập nhật như sau:
old
i
KT
k
i
k
i
KT
new
ire
T
l
er k
i
k
iˆ
..1
ˆ/
)(
)(
/)()( (3.14)
với )1()()(
k
i
k
i
k
ittT 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
ii rlabel ˆ
(3.15)
Bổ sung vào sự ước lượng tốc độ mỗi luồng, thuật toán giảm gói của router
lõi CSFQ được thực hiện trong router biên.
Thuật toán giảm gói CSFQ trong router lõi
Trong luồng lưu lượng, tốc độ đến tổng n luồng trong tuyến đơn của router
lõi là:
n
ii
rA
1
(3.16)
Mỗi luồng đó phải sử dụng tốc độ phân bổ công bằng
với tốc độ đường ra C của
router lõi được khởi tạo:
n
ii
rC
1
,min
(3.17)
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
ii
rF
1
ˆ
,
ˆ
min
ˆ
(3.18)
Tổng tốc độ đến router lõi được ước lượng dựa vào hàm mũ trung bình:
old
KTKT Ae
T
l
eˆ
..1A
ˆ//
new
(3.19)
với thời gian đến T giữa gói trước và gói hiện tại và giá trị hằng số
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 Kc, đường truyền được giả thiết bị tắc
nghẽn. Nếu CA
ˆ
trong tất cả các khoảng Kc, đườ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:
oldnew
F
C
ˆ
.
ˆ
ˆ (3.20)
Nếu đường truyền không tắc nghẽn thì new
ˆ được thiết lập bằng tốc độ lớn
nhất của luồng tích cực bất kỳ, tức là, đến nhãn lớn nhất trong gói, trong suốt
khoảng thời gian Kc. Thêm vào đó, hai phỏng đoán được dùng để giới hạn sự dao
động giữa các tính toán
ˆ liên tiếp nhau.
Sau mỗi khi hàng bị tràn,
ˆ bị giảm bởi 1 phân số nhỏ cố định, chẳng hạn,
0.01.
Để tránh sự điều chỉnh lại, giảm
ˆ 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
ir
Pˆ
ˆ
1,0max
(3.21)
Nếu các gói trong luồng i bị giảm, tốc độ mới i
r của luồng i thay đổi đến xấp
xỉ
ˆ, khi tốc độ đến của luồng i tại router lõi hay biên tiếp theo là xấp xỉ
ˆ. Do đó,
các gói trong luồng i phải được dán nhãn lại với:
old
i
new
ilabellabel ,
ˆ
min
(3.22)
Do đó, sau khi gói đi qua router biên ở phía nhận của luồng đó nhãn của gói
chứa tốc độ luồng hiện tại mà thành phần mạng CSFQ đã cung cấp. Thông tin này
có thể được truyền đến phía nhận và truyền trở lại phía gởi để điều chỉnh tải mà
phía gởi đặt vào mạng. Nhưng CSFQ không cung cấp cơ cấu phản hồi chống tắc
nghẽn rõ. Chỉ có gói bị mất trong router lõi và biên của phần mạng có khả năng
CSFQ được dùng để góp phần khai báo ẩn cho phía gởi về tắc nghẽn (đang đe dọa)
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.
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
ˆ
, nó gởi giá trị này đến TCP phía nhận
để tính cửa sổ gởi mới mà TCP phía gởi cho phép.
Cửa sổ gởi được phép= rRTT
ˆ
. (3.23)
sử dụng RTT ước lượng. Do khả năng song công của TCP, tức là, TCP phía nhận
đồng thời là TCP phía gởi và ngược lại, nó giả thiết rằng TCP phía nhận có sự ước
lượng RTT thích hợp trong đường dẫn mạng. Giá trị nhỏ nhất của cửa sổ gởi và số
bytes hiện thời mà TCP phía nhận có thể được nhận được từ TCP phía gởi là cửa sổ
thông báo phía nhận của TCP phía nhận.
Cửa sổ thông báo phía nhận này được gởi đến TCP phía gởi trong xác nhận
TCP tiếp theo.
3.3.5 QS-TCP (Quick Start TCP):
QS-TCP (Quick Start TCP) đã được đề xuất năm 2002 bởi Jain và Floyd
trong [3] như là một cách để tăng cửa sổ khởi tạo của một kết nối TCP. Trong thủ
tục thiết lập kết nối TCP (TCP SYN và TCP SYN/ACK) phía gởi TCP chèn một
yêu cầu bắt đầu nhanh (Quick Start Request) vào gói TCP, đó chính là tốc độ khởi
tạo mà phía gởi muốn truyền. Mỗi bộ định tuyến dọc theo đường truyền xác nhận
liệu nó có thể đáp ứng yêu cầu lưu lượng mới này. Nếu nó có thể đáp ứng yêu cầu
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.