Agent Traffic on Shared Internal Services: Per-Tenant Fair Queuing, Concurrency Caps and Re-Plan Amplification

A familiar service with a new kind of caller

Most companies have a handful of internal services that everything calls: order lookup, customer profile, pricing, entitlement checks. They were sized for callers whose behaviour is known. A checkout flow calls order lookup once per page; a batch job calls it at a rate someone configured. When those callers misbehave, they misbehave in a predictable way, and the classic protections work: a shared queue, a timeout, a retry policy with backoff.

Agents change the shape of the traffic in two ways. First, an agent loop decides at run time how many tool calls to make. A loop that is stuck, or that has been given a broad task, can call the same service forty times a second for a minute without anyone having configured that rate. Second, an agent does not merely retry a failed call. It re-plans: a refused lookup becomes two different lookups, or a search followed by a fetch. Each failure creates more work, so the load on a struggling service grows as the service struggles. This article keeps the existing service and changes how it admits calls, and how the agent runtime spends them.

What stays deterministic

None of the protections below involves a model. They are admission rules on the service side and a budget on the caller side, and both can be tested with synthetic traffic.

Three admission policies

The worked example compares three ways of admitting calls to the same service.

• One shared FIFO queue. Every call joins one bounded queue; when it is full, new calls are refused; calls that wait too long are abandoned by their callers. Whoever sends most occupies most of the queue, so a burst from one tenant becomes waiting time for all of them.
• Shared queue with a per-tenant concurrency cap. No tenant may have more than N calls running. This protects workers: the noisy tenant can no longer occupy all of them. It does not protect the queue. The capped tenant’s calls still wait in the shared queue, and when that queue is full the others are refused.
• One bounded queue per tenant, served round-robin. Each tenant can only fill its own queue, and the dispatcher takes one call from each backlogged tenant in turn. This is the idea behind fair queuing, and the Kubernetes API server applies it to its own traffic: API Priority and Fairness queues requests per flow and uses shuffle sharding so that a heavy flow shares a queue with few light ones.

Worked example

A service has eight workers and each call takes 200 ms, so it handles about 40 calls per second. Tenants A, B and C send eight calls per second each. Tenant D is an agent that also sends eight per second until, from 30 s to 70 s, its loop runs away at 40 per second. Every refused or abandoned agent call is re-planned into two new calls half a second later, for at most three rounds. Callers give up on a call that has waited two seconds. The queue holds 200 calls; the per-tenant variant splits it into four queues of 50. The run lasts 120 s.

Read the table from the top. Before the runaway the four tenants offer 32 calls per second against a capacity of 40, so nothing waits. During the runaway they offer 64, and the shared queue fills. Ordinary tenants lose up to a quarter of their calls. Turning off re-planning helps but does not fix it: the runaway alone is enough to hurt them. The concurrency cap does less than people expect, because the agent’s calls fill the shared queue and the ordinary tenants are refused at admission even though workers are free for them.

Per-tenant queues protect A, B and C completely. They do nothing for D itself: more of its calls are refused, each refusal is re-planned, and it ends up offering 24,816 calls for the same original work of 2,240. The last row stops that at the source. A token bucket in the agent runtime holds back 1,191 calls before they leave, so the service never sees the burst and the agent never re-plans. The runnable example reproduces every row, and the interactive lab linked below runs the same model with every input exposed.

Service side: per-tenant queues

The admission layer is short. The important properties are that the tenant comes from authenticated identity, that each tenant has its own bound, and that the dispatcher rotates.

Illustrative python, checked for syntax; adapt names and storage to your system.

class FairAdmission:
    """One bounded queue per tenant, dispatched round-robin."""

    def __init__(self, tenants, limit_per_tenant):
        self.order, self.limit = list(tenants), limit_per_tenant
        self.queues = {t: deque() for t in tenants}
        self.next = 0

    def offer(self, call) -> bool:
        q = self.queues[call.tenant]
        if len(q) >= self.limit:
            return False              # refuse this tenant only; return 429 with Retry-After
        q.append(call)
        return True

    def take(self):
        for _ in range(len(self.order)):
            t = self.order[self.next % len(self.order)]
            self.next += 1
            if self.queues[t]:
                return self.queues[t].popleft()
        return None

Two refinements matter in production. Weight tenants by what they pay for or by priority, rather than giving every tenant an equal turn, and when there are thousands of tenants, hash them onto a fixed set of queues instead of creating one queue each; shuffle sharding keeps the chance that a heavy tenant shares every queue with a given light one small.

Caller side: the agent budget

The Google SRE book describes client-side adaptive throttling: a client that sees many of its recent requests rejected starts rejecting new ones locally, and it caps retries at three attempts per request and at about ten percent of requests per client. The agent runtime needs the same two limits, applied to tool calls rather than retries: a rate per run or per tenant, checked before the call is sent, and a cap on how many rounds of re-planning a failure may trigger. A refusal from the service should reach the model as a result it can reason about, such as service busy, retry after 2 s, not as a prompt to try something else immediately.

Migration steps for an existing service

1. Measure first. Break the service’s request rate, queue time and refusals down by caller identity, and mark which identities are agent runtimes.
2. Give every agent runtime its own identity per tenant, so the service can tell one customer’s agent from another’s.
3. Add per-tenant queues in shadow mode: compute what would have been refused and compare it with what was.
4. Switch admission to per-tenant queues and return 429 with Retry-After when a tenant’s queue is full.
5. Add the budget and round cap to the agent runtime, and surface refusals to the model as structured results.
6. Alert on re-plan share: the fraction of an agent’s calls that follow a failure. A rising share is the earliest sign of amplification.

When the protections are unnecessary

If agents call a service through a queue that already enforces per-customer quotas, or the service is cheap enough to scale out faster than any burst, a shared queue may be fine. If the agent makes a small, fixed number of calls per task, a plain retry budget covers it. The pattern earns its keep when agent loops are open-ended, several tenants share a service sized for steady traffic, and failures feed back into more calls.

Failure modes

• Tenant taken from a request header the agent can set, so a runaway loop can spread itself over many tenants.
• Per-tenant concurrency caps without per-tenant queues, which protect workers and leave the queue to the noisiest tenant.
• A budget per agent run but none per tenant, so a hundred parallel runs each stay within budget and together do not.
• Refusals reported to the model as plain errors, which invites the model to re-plan around them.
• Weights set once and never revisited, so a tenant that grew legitimately is throttled as if it were misbehaving.

Verification

Replay a burst from one tenant against a staging service and check three numbers per tenant: share of calls served, queue wait, and refusals. The ordinary tenants’ numbers should not move when the burst starts. Then disable the agent budget and confirm that the re-plan share rises and the service-side queues still hold. Keep the per-tenant metrics on the dashboard after the rollout; fairness that is not measured drifts.

Practice and related reading

Hands-on: Agent tenants on a shared service: fair queues and re-plans, an interactive lab on synthetic data.

Further reading:

• Bulkhead pattern
• Load shedding
• Retry and backoff patterns
• A2A multi-tenancy

Sources and scope

Checked against these sources on 22 October 2026. Examples and figures are illustrative, not measurements.

• Kubernetes documentation: API Priority and Fairness (fair queuing, shuffle sharding)
• Amazon Builders’ Library: Fairness in multi-tenant systems
• Google SRE book, chapter 21: Handling Overload (adaptive throttling, retry budgets)
• Netflix concurrency-limits (adaptive concurrency limits), GitHub