4.2.1 Fair Queuing (FQ) Basics

In standard FIFO, a large "bulky" packet blocks a small "interactive" packet. FQ creates separate queues for each flow and services them bit-by-bit logically.

4.2.2 Generalized Processor Sharing (GPS)

GPS is the theoretical "ideal" fluid-flow model.

• Concept: The server processes bits from all non-empty queues simultaneously.
• Guarantees: Flow $i$ is guaranteed a rate $R_i = rac{w_i}{sum w_j} C$.
• Efficiency: If a flow is idle, its capacity is redistributed proportionally to active flows.

4.2.3 Weighted Fair Queuing (WFQ)

Since we cannot send bits in parallel from different packets, WFQ emulates GPS by sending packets in order of their Virtual Finishing Times.

Finishing Time Calculation Algorithm:

For packet $k$ of flow $i$: $$F_{i,k} = max(F_{i,k-1}, V(a_{i,k})) + rac{L_{i,k}}{w_i}$$

1. $a_{i,k}$: Arrival time.
2. $L_{i,k}$: Packet length.
3. $w_i$: Flow weight.
4. $V(t)$: Virtual Time (Round Number) of the system.

Numerical Scenario Trace:

Suppose Flow 1 ($w=1$) and Flow 2 ($w=2$) share a 30Mbps link. All packets size 1000 bits.

• Packet 1 (Flow 1) arrives at $t=0$: $F_{1,1} = 0 + 1000/1 = 1000$.
• Packet 1 (Flow 2) arrives at $t=0$: $F_{2,1} = 0 + 1000/2 = 500$.
• Result: Packet 2 (Flow 2) is transmitted first, as its Finishing Time is earlier.

4.2.4 Bit-Round Fair Queuing (BRFQ)

BRFQ is a variation that uses "bit-rounds" (the time to send one bit from each active flow) as the unit of Virtual Time. It is computationally simpler for high-speed switch ASICs.