CHOKe – Sự cải tiến cơ chế hàng đợi của RED
CHOKe – SỰ CẢI TIẾN CƠ CHẾ QUẢN LÝ HÀNG ĐỢI CỦA RED
1. Mở đầu
Ngày nay internet phải đối mặt với sự bùng nổ về số lượng máy tính kết nối
và sự đa dạng của các lớp ứng dụng triển khai trên nó. Quản lý hàng đợi tích
cực là một trong các giải pháp cho điều khiển tránh tắc nghẽn trên Internet.
Trong những năm gần đây, các nhà nghiên cứu về mạng đã đề xuất nhiều cơ
chế quản lý hàng đợi tích cực. Sự phát triển của Internet ngày nay phụ thuộc rất
nhiều vào cơ chế điều khiển tắc nghẽn TCP, tuy nhiên, ngày càng có nhiều ứng
dụng UDP (ví dụ như gói tin âm thanh / video) được truyền đi trên Internet, người
ta không thể dựa vào nhu cầu của người dùng đầu cuối để điều khiển tắc nghẽn
thích hợp. Cơ chế định tuyến phải được cung cấp để bảo vệ luồng thông tin được
đáp ứng từ những người dùng và ngăn chặn bùng nổ lưu lượng. Một số phương
pháp đã được đề xuất cho việc quản lý tài nguyên chia sẻ trên Internet, quản lý
hàng đợi tích cực là một trong những phương pháp chính.
Thông lượng trên Internet có xu hướng biến động theo chiều hướng tham
lam. Lý tưởng nhất là một thuật toán quản lý hàng đợi mà router sẽ cho phép lưu
lượng bùng phát tạm thời, và loại bỏ các luồng có xu hướng liên tục tăng băng
thông, sử dụng quá nhiều băng thông. Ngoài ra, các thuật toán nên có độ phức tạp
nhỏ bằng cách hạn chế chiều dài hàng đợi, giảm tỉ lệ mất mát gói tin bằng cách cho
phép xếp hàng tạm thời, và việc phân bổ tài nguyên hàng đợi một cách công bằng
giữa các loại giao thức truyền tin. Trong thực tế, hầu hết các thiết bị định tuyến
đang được triển khai sử dụng thuật toán đơn giản DropTail, vì nó đơn giản để thực
hiện với chi phí tính toán tối thiểu, nhưng cung cấp hiệu suất không đạt yêu cầu.
Để cải tiến vấn đề này, nhiều thuật toán quản lý hàng đợi được đề xuất,
chẳng hạn như RED (Random Early Drop), FRED (Flow Random Early Drop),
BLUE , SFB (Stochastic Fair BLUE). Hầu hết các thuật toán cho đều có thể cung
cấp chia sẻ công bằng giữa các gói khác nhau mà không áp đặt quá nhiều việc triển
khai phức tạp. Các đề xuất tập trung vào một khía cạnh của vấn đề (sự công bằng,
phức tạp khi triển khai, hoặc chi phí tính toán), hoặc sửa chữa các khiếm khuyết
của các thuật toán trước đó và mô phỏng nó theo những cách thiết lập khác.

: là giới hạn của ngưỡng kích thước hàng đợi cực đại,
min
th
:

là giới hạn của ngưỡng kích thước hàng đợi cực tiểu
max
p
: xác suất rơi cực đại
ω
: là trọng số hàng đợi trong đoạn [0,1], 0
≤
ω
≤
1.
Khi các gói tin bị mất ở hàng đợi tức là có dấu hiệu bộ đệm bị tràn. Vì vậy
ECN có thể nhận ra tắc nghẽn thông qua việc mất gói tin, giúp ích cho việc nâng
cao hiệu năng mạng.
3. Cơ chế quản lý hàng đợi CHOKe
Để cải thiện khả năng RED một cải tiến của RED đã được đề xuất. Cụ thể,
chúng ta thể hiện một thuật toán quản lý hàng đợi hoạt động tương tự RED chỉ
Dương Khắc Hưởng Page 2
CHOKe – Sự cải tiến cơ chế hàng đợi của RED
khác nhau về thuật toán khi chọn những gói tin để cho rơi đó là CHOKe, đơn giản
là thực hiện sự khác biệt gây bất lợi cho luồng hỏng bằng cách cho rơi các gói tin
của luồng đó.
Ý tưởng cơ bản của CHOKe là từ bộ đệm FIFO sẽ xử lý các luồng lưu lượng
hỏng . Khi một gói tin đến một bộ định tuyến xảy ra tắc nghẽn, CHOKe rút ra một
gói tin ngẫu nhiên từ bộ đệm FIFO và so sánh nó với các gói tin đến. Nếu cả hai
đều thuộc về cùng một luồng lưu lượng thì đánh rớt cả hai gói. Ngược lại, các gói

th
thì gói tin được gán một xác suất p.
Nếu kích thước hàng đợi trung bình đạt cực đại max
th
thì đánh rớt gói mới và
kết thúc.
4. Mô phỏng
Để thấy được sự cải tiến cơ chế quản lý hàng đợi CHOKe trong tiểu luận
này tôi sử dụng phần mềm mô phỏng mạng NS2 để mô phỏng các cơ chế quản lý
hàng đợi RED và CHOKe.
Sơ đồ mô phỏng
Sơ đồ gồm 36 nút, trong đó:
+ 17 nút gửi (8 nút TCP, 9 nút UDP);
+ 17 Nút nhận (8 nút TCPShink, 9 nút NUL);
+ 2 nút trung gian;
Thắt nút cổ chai tạo tắc nghẽn giữa đường tryền hai nút trung gian với
Bandwidth = 1Mb/sec và Delay = 2 ms.
Các đường truyền giữa các nút khác có Bandwitdh=1Mb/sec và Delay=5ms
Dương Khắc Hưởng Page 4
CHOKe – Sự cải tiến cơ chế hàng đợi của RED
Dương Khắc Hưởng Page 5
CHOKe – Sự cải tiến cơ chế hàng đợi của RED
Với mô hình như nhau và cùng thông số như nhau đối với RED và CHOKe:
limit_ 20 (giới hạn kích thước cửa sổ)
thresh_ 5 (giới hạn nhỏ nhất của của kích thước hàng đợi TB)
maxthresh_ 20.000000 (giới hạn lớn nhất của của kích thước hàng đợi TB)
mean_pktsize_ 500 (ước lượng kích thước gói tin trung bình tính bằng byte)
q_weight_ 0.002000 (trọng số hàng đợi)
linterm_ 15.000000 (Giá trị nghịch đảo của Max
p

Khi có sự tắc nghẽn thì:
+ Các luồng lưu lượng đáp ứng khi nhận được thông báo nghẽn sẽ giảm tốc
độ gửi dữ liệu;
+ Các luồng lưu lượng không đáp ứng vẫn tiếp tục gửi dữ liệu như bình
thường;
Dẫn đến các luồng không đáp ứng chiếm băng thông nhiều hơn
Đối với RED chỉ cho rơi gói tin khi đến khi số gói tin trong hàng đợi vượt
quá maxth còn đối với CHOKe nếu gói tin đến cùng luồng với một gói tin nào đó
đó được lấy ra ngẫu nhiên trong hàng đợi thì cả hai gói đều bị cho rơi còn khi số
gói tin trong hàng đợi vượt quá maxth thì cơ chế cho rơi gói tin hoàn toàn giống
RED.
Tỷ lệ gói tin mất của CHOKe (86.97%) ít hơn đáng kể so với RED
(87.04%).
Tỷ lệ gói tin rơi của CHOKe (86.83%) ít hơn đáng kể so với RED (86.86%).
Như vậy sự cho rơi sớm gói tin của CHOKe tránh cho hàng đợi nhanh đầy
hơn RED dẫn đến sự tắc nghẽn xảy ra đối với CHOKe chậm hơn RED làm cho
hiệu suất của CHOKe (13.03%) lớn hơn đáng kể so với RED (12.96%).
6. Tài liệu tham khảo
[1] Nguyễn Kim Quốc, Võ Thanh Tú - ĐÁNH GIÁ HIỆU NĂNG CỦA MỘT SỐ
CƠ CHẾ QUẢN LÝ HÀNG ĐỢI TÍCH CỰC DỰA TRÊN KÍCH THƯỚC HÀNG
ĐỢI VÀ TẢI NẠP.
[2] Rong Pan, Balaji Prabhakar, Konstantinos Psounis - A stateless active queue
management scheme for approximating fair bandwidth allocation.
[3] Ao Tang, Student Member, IEEE, Jiantao Wang, and Steven H. Low, Senior
Member, IEEE - Understanding CHOKe: Throughput and Spatial Characteristics
Dương Khắc Hưởng Page 10