WFQ (Weighted Fair Queuing)

1. Tổng quan

A. Định nghĩa

WFQ là một kỹ thuật xếp hàng mạng (hàng đợi), là phương thức lập lịch gán trọng số cho nhiều luồng lưu lượng (flow) để phân chia băng thông một cách công bằng. Nó cấp nhiều băng thông hơn cho lưu lượng quan trọng cao, đồng thời bảo đảm phần tối thiểu để luồng thấp không bị đói (starvation). Về lý thuyết, nó được định nghĩa là xấp xỉ theo từng gói tin (PGPS) mô hình chất lỏng lý tưởng GPS (Generalized Processor Sharing).

Lý do căn bản cần WFQ nằm ở vấn đề cốt lõi của QoS: 'phân chia băng thông hữu hạn thế nào cho công bằng và hiệu quả'. FIFO (vào trước ra trước) - kỹ thuật xếp hàng đơn giản nhất - xử lý theo thứ tự đến, nên nếu một luồng truyền tệp dung lượng lớn (ví dụ: lưu lượng backup vài trăm MB) chiếm trọn hàng đợi thì lưu lượng nhạy cảm với độ trễ như gọi video hay VoIP bị đẩy lùi phía sau vô hạn. Điều này gọi là độc chiếm hàng đợi (hogging), đặc biệt nghiêm trọng trên liên kết WAN tốc độ thấp. Ngược lại, xếp hàng công bằng đơn giản (Fair Queuing) chia đều cho mọi luồng có hạn chế là không phân biệt được lưu lượng quan trọng và lưu lượng ít quan trọng.

WFQ giải quyết đồng thời vấn đề của cả hai. Nó phân biệt từng luồng lưu lượng và đưa vào hàng đợi riêng, đặt trọng số (weight) cho mỗi luồng và phân bổ băng thông theo tỷ lệ đó. Nhờ vậy lưu lượng ưu tiên cao (trọng số lớn) nhận nhiều băng thông hơn và được xử lý nhanh, trong khi luồng thấp cũng được bảo đảm phần tối thiểu để tránh bị đói. Tức là bản chất của WFQ là hiện thực 'công bằng có phân biệt (differentiated fairness)'. Điều này hiệu quả trong việc giữ chất lượng từng dịch vụ trong mạng hội tụ (converged network) nơi thoại, video, dữ liệu trộn lẫn, và ngày nay nó đã trở thành bộ lập lịch chuẩn trên thực tế cho QoS của router, switch.

B. Bối cảnh ra đời và gốc rễ lý thuyết

Cuối thập niên 1980, khi lưu lượng thời gian thực như thoại, video và dữ liệu dung lượng lớn bắt đầu cùng tồn tại trên Internet, FIFO đơn thuần không thể bảo đảm QoS nên cần xếp hàng có phân biệt và công bằng. WFQ được Demers, Keshav, Shenker đề xuất năm 1989 trong bài báo SIGCOMM "Analysis and Simulation of a Fair Queueing Algorithm", sau đó năm 1993 Parekh, Gallager xác lập lý thuyết về mô hình chất lỏng lý tưởng GPS và xấp xỉ gói tin của nó là PGPS (Packet-by-Packet GPS), chứng minh cận trên độ trễ (delay bound) mang tính toán học. Kết luận cốt lõi là "với bất kỳ mẫu đến nào, PGPS chỉ chênh lệch với GPS trong phạm vi tối đa thời gian truyền 1 gói tin", bảo đảm rằng WFQ có thể mô phỏng rất sát phân bổ công bằng lý tưởng một cách thực tiễn. Nhờ nền tảng lý thuyết này, WFQ được công nhận không phải là heuristic đơn thuần mà là kỹ thuật có thể bảo đảm QoS định lượng.

C. Đặc điểm

WFQ có bốn tính chất: tự động phân loại luồng (nhận diện hội thoại bằng 5-tuple, v.v. không cần cấu hình riêng), phân bổ tỷ lệ theo trọng số, chống đói (luân phiên phục vụ mọi luồng hoạt động), phân bổ lại băng thông thích ứng (luồng hoạt động chia nhau phần của luồng nhàn rỗi). Đặc biệt nhờ tính chất cuối (work-conserving) mà liên kết không có lúc nào trống, hiệu suất sử dụng băng thông cao.

2. Quan hệ giữa mô hình lý tưởng GPS và WFQ — Cấu trúc tổng thể

Để hiểu WFQ, trước tiên cần biết hình mẫu lý tưởng của nó là GPS. GPS là mô hình giả định phục vụ nhiều luồng đồng thời, chia nhỏ vô hạn (như chất lỏng) theo tỷ lệ trọng số. Chẳng hạn nếu trọng số các luồng A, B, C là 3:2:1, GPS tại mọi thời điểm chia băng thông chính xác thành 3/6, 2/6, 1/6 để truyền. Nhưng gói tin thực tế không thể chia nhỏ, nên mỗi lần chỉ gửi được một gói. WFQ xấp xỉ GPS bằng cách tính "nếu là GPS thì gói này sẽ truyền xong khi nào" (thời điểm hoàn tất ảo), rồi thực sự gửi gói theo thứ tự đó.

flowchart TB
  subgraph IDEAL["Mô hình lý tưởng: GPS (dòng chất lỏng)"]
    G["Chia băng thông theo tỷ lệ trọng số<br/>đồng thời, liên tục (khác thực tế không thể chia)"]
  end
  subgraph REAL["Thực tế: WFQ (xấp xỉ theo gói = PGPS)"]
    direction LR
    IN["Lưu lượng đầu vào hỗn hợp"] --> CL{"Phân loại luồng<br/>(nhận diện hội thoại 5-tuple)"}
    CL --> Q1["Hàng đợi 1 (trọng số w1)"]
    CL --> Q2["Hàng đợi 2 (trọng số w2)"]
    CL --> Q3["Hàng đợi 3 (trọng số w3)"]
    Q1 & Q2 & Q3 --> VT["Tính thời điểm hoàn tất ảo<br/>(mô phỏng GPS)"]
    VT --> SEL["Chọn gói có thời điểm hoàn tất nhỏ nhất"]
    SEL --> OUT["Liên kết đầu ra"]
  end
  IDEAL -. xấp xỉ (sai số ≤ 1 thời gian truyền gói) .-> REAL
  style VT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style SEL fill:#fff3e0,stroke:#e8890c,stroke-width:2px

Trong sơ đồ cấu trúc trên, điểm cốt lõi là đường nét đứt nối GPS (lý tưởng) và WFQ (thực tế). Với mỗi gói, WFQ mô phỏng GPS bên trong để gắn nhãn thời gian gọi là thời điểm hoàn tất ảo, rồi gửi trước gói có giá trị nhỏ nhất. Như vậy thứ tự truyền thực tế gần như trùng với thứ tự kết thúc của phân bổ chất lỏng lý tưởng, đạt đồng thời tính công bằng và bảo đảm độ trễ.

3. Nguyên lý hoạt động — Thời gian ảo và thời điểm hoàn tất ảo

Trái tim của WFQ là thời gian ảo (virtual time, V(t)) và thời điểm hoàn tất ảo (virtual finish time, F). Thời gian ảo là đồng hồ nội bộ thể hiện máy chủ GPS đã tiến hành công việc đến đâu, tốc độ tiến triển thay đổi theo số luồng hoạt động và tổng trọng số. Khi mỗi gói đến, WFQ tính gói đó sẽ kết thúc truyền trong GPS khi nào như sau.

flowchart LR
  A["Gói k đến<br/>(luồng i)"] --> B["Tính thời gian ảo V(thời điểm đến)"]
  B --> C["Thời điểm bắt đầu = max(thời điểm hoàn tất gói trước F, V)"]
  C --> D["Thời điểm hoàn tất F = bắt đầu + độ dài gói/trọng số<br/>F(i,k)=max(F(i,k-1),V) + L/w_i"]
  D --> E["Gán F làm nhãn"]
  E --> F["Trong các gói đang chờ ở mọi hàng đợi<br/>chọn, truyền F nhỏ nhất"]
  F --> G["Sau truyền cập nhật V → gói tiếp theo"]
  style D fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px

Hãy giải thích ý nghĩa từng số hạng trong công thức F(i,k) = max(F(i,k-1), V(a)) + L(i,k)/w_i. Số hạng max(...) có nghĩa "nếu gói trước của luồng này chưa kết thúc thì nối tiếp sau nó, nếu đã kết thúc thì bắt đầu từ thời điểm hiện tại (thời gian ảo)". Nhờ đó ngăn luồng nghỉ lâu đột ngột bùng phát và dồn chiếm băng thông. Số hạng L/w_i là độ dài gói L chia cho trọng số w; trọng số càng lớn thì phần tăng này càng nhỏ, thời điểm hoàn tất được kéo sớm và cuối cùng được truyền trước. Tức là cấu trúc là gói của luồng có trọng số càng lớn thì nhãn càng nhỏ và được phục vụ ưu tiên.

Lý do phương thức này ưu việt nằm ở chỗ công bằng bất kể kích thước gói. Round robin đơn giản (WRR) chia theo 'số lượng' gói mỗi vòng quay hàng đợi, nên phát sinh bất công là luồng chỉ gửi gói lớn thực tế lấy nhiều byte hơn luồng gói nhỏ. Ngược lại, WFQ phản ánh độ dài L theo đơn vị byte vào tính thời điểm hoàn tất, nên dù kích thước gói khác nhau vẫn giữ đúng tỷ lệ trọng số theo byte. Đây là điểm cốt lõi khiến WFQ vượt trội WRR về lý thuyết.

Trong thực tế, trọng số được xác định bằng giá trị đánh dấu lưu lượng. Ví dụ, WFQ dựa trên luồng của Cisco gán trọng số lớn hơn khi giá trị IP Precedence (0~7) càng cao, tự động điều chỉnh để thoại Precedence 5 nhận băng thông gấp nhiều lần dữ liệu thông thường Precedence 0. Trên thực tế nó được hiện thực bằng cách gán trọng số nội bộ tỷ lệ nghịch với (Precedence+1), nên mỗi khi ưu tiên tăng một bậc, phần băng thông tương đối tăng lên (hằng số cụ thể khác nhau theo phiên bản IOS nên ở đây khái quát hóa).

A. Tính thời điểm hoàn tất — Ví dụ số theo từng bước

Để cụ thể hóa khái niệm, hãy xem một ví dụ đơn giản. Có luồng A (trọng số 2) và luồng B (trọng số 1), để tiện giả định thời gian ảo bằng thời gian thực và độ dài gói biểu diễn theo đơn vị thời gian phục vụ. Nhãn thời điểm hoàn tất được gán theo thứ tự sau.

t=0: Gói A1 (độ dài 4) của A đến. Không có thời điểm hoàn tất trước nên F(A1)=max(0,0)+4/2=2.
t=0: Gói B1 (độ dài 3) của B đến. F(B1)=max(0,0)+3/1=3.
Lựa chọn: Nhỏ nhất trong hai nhãn là A1 (2) nên truyền A1 trước. A có trọng số lớn hơn thắng trong cạnh tranh cùng thời điểm.
Sau khi t tiến: Gói A2 (độ dài 4) của A đến. F(A2)=max(F(A1)=2, V)+4/2=2+2=4.
Lựa chọn: Các nhãn đang chờ là B1 (3), A2 (4). Nhỏ nhất là truyền B1 (3) → tiếp theo A2 (4). Thứ tự truyền kết quả là A1→B1→A2.

Điều cần quan sát trong chuỗi này là A có trọng số gấp 2 lần gửi được khoảng gấp 2 lần số byte so với B trong cùng cửa sổ thời gian (A1+A2=8 so với B1=3 và tiếp tục), nhưng B không bị đẩy ra hoàn toàn mà nhất định được phục vụ ở giữa. Đây là hình ảnh 'công bằng có phân biệt' được hiện thực bằng số học nhãn thực tế; nếu là hàng đợi ưu tiên thuần túy thì B1 sẽ không được truyền cho đến khi lưu lượng A ngừng.

4. Các loại và mở rộng — Flow-based WFQ, CBWFQ, LLQ, DRR

WFQ không phải một thuật toán cố định mà đã phát triển thành nhiều dạng phái sinh, mở rộng. Bản gốc WFQ dựa trên luồng (Flow-based / conversation-based) tự động nhận diện hội thoại bằng 5-tuple như IP nguồn, đích, giao thức, cổng để tạo hàng đợi động. Ở Cisco, truyền thống nó là bộ lập lịch mặc định cho giao diện serial tốc độ thấp từ 2.048 Mbps trở xuống, bảo vệ lưu lượng thời gian thực nhỏ khỏi lưu lượng bulk lớn mà không cần định nghĩa lớp riêng. Tuy nhiên do duy trì trạng thái cho từng luồng, trên router lõi lớn có hàng chục nghìn luồng đi qua thì có giới hạn về khả năng mở rộng (scalability).

Để giải quyết vấn đề mở rộng này, CBWFQ (Class-Based WFQ) ra đời. CBWFQ tạo hàng đợi không theo từng luồng mà theo lớp do người dùng định nghĩa (ví dụ: thoại, video, lưu lượng nghiệp vụ, khác), và bảo đảm băng thông cho từng lớp bằng giá trị tuyệt đối (kbps) hoặc phần trăm. Dù số luồng nhiều đến đâu, số hàng đợi bị giới hạn bằng số lớp (tối đa 64, v.v.) nên ngay cả ở mạng lõi cũng dự đoán được và dễ quản lý. Phần lớn thiết kế QoS thực tế dựa trên CBWFQ.

Tuy nhiên chỉ CBWFQ thì khó bảo vệ hoàn hảo lưu lượng cực kỳ nhạy cảm với độ trễ, jitter như VoIP. Bởi chỉ phân bổ trọng số thì trong trường hợp xấu nhất gói thoại có thể phải chờ một chút sau hàng đợi khác. Vì vậy LLQ (Low Latency Queuing) đặt thêm một hàng đợi ưu tiên nghiêm ngặt (strict priority queue) lên CBWFQ, để lưu lượng thoại được truyền ngay trước bất kỳ hàng đợi nào khác, nhưng nếu vượt hạn mức băng thông quy định (policer) thì bị cắt để ngăn các lớp khác bị đói. Ngày nay LLQ là chuẩn trên thực tế của QoS cho mạng thoại doanh nghiệp.

Mặt khác, về độ phức tạp tính toán, việc sắp xếp thời điểm hoàn tất của WFQ tốn chi phí O(log N) với số luồng N. Trên phần cứng siêu tốc, ngay cả chi phí sắp xếp này cũng là gánh nặng, nên DRR (Deficit Round Robin) đơn giản hóa về O(1) được dùng rộng rãi. DRR đặt bộ đếm 'thâm hụt (deficit)' và lượng tử (quantum) cho mỗi hàng đợi để xấp xỉ công bằng theo byte, là dạng dung hòa giữa chi phí hiện thực thấp của round robin và công bằng byte của WFQ. Trên thực tế, không ít bộ lập lịch của ASIC switch hiệu năng cao chọn DRR hoặc biến thể của nó.

5. So sánh với các kỹ thuật xếp hàng khác

Bảng dưới đây tổng hợp các kỹ thuật xếp hàng tiêu biểu, nhưng chỉ bảng thì khó biết 'tại sao' có khác biệt như vậy. Phần văn sau bảng giải thích nguyên nhân khác biệt và hàm ý thực tế.

Kỹ thuật	Phương thức cốt lõi	Điểm mạnh	Điểm yếu
FIFO	Vào trước ra trước đơn giản	Hiện thực đơn giản, overhead tối thiểu	Không bảo đảm QoS, nguy cơ độc chiếm hàng đợi
PQ (xếp hàng ưu tiên)	Ưu tiên cao tuyệt đối đi trước	Độ trễ tối thiểu cho lưu lượng ưu tiên nhất	Hàng đợi thấp bị đói
WRR	Round robin có trọng số (số gói)	Dễ hiện thực, có thể phân biệt	Bất công theo kích thước gói
WFQ	Tỷ lệ trọng số + công bằng byte	Chống đói, công bằng byte	Duy trì trạng thái luồng, khả năng mở rộng
CBWFQ	WFQ dựa trên lớp	Bảo đảm băng thông, khả năng mở rộng	Bảo đảm độ trễ thời gian thực yếu
LLQ	CBWFQ + ưu tiên nghiêm ngặt	Độ trễ, jitter thoại tối thiểu	Loại bỏ khi vượt băng thông ưu tiên

FIFO không giữ được QoS, còn xếp hàng ưu tiên thuần túy (PQ) có thể để ưu tiên cao độc chiếm băng thông khiến lưu lượng thấp bị đói. WRR có thể phân biệt nhưng như đã giải thích, do chia theo 'số lượng' gói nên luồng gói lớn được lợi một cách bất công. WFQ vượt qua cả ba vấn đề bằng phân bổ trọng số theo byte, nhưng do duy trì trạng thái theo luồng, chuẩn mực thực tế là mở rộng sang CBWFQ trong mạng quy mô lớn và bổ sung LLQ khi cần bảo đảm độ trễ như thoại. Tức là cần hiểu chúng không phải công nghệ cạnh tranh mà là công cụ phân tầng dùng chồng lên nhau tùy mức yêu cầu.

Ví dụ số cụ thể, trên liên kết 155 Mbps, nếu cả ba luồng thoại (trọng số 5), video (3), dữ liệu (1) đều bùng phát, WFQ chia băng thông khoảng 5/9 (≈86 Mbps), 3/9 (≈52 Mbps), 1/9 (≈17 Mbps). Nếu luồng dữ liệu tạm nghỉ, phần của nó được thoại và video chia theo tỷ lệ 5:3 nên liên kết không nhàn rỗi (work-conserving). Đạt đồng thời phân bổ định lượng và tái sử dụng băng thông nhàn rỗi như vậy là giá trị thực chất của WFQ.

6. Chuyên sâu — Thiết kế QoS thực tế và xu hướng mới

Trong thực tế, họ WFQ được dùng kết hợp với kiến trúc DiffServ (Differentiated Services). DiffServ đánh dấu (marking) lớp vào trường DSCP của gói tại biên mạng, router lõi áp dụng PHB (Per-Hop Behavior) theo dấu đó, và bộ lập lịch thực sự hiện thực PHB này chính là CBWFQ, LLQ. Ví dụ, EF (Expedited Forwarding, thoại) được ánh xạ vào hàng đợi ưu tiên của LLQ, AF (Assured Forwarding, nghiệp vụ) vào hàng đợi bảo đảm băng thông của CBWFQ. Do đó có thể xem WFQ là engine cốt lõi đảm nhận giai đoạn lập lịch trong pipeline 'phân loại → đánh dấu → lập lịch → tránh tắc nghẽn (WRED)' của chính sách QoS.

Một ví dụ áp dụng công nghiệp: trong mạng doanh nghiệp nối chi nhánh và trụ sở bằng WAN tốc độ thấp, khi hội nghị video thường xuyên bị gián đoạn, cách làm điển hình là cấu hình LLQ ở đầu ra router trụ sở để xử lý ưu tiên thoại, video (EF/AF41), gom chia sẻ tệp, backup vào lớp thấp hơn và giới hạn băng thông, từ đó ổn định chất lượng hội nghị. Lúc này nếu phân quá nhiều băng thông cho hàng đợi ưu tiên thì lưu lượng nghiệp vụ khác bị đói, nên thông lệ thiết kế phổ biến là giới hạn băng thông ưu tiên trong 33% liên kết.

Về xu hướng mới, khi yêu cầu độ trễ siêu thấp tăng trong trung tâm dữ liệu và mạng truyền tải 5G, các nghiên cứu nhằm khái quát hóa ý tưởng của WFQ ở tốc độ đường truyền phần cứng đang sôi nổi, như bộ lập lịch lập trình được dựa trên PIFO (Push-In First-Out) hay bộ định hình nhận biết thời gian (Time-Aware Shaper) của mạng nhạy cảm thời gian (TSN). Tuy nhiên các công nghệ mới này cũng đứng trên nguyên lý căn bản của WFQ "chia công bằng theo tỷ lệ trọng số, không để đói", nên WFQ vẫn còn giá trị như điểm tham chiếu (reference) của lý thuyết xếp hàng. Từ góc độ Kỹ sư chuyên nghiệp, chiến lược đạt điểm cao là trình bày WFQ không phải như một kỹ thuật riêng lẻ mà như trục trung tâm của phả hệ lập lịch QoS xuất phát từ hình mẫu lý tưởng GPS, phân nhánh thành CBWFQ, LLQ, DRR và mở rộng sang DiffServ, TSN.

7. Các điểm cần lưu ý và hàm ý

Cân bằng giữa phân biệt và công bằng là giá trị cốt lõi của WFQ. WFQ đạt đồng thời việc ưu đãi lưu lượng quan trọng và bảo đảm băng thông tối thiểu, vượt qua cả vấn đề đói của phương thức ưu tiên thuần túy (PQ) và vấn đề không phân biệt của phương thức công bằng thuần túy. Khi thiết kế, thiết lập trọng số gắn trực tiếp với SLA dịch vụ, nên việc xác định trọng số dựa trên phân tích đặc tính lưu lượng quyết định thành bại.
Phải xem xét đánh đổi về khả năng mở rộng. WFQ dựa trên luồng chi tiết nhưng chi phí duy trì trạng thái luồng lớn, nên hợp lý là chọn CBWFQ gom theo lớp ở mạng lõi, quy mô lớn, và DRR độ phức tạp O(1) ở phần cứng siêu tốc. Cần đặt điểm cân bằng giữa quy mô và độ chính xác phù hợp môi trường tổ chức.
Bổ sung LLQ cho lưu lượng thời gian thực. Chỉ phân bổ trọng số của WFQ thì khó bảo đảm cận trên độ trễ, jitter của VoIP, video. Cần cơ chế an toàn kép: xử lý ngay lưu lượng thời gian thực bằng LLQ có thêm hàng đợi ưu tiên nghiêm ngặt, nhưng giới hạn băng thông bằng policer để ngăn các lớp khác bị đói.
Thiết kế tích hợp như một phần của chính sách QoS. WFQ kết hợp với phân loại (classification), đánh dấu (marking), tránh tắc nghẽn (WRED) để hoạt động như giai đoạn lập lịch của toàn bộ chính sách DiffServ. Chất lượng thực tế chỉ được bảo đảm khi có tiền đề đánh dấu DSCP và ánh xạ PHB nhất quán đầu cuối (end-to-end), chứ không phải tinh chỉnh riêng lẻ.
Triển vọng: liên kết với tốc độ đường truyền phần cứng và lập lịch lập trình được. Trong các lĩnh vực độ trễ siêu thấp như trung tâm dữ liệu, 5G, TSN, nguyên lý công bằng của WFQ đang tiến hóa thành bộ lập lịch lập trình được và bộ định hình nhận biết thời gian, vì vậy cần góc nhìn hiểu và liên kết WFQ không như kiến thức tĩnh mà như nền tảng lý thuyết của QoS thế hệ tiếp theo.

Tài liệu tham khảo

Demers, Keshav, Shenker, "Analysis and Simulation of a Fair Queueing Algorithm" (SIGCOMM 1989): https://www.cs.emory.edu/~cheung/Courses/558/Syllabus/11-Fairness/WFQ.html
Tổng quan Weighted fair queueing: https://en.wikipedia.org/wiki/Weighted_fair_queueing
Tài liệu bài giảng Packet Scheduling (WFQ/Virtual Clock) (UT Austin): https://www.cs.utexas.edu/~lam/396m/slides/Packet_scheduling.pdf
Cisco, hướng dẫn cấu hình "Quality of Service — Congestion Management (WFQ/CBWFQ/LLQ)": https://www.cisco.com/c/en/us/support/docs/quality-of-service-qos/qos-congestion-management/index.html

Tóm tắt một câu: WFQ là kỹ thuật xếp hàng xấp xỉ mô hình chất lỏng lý tưởng GPS theo từng gói (PGPS) để gán trọng số cho các luồng lưu lượng và phân bổ băng thông công bằng theo byte theo thứ tự thời điểm hoàn tất ảo, giải quyết cả việc độc chiếm của FIFO, tình trạng đói của PQ và bất công theo kích thước của WRR, mở rộng thành CBWFQ, LLQ, DRR và liên kết với DiffServ, TSN để hiện thực QoS đầu cuối.