Số hóa bởi Trung tâm Học liệu

P

Trang 1

ĐẠI HỌC THÁI NGUN
TRƢỜNG ĐẠI HỌC KỸ THUẬT CƠNG NGHIỆP
LUẬN VĂN THẠC SĨ KỸ THUẬT
NGÀNH: PHÂN TÍCH ĐÁNH GIÁ

MỘT SỐ THUẬT TỐN QUẢN LÝ HÀNG ĐỢI


LUẬN VĂN THẠC SĨ KỸ THUẬT PHÂN TÍCH ĐÁNH GIÁ MỘT SỐ THUẬT TỐN

QUẢN LÝ HÀNG ĐỢI TÍCH CỰC TRONG TCP NETWORK 23 Ngành:
Mã số: 60.52.70
Học viên:
Người HD Khoa học: PGS.TS

THÁI NGUN – 2012
Số hóa bởi Trung tâm Học liệu

P


Số hóa bởi Trung tâm Học liệu

P

Trang 4
1.1: Kiến trúc mạng đơn giản
nó sẽ chuyển các gói tin đến thẳng thiết bị thu. Nếu khơng phải nối trực tiếp, bộ
định tuyến này sẽ chuyển gói tin đến một bộ định tuyến khác mà nó biết được qua
q trình phân tích thơng tin theo lộ trình ở trên. Q trình như vậy được lặp lại cho
đến khi gói tin được chuyển đến một bộ định tuyến được kết nối trực tiếp với thiết
bị thu và được chuyển đến đích cuối cùng.
Trong một hệ thống mạng, một bộ định tuyến (router) thường có nhiều giao diện
mạng gắn với những mối liên kết khác nhau như trong hình 1.2. Những liên kết này
dùng để kết nối với các bộ định tuyến khác hay kết nối với các mạng con
(subnetwork). Một router sau khi nhận được một gói tin sẽ sử dụng địa chỉ nơi nhận
và dữ liệu thơng tin lộ trình của gói tin để xác định liên kết đầu ra cho gói tin đó.
Khi có nhiều gói tin từ nhiều nguồn khác nhau cùng đến router với một lộ trình đầu
ra giống nhau thì chỉ có duy nhất một gói tin được đáp ứng còn các gói tin còn lại bị
đẩy vào một hàng đợi tại mối liên kết đầu ra mà chúng u cầu. Khi nhịp độ đến
router của các gói tin như vậy tăng lên, chúng sẽ tiếp tục được đưa vào hàng đợi đó.
Thơng thường, hàng đợi này sẽ được duy trì với cơ chế FIFO (first in first out).
Với cơ chế này thì những gói tin đến sau sẽ được xếp vào cuối hàng đợi. Nếu mức
độ chuyển các gói tin đi của router lớn hơn mức độ các gói tin khác đến router thì
sau một khoảng thời gian nào đó hàng đợi sẽ trở nên rỗng. Ngược lại, nếu mức độ
chuyển các
gói tin đi nhỏ hơn mức độ các gói tin khác đến router thì sau một khoảng thời gian
hàng đợi sẽ đầy. Khi đó, router sẽ phải loại bỏ các gói tin theo một cơ chế nào đó,

quan trọng là phải điều khiển được tắc nghẽn trong mạng. Đó có thể là hành động
điều khiển để phòng tránh tắc nghẽn và cũng có thể là điền khiển tắc nghẽn khi nó
đã xảy ra.
1.2.2. Các kỹ thuật được sử dụng trong quản lý tắc nghẽn
- Điều khiển luồng phía đầu cuối: đây khơng phải lược đồ điều khiển tắc nghẽn
nhưng cũng là cách để tránh trường hợp phía phát gửi q nhiều lưu lượng vượt qua
cả khơng gian bộ đệm chia thu.
Số hóa bởi Trung tâm Học liệu

P

Trang 6
- Điều khiển tắc nghẽn mạng: trong lược đồ này, các hệ thống đầu cuối giảm tốc
độ của luồng lưu lượng để tránh tắc nghẽn trong mạng, cơ chế này tương tự như
điều khiển luồng đầu cuối, nhưng mục đích chính là để giảm tắc nghẽn trong mạng
chứ khơng phải phía thu.
- Tránh tắc nghẽn trên cơ sở mạng: trong lược đồ này, router sẽ cố gắng dò tìm
ra tắc nghẽn khi nó có khả năng xảy ra, và cố gắng giảm tốc độ của luồng đầu vào
trước khi hàng đợi đầy.
- Phân phối tài ngun: kỹ thuật bao gồm tiến trình lập lịch có sử dụng các mạch
vật lý hoặc các luồng tài ngun khác. Một mạch ảo được xây dựng qua nhiều
chuyển mạch cùng với băng thơng đảm bảo cũng là một loại phân phối tài ngun.
Kỹ thuật này rất khó nhưng nó có khả năng loại trừ tắc nghẽn trong mạch bằng việc
khóa các lưu lượng vượt q khả năng của mạng.
Giải pháp quan trọng nhất trong điều khiển tắc nghẽn đó là sử dụng kỹ thuật
quản lý hàng đợi. Các bộ đệm trong các thiết bị mạng được quản lý bởi rất nhiều kỹ
thuật hàng đợi. Nói đúng ra quản lý hàng đợi có thể tối thiểu hóa việc mất gói trong

Thơng thường khi một host nhận một gói hoặc một tập các gói thì nó sẽ gửi một
ACK (acknowlegement) cho phía phát để thơng báo là đã nhận được gói tin. Cơ chế
cửa sổ cho phép host nhận đa gói tin mà chỉ dùng một ACK. Việc phía gửi khơng
nhận được ACK chứng tỏ rằng phía thu bị tràn bộ đệm hoặc mạng bị nghẽn do đó
phía phát phải dừng việc chuyển gói hoặc giảm tốc độ.
Một chiến lược được đưa ra là “Giảm theo cấp số nhân, tăng theo cấp số cộng”
để điều chỉnh số lượng các gói đến trong cùng một thời điểm. Nếu vẽ lược đồ về
luồng dữ liệu ta sẽ thấy số lượng các gói tăng lên cho đến khi có tắc nghẽn xuất
hiện trong mạng (tăng theo cấp số cộng) và khi gói bắt đầu bị loại bỏ thì ta giảm
nhanh các gói truyền cho đến khi việc truyền gói bắt đầu dừng (giảm theo cấp số
nhân). Kích thước cửa sổ sẽ lần lượt giảm một nửa khi có tắc nghẽn xảy ra. Các
host sẽ tìm ra tốc độ truyền dẫn tối ưu bằng việc thường xun kiểm tra mạng với
tốc độ cao hơn. Thỉnh thoảng tốc độ truyền cao hơn này được chấp nhận nhưng khi
mạng bận thì các gói bắt đầu bị loại bỏ và host lại quay trở lại tốc độ ban đầu. Lược
đồ này coi mạng như một hộp đen loại bỏ các gói khi có tắc nghẽn. Do đó điều
khiển tắc nghẽn được thực hiện bới các hệ thống đầu cuố
gói là để chỉ thị tắc nghẽn. Phía người gửi sẽ truyền một số lượng lớn các file để
đẩy lên tốc độ cao hơn cho tới khi nó đạt được tất cả băng thơng. Các host khác có
thể gặp vài vấn đề khi chuyển gói qua mạng. Các host bị túm lấy băng thơng thì chỉ
truyền tải được rất ít lưu lượng quan trọng.
Số hóa bởi Trung tâm Học liệu

P

Trang 8
Tất nhiên, mạng có thể sử dụng vai trò tích cực trong điều khiển tắc nghẽn. Cơ
chế điều khiển và tránh tắc nghẽn có thể chia ra thành các q trình:
P

Trang 9
tục tại phía phát cho đến khi khơng nhận được phản hồi ACK. Việc chỉ thị này cho
thấy khả năng xử lý lưu lượng của mạng hoặc khả năng xử lý lưu lượng tới của phía
thu.
Khởi đầu chậm khơng có khả năng ngăn chặn tắc nghẽn mà nó chỉ giúp cho các
host tránh được trạng thái tắc nghẽn tạm thời. Nếu một host gửi q nhiều gói thì nó
sẽ gây ra nghẽn mạng, tràn bộ đệm và các gói sẽ bị loại bỏ. Nhưng trong một số ứng
dụng mới như: thoại qua IP thì khơng thể chấp nhận được trễ gây ra bởi việc khởi
đầu chậm, do đố trong một số trường hợp thì mạng sẽ khơng sử dụng kiểu này:
- Khơi phục và truyền lại nhanh:
Truyền lại và khơi phục lại nhanh là các thuật tốn được thiết kế để tối thiểu hóa
việc loại bỏ gói khi truyền trong mạng. Cơ cế truyền lại nhanh suy luận từ cơ chế
truyền TCP. Phía thu sẽ gửi các báo hiệu tới phía gửi rằng nó nhận được các gói
khơng theo trật tự. Kỹ thuật này sẽ phải gửi rất nhiều bảo sao ACK tới phía phát.
Đây là cách để chỉ thị cá gọi bị mất. Thay cho việc chờ đợi phản hồi ACK cho đến
khi hết thời gian thì nguồn gửi sẽ tự phát lại gói khi nhận được 3 bản sao ACK.
Việc này xảy ra trước khi thời gian hết hạn do đó chúng cải thiện được khả năng
thơng qua của mạng. Ví dụ khi một host nhận được gói thứ 5 và 7 (mà khơng nhận
được gói thứ 6) thì nó sẽ gửi phản hồi ACK cho gói thứ 5 khi nó nhận được gói thứ
7.
Khơi phục nhanh là cơ chế thay thế cho kiểu khởi đầu chậm khi truyền lại nhanh
được sử dụng. Các ACK vẫn tiếp tục được truyền để chỉ thị có bị mất gói hay khơng
cho tới khi phía nguồn nhận được ACK có số thứ tự cao hơn gói bị mất. Trong
trường hợp đó có nghĩa là có một gói đơn bị mất và mạng khơng bị nghẽn hồn
tồn. Do đó phía phát khơng cần thiết phải quay trở lại khởi động chậm ngay lập tức
mà chỉ cần giảm tốc độ truyền xuống bằng một nửa so với tốc độ ban đầu.

IP.
Hình 1.3. Mơ hình hàng đợi đơn giản trong mạng
Số hóa bởi Trung tâm Học liệu

P

Trang 11
Tin tức (có thể là gói tin hay bản tin) đến hệ thống để u cầu phục vụ. Nếu
server rỗi thì gói tin sẽ được phục vụ ngay lập tức, ngược lại chúng sẽ được lưu giữ
trong các hàng đợi. Khi rời khỏi hàng đợi các gói sẽ được xử lý.
Các tham số cơ bản liên quan tới hàng đợi:
Bảng 1.1: Bảng các tham số cơ bản của hàng đợi

Tham số
Kí hiệu
Chú thích
Tốc độ đến TB


Thời gian TB giữa thời điểm gửi gói
tới server và thời điểm rời khỏi server
Độ dài hàng đợi TB
L
q
Số gói trung bình trong hệ thống, bao
gồm các gói đang được sử dụng và các gói
đang chờ trong hàng đợi.
Thời gian xếp hàng TB
T
q
Thời gian các gói ở trong hệ thống

Số hóa bởi Trung tâm Học liệu

P

Trang 12
Các gói đến hàng đợi với tốc độ thay đổi và đây là một q trình poisson, thời
gian phục vụ có phân bổ mũ tốc độ µ (thực chất là thời gian trung bình mà các gói
tin rời khỏi hàng đợi). Khi các gói đến hệ thống tăng thì hiệu suất sử dụng hệ thống
cũng tăng, dẫn tới tắc nghẽn có khả năng xảy ra. Với p = 1 thì các server bão hòa do
đó tốc lớn nhất theo lý thuyết mà hệ thống có thể xử lý được là:
max
=1/Ts
Tại
max


P

Trang 13
Các thuật tốn lập tích vòng mờ quyết định xem gói nào sẽ được gửi kế tiếp.
Thuật tốn này quyết định trật tự các gói truyền dẫn trên cơ sở trật tự sắp xếp các
gói đến và các lớp lưu lượng ưu tiên trong gói.
Dịch vụ phân biệt sử dụng 3 bit trong tiêu đề mỗi gói để định nghĩa lớp. Q
trình lập lịch của gói điều khiển trật tự truyền dẫn giống như phân bố băng thơng
tương ứng cho mỗi lớp dịch vụ. Lập lịch bao gồm các thuật tốn liên quan tới hàng
đợi: hàng đợi FIFO, hàng đợi cân bằng có trọng số WFQ, và các thuật tốn lập lịch
như: Thuật tốn RR, thuật tốn PS.

Hình 1.4: Tiến trình xử lý hàng đợi trong router
Để hiểu rõ về các hàng đợi được sử dụng trong có chế điều khiển tắc nghẽn ta
phải trả lời các câu hỏi:
- Các gói sẽ được sắp đặt như thế nào trong hàng đợi:
- Thứ tự hay cách thức nào mà các thiết bị mạng phục vụ các hàng đợi của
chúng?
- Các hoạt động nào cảu mạng để đối xử với các bó lưu lượng và hàng đợi bị
tràn?
Ở ví dụ mơ tả trong hình 1.4, router được xem như hộp lớn, trong đó có các
thành phần thực hiện việc truyền thơng tin. Trong ví dụ này ta xét router có 2 giao
diện. Gói tin đi từ mạng A tới mạng B. Mạng A tiếp xúc với router qua giao diện
IF0, mạng B tiếp xúc với router qua giao diện IF1. Sau khi các gói được đưa đến từ
giao diện IF0 sẽ được đặt vào trong h đợi queue 0 (hàng đợi đầu vào). Tiếp theo
Số hóa bởi Trung tâm Học liệu

- Loại bỏ gói nếu hàng đợi đã đầy.
- Xóa bỏ gói khi được u cầu bởi bộ lập lịch.
- Thường xun quản lý độ chiếm giữ của hàng đợi.
Số hóa bởi Trung tâm Học liệu

P

Trang 15
- Loại bỏ gói khi hàng đợi đã đầy.
- Đánh dấu các gói khi hàng đợi chuẩn bị đầy.
- Sự cần thiết của quản lý hàng đợi
Mục đích chính của hàng đợi là điều khiển lưu lượng, chống tắc nghẽn trong
mạng, đặc biệt là tại các nút cổ chai. Kỹ thuật quản lý hàng đợi trước đây là thiết lập
một kích thước hàng đợi lớn nhất cho mỗi hàng đợi, các gói sẽ được đưa vào trong
hàng đợi cho đến khi hàng đợi đầy sau đó nếu còn có gói đến thì sẽ loại bỏ các gói
mới tới nay. Khi số lượng các gói trong hàng đợi giảm do được truyền tới chặng
tiếp theo thì lúc đó hàng đợi mới nhập tiếp các gói tới. Đây cũng chính là kĩ thuật
“loại bỏ phần đi” (drop tail). Tuy nhiên cách này có 2 hạn chế:
- Kĩ thuật này chỉ cho phép các gói từ một kết nối đơn hoặc một vài luồng đủ để
chiếm dụng khơng gian hàng đợi, ngăn chặn khơng cho các kết nối khác cùng đến
một hàng đợi. Kĩ thuật này là kết quả của q trình đồng bộ hoặc có hiệu quả định
thời.
- Thường thì các luồng lưu lượng đến hàng đợi dưới dạng bó. Khi hàng đợi đầy
thì bất kì luồng nào đến cũng đều bị loại bỏ cho tới khi số gói trong hàng đợi giảm
xuống. Kĩ thuật này sẽ loại bỏ các bó thơng tin chứ khơng phải chỉ là các gói, do đó
việc mất mát thơng tin là rất lớn.
Quản lý hàng đợi có các tính năng sau:

CÁC PHƢƠNG PHÁP QUẢN LÝ HÀNG ĐỢI TÍCH CỰC
2.1. Tổng quan
2.1.1. Khái niệm quản lý hàng đợi tích cực AQM (Active Queue Managament)
Quản lý hàng đợi tích cực (AQM) là một cơ chế phát hiện sự tắc nghẽn trong hệ
thống mạng. Những giải thuật quản lý hàng đợi tích cực chạy bên trong nh ng bộ
định tuyến và phát hiện sự hình thành tắc nghẽn điển hình bằng cách theo dõi chiều
dài hàng đợi tức thời hay chiều dài hàng đợi trung bình. Khi kích thước hàng đợi
trung bình vượt q một ngưỡng nhất định nhưng vẫn còn ít hơn khả năng xử lý của
hàng đợi, những giải thuật quản lý hàng đợi tích cực xem xét sự tắc nghẽn trên mối
liên kết và thơng báo trở lại cho những hệ thống bằng cách thả một số gói tin
chuyển đến bộ định tuyến. Các giải thuật AQM có thể cũng đặt một bit vào header
của một gói tin nào đó rồi chuyển nó về phía thiết bị nhận của gói đó sau khi sự tắc
nghẽn được phát hiện. Khi thiết bị thu nhận được gói tin đã được đánh dấu này, nó
sẽ gửi trở lại bên phát gói tin đó một bit khác trong phiên làm việc giữa nó và bên
phát. Khi bên phát nhận được tín hiệu này, nó sẽ giảm bớt tín hiệu truyền dữ liệu.
Q trình đặt một bit đặc biệt trong header của gói tin bởi những giải thuật AQM và
việc chuyển gói tin đã được đánh dấu đó đến bên nhận gọi là sự đánh dấu (mark).
Gói tin chứa bit đặc biệt trong q trình trên gọi là gói tin đánh dấu. Những hệ
thống trải qua việc bị đánh dấu hoặc bị mất mát gói tin sẽ giảm nhịp độ truyền dữ
liệu để giải tỏa sự tắc nghẽn và ngăn việc tràn hàng đợi.
Mục tiêu quan trọng nhất cảu các giải thuật AQM là ngăn ngừa sự tắc nghẽn
trước khi nó thực sự xuất hiện. Như vậy, việc sử dụng hiệu quả các giải thuật quản
lý hàng đợi sẽ đem lại những hiệu quả đó là: giảm bớt sự mất mát các gói tin, đạt
được một lưu lượng truyền dữ liệu cao và một độ trễ hàng đợi thấp. Điều này thật
sự là một cải thiện rất tốt cho những ứng dụng tương tác như duyệt Web hay các
cuộc hội thoại trực tiếp.
Một mục tiêu quan trọng khác của quản lý hàng đợi tích cực là quản lý tắc
nghẽn với u cầu ngăn ngừa sự đồng bộ hóa tồn cục (global synchronization)
Số hóa bởi Trung tâm Học liệu


loại bỏ. Điều này có thể dẫn đến một sự đồng bộ hóa ở phạm vi lớn các gói tin đến
sau, làm cho lưu lượng tồn bộ q trình giảm. Full Queue gây lên trạng thái khơng
ổn định trong hàng đợi.
Một cơ chế quản lý hàng đợi tích cực có thể đem lại những ưu điểm sau:
Số hóa bởi Trung tâm Học liệu

P

Trang 19
- Giảm bớt những gói tin bị loại bỏ trong router. Các gói tin đến dạng bó là một
khía cạnh khơng thể tránh được của mạng gói. Nếu tất cả khơng gian hàng đợi trong
router đã trạng thái chuyển vận ổn định, hay nếu khơng gian bộ đệm khơng đủ,
router sẽ khơng có khả năng xử lý các bó gói tin. Bằng việc giữ cho kích thước
hàng đợi trung bình nhỏ, quản lý hàng đợi tích cực sẽ cung cấp khả năng lớn hơn để
giảm bớt các gói bị loại bỏ trong q trình chuyển vận. Hơn nữa, nếu như khơng có
quản lý hàng đợi tích cực thì sẽ có nhiều gói tin bị loại bỏ khi hàng đợi bị tràn đầy.
Đây là một hạn chế cho hàng đợi bởi các lý do:
- Với một hàng đợi dùng chung, một sự đồng bộ hóa các gói tin bị loại bỏ dẫn
đến hiệu quả thấp hơn trong việc sử dụng mối liên kết trung bình và làm giảm lưu
lượng mạng.
- Làm cho q trình phục hồi của hệ thống khó khăn hơn.
- Đó là một sự tiêu phí băng thơng một cách khơng cần thiết.
- Giảm độ trễ dịch vụ: bằng việc giữ cho kích thước hàng đợi trung bình nhỏ,
quản lý hàng đợi sẽ giảm bớt độ trễ giữa các luồng dữ liệu.
. Tránh hiện tượng Knock-out: Quản lý hàng đợi tích cực sẽ gần như ln ln
đảm bảo một bộ đệm sẵn có cho các gói tin được chuyển tới hàng đợi. Hàng đợi
tích cực sẽ có thể ngăn ngừa một sự thiên lệch trong router chống lại việc giải thơng


Hình 2.1: Phân loại các phương pháp quản lý hàng đợi tích cực
2.2. Quản lý hàng đợi tích cực dựa trên chiều dài hàng đợi
2.2.1. Cơ chế ECN (Explicit Congestion Notification)
2.2.1.1. Khái niệm chung
Cơ chế thơng báo tắc nghẽn rõ ràng ECN (Explicit Congestion Notification) là
một phương pháp điều khiển tắc nghẽn, ứng dụng vào điều khiển các luồng chuyển
vận được sử dụng trong hệ thống sử dụng giao thức TCP/IP.
Phương pháp ECN được đề xướng vào năm 1999 từ ý tưởng sẽ phát hiện sớm
những tắc nghẽn của hệ thống và gửi những tín hiệu thơng báo đến hệ thống trước
khi hàng đợi bị tràn. Phương pháp này là một sự tiếp cận khác từ phương pháp RED
và WRED (ta sẽ đề cập cụ thể hơn về 2 phương pháp này ở phần sau). [1] [2].
Queue Length & Load Based

Active Queue Managament
Queue Length Based
Load Based
1. RED 10. SHRED
2. FRED 11. HRED
3. CBT 12. ARED
4. SRET 13. RARED
5. DSRED 14. QAVRED
6. MRED 15. PUNSI
7. Adaptive RED 16. CHOCKe

Vì thế, người ta đề ra giải pháp để phát triển việc phát hiện sự tắc nghẽn
hệ thống bằng cách tính tốn kích thước hàng đợi trung bình và đặt một
bit ECN trong packet header khi kích thước hàng đợi trung bình vượt q một
ngưỡng nào đó với ý tưởng sẽ phát hiện và thơng báo sự tắc nghẽn mà khơng cần
phải dựa vào những gói tin bị loại bỏ. Đây chính là sự khác biệt cơ bản giữa cơ chế
ECN và cơ chế RED. Ở cơ chế RED, khi xảy ra tắc nghẽn, các gói tin được loại bỏ
một cách ngẫu nhiên. Còn ở cơ chế ECN, những trường đã được đánh dấu sẽ được
đi qua để thơng báo sự tắc nghẽn đến hệ thống. Điểm giống nhau giữa hai cơ chế
này là đều cùng sử dụng chung một giải thuật lựa chọn gói tin dự báo sự tắc nghẽn.
[2]
2.2.1.2. Sự đánh dấu trong IP header
ECN FIELD (Trường ECN trong IP header)
ECT
CE

0
0
Not-ECN
0
1
ECT (1)
1
0
ECT (0)1
1
1
CE

Hình 2.2: ECN Field trong IP header
TCP sử dụng một trường ECN ở IP header với hai bit để đánh dấu 4 mã ECN từ

P

Trang 23
ECN sử dụng hai cờ ECT và CE ở trong IP header để báo hiệu giữa các endpoint
(điểm cuối) với những bộ định tuyến trong một kết nối. Hai cờ CWR và ECN-Echo
trong TCP header để giao tiếp giữa 2 TCP-endpoit.
Hoạt động giữa bên thu và bên phát TCP diễn ra theo một chuỗi các sự kiện:
- Sau những thỏa thuận rõ ràng giữa bên phát và bên thu về việc quyết định sử
dụng ECN, bên phát đặt một mã ECN-Capable Transport (ECT) vào IP header của
gói tin.

Hình 2.4: Cấu trúc hai trường code field và Reserved field của TCP hearder
- Khi một bộ định tuyến có sử dụng ECN phát hiện ra sự tắc nghẽn, nó sẽ lựa
chọn một gói tin. Nếu gói tin đó được đặt mã ECT, thay vì loại bỏ gói tin này, bộ
định tuyến sẽ đặt một mã CE (Congestion Experienced) thơng báo sự tắc nghẽn vào
IP header của gói tin này mục đích để thơng báo đến bên thu dấu hiệu của sự tắc
nghẽn sắp xảy ra và tiếp tục chuyển nó đến bên nhận.
- Khi nhận được gói tin với bit CE này, thiết bị thu sẽ đặt một cờ ECN-Echo
(ECE) trong phiên TCP ACK tiếp theo của bên phát.
- Khi bên phát nhận được gói ACK này, nó sẽ đặt một cờ CWR xác nhận việc
nó đã nhận được gói ACK với cờ ECE kia và đồng thời nó sẽ giảm nhịp độ gửi dữ
liệu và thơng báo nó đã sẵn sàng phản ứng lại tới sự tắc nghẽn sắp xảy đến. [1] [3]
[7].
Code field 6 bit
URG
1bit
ACK

2.2.2.1. Khái qt
Khi một hàng đợi bị đầy, nó khơng còn chỗ cho các gói tin vừa đến, vì vậy nó sẽ
loại bỏ các gói này. Hiện tượng này gọi là loại bỏ cuối hàng (tail drop). Thơng
thường khi một hàng đợi bị đầy, vài gói tin sẽ bị loại bỏ cùng lúc ở một thời điểm.
Cơ chế loại bỏ cuối hàng tail drop có thể gây ảnh hưởng tiêu cực trên lưu lượng
mạng, đặc biệt là lưu lượng TCP. Khi thả một gói tin bị mất, vì bất kỳ lý do gì, các
kết nối TCP sẽ giảm tốc độ gửi dữ liệu. Khi hiện tượng loại bỏ gói tin xảy ra và
nhiều gói tin bị mất, các kết nối TCP sẽ giảm tốc độ thêm nữa. Ngồi ra, hầu như
các mạng đều gửi một tỉ lệ phần trăm của lưu lượng TCP nhiều hơn UDP, nghĩa là
tồn bộ tải của mạng có khuynh hướng bị loại bỏ.
Thơng lượng tổng thể của mạng có thể dược cải tiến bằng cách loại bỏ chỉ vài
gói tin khi hàng đợi bắt đầu bị đầy. Cách tốt hơn là chờ những ảnh hưởng của cơ
chế Tail Drop. Cisco đã tạo ra cơ chế WRED (Weighted Random Early Detection)
đặt biệt cho mục đích giám sát chiều dài hàng đợi và loại bỏ một số gói tin trong
hàng đợi để cải tiến hiệu năng của mạng. Khi hàng đợi trở nên dài hơn, WRED bắt
đầu loại bỏ nhiều gói tin, với hy vọng rằng sự gia giảm trong phần tải có thể đủ để
ngăn ngừa hàng đợi bị đầy [3] [13].
2.2.2.2. Cơ chế hoạt động
Số hóa bởi Trung tâm Học liệu

P

Trang 25
Hình 2.5: Sơ đồ hoạt động của WRED
WRED dùng vài chỉ số khi thực hiện quyết định. Đầu tiên, WRED dùng thơng
số kích thước hàng đợi trung bình khi nó quyết định là một hàng đợi đã bị đầy đủ để
bắt đầu loại bỏ gói tin. WRED sau đó sẽ so sánh chiều sâu trung bình với mức giới