Weighted Fair Queueing (WFQ) is a network scheduling algorithm that ensures fair and efficient allocation of bandwidth among different flows. Let’s dive into the technical details:
- General Idea:
- WFQ combines aspects of both Generalized Processor Sharing (GPS) and Fair Queuing (FQ).
- It allows each flow to have a specific share of the link capacity, which is typically specified by the flow itself.
- GPS and FQ Background:
- Generalized Processor Sharing (GPS) is a theoretical ideal where each flow gets an equal share of the link capacity over time.
- Fair Queuing (FQ) divides the link’s capacity into equal subparts, ensuring fairness among flows.
- WFQ Parameters and Fairness:
- In WFQ, the network administrator assigns weights to each flow. These weights determine the fraction of capacity allocated to each flow.
- There’s no unique definition of “fairness,” but proportionally fair behavior can be achieved by setting weights based on the cost per data bit of each flow.
- For example, in CDMA cellular networks, the cost might be energy (interference level), while in dynamic channel allocation, it could be avoiding co-channel interference.
- Algorithm:
- WFQ configures a scheduler with one weight per flow (N flows).
- Flow number i achieves an average data rate of\frac{{w_i}}{{\sum_{j=1}^{N} w_j}} \cdot \text{{link rate}}, wherew_iis the weight of flow i.
- WFQ with equal weights becomes a standard FQ scheduler.
- Each flow is protected from others, and end-to-end delay bounds can be guaranteed for leaky bucket-constrained flows.
- WFQ Implementation:
- For each packet, a virtual theoretical departure date is computed (as if it were a perfect GPS scheduler).
- When the output link is idle, the packet with the smallest virtual date is selected for transmission.
- The pseudo code is similar to FQ, with the virtual departure time calculation adjusted.
- GPS Approximation:
- WFQ approximates GPS “to within one packet transmission time, regardless of arrival patterns.”
- It has the same O(log(n)) complexity as FQ, where n is the number of flows.
- WFQ can be arbitrarily ahead of GPS but is at most “one packet” late.