AUDIBLE: A Convolution-Based Resource Allocator for Oversubscribing Burstable Virtual Machines

Seyed Ali Jokar Jandaghi, Kaveh Mahdaviani, Amirhossein Mirhosseini, Sameh Elnikety, Cristiana Amza and Bianca Schroeder

Cloud providers sell burstable VMs — cheap machines that idle most of the time but can briefly spike using saved-up credits — and because they mostly sit idle, many can be packed onto one server; but the packing must not be so aggressive that too many burst at once and the server runs out of room, and this paper (Toronto, Microsoft, Michigan) shows the usual bell-curve math badly misjudges those rare simultaneous bursts, so it builds AUDIBLE, which instead adds up the actual observed usage histograms by convolution to read the true risk, packing servers as tightly as an oracle while keeping capacity-shortfall events under half a percent.

The argument in one glance

Problem

Burstable VMs are cheap to pack tightly, but pack them wrong and servers run out of room

Cloud servers sit mostly idle, because customers renting a fixed-size virtual machine size it for their peak demand and then use far less most of the time. To recover that waste, providers sell burstable VMs: a burstable VM has a low baseline allocation, earns credits whenever its usage stays below that baseline, and can spend those credits to briefly burst above the baseline up to a peak. Because a burstable VM stays below its baseline almost all the time — in production, the median one uses only about seven and a half percent of its allocated CPU — a provider can pack many of them onto one server, oversubscribing its capacity. But there is a hard limit on how tightly. If too many burstable VMs on a server accumulate credits and try to burst at the same moment, their combined demand can exceed the server's real capacity, forcing some to be throttled despite having earned the right to burst. That is a server capacity violation, and it breaks the customer's service guarantee. So the allocator must pack aggressively enough to raise utilization, yet keep these violations under a strict limit — and no prior work had studied how to do it for burstable VMs.
What people did

Reuse the standard oversubscription tools

There are two established ways to oversubscribe cloud resources. One is a fixed oversubscription ratio: pretend each server has, say, twenty percent more capacity than it physically does, and pack accordingly. The other, common in the literature, models the combined demand of many VMs as a bell curve using the Central Limit Theorem, then places a VM only if the chance of exceeding capacity stays below the target.
Why it fell short

A fixed ratio is too rigid, and the bell curve misjudges the dangerous tail

Both standard tools fail on burstable VMs, and a study of production traces shows why. A fixed oversubscription ratio is one-size-fits-all, but burstable workloads vary enormously over time and from VM to VM — they are highly skewed and bursty, and they run hotter early in life when freshly granted credits — so any single ratio is either too conservative, wasting capacity, or too aggressive, causing violations; even an oracle that picks the optimal ratio cannot adapt well enough. The Central-Limit-Theorem approach fails for a subtler reason: the risk of a capacity violation lives entirely in the far right tail of the aggregate-demand distribution, the rare moment when many VMs burst together, and a Gaussian bell curve systematically underestimates that tail because real burstable aggregates are far more heavy-tailed than a Gaussian. In the evaluation, the Central-Limit approach achieves high utilization but blows through the violation limit on a meaningful fraction of servers. The problem demands a model that captures the true tail, not an assumed shape.
This paper's idea

Add up the actual usage histograms by convolution to read the real risk

AUDIBLE drops the assumption that demand is Gaussian and instead works directly with the observed empirical distributions. To decide whether a candidate server can safely host a new burstable VM, it takes the histogram of the server's aggregate CPU usage over the recent past, and the histogram of the incoming VM's demand drawn from other VMs of the same type, and combines them by convolution — the exact operation for the distribution of the sum of two independent quantities. From the resulting distribution of what the server's total demand would become, it reads off the probability of a capacity violation directly, tail and all, and places the VM only if that probability stays under the limit. Because it uses measured histograms rather than a fitted curve, it is non-parametric, light-weight, and workload-independent — no machine-learning model to train, no magic parameters to tune — and it packs servers as tightly as an optimal oracle while holding violations well under target.

Why this problem is worth solving

Burstable VMs exist precisely to reclaim idle capacity, and whether they deliver on that hinges entirely on the placement decision.

A burstable VM is designed for workloads that are quiet most of the time and occasionally spike. It has a low baseline CPU allocation and a token bucket: while its usage stays below the baseline it earns tokens at a fixed rate, and it spends tokens to burst above the baseline, up to a peak, one token buying one core-minute at full capacity. Customers like this because they stop paying for cores they rarely use, and providers like it because the contract makes the workload’s shape explicit — below baseline almost always, with a built-in limit on how much it can burst — which is an invitation to pack many burstable VMs onto one server and oversubscribe its capacity. The catch is the server capacity violation: a moment when the burstable VMs on a server collectively have the tokens and the demand to burst beyond what the server physically provides, so some must be throttled despite having earned the right to run, breaking their service guarantee. Providers therefore set a strict cap on the acceptable rate of such violations, and the allocator’s job is to maximize how tightly it packs while keeping violations under that cap. Get it right and idle capacity is recovered; get it wrong and either the servers stay empty or customers get throttled.

The heart of the difficulty is that the risk lives in a tail that the usual mathematics gets wrong.

A natural way to reason about many VMs sharing a server is the Central Limit Theorem: the sum of many independent random demands tends toward a Gaussian whose mean and variance are just the sums of the individual means and variances, so you can estimate the chance the aggregate exceeds capacity from that Gaussian and place a VM only if the chance is small enough. This works passably for some datacenter workloads and is widely used. But a server capacity violation is by definition a rare, extreme event — many VMs happening to burst at once — so the entire decision depends on the far right tail of the aggregate-demand distribution. And that is exactly where a Gaussian is least trustworthy: burstable-VM demand is highly skewed and heavy-tailed, with rare large bursts that a bell curve smooths away, so a Gaussian systematically underestimates the probability of the very simultaneous-burst events the allocator is trying to prevent. A model can look accurate in the body of the distribution and still be dangerously optimistic in the tail. To enforce a stringent violation limit, the allocator needs the tail represented as it actually is, which is what motivates abandoning the parametric assumption altogether.

What people did before, and where it broke

Fixed oversubscription ratio. Treat each server as if it had a fixed percentage more capacity and pack to that inflated number. Where it broke. Burstable workloads are too variable across time and VMs for one ratio to fit; even an oracle-chosen optimal ratio is too rigid, yielding either low utilization or violations.
The provider’s conservative baseline allocator. Reserve capacity cautiously to avoid any risk. Where it broke. It never violates but achieves very low utilization, defeating the purpose of oversubscription.
Per-configuration modeling with perfect predictions. Model each VM by its type’s baseline and peak, even assuming an oracle that predicts its usage bucket. Where it broke. Still overly conservative, leaving utilization low even with clairvoyant information.
Central-Limit-Theorem Gaussian aggregation. Model combined demand as a Gaussian and place a VM if the chance of exceeding capacity is small. Where it broke. The Gaussian underestimates the heavy right tail of burstable aggregates, so it hits the violation limit on a meaningful fraction of servers while chasing high utilization.
The gap. No allocator captured the true, heavy-tailed distribution of aggregate burstable demand to place VMs both tightly and within a strict violation bound, without training or tuning. Building that from observed empirical distributions is what AUDIBLE contributes.

How AUDIBLE works

Deciding if a server can safely host a burstable VM, from measured histograms

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Reclaim idle capacity by packing, but let the tail risk set the density. AUDIBLE starts from the same premise as all oversubscription — servers are underused because burstable VMs sit far below their allocation almost all the time, so many can share a server — but insists that how many is not a fixed number, it is whatever keeps the chance of a simultaneous-burst overflow under the limit. The whole design is organized around estimating that one probability accurately for each placement, so the packing can be as aggressive as the actual risk permits and no more. Recovering the large gap between what cloud tenants are allocated and what they actually use, by carefully overcommitting the slack, is the same opportunity the work on memory-harvesting VMs in cloud platforms covered elsewhere on this site pursues, turning consistently unused reservations into capacity that can be safely handed to other work.

Model the demand from what was measured, not from a convenient formula. The technical pivot is to go non-parametric. Rather than assume the aggregate demand is Gaussian and reason from its mean and variance, AUDIBLE keeps the empirical histograms themselves — the server’s own recent usage, and the observed demand of same-type VMs — and computes with them directly, convolving the two to get the exact distribution of their sum. This is what lets it see the heavy right tail that a bell curve erases, and it needs no fitting, no training, and no tuned parameters, because the data is the model. Driving an allocation decision from the observed statistical profile of the real workload, rather than a parametric stand-in, is the same data-grounded discipline the work on statistical-feature-based memory optimization covered elsewhere on this site follows, letting the measured behavior of the workload dictate the decision instead of an assumed shape.

Hold a hard service guarantee while still packing tightly. The payoff is that AUDIBLE does not trade utilization for safety or safety for utilization: it packs as densely as an oracle that knows the optimal fixed ratio, yet keeps every server’s violation rate well under the strict cap, because its accurate tail estimate lets it approach the limit without crossing it. Enforcing a firm bound on service-level violations while squeezing utilization as high as that bound allows is the same balancing act the work on resource management for shared microservices with service-level guarantees covered elsewhere on this site performs, co-locating aggressively right up to the point where the guarantee would break, and not past it.

Following a placement decision through AUDIBLE

Should this server take one more burstable VM?

A trace, following the paper's design, of how AUDIBLE decides whether a candidate server is a valid host for an incoming burstable VM.

Step 1 of 5

A burstable VM arrives to be scheduled

The scheduler has narrowed the incoming burstable VM to a set of candidate servers with nominally free capacity, and must judge each one on the risk that adding this VM would push aggregate demand past capacity too often.

A capacity violation means some VM with earned tokens gets throttled, breaking its guarantee.

Why it works

The empirical histogram carries the tail the decision depends on. A capacity violation is a rare extreme event, so the placement risk is a tail probability → but the observed usage histogram records those rare large aggregates as they really occur → so AUDIBLE reads the true tail instead of a Gaussian that would smooth it away.
Convolution gives the exact sum-distribution, not an approximation. Adding a VM means adding its demand to the server’s, and the distribution of a sum is a convolution → but convolving the two empirical histograms computes that sum-distribution directly → so the estimated post-placement demand distribution is faithful, heavy tail included.
Being non-parametric removes training and tuning. A fitted or learned model needs parameters and calibration that can drift → but AUDIBLE’s model is just the measured data combined by convolution → so it is light-weight and workload-independent, adapting on its own as behavior changes, with no magic numbers.
Conservative per-type estimates guard the unknown new arrival. A just-placed VM has no history and tends to run hot early with its initial tokens → but AUDIBLE estimates it from the high-demand end of its configuration’s historical distribution → so early-life spikes do not blow the budget it was placed against.
Accurate risk lets it approach the limit without crossing it. A fixed ratio must leave slack for safety or risk violations, capping utilization → but a precise tail estimate lets AUDIBLE pack right up to the allowed violation rate → so it matches an optimal oracle’s density while staying within the guarantee.

What it costs (trade-offs and scope)

Convolution assumes the demands are independent. Combining the incoming VM’s and the server’s distributions by convolution treats them as independent random quantities; correlated bursts across VMs are not directly modeled, and AUDIBLE leans on conservative high-percentile estimates to hedge that assumption rather than modeling the correlation.
It needs measured distributions and a warm-up. The method depends on the server’s recent empirical usage and on historical per-configuration demand data; brand-new VMs are handled by conservative type-based estimates, but the accuracy rests on having representative history, and the conservative estimate can leave some utilization unclaimed.
It targets burstable VMs and CPU. The design and evaluation are for burstable-VM CPU oversubscription; an exploratory extension to regular VMs showed promise but occasionally exceeded the threshold, because large regular VMs can dominate a server’s demand in a way small burstable VMs rarely do.
The evaluation is trace-driven simulation. Results come from large-scale simulation driven by production traces from one major cloud provider, on the common server size and specific violation limits; they are realistic and reproducible via a released artifact, but not a live production deployment.
It solves the validity question, not the whole scheduler. AUDIBLE decides whether a candidate server can safely host a VM; the surrounding choices — which cluster, which valid server to pick, hardware and fault-domain constraints — are orthogonal and handled by the existing scheduler.

The evaluation

Oversubscribing burstable VMs under a strict violation limit

Property	Fixed ratio / conservative	Central Limit Theorem	AUDIBLE
Model of aggregate demand
Utilization
Meets the violation limit
Training or tuning
Worst-server violation vs 1 percent limit

From the paper's trace-driven simulation on 48-core servers with a 1 percent violation limit. AUDIBLE holds every server's violation rate well under target (worst case 0.45 percent) while achieving utilization matching an optimal fixed-ratio oracle and only slightly below the Central-Limit approach — which reached high utilization only by exceeding the limit on 2.5 percent of servers, up to a 1.9 percent violation rate. The overly conservative fixed-ratio and provider-baseline approaches never violate but leave utilization very low.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is twofold: the first characterization study of real burstable-VM workloads, and an allocator that turns its lessons into a clean statistical method. AUDIBLE observes that the risk of a server capacity violation is a tail event that the usual Central-Limit Gaussian systematically underestimates, and that a fixed oversubscription ratio is too rigid for such variable workloads. So it estimates the post-placement demand distribution non-parametrically, convolving the server’s recent empirical usage histogram with a conservative per-type histogram for the incoming VM, and reads the violation probability straight off the true tail. The result packs as tightly as an optimal oracle while keeping every server well under a 1 percent violation limit, with no training and no tuned parameters. Read it within scope. The convolution assumes independence and hedges correlation with conservative estimates; it needs representative measured history and a warm-up; it is built for burstable-VM CPU, with the regular-VM extension still imperfect because large VMs dominate; and the evidence is trace-driven simulation from one provider, not a live deployment. Within those bounds it is a compelling case that using the measured distribution, tail and all, beats assuming a convenient one.

Background

Why datacenter utilization is a perennial fight

It helps to see the larger stakes. Datacenters are enormously expensive to build and power, yet their servers routinely run far below capacity, because the safest thing an operator can do is give every workload the headroom it might ever need and leave the rest idle. That idle capacity is money and energy spent for nothing, so a long line of systems work tries to reclaim it without breaking the guarantees that made operators cautious in the first place — overcommitting memory, harvesting unused cores, offloading cold data to cheaper tiers, packing jobs more densely. The recurring tension is always the same: push utilization up, but not so far that the workloads that were promised resources get starved when they finally need them. Reclaiming the persistent gap between provisioned and used resources across a fleet, while protecting the tenants whose slack is being borrowed, is the same objective the work on transparent memory offloading in datacenters covered elsewhere on this site pursues, quietly moving what is not being used so more of the machine earns its keep. Burstable VMs are the cloud market’s answer to this tension made explicit in the product itself, and AUDIBLE is the allocator that lets a provider actually cash in the slack the contract exposes.

If you remember only three things

1. Burstable VMs stay below a low baseline almost all the time (the median uses about 7.5 percent of its allocated CPU) and only occasionally burst above it using accumulated credits, so many can be packed onto one server, but the allocator must keep the rate of server capacity violations — where too many burst at once and exceed the server's real capacity, forcing throttling that breaks the service guarantee — under a strict limit while maximizing utilization; a production-trace study shows the standard tools fail, because a fixed oversubscription ratio is too rigid for such variable, skewed workloads and a Central-Limit Gaussian model underestimates the heavy right tail where simultaneous-burst risk actually lives.
2. AUDIBLE is a non-parametric, convolution-based allocator: to judge whether a candidate server can safely host a new burstable VM, it takes the empirical histogram of the server's aggregate CPU usage over the last twenty-four hours (sampled every five minutes) and a conservative empirical histogram of the incoming VM's demand (from the highest-demanding VMs of its configuration, since burstable VMs run hot early in life), combines them by convolution to get the exact distribution of the would-be total demand, reads the capacity-violation probability directly off its true tail, and places the VM only if that probability stays under the operator's threshold — needing no machine-learning training and no tuned parameters because the measured data is the model.
3. In trace-driven simulation on 48-core servers with a 1 percent violation limit, AUDIBLE held every server well under target (worst case 0.45 percent) while matching the utilization of an optimal fixed-ratio oracle and nearly that of the Central-Limit approach — which reached high utilization only by exceeding the limit on 2.5 percent of servers (up to 1.9 percent), whereas the conservative fixed-ratio and provider-baseline methods never violated but left utilization very low; the approach assumes independence (hedged by conservative estimates), needs representative measured history, targets burstable-VM CPU (a regular-VM extension is promising but imperfect because large VMs dominate), and is evaluated in simulation from one provider with a released dataset and simulator.

Check yourself

Check your understanding

1. Why can a provider pack many burstable VMs onto one server, and what limits how many?
2. Why does a Central-Limit-Theorem (Gaussian) model of aggregate demand fail for burstable VMs?
3. What is AUDIBLE's core method for deciding if a server can host a new burstable VM?
4. What did AUDIBLE achieve, and what are its limits?

Sources

The paper is “AUDIBLE: A Convolution-Based Resource Allocator for Oversubscribing Burstable Virtual Machines” by Seyedali Jokar Jandaghi, Kaveh Mahdaviani, Amirhossein Mirhosseini, Sameh Elnikety, Cristiana Amza, and Bianca Schroeder (University of Toronto, University of Michigan, and Microsoft Research), published at ASPLOS 2024 (Volume 3), DOI 10.1145/3620666.3651376.

This explainer is written from the full text of the authors’ version. Everything above comes from the paper’s own sections: the introduction and background on burstable VMs (their baseline, token bucket, peak, and initial tokens, as offered by Microsoft Azure and Amazon), the goal of maximizing utilization while keeping server capacity violations below a specified limit, and the three-level VM scheduling process with its valid-candidate question; the first workload study of burstable VMs from Microsoft Azure production traces spanning more than four million VMs, and its lessons — that burstable VMs are small and greatly underutilize their allocation (a median CPU usage of 7.5 percent of allocation, 38.9 percent even at the 95th percentile), run hotter early in life due to initial tokens, exhibit high skewness, and that Central-Limit-Theorem approximations are inaccurate in the tail; the three adapted baselines (fixed oversubscription ratio with an oracle, a per-configuration oracle-aided method, and the Central-Limit-Theorem method with conservative 95th-percentile mean and variance estimates and a six-hour update); the AUDIBLE design as a non-parametric method that approximates the server’s aggregate demand distribution from the last twenty-four hours of five-minute empirical measurements and the incoming VM’s demand from the 95th-percentile highest-demanding VMs of its configuration, convolves the two to estimate the post-placement demand distribution, and validates a server only if the resulting capacity-violation probability is below the threshold; and the trace-driven simulation evaluation on 48-core servers with a 1 percent violation limit, reporting that AUDIBLE’s worst server had a 0.45 percent violation rate while matching the utilization of the optimal-ratio oracle and nearly that of the Central-Limit method, which exceeded the limit on 2.5 percent of servers (worst case 1.9 percent), along with the discussion of extending the approach to regular VMs and the released dataset and simulator artifact.