Tìm hiểu thuật toán quản lý hàng đợi tích cực BLUE
MỤC LỤC
MỤC LỤC 1
1
Tìm hiểu thuật toán quản lý hàng đợi tích cực BLUE
I GIỚI THIỆU
Để ngăn chặn tỷ lệ mất gói tin ngày càng tăng do sự gia tăng hàm mũ trong lưu lượng
mạng, IETF đã xem xét và triển khai thông báo tắc nghẽn mà không rơi gói (ECN) cùng
với các kỹ thuật quản lý hoạt động hàng đợi như RED (Random Early Detection).
Trong khi ECN (Explicit Congestion Notification) là cần thiết để loại bỏ mất gói tin
trong mạng Internet, chúng tôi chỉ ra rằng RED, ngay cả khi sử dụng kết hợp với ECN, là
không hiệu quả trong việc ngăn ngừa mất gói tin.
Ý tưởng cơ bản của quản lý hàng đợi RED là để phát hiện sớm tắc nghẽn để chuyển tải
thông báo tắc nghẽn đến các trạm cuối, cho phép giảm tỷ lệ truyền trước khi tràn hàng đợi
trong mạng và các gói dữ liệu bị rơi.
Để làm điều này, RED duy trì một mức độ thay đổi chiều dài trung bình của hàng đợi -
mà nó sử dụng để nhận ra sự tắc nghẽn - có trọng số theo hàm mũ(exponentially-
weighted).
Khi chiều dài hàng đợi trung bình vượt quá một ngưỡng tối thiểu (min
th
), các gói được
ngẫu nhiên bị bỏ rơi hoặc đánh dấu bằng một thông báo tắc nghẽn mạng (ECN). Khi chiều
dài hàng đợi trung bình vượt quá một ngưỡng tối đa, tất cả các gói dữ liệu bị rơi hoặc được
đánh dấu.
Một trong những vấn đề cơ bản với kỹ thuật quản lý RED và các hoạt động hàng đợi
là dựa vào chiều dài hàng đợi như là một ước tính của tắc nghẽn. Trong khi sự có mặt của
một hàng đợi là đòi hỏi của tắc nghẽn, chiều dài của nó cho phép thông tin rất ít dẫn đến
mức độ nghiêm trọng của tắc nghẽn, nghĩa là, số lượng kết nối cạnh tranh đang chia sẻ liên
kết. Từ kết quả nổi tiếng trong lý thuyết xếp hàng, đó là các gói tin xung đột tuân theo mô
hình phân phối Poisson, độ dài hàng đợi liên quan trực tiếp tới số lượng các nguồn hoạt
động, và mức độ của tắc nghẽn.

bit ECN của họ thiết lập. Đáp lại, dupliCate acknowlegdements và / hoặc TCP dựa trên
ECN tín hiệu được đưa trở lại các nguồn. Tại t = 5, các duplicate acknowlegements và /
hoặc ECN tín hiệu thực hiện theo cách của nó là trở về nguồn để báo hiệu tắc nghẽn.
Tại t = 6, các nguồn cuối cùng đã phát hiện tắc nghẽn và điều chỉnh tỷ lệ truyền dẫn
của. Cuối cùng, tại t = 7, một giảm tải được cung cấp tại liên kết nút cổ chai đã được Quan
sát.
3
Tìm hiểu thuật toán quản lý hàng đợi tích cực BLUE
Hình 1: Ví dụ về RED
I. BLUE
Để khắc phục những thiếu sót của RED, chúng ta đề xuất, thực hiện và đánh giá một
thuật toán quản lý hàng đợi cơ bản khác, đó là BLUE.
Sử dụng cả mô phỏng và thử nghiệm, cho thấy BLUE vượt qua nhiều thiếu sót của RED.
RED đã được thiết kế với mục tiêu (1) giảm thiểu mất gói tin và độ trễ của hàng đợi, (2)
tránh đồng bộ hóa toàn cầu về nguồn, (3) duy trì sử dụng liên kết cao, và (4) loại bỏ xu
hướng chống lại quá tải nguồn. Phần này cho thấy cách BLUE kết hợp cải thiện hiệu suất
của RED trong tất cả các khía cạnh. Các kết quả cũng cho thấy rằng BLUE hội tụ thuật
toán lý tưởng thể hiện trong hình 1 (b) ở hầu hết các kịch bản, ngay cả khi được sử dụng
với bộ đệm rất nhỏ.
Thuật toán
4
Tìm hiểu thuật toán quản lý hàng đợi tích cực BLUE
Ý tưởng chính đằng sau thuật toán quản lý hàng đợi BLUE là dựa trực tiếp trên sự mất
gói tin và việc sử dụng các liên kết hơn là trên các độ dài trung bình hàng đợi tức thời.
Điều này tương phản sắc nét với tất cả các kỹ thuật quản lý hàng đợi đã được sử dụng
trong điều khiển tắc nghẽn trước đó. BLUE duy trì một xác suất duy nhất, p
m
, mà nó sử
dụng để đánh dấu (hoặc làm rơi) các gói dữ liệu khi chúng được cho vào hàng. Nếu hàng
đợi liên tực rơi gói tin do tràn bộ nhớ đệm, BLUE tăng xác suất đánh dấu p

nhiên đã được bắt đầu trong vòng 1 giây đầu tiên của mô phỏng, và được sử dụng 1kB gói
dữ liệu. Gói dữ liệu thống kê thiệt hại sau đó đã được đo sau 100 giây của mô phỏng.
Thống kê mất gói dữ liệu cũng được đo cho RED bằng cách sử dụng mạng tương tự với
điều kiện giống hệt nhau. Đối với hàng đợi RED, min
th
và max
th
đã được thiết lập tới 20%
và 80% kích thước hàng đợi tương ứng. Kỹ thuật thông báo tắc nghẽn của RED đã được
thực hiện như là tích cực nhất có thể bằng cách thiết lập max
p
đến 1.
Hình 4: Kiến trúc mạng
Đối với những thí nghiệm này, điều lý tưởng của max
p
là nó giảm thiểu cả độ trễ của
hàng đợi và tỷ lệ mất gói cho RED [9]. Đưa ra các cài đặt này, một loạt các cấu hình RED
được nghiên cứu trong đó thay đổi giá trị của w
q
, là kích thước hàng đợi trung bình của
RED. Đáng lưu ý rằng, khi w
q
được thiết lập tương đối nhỏ, ảnh hưởng của chiều dài hàng
đợi đối với thuật toán quản lý hàng đợi RED cũng trở nên nhỏ hơn. Đối với các giá trị vô
cùng nhỏ của w
q
, thuật toán RED trở nên tách biệt khỏi chiều dài hàng đợi (không phụ
thuộc vào chiều dài hàng đợi) và do đó nó hoạt động gần giống với BLUE.
Bảng 1 cho thấy các cấu hình được sử dụng cho RED. Đối với những thí nghiệm
BLUE, δ1 và δ2 được thiết lập sao cho δ1 lớn hơn δ2 rất nhiều. Sử dụng các giá trị này,

là 1 và độ trễ của hàng đợi tương đương với max
th
. Đây là trạng thái duy nhất của hoạt
động ngay lập tức bị gián đoạn bởi bất kỳ thay đổi trong tải hoặc round-trip-time. Khi độ
trễ của bộ đệm tăng lên, round-trip-time tương ứng tăng và gây ra giao thức TCP ít linh
hoạt hơn.
Hiểu BLUE
Hình 6: Biểu đồ hàng đợi của RED và BLUE
Để hoàn toàn hiểu sự khác biệt giữa các thuật toán RED và BLUE, hình 6 so sánh
chiều dài hàng đợi của chúng trong một thử nghiệm bổ sung bằng cách sử dụng các cấu
hình B4 của BLUE và cấu hình R2 của RED.
8
Tìm hiểu thuật toán quản lý hàng đợi tích cực BLUE
Trong thử nghiệm này, lưu lượng của các nguồn được thay đổi bằng cách tăng số
lượng kết nối lên 200 cứ sau mỗi 20 giây. Như Hình 6 (a) cho thấy, RED mất gói liên tục
trong suốt thử nghiệm. Ngoài ra, ở tải thấp hơn, thời gian mất gói thường kéo theo là thời
gian sử dụng đường truyền với hiệu quả thấp như xác định gói dữ liệu đánh dấu và loại bỏ
chúng, để các nguồn gửi giảm tốc độ truyền các gói tin. Ngược lại, như hình 6 (b) cho
thấy, khi BLUE quản lý mức độ đánh dấu của nó thông minh hơn, đồ thị chiều dài hàng
đợi của nó là ổn định hơn. Thông báo tắc nghẽn được gửi với một tốc độ mà ở đó không
gây ra thời gian mất gói kéo dài thời gian sử dụng đường truyền hiệu quả liên tục hơn. Chỉ
khi tải cung cấp tăng lên đến 800 kết nối, thì mới xảy ra hiện tượng mất gói tin ở BLUE.
II. KẾT QUẢ MÔ PHỎNG
Dựa trên những nghiên cứu về giải thuật quản lý hàng đợi tích cực Blue, nhóm chúng
tôi đã tiến hành mô phỏng bằng phần mềm NS2 version: 2.34 trên hệ điều hành Ubuntu
9.10 và được một số kết quả ban đầu như sau:
a) Cấu trúc mạng:
Số lượng nút: 28
9
Tìm hiểu thuật toán quản lý hàng đợi tích cực BLUE

93
525
119
310
76
448
78
488
Bảng 2-2: Kết quả thực hiện mô phỏng sử dụng BLUE
(có hoặc không sử dụng ECN)
c) Nhận xét:
Bằng việc thực hiện mô phỏng nói trên nhóm chúng tôi nhận thấy rằng: BLUE là
một giải thuật quản lý hàng đợi tích cực mạnh hơn RED về việc giảm tỷ lệ rơi và mất gói
tin. Trong trường hợp số lượng nút trong mạng rất lớn thì BLUE càng thể hiện sự vượt
trội so với RED. Ví dụ: với mạng được thiết kế gồm 2002 nút (2 nút cổ chai) thì số lượng
mất và rơi gói tin được thể hiện trong bảng sau:
11
Tìm hiểu thuật toán quản lý hàng đợi tích cực BLUE
RED BLUE
Số lượng gói tin rơi 10470 6470
Số lượng gói tin mất 10507 6542
III.KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Chúng tôi đã chỉ ra sự yếu kém vốn có của thuật toán quản lý hàng đợi hiện nay đang
hoạt động. Mục đích của vấn đề này, chúng tôi đã thiết kế và đánh giá một quy tắc cơ bản
khác của thuật toán quản lý hàng đợi đó là BLUE. BLUE sử dụng mất gói và lịch sử sử
dụng liên kết của hàng đợi tắc nghẽn, thay vì độ dài hàng đợi để quản lý tắc nghẽn.
Trong tương lai, nhóm cũng mong muốn mở rộngviệc nghiên cứu, đánh giá một cách
toàn diện về BLUE và hiệu quả của nó so với các giải thuật quản lý hàng đợi khác để có
thể áp dụng BLUE trong thực tế.
Đồng thời nhóm cũng muốn nghiên cứu giải thuật quản lý hàng đợi SFB (Stochastic