Hàng đợi ưu tiên PQ (Priority Queue)

[thanhsang_truong]

Tác giả: (st)

HÀNG ĐỢI ƯU TIÊN PQ (PRORITY QUEUE)

- Tính năng đặc biệt của PQ là ở bộ lập lịch. PQ lập lịch lưu lượng đảm bảo hàng đợi ưu tiên luôn được phục vụ trước. Với 4 mức ưu tiên: cao, trung bình, bình thường, và thấp. Nguyên lý lập lịch được thể hiện trong hình 3-5.
- Hình 3-5, nếu hàng đợi ưu tiên cao luôn có một gói đang chờ, bộ lập lịch luôn luôn lấy các gói trong hàng đợi ưu tiên cao. Nếu hàng đợi ưu tiên cao không có gói nào đang chờ nhưng có trong hàng đơi ưu tiên trung bình, một gói trong hàng đợi này sẽ được lấy và tiến trình cứ như thế tiếp tục.
- Bộ lập lịch PQ có một số thuận lợi và hạn chế. Các gói trong hàng đợi ưu tiên cao có thể đạt 100% băng thông liên kết, với độ trì hoãn nhỏ và độ biến động trễ nhỏ. Thật ra, khi nghẽn mạch, các gói trong hàng đợi ưu tiên thấp tốn nhiều thời gian phục vụ. Khi liên kết tắc nghẽn, các ứng dụng người dùng có thể ngừng làm việc nếu các gói đặt trong hàng đợi ưu tiên thấp.

- PQ phân lớp các gói dựa trên nội dung của các tiêu đề. Nó sử dụng tối đa 4 hàng đợi. Chỉ áp dụng chính sách hủy gói cuối hàng đợi, mặt khác sau khi phân lớp các gói, nếu hàng đợi tương ứng đầy, các gói bị bỏ. Mặt khác, chiều dài mỗi hàng đợi là nguyên nhân ảnh hưởng đến độ trễ và mất gói. Thật ra, PQ có thể thiết lập chiều dài hàng đợi trở về giá trị 0, có nghĩa là chiều dài hàng đợi “không giới hạn”. (“không giới hạn” có nghĩ là khi bộ định tuyến ra ngoài vùng nhớ, các gói không thể lập lịch; tuy nhiên, chúng ta gặp vấn đề rắc rối hơn việc lập lịch cho gói nếu bộ định tuyến ngoài vùng nhớ.) Hình 3-6 tổng quát hóa các tính năng quan trọng của PQ.
- Hình 3-6, thể hiện hoạt động bên trong một bộ định tuyến, sau bộ định tuyến nhận dạng cổng xuất cho gói.

1. PQ có thể phân lớp các gói sử dụng danh sách điều khiển truy cập ACL với giao thức lớp 3. PQ cũng có thể so trùng trực tiếp không cần sử dụng ACL, đầu vào, chiều dài gói và cổng TCP và UDP.
2. Hủy bỏ gói cuối hàng đợi là chính sách bỏ gói mặc định.
3. Số hàng đợi cực đại là 4.
4. Chiều dài hàng đợi cực đại có thể là 0, nghĩa là hàng đợi có chiều dài “không xác định” theo lý thuyết. Mặc định là 20, 40, 60 và 80 tướng ứng với các hàng đợi ưu tiên cao, trung bình, bình thường và thấp.
5. Bên trong một hàng đợi, PQ sử dụng nguyên lý PQ.
6. Khi lập lịch các hàng đợi, PQ luôn phục vụ các hàng đợi ưu tiên cao trước.

- Khi ngõ xuất không tắc nghẽn (nói một cách khác TXR không đầy), các gói mới đặt vào TXR một cách trực tiếp. Khi TXR đầy, PQ thể hiện việc lập lịch. Khi tất cả các hàng đợi PQ truyền hết các gói (TXR không đầy), tắc nghẽn dịu đi. Các gói mới đến lại vào TXR, cho đến khi nó đầy trở lại, nó sẽ khởi động tiến trình hàng đợi với PQ.
- PQ làm việc tốt trong các chính sách QoS cần xử lý một loại lưu lượng với khả năng phục vụ tốt nhất. Tuy nhiên, dịch vụ PQ với các hàng đợi thấp giảm nhanh chóng, làm cho PQ không thiết thực cho hầu hết các ứng dụng hiện nay. Chẳng hạn, việc chạy một kết nối FTP, một trình duyệt web, một cuộc gọi NetMeeting, và 2 cuộc gọi VoIP khi xuất, các kết nối TCP với lưu lượng HTTP và FTP thường xuyên vượt quá thời gian cho phép.
- Bảng III-1 tổng kết một vài chức năng quan trọng và các tính năng của PQ.