NGHIÊN CỨU KỸ THUẬT QUẢN LÝ HÀNG ĐỢI TRONG MẠNG IP CHƯƠNG 3_2 potx

TỐT NGHIỆP ĐẠI HỌC

Đề tài:

NGHIÊN CỨU KỸ THUẬT QUẢN LÝ

HÀNG ĐỢI TRONG MẠNG IP

CHƯƠNG 3: QUẢN LÝ HÀNG ĐỢI VÀ CÁC THUẬT

TOÁN

Hàm xác suất loại bỏ gói tin :

0 nếu q < max buffer size

d(q) =

1 nếu q > max buffer size

Khi các gói đến hàng đợi dưới dạng bó, các gói đến với tốc độ thay đổi λ

(quá trình các gói đến là quá trình poisson) và mỗi bó có B gói tin, và phân bố mũ

là µ. Các gói được đệm trong hàng đợi có dạng chuỗi Markov có phân bố dừng là

π. Cho kích thước hàng đợilà K, ta có công thức tính xác suất loại bỏ gói của tail

drop :

PTD = π(K) +π(K-1)d(K-1) +…..+ π(1)d(1)

Tail drop rất đơn giản, nhưng nó có hai điều hạn chế.

 Trong một số trương hợp nó chỉ cho phép một kết nối đơn hoặc một

vài kết nối độc quyền chiếm dụng không gian hàng đợi, ngăn cản các kết nối khác

đến hàng đợi. Đây là hiện tượng chặn luồng từ các kết nối khác (lock out). Hiện

tượng lock out là kêt quả của các ảnh hưởng đồng bộ và định thời của lưu lượng.

 Tail drop cho phép các hàng đợi duy trì trạng thái đầy trong chu kì

thời gian dài kể từ lúc có thông báo tắc nghẽn của tail drop xuất hiện thông qua

hiện tượng mất gói khi hàng đợi bắt đầu đầy. Điều này rất quan trọng để giảm kích

thước hàng đợi ở trạng thái không đổi trong quản lý hàng đợi. Do các gói đến hàng

đợi dưới dạng bó nên việc loại bỏ gói trong một bó dễ gây ra loại đa gói. Điều này

có thể dẫn đến đồng bộ trên toàn thể luồng.

Khi hàng đợi đầy có hai cách loại bỏ gói tin đến :

 Loại bỏ trong hàng đợi: nếu hàng đợi đầy mà có các gói tin hàng đợi thì

việc loại bỏ gói tin sẽ xảy ra ngẫu nhiên bên trong hàng đợi. Một gói mới sẽ đến hàng

đợi

 Loại bỏ đầu hàng đợi : nếu hàng đợi đầy mà vẫn có gói tin đến hàng

đợi thì router sẽ loại bỏ gói tin nằm tại vị trí đầu hàng đợi.

Cả hai cách trên đều giải quyết được vấn đề lock out nhưng vẫn không giải

quyết được vấn đề đầy hàng đợi. Trong mạng Internet hiện tại việc loại bỏ gói tin

giống như cơ chế thông báo tắc nghẽn tới các node đích. Giải pháp cho vấn đề

hàng đợi đầy là router loại bỏ các gói trước khi hàng đợi bắt đầu đầy, do đó các

node cuối có thể phản ứng lại với tắc nghẽn trước khi bộ đệm tràn.