[Flow Control] Saturation Activated Cross-Band Fairness Policy

[loicmarchal]

Proposal: Saturation-Activated Weighted Fair Queuing Dispatch

Summary

The Flow Controller's dispatch cycle iterates priority bands strictly from highest to lowest, dispatching from the first non-empty eligible band. Under sustained high-priority load, lower-priority bands never receive dispatch opportunities and starve indefinitely. This proposal introduces an optional Weighted Fair Queuing (WFQ) dispatch policy that activates above a configurable saturation threshold, distributing dispatch slots across eligible priority bands proportionally to their weights while preserving strict priority semantics under light load.

---

Motivation

The current strict dispatch model is correct when high-priority traffic is bursty: lower bands drain in the gaps. However, when high-priority load is sustained, lower-priority requests queue until they hit capacity limits or TTL, and are rejected without ever being served.

This matters in multi-tenant deployments where different tenants use different priority bands and operators need to guarantee some minimum service level to all tiers, not just "best effort when higher bands are idle." It also matters in deployments mixing online real-time requests with batch requests, where batch traffic typically receives the lowest priority and can starve indefinitely under sustained online load.

A WFQ dispatch policy addresses this by ensuring that, under pressure, every eligible band receives a share of dispatch slots proportional to its configured weight.

---

Current Behavior

The Flow Controller uses a strict 3-Tier Dispatch Hierarchy:

1. Priority (Band Selection): dispatchCycle() iterates AllOrderedPriorityLevels() in descending order (highest numeric value first). For each band, it checks saturation >= ceiling[i]. If true, the entire cycle stops (Head-of-Line blocking). If false, it attempts to dispatch one item from that band.
2. Fairness (Flow Selection): The configured fairness policy (Global Strict or Round Robin) selects which flow's queue within the band to serve.
3. Ordering (Item Selection): The ordering policy (FCFS, SLO Deadline, EDF) determines which request from that queue is dispatched.

The cycle dispatches at most one item per tick and returns immediately after the first successful dispatch. As long as a higher-priority band has items, lower bands never get a turn.

---

Proposed Design

Saturation-Activated WFQ

The WFQ dispatch policy replaces the strict top-down band iteration with a weighted scheduler, but only when saturation exceeds a configurable activation threshold. Two scheduling mechanisms are available (see below). This creates three operating regions:

Saturation Region	Behavior
Below activation threshold	Strict dispatch (current behavior). All bands drain naturally; no intervention needed.
Between activation threshold and holdback ceilings	WFQ active. Dispatch slots are distributed across eligible bands proportionally to weights.
Above holdback ceilings	Holdback gates lower bands. WFQ distributes among the remaining eligible bands only.

Interaction with Priority Holdback

The two mechanisms are orthogonal and composable:

• Holdback controls which bands are eligible (ceiling check).
• WFQ controls how eligible bands share dispatch slots.

Holdback ceilings remain authoritative. A band gated by holdback is excluded from WFQ consideration entirely. WFQ only operates over the set of bands that pass their ceiling check.

Example with bands {20, 10, 0}, holdback ceilings {1.0, 0.7, 0.3}, WFQ activation at 0.5:

Saturation	Band 20	Band 10	Band 0	Dispatch Mode
0.3	eligible	eligible	eligible	Strict (below 0.5)
0.6	eligible	eligible	gated	WFQ over {20, 10}
0.8	eligible	gated	gated	WFQ over {20} (effectively strict)
1.0	gated	gated	gated	Nothing dispatches

Scheduling Mechanisms

Two scheduling mechanisms are available, selectable via the schedule parameter. Both maintain the same proportional dispatch ratio; they differ in how dispatch slots are distributed over time.

priority-first (default) — Credit-Based Priority Rounds

Front-loads higher-priority bands, serving them first within each round before moving to lower bands. Each round spans W = sum(weights) dispatch cycles, and each band receives a credit quota equal to its weight.

Best for workloads where minimizing high-priority latency under saturation is the primary goal. This is the default because it stays closest to the original strict dispatch behavior while preventing starvation.

State: Each eligible band i has a weight w_i and a credit counter c_i.

Each dispatch cycle:

1. Filter out bands gated by holdback (saturation >= ceiling[i]).
2. Among remaining eligible bands, select the highest-priority band with credit > 0.
3. Dispatch one item from the selected band. Decrement: c_i -= 1.
4. When all credits reach 0, start a new round: c_i = w_i for all eligible bands.

Lifecycle:

• When WFQ activates (saturation crosses the activation threshold upward), credits initialize to w_i for each eligible band (start of a fresh round).
• When WFQ deactivates (saturation drops below the threshold), credits reset.
• Bands gated by holdback lose their remaining credit. When a gated band becomes eligible again, it starts with zero credit and receives its full quota at the next round reset.

Example with bands {20, 10, 0}, weights {6, 3, 1} (simplified for illustration; see Weight Distribution for the derivation formula), all bands eligible and non-empty:

Cycle	credit_20	credit_10	credit_0	Selected	Reasoning
1	6	3	1	band 20	Highest priority with credit
2	5	3	1	band 20	Highest priority with credit
3	4	3	1	band 20	Highest priority with credit
4	3	3	1	band 20	Highest priority with credit
5	2	3	1	band 20	Highest priority with credit
6	1	3	1	band 20	Highest priority with credit
7	0	3	1	band 10	Band 20 exhausted
8	0	2	1	band 10	Band 20 exhausted
9	0	1	1	band 10	Band 20 exhausted
10	0	0	1	band 0	Bands 20, 10 exhausted
reset	6	3	1		New round

After 10 cycles: band 20 dispatched 6 times, band 10 dispatched 3 times, band 0 dispatched 1 time -- a 6:3:1 ratio matching the weights, with higher-priority bands served first within each round. Under strict dispatch, all 10 cycles would go to band 20.

Round size derivation: Credits are derived from weight ratios, normalized so the smallest weight receives 1 credit. The round size is the sum of all credits. With proportional distribution and bands {20, 10, 0}: ratio 21:11:1, credits {21, 11, 1}, round size = 33.

When priority values are widely spaced, rounds can be long. With bands {100, 50, 1}: credits {100, 50, 1}, round size = 151 -- band 1 waits up to 150 cycles, which may exceed its TTL. The optional maxFairnessWindow parameter caps the round by rescaling credits proportionally, with a floor of 1 credit per band.

Rescaling algorithm:

1. Scale each weight proportionally: c_i = w_i * maxFairnessWindow / sum(w).
2. Floor each value, with a minimum of 1 per band.
3. Distribute any remaining credits (due to rounding) to bands with the largest fractional remainders.

maxFairnessWindow	Credits	Actual round	Band 1 max wait
(unset)	{100, 50, 1}	151	150 cycles
80	{53, 26, 1}	80	79 cycles
20	{13, 6, 1}	20	19 cycles

Example with credit remainder: bands {20, 10, 3}, proportional distribution weights {18, 8, 1}, sum = 27, maxFairnessWindow = 10:

1. Scale: {18*10/27, 8*10/27, 1*10/27} = {6.67, 2.96, 0.37}
2. Floor with min 1: {6, 2, 1} = 9. Target is 10, so 1 credit remains.
3. Fractional parts: 0.67 (band 20), 0.96 (band 10), 0 (band 3). Largest is 0.96, so band 10 gets +1.
4. Result: {6, 3, 1} = 10.

Ratios shift slightly due to integer rounding, but the proportional relationship between bands is preserved. Use maxFairnessWindow when mixing high-priority online traffic with low-priority traffic (such as batch traffic) and the low priority tier needs a bounded worst-case wait despite its low weight.

interleaved — Virtual-Time Scheduling

Distributes dispatch slots evenly across time. Each priority band maintains a virtual time counter that advances by a stride inversely proportional to its weight: higher-weight bands advance slowly (selected more often), lower-weight bands advance quickly (selected less often).

Best for workloads where consistent latency across all priority bands matters, such as multi-tenant environments where every tier has an SLO.

State: Each eligible band i has a weight w_i and a virtual time vt_i.

Each dispatch cycle:

1. Filter out bands gated by holdback (saturation >= ceiling[i]).
2. Among remaining eligible bands, select the band with the smallest vt. On tie, the highest-priority band wins.
3. Dispatch one item from the selected band.
4. Advance the selected band's virtual time: vt_i += 1 / w_i.

Lifecycle:

• When WFQ activates, all virtual times initialize to zero.
• When WFQ deactivates, virtual times reset.
• Bands gated by holdback do not participate in selection and do not advance. When a gated band becomes eligible again, its virtual time resets to the current minimum vt across eligible bands, preventing it from monopolizing dispatch after rejoining.

Example with bands {20, 10, 0}, weights {6, 3, 1} (simplified for illustration; see Weight Distribution for the derivation formula), all bands eligible and non-empty:

Cycle	vt_20	vt_10	vt_0	Selected	Reasoning
1	0	0	0	band 20	Three-way tie, highest priority wins
2	0.17	0	0	band 10	Tie at 0 between {10, 0}, higher priority wins
3	0.17	0.33	0	band 0	Smallest vt
4	0.17	0.33	1.00	band 20	Smallest vt
5	0.33	0.33	1.00	band 20	Tie, highest priority wins
6	0.50	0.33	1.00	band 10	Smallest vt
7	0.50	0.67	1.00	band 20	Smallest vt
8	0.67	0.67	1.00	band 20	Tie, highest priority wins
9	0.83	0.67	1.00	band 10	Smallest vt
10	0.83	1.00	1.00	band 20	Smallest vt

After 10 cycles: band 20 dispatched 6 times, band 10 dispatched 3 times, band 0 dispatched 1 time -- the same 6:3:1 ratio as priority-first, but lower-priority bands start being served earlier (band 0 is served by cycle 3 instead of cycle 10).

Comparison

Property	priority-first	interleaved
Dispatch ratio	Proportional to weights	Proportional to weights
High-priority latency	Best (served first each round)	Slightly worse (shares early slots)
Low-priority latency	Worse (waits until higher bands exhaust credit)	Best (served early via interleaving)
Burst pattern	Grouped by priority	Evenly spread
Best fit	Saturation defense with starvation prevention	Multi-tenant SLO guarantees

Weight Distribution

The distribution parameter controls how weights are derived for each priority band. Three modes are available:

Proportional (default): Weights are derived from numerical priority values, shifted so the lowest-priority band always receives a weight of 1. This ensures all bands get a non-zero weight, including bands with priority 0 or negative values (e.g., -1 for batch traffic).

w_i = (p_i - p_min + 1) / sum(p_j - p_min + 1 for all eligible j)

Where p_min is the lowest priority value among eligible bands.

With bands {20, 10, 0}: weights = {21/33, 11/33, 1/33} = {0.64, 0.33, 0.03}.
With bands {20, 18, 1}: weights = {20/39, 18/39, 1/39} = {0.51, 0.46, 0.03}.
With bands {20, 10, -1}: weights = {22/35, 12/35, 1/35} = {0.63, 0.34, 0.03}.

Use when the numerical spacing between priority values carries meaning and priorities that are close in value should receive similar dispatch shares. This is the default because it stays closest to the original strict priority behavior, where higher values dominate.

Linear: Weights decrease linearly by ordinal position, ignoring numerical priority values. The highest-priority band (rank 0) gets the largest weight.

w_i = (N - i) / sum(N - j for j in 0..N-1)

Where i is the index in descending priority order (0 = highest) and N is the count of eligible bands.

With 3 eligible bands (regardless of their numerical values): weights = {3/6, 2/6, 1/6} = {0.50, 0.33, 0.17}. The result is identical for bands {20, 10, 0}, {20, 18, 1}, or {100, 50, 1}.

Use when priority values are arbitrary categorical labels and the numerical spacing should not affect dispatch share.

Explicit: The operator configures a weight for each priority band directly via the ratios parameter. This decouples dispatch share from priority values entirely.

---

Integration Points

New Plugin Type: DispatchPolicy

A DispatchPolicy interface is added to the flow control plugin model, following the same pattern as UsageLimitPolicy and FairnessPolicy:

• Interface: Defines the dispatch band selection logic, called once per dispatch cycle.
• Factory registration: Registered in runner.registerInTreePlugins() alongside existing plugin types.
• Injection: Passed to the Processor constructor, stored as a field.

Two implementations:

• Strict (default): Current behavior. Iterates bands top-down, stops on first HoL block. This is the zero-change baseline when WFQ is not configured.
• WFQ: Weighted scheduling with activation threshold and configurable scheduling mechanism (priority-first or interleaved), as described above.

Processor Changes

dispatchCycle() delegates band selection to the DispatchPolicy instead of performing inline iteration. The policy receives the current saturation, the ordered priority list, the ceilings from UsageLimitPolicy, and returns the selected priority band (or signals that no band is eligible).

Scheduling state (virtual-time counters or credit counters, depending on the mechanism) is managed internally by the WFQ policy instance and is scoped to the processor (one state table per shard).

Configuration Loading

A new optional field dispatchPolicyPluginRef is added to the flowControl configuration section. When absent, the strict dispatch policy is used (preserving backward compatibility).

---

Configuration

WFQ with priority-first scheduling and proportional weights (default):

plugins:
  - type: priority-holdback-policy
    name: my-holdback
    parameters:
      domain: value
      minCeiling: 0.3
      maxCeiling: 1.0
  - type: cross-band-fairness-policy
    name: my-cross-band-fairness
    parameters:
      activationThreshold: 0.5
      schedule: priority-first
      distribution: proportional

flowControl:
  usageLimitPolicyPluginRef: my-holdback
  dispatchPolicyPluginRef: my-cross-band-fairness

WFQ with interleaved scheduling and linear weights:

plugins:
  - type: priority-holdback-policy
    name: my-holdback
    parameters:
      domain: rank
      minCeiling: 0.3
      maxCeiling: 1.0
  - type: cross-band-fairness-policy
    name: my-cross-band-fairness
    parameters:
      activationThreshold: 0.5
      schedule: interleaved
      distribution: linear

flowControl:
  usageLimitPolicyPluginRef: my-holdback
  dispatchPolicyPluginRef: my-cross-band-fairness

WFQ with explicit weights:

plugins:
  - type: cross-band-fairness-policy
    name: my-cross-band-fairness
    parameters:
      activationThreshold: 0.5
      distribution: explicit
      ratios:
        20: 0.7
        10: 0.2
        0: 0.1

flowControl:
  dispatchPolicyPluginRef: my-cross-band-fairness

No WFQ (current behavior, default):

flowControl:
  # dispatchPolicyPluginRef is omitted; strict dispatch is used.

Parameters

• activationThreshold (float64, required): Saturation level above which WFQ engages. Must be in [0.0, 1.0). Below this value, strict dispatch applies.
• schedule (string, optional, default: "priority-first"): Scheduling mechanism. "priority-first" uses credit-based priority rounds that front-load higher bands. "interleaved" uses virtual-time scheduling that spreads slots evenly across bands.
• distribution (string, optional, default: "proportional"): Weight assignment strategy. "proportional" derives weights from numerical priority values. "linear" derives linearly decreasing weights by ordinal position. "explicit" uses operator-provided weights.
• ratios (map[int]float64, required when distribution is "explicit", ignored otherwise): Dispatch ratio per priority band, expressed as proportions summing to 1. Bands not listed receive no dispatch slots.
• maxFairnessWindow (int, optional, no default): Maximum number of dispatch cycles per round for the priority-first mechanism. When the natural round size (derived from weights) exceeds this cap, weights are rescaled proportionally with a floor of 1 credit per band. This bounds the worst-case wait time for the lowest-priority band to maxFairnessWindow - 1 cycles. Ignored when schedule is "interleaved". When unset, the round size is determined entirely by the weight ratios.

---

Trade-offs

What this adds:

• Bounded starvation for lower-priority bands under sustained load.
• Composable with existing holdback and fairness policies without modifying them.
• Zero behavioral change when not configured (strict dispatch remains the default).
• Configurable activation point avoids interfering with normal low-saturation operation.

What it costs:

• Marginal latency increase for highest-priority requests when WFQ is active, since some dispatch slots go to lower bands.
• Additional per-cycle computation: scheduling state tracking, eligible-band filtering. Negligible relative to the 1ms dispatch tick.
• Operators must reason about additional parameters (activation threshold, distribution, and optionally ratios).

Design constraints:

• WFQ intentionally does not override holdback ceilings. If the operator wants a band fully gated under high saturation, WFQ respects that.
• Strict dispatch is not "unfair" in all cases. When high-priority traffic is bursty and lower bands drain in the gaps, WFQ adds complexity without benefit. The activation threshold mitigates this by keeping strict dispatch active under light load.

[loicmarchal]

@lioraron this is a proposal for a cross priority band starvation prevention (related to kubernetes-sigs/gateway-api-inference-extension#1861). Let me know what you think and if it addresses the issue you raised.

[loicmarchal]

@lioraron I adapted the formula of the weight distribution for the priority-first so that it supports negative priority values through a shift. I remembered for batch the priority value can be -1

[loicmarchal]

@LukeAVanDrie I'd be interested to have your feedback on this. It addresses an issue raised awhile back in kubernetes-sigs/gateway-api-inference-extension#1861

[LukeAVanDrie]

Will take a look! This is highly relevant to a recent thread, will tag you in the slack.

[LukeAVanDrie]

Thanks @loicmarchal! The architecture looks solid: a dedicated dispatch-policy plugin, keeping strict top-down as the default, and cleanly separating holdback eligibility from WFQ sharing.

Here is some specific feedback on a few edge cases we need to flesh out:

1. Handling Empty Bands (Work Conservation)

How do we handle bands that are eligible but have no queued items?

• priority-first: If an empty band never spends its credit, the round never resets. Also, does a failed selection consume credit? Consuming it skews the ratios away from the configured weights; not consuming it means we need a defined fallback to another band within the same cycle.
• interleaved: An empty band's virtual time (vt) will lag. When traffic returns, it will have the smallest vt and monopolize dispatch to "catch up." We need a reset mechanism for empty-to-busy transitions.

2. Dynamic Priorities

Bands can come and go, but the current weight derivations assume a fixed set.

• Proportional: If the lowest priority band disappears, the shift changes and drastically alters the ratio between the remaining bands. The ratio between two bands shouldn't depend on which other bands happen to exist.
• Explicit: A newly provisioned band missing from the config will permanently starve. We need a defined fail-open default weight.
• What happens to credits or vt state when the band set changes mid-round?

3. Interface Shape: Rank Function + Outcome Callback

One refinement within the proposed architecture: keep the loop in the framework and make the policy a rank function rather than a selector. The policy returns a preference order over the eligible bands, the processor walks that order work-conservingly (exactly like today's loop), and the framework reports back which band actually dispatched. The policy then never has to model empty bands or failed selections; it just orders candidates and settles credit/vt accounting on the outcome callback. Strict dispatch falls out as the identity order over descending priorities, and most of the questions in point 1 stop being policy concerns at all.

Nit: Let's also drop the "one state table per shard" phrasing. Since we run a single processor now, the state (like credits or vt) should just live with the policy instance, similar to how it works for UsageLimitPolicy.

4. Policy Contracts & Conflicts

• We need to update the UsageLimitPolicy contract. Since dispatch order is now pluggable, it should state that ceilings are authoritative per band, rather than relying on the old top-down early stop. The monotone-ceilings requirement should stay, though, so any usage-limit policy composes predictably with any dispatch policy.
• soft-reflective-ceiling-policy already does its own cross-band sharing. Mixing it with WFQ will create conflicting schedulers. We should declare this specific combination unsupported for now.

5. State Resets on Toggling

Saturation detectors aren't smoothed. If saturation hovers near the activationThreshold, we'll rapidly toggle between strict and WFQ, resetting credits or vt on every crossing (meaning a round might never actually complete). We either need hysteresis, state retention across deactivations, or smoothing in the detector layer.

[LukeAVanDrie]

Two more suggestions, less about correctness and more about scoping / naming

Most of the spec complexity concentrates in priority-first + proportional: the round-size derivation, maxFairnessWindow rescaling with remainder distribution, and the rejoin asymmetry (a band returning from holdback waits at zero credit until the round ends, while interleaved rejoins immediately at min-vt). interleaved with explicit/linear already covers the multi-tenant SLA case in the motivation. I'd land that first and follow up with priority-first once the extension-point contract has settled.

I'd also name the interface for the decision, not the goal; e.g., BandSelectionPolicy, with bandSelectionPolicyPluginRef. The extension point covers strict dispatch too, and strict isn't "fairness," so naming the interface after cross-band fairness would misdescribe its default implementation.

This mirrors the existing precedent: UsageLimitPolicy names the decision, while priority-holdback and soft-reflective-ceiling name the strategies. The implementations then become strict (default) and cross-band-fairness-policy (the WFQ in this proposal), so the "cross-band fairness" name survives as the plugin type. I'd avoid DispatchPolicy for the interface: the framework's deprecated names for ordering and fairness were IntraFlowDispatchPolicy/InterFlowDispatchPolicy, so the term historically meant something else here. BandSelectionPolicy also reads correctly next to FairnessPolicy (among flows) and OrderingPolicy (among items).

[LukeAVanDrie]

This may also be impacted by #2120. Worth a closer look to see if these are compatible.