người dùng 2. Tất cả sự phân phối với x1+x2=Xgoal là phân phối có hiệu quả. Nó
tương ứng với đường thẳng là “đường hiệu quả” (efficiency line). Tất cả phân phối
mà x1= x2 là phân bố bình đẳng. Nó tương ứng với đường thẳng được gọi là “đường
bình đẳng” (fairness line). Hai đường này cắt nhau tại điểm (Xgoal/2, Xgoal/2) là điểm
tối ưu. Mục tiêu (goal) của phương pháp điều khiển là làm cho hệ thống đến hoạt
động tại điểm này mà không quan tâm đến vị trí bắt đầu. Tất cả các điểm bên dưới
đường hiệu quả mô tả hệ thống “không đủ tải”(underload) và một cách lý tưởng hệ
thống sẽ yêu cầu người dùng tăng tải. Theo quan sát, chẳng hạn, điểm x0=(x10, x20).
Nguyên tắc tăng cộng tăng phân phối của cả 2 người dùng bởi a1 tương ứng với việc
dịch chuyển dọc đường tạo với trục ngang góc 45 0. Nguyên tắc tăng nhân tăng
phân phối cho cả 2 người dùng bằng hệ số b1 tương ứng với việc dịch theo đường
nối điểm đó với gốc toạ độ. Tương tự, tất cả các điểm trên đường hiệu quả mô tả hệ
thống quá tải (overload) và giảm cộng mô tả bởi đường tạo với trục ngang góc 45 0,
khi giảm nhân được mô tả bởi đường nối điểm đó với gốc.
Tính bình đẳng tại điểm bất kỳ (x1, x2) được cho bởi:
2
2
2
1
2
21
2xx
xx
F
Chú ý rằng nhân cả hai phân bố với hệ số b không thay đổi tính bình đẳng.
Đó là, (bx1,bx2) có cùng tính bình đẳng với (x1, x2) cho tất cả các giá trị của b. Do
đó, tất cả các điểm trên đường nối điểm đó với gốc có cùng tính bình đẳng. Chúng
ta, gọi đường đi qua gốc là đường “đồng đẳng” (equi-fairness). Tính bình đẳng
giảm khi độ dốc của đường này hoặc tăng lên trên hoặc giảm xuống dưới đường
bình đẳng.
Hình 2.8 cho ta thấy quỹ đạo của hệ thống 2 người dùng bắt đầu từ điểm x0
dùng nguyên tắc điều khiển tăng cộng/giảm nhân. Điểm x0 nằm dưới đường hiệu
quả và do đó cả hai người dùng đều được yêu cầu tăng. Chúng di chuyển dọc đường
tạo với trục ngang góc 450. Nó di chuyển đến x1 nằm trên đường hiệu quả. Người
dùng được yêu cầu giảm và thực hiện phép nhân, tương ứng với việc chuyển động
đến điểm gốc trên đường nối x1 và gốc. Nó di chuyển đến điểm x2, nằm dưới đường
hiệu quả và lập lại theo chu kỳ. Chú ý rằng x2 có tính bình đẳng cao hơn x0. Do đó,
với mỗi chu kỳ, tính bình đẳng tăng chậm, và cuối cùng, hệ thống hội tụ đến trạng
thái tối ưu, dao động quanh điểm “goal”.
Quỹ đạo tương tự có thể vẽ cho nguyên tắc điều khiển khác. Mặc dù không
phải tất cả các nguyên tắc điều khiển đều hội tụ. Chằng hạn, hình 2.9 cho ta thấy
quỹ đạo của nguyên tắc điều khiển tăng cộng/giảm cộng AIAD bắt đầu từ vị trí x0.
Hệ thống giữ chuyển động lùi và đến dọc theo đường qua điểm x0, tạo với trục
ngang góc 45 0. Với nguyên lý như thế, hệ thống có thể hội tụ đến hiệu quả, nhưng
nó không bình đẳng.
Đường bình đẳng
Đường hiệu quả
Phân
bố x2
của
người
dùng 2
Hình 2.8 AIMD hội tụ đến điểm tối ưu
Hình 2.9 AIAD không hội tụ
Đường bình đẳng
Đường hiệu quả
Phân
bố x2
của
người
dùng
thứ 2
Phân bố x1 của người dùng 1
Điểm làm việc dao
đ
ộng
d
ọc
đư
ờng
n
ày
Điều kiện để hội tụ đến hiệu quả và bình đẳng được đưa ra theo phương pháp
đại số trong [7].
2.6 Kết luận chương
Hiện tượng tắc nghẽn xảy ra trong mạng là vấn đề khó tránh khỏi, do đó điều
khiển tắc nghẽn ngày càng trở nên cấp thiết. Chương 2 đã nêu tổng quan về nguyên
lý, phân loại các phương pháp điều khiển tắc nghẽn, tiêu chí đánh giá những
phương pháp điều khiển. Ngoài ra, thuật toán tăng giảm (ở đây chỉ nói đến tăng
giảm tuyến tính) cũng đã đề cập đến. Từ đó, ta thấy rằng AIMD được sử dụng nhiều
hơn các thuật toán khác do nó đảm bảo hội tụ đến tính hiệu quả và bình đẳng. Phần
tiếp theo sẽ đi sâu vào các phương pháp điều khiển tắc nghẽn.
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 ẩn. 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ước cửa sổ được tăng lên theo phép
cộng.
DECbit là phương pháp khá đơn giản và hữu hiệu. Tuy nhiên, căn cứ vào các
tiêu chí nêu trên thì thuật toán này không đạt được tính hiệu quả vì lưu lượng bị gạt
bỏ đáng kể (qua hệ số 0,875) dẫn đến thông lượng rất thấp. Ngoài ra, các tiêu chí về
tính bình đẳng, độ hội tụ, độ mịn điều khiển cũng không đạt được. Thuật toán
không phù hợp cho các ứng dụng mới trong NGN.