Deficit Round Robin Queue Scheduling

The router uses a Deficit Round Robin (DRR) variant that is work-conserving across dispatchable physical policy classes. DRR determines which class can dispatch next; the configured FCFS or WSPT policy determines request order within that class’s shared and exact-worker lanes.

This separation provides:

• Weighted service across policy classes with different request sizes.
• Independent within-class ordering, exact-worker lanes, and strict-priority tiers.
• Progress for requests whose token cost is much larger than their class quantum.
• Bounded arbitration work that does not loop once per token or DRR round.

Request Cost and Quantum

Each request receives an immutable queue snapshot when it is enqueued:

uncached_tokens = raw_isl_tokens - cached_tokens
scheduling_cost = max(1, uncached_tokens)

The router uses exact uncached tokens for cache-bucket classification and uses the clamped scheduling_cost for DRR and WSPT. The snapshot is not recomputed while the request waits.

Each physical policy class defines a positive quantum, measured in uncached tokens. A class with quantum 4096 earns four times as much DRR credit per round as a class with quantum 1024. This weighting controls token service, not request count: variable-size requests consume correspondingly different amounts of credit.

DRR State

The scheduler maintains the following state for each physical class:

• A shared pending heap for requests that can use any eligible worker.
• One pending heap per exact-worker target, ordered by the same strict priority and FCFS or WSPT policy.
• A deficit containing earned but unspent credit.
• A quantum controlling how quickly the deficit grows.

The scheduler also maintains a ring cursor identifying the first class to visit on the next arbitration call. Starting each scan at the cursor prevents the configured class order from becoming a permanent preference.

Selecting the Next Request

For each class in cursor order, the scheduler selects a class candidate by comparing the dispatchable shared-heap head with the dispatchable head of each exact-worker lane. It then applies DRR to that candidate:

1. If the class is empty, reset its deficit to zero.
2. If none of its lane heads can currently dispatch, retain its deficit but add no credit.
3. If existing deficit covers the selected candidate’s cost, dispatch it without adding another quantum.
4. Otherwise, add one quantum and dispatch if the candidate is now affordable.
5. If the candidate remains unaffordable, continue to the next class.

Quantum is granted per ring round, not per request. A class that retained enough credit can dispatch multiple requests from the same weighted allocation:

quantum = 10
request costs = 3, 3, 3, 3
grant one quantum: deficit = 10
dispatch cost 3:   deficit = 7
dispatch cost 3:   deficit = 4
dispatch cost 3:   deficit = 1
next cost is 3:    advance the cursor

Adding another quantum for every request would let small requests accumulate credit faster than they consume it and would violate the configured weighting.

Bulk Credit for Oversized Requests

A request may cost many times its class quantum. Repeatedly scanning the ring once per virtual round would make arbitration time proportional to request size. Instead, after one complete ring makes no progress, the scheduler calculates how many additional complete rounds are required for each dispatchable class:

rounds_needed =
    ceil((head_cost - current_deficit) / quantum)

It selects the minimum rounds_needed, adds that number of virtual rounds to every dispatchable class, and scans the ring once more. Each class receives:

added_credit = class_quantum * virtual_rounds

Applying the same virtual-round count preserves weighting because every class still scales credit by its own quantum.

For example:

The scheduler fast-forwards four rounds. standard gains 4000 credit and reaches 5000, while latency gains 8000 and reaches 10000. latency can then dispatch and retains 1000 credit after paying its cost.

If every class head is blocked, there are no dispatchable classes and the scheduler adds no bulk credit.

Charging and Cursor Movement

After selecting a request, the scheduler subtracts its immutable scheduling cost from the class deficit.

• If the class becomes empty, its deficit resets and the cursor advances.
• If the next head is already affordable, the cursor stays on the class so it can spend the remainder of its weighted burst.
• Otherwise, the class retains its remaining deficit and the cursor advances.

Blocked classes retain previously earned credit but do not accumulate more credit while blocked. This prevents unavailable classes from building an unbounded burst while preserving work they had already earned.

Dispatchability and Head-of-Line Behavior

A shared head is dispatchable when its eligible workers are not all above the class busy threshold. An exact-worker lane head is checked against its target worker. If no eligible endpoint remains, the candidate proceeds to worker selection so the router can return the appropriate error instead of parking it indefinitely. Eligibility continues to enforce exact pins, worker allow-lists, DP-rank bounds, taints, and overload filtering.

Head-of-line blocking is lane-local. The shared heap does not search past a blocked shared head, and an exact-worker lane does not search past its own blocked head. A blocked exact-worker lane does not prevent another exact-worker lane, or a dispatchable shared head, from competing for the class. FCFS/WSPT ordering is not bypassed within any individual lane.

New arrivals also join an existing backlog in their resolved class instead of bypassing queued work. Queue limits, ordering, and DRR charging apply equally to allow-listed and unconstrained requests.

Complexity and Progress

One arbitration call performs:

1. At most one ring scan across all classes.
2. One linear calculation for bulk virtual rounds when required.
3. At most one final ring scan.

For C configured classes and L exact-worker lane heads that must be inspected or rechecked, arbitration is O(C + L log L) in the worst case, regardless of request cost or quantum. Candidate exact-worker heads are tree indexed, so ordinary selections do not need to rescan every ready lane; a worker-state recheck can visit the affected blocked lanes and pay the tree update factor. The queue actor calls arbitration repeatedly while work remains dispatchable, but each individual selection is bounded and continuation draining remains local to the actor.

With only the synthetic no-YAML default class, the ring contains one class. DRR reduces to single-class arbitration, but exact-worker requests still use their separate lanes.

Configuration

Set each physical class’s quantum in the router policy YAML:

1
default_policy_family: standard
2
uncached_isl_buckets:
3
  - min_tokens: 0
4
    bucket: cached
5
  - min_tokens: 3072
6
    bucket: uncached
7
8
policy_classes:
9
  - name: cached
10
    policy_family: standard
11
    cache_bucket: cached
12
    queue_policy: wspt
13
    quantum: 2048
14
15
  - name: uncached
16
    policy_family: standard
17
    cache_bucket: uncached
18
    queue_policy: fcfs
19
    quantum: 512

Use larger quantum ratios only when the corresponding classes should receive larger shares of uncached-token service. For the complete policy-family and cache-bucket schema, thresholds, and per-worker queue limits, see Configuration and Tuning. See the tested sample policy for a complete profile.

Prioritize Premium Requests with Policy Classes

Policy classes help a shared deployment protect premium traffic during demand spikes. Under sustained prefill pressure, the router gives premium requests a larger share of queued service while regular requests continue receiving service. When premium demand subsides, regular traffic can use all available capacity.

Configure Premium and Regular Classes

This example mirrors the CPU Mocker regression test: one aggregated worker serves four concurrent sequences, and every request has 512 uncached input tokens and generates one output token. Save the following configuration as policy-classes.yaml:

1
default_policy_family: regular
2
uncached_isl_buckets:
3
  - min_tokens: 0
4
    bucket: all
5
policy_classes:
6
  - name: premium
7
    policy_family: premium
8
    cache_bucket: all
9
    queue_policy: fcfs
10
    quantum: 512
11
    prefill_busy_threshold: 1536
12
    request_queue_limit_per_worker: 1024
13
  - name: regular
14
    policy_family: regular
15
    cache_bucket: all
16
    queue_policy: fcfs
17
    quantum: 128
18
    prefill_busy_threshold: 1536
19
    request_queue_limit_per_worker: 1024

Start the backend worker, then launch the frontend with load tracking and the policy configuration:

$
python -m dynamo.frontend \
>
    --router-mode kv \
>
    --load-aware \
>
    --router-policy-config ./policy-classes.yaml

In this one-output-token, four-wide workload, prefill_busy_threshold: 1536 admits four 512-token requests before sustained prefill pressure causes later requests to enter the policy queues. While both queues remain backlogged, the 512:128 quantum ratio gives premium four times the DRR credit. Tune the threshold to the request sizes and prefill pressure at which queueing should begin in your deployment.

Select a Class on Each Request

Send the requested policy family in the x-dynamo-meta-policy-class header:

$
curl http://localhost:8000/v1/completions \
>
    -H "content-type: application/json" \
>
    -H "x-dynamo-meta-policy-class: premium" \
>
    -d '{"model":"YOUR_MODEL","prompt":"YOUR_PROMPT","max_tokens":1}'
$
$
curl http://localhost:8000/v1/completions \
>
    -H "content-type: application/json" \
>
    -H "x-dynamo-meta-policy-class: regular" \
>
    -d '{"model":"YOUR_MODEL","prompt":"YOUR_PROMPT","max_tokens":1}'

Requests with a missing or unrecognized class header use the regular default family in this configuration. See Policy-Class Queues for the complete class and cache-bucket resolution rules.

Observe the Premium Share

The regression workload releases 320 distinct 512-token prompts from each class at the same time. This keeps both queues backlogged with identical request costs. An equal-share control changes the regular quantum from 128 to 512. Across four fresh CPU Mocker runs, the test observed:

The weighted configuration shifts the first 320 completions from an even split to approximately 4:1. Premium receives substantially more service, and regular still completes 63-66 requests during the same window. Measuring a completion prefix captures the service share while both queues are active.

Each request costs 512 uncached tokens in this workload. Premium earns 512 tokens of DRR credit per round and regular earns 128, producing the ideal 256:64 split. Equal request costs make the queued token-service ratio visible directly in request completions; with varied request sizes, quantum continues to control the share of uncached-token service.

The CPU Mocker regression test at tests/router/test_policy_class.py asserts both the larger premium share and continued regular progress.