EAMS: An Energy-Aware Market Scheduler for Kubernetes

An improvement to an existing system: a kube-scheduler plugin that places pods by ε-auction, with work-per-joule bids gated by each node’s power headroom, benchmarked against the default scheduler and a MILP planner across load regimes.

1. Problem statement

The lunar-construction paper found that an energy-aware hierarchical market beat both first-come-first-served and a MILP central planner. It did so only in the contended middle: when capacity was neither starved nor over-provisioned. In that regime it raised printed mass by 29% over FCFS and 17% over the central planner. A datacenter cluster is the same allocation problem on Earth:

Lunar market	Cluster
Hauling tasks	Pods
Haulers	Nodes
Mass recovered per joule	Work done per joule
State-of-charge gate	Power-cap headroom gate

The incumbent here is kube-scheduler. It places one pod per scheduling cycle: filter feasible nodes, score them with fixed-weight plugins, bind the winner. That is fast and robust, but it is myopic under contention. Each pod takes the locally best node without regard for the pods behind it, and power or energy is not an input at all.

EAMS asks: in the contended regime, does a batch auction with energy-aware bids reduce energy per unit of work without hurting completion time, and does the gain vanish outside that regime as it did on the Moon?

2. Systems approach

EAMS follows the same V-model as the physical systems. The verification side is a benchmark harness rather than a test bench.

EAMS improves an existing system rather than replacing it. It ships as scheduler-framework plugins in a secondary scheduler profile. Pods opt in by schedulerName, and the default plugins still enforce every feasibility rule.

3. Requirements

ID	Requirement	Verification
AR-1	Drop-in: runs as a secondary profile; no API or workload changes beyond `schedulerName`	Inspection
AR-2	p99 pod scheduling latency ≤ 250 ms at 1,000 nodes and 100 pods/s	Benchmark
AR-3	≥ 10% lower energy per unit work than default at ρ ∈ [0.7, 1.0], with ≤ 5% p95 completion-time regression	Benchmark + metered cluster
AR-4	Never violates a Filter predicate (resources, taints, affinity)	Property test: 0 violations in 10⁶ placements
AR-5	Fail-safe: if EAMS is unhealthy, pods fall back to default placement within 5 s	Fault-injection test
AR-6	Bids degrade gracefully with stale telemetry; readings older than 15 s are discounted	Unit + benchmark
AR-7	Jain's fairness index ≥ 0.9 across tenants	Benchmark
AR-8	Benchmarks replay deterministically from a manifest	Inspection

AR-6 follows directly from the coordination research: a market is a coordination mechanism, and it fails on stale state before it fails on anything else.

4. Architecture

EAMS hooks four framework extension points. The auction runs in a sidecar; the scheduler only reads the clearing table.

Extension point	EAMS's role
QueueSort	Groups pending pods into batches of window W = 200 ms
PreFilter / Filter	Unchanged defaults, which provide AR-4 for free
Score	The node the auction cleared for this pod gets the maximum score
Reserve / Unreserve	Records the clearing price; releases it if binding fails
Permit	Waits for the batch to clear, up to W + 50 ms, then allows or falls back

Waiting at Permit has precedent: the co-scheduling (gang) plugin in the Kubernetes scheduler-plugins project holds pods at Permit until their whole group can be placed. EAMS uses the same hook to hold a batch until its auction clears.

One batch. Steps 3–4 repeat until every pod holds a node or the iteration cap is hit.

5. Mechanism design

5.1 Energy model

Node power uses the standard linear utilization model:

P_n(u) = P^{\text{idle}}_n + \big(P^{\max}_n - P^{\text{idle}}_n\big)\,u_n .

A pod $j$ needing $c_j$ of node $n$ 's $C_n$ cores, with work $w_j$ at node speed $s_n$ , runs for $t_{jn} = w_j / s_n$ . Its marginal energy includes the cost of waking an empty node:

\Delta E_{jn} = \big(P^{\max}_n - P^{\text{idle}}_n\big)\frac{c_j}{C_n}\,t_{jn} \;+\; \mathbb{1}[\,n\ \text{empty}\,]\;P^{\text{idle}}_n\,t_{jn}.

Worked example. Take a 4-core pod with one reference hour of work, and two candidate nodes, each already running other pods:

Node	Cores	$P^{\max} - P^{\text{idle}}$	Speed	Runtime	$\Delta E$
A	32	140 W	1.0	3,600 s	140 × 4/32 × 3,600 ≈ 63 kJ
B	32	220 W	1.5	2,400 s	220 × 4/32 × 2,400 ≈ 66 kJ

Node B finishes 33% sooner for about 5% more energy. A single-pod greedy scorer has to hard-code a preference between those two. A market prices the trade-off against whatever else is waiting in the batch.

5.2 Bids

Pod $j$ values node $n$ by work per joule, weighted by priority $\pi_j$ and gated by power headroom $h_n = 1 - P_n/P^{\text{cap}}_n$ :

v_{jn} = \pi_j \cdot \frac{w_j}{\Delta E_{jn}} \cdot \sigma\!\big(k\,(\hat h_n - h_0)\big), \qquad \hat h_n = h_n - \kappa\, a_n .

The sigmoid gate plays the same role as the state-of-charge gate in the lunar market: a node near its power cap withdraws from the market instead of being pushed over it. The headroom estimate $\hat h_n$ is discounted by telemetry age $a_n$ (AR-6), so stale nodes look fuller than they claim.

Bid gate. With k = 25 the gate is nearly closed below 10% headroom and fully open above 35%.

5.3 The ε-auction

Each node offers capacity slots, and each slot carries a price $p_n$ . An unassigned pod $j$ finds its best and second-best net value:

n^* = \arg\max_n\,(v_{jn} - p_n),\qquad \beta_j = v_{jn^*} - p_{n^*},\qquad \omega_j = \max_{n \ne n^*}(v_{jn} - p_n),

then bids, raising the price by more than its margin:

p_{n^*} \leftarrow p_{n^*} + (\beta_j - \omega_j + \varepsilon).

The pod takes the slot, displacing any previous holder back into the unassigned set. This is Bertsekas's auction algorithm. It terminates with every assignment satisfying ε-complementary slackness, so the total value is within $J\varepsilon$ of optimal for $J$ assigned pods. ε-scaling (starting coarse and refining) keeps the number of bidding rounds small. EAMS also caps iterations per batch and falls back to the greedy assignment if the cap is hit.

Modelling assumption: pods are quantized to slot units, and multi-slot pods bid for a bundle on one node. Multi-resource bundles (CPU, memory, GPU) are deferred to phase 2.

5.4 Regime hypothesis

Offered load is $\rho = \lambda\,\mathbb{E}[c\,t] / \sum_n C_n$ . The lunar result predicts:

Hypothesis: when capacity is plentiful, every scheduler finds a good node; when saturated, there is no choice to make. Only the contended middle rewards a better mechanism.

If EAMS shows a flat gain across all ρ instead of this hump, the lunar result's explanation is wrong for clusters. That would be worth reporting too.

6. Budgets

6.1 Scheduling latency (AR-2)

Stage	Budget
Wait for batch window, worst case	200 ms
Snapshot + Filter for the batch	10 ms
Auction: 500 pods × 1,000 nodes	≤ 30 ms (target; benchmark gate)
Score + Permit release + Bind	10 ms
p99	≤ 250 ms

The window is a deliberate trade: up to 200 ms of added queueing for a better joint decision. For batch, ML and CI workloads measured in minutes, that cost is negligible. For latency-critical services it is not, so those keep using the default scheduler (AR-1).

6.2 Fairness (AR-7)

\mathcal{J}(x_1,\dots,x_m) = \frac{\left(\sum_i x_i\right)^2}{m\sum_i x_i^2}

This is computed over each tenant's share of allocated work, normalized by its quota. Without a guard, a market can starve low-priority tenants, so $\pi_j$ is bounded by Kubernetes PriorityClass and quota rather than being self-declared.

7. Trade studies

Integration point:

Option	Latency (0.30)	Reuses filters (0.25)	Ops simplicity (0.25)	Batch decisions (0.20)	Score
Framework plugins	5	5	4	4	4.55
Scheduler extender (webhook)	2	4	4	3	3.20
Descheduler, post-hoc	3	4	4	1	3.10
Standalone custom scheduler	4	1	2	5	2.95

Allocation mechanism:

Option	Quality (0.30)	Latency (0.30)	Explainability (0.20)	Robustness (0.20)	Score
ε-auction	4	4	5	4	4.20
Greedy scoring (default)	2	5	3	5	3.70
MILP (CP-SAT)	5	2	2	3	3.10
Learned policy (RL)	4	4	1	2	3.00

MILP and greedy are not discarded. They become the baselines, which is what makes the comparison credible.

8. Failure modes and effects

Failure mode	Effect	S	O	D	RPN	Mitigation
Sidecar crash or hang	Pods stuck at Permit	8	3	2	48	Permit timeout falls back to default placement (AR-5); liveness probe
Price war, slow convergence	Batch misses its window	5	4	3	60	ε floor, iteration cap, greedy fallback
Stale power telemetry	Node overloaded past cap	7	5	4	140	Age-discounted headroom; hard cap still enforced by node power capping
Herding onto the cheapest node	Hotspot	5	4	3	60	Per-slot pricing makes congestion expensive
Priority inflation by a tenant	Unfair allocation	6	3	4	72	π bound to PriorityClass; Jain index alarm

9. Verification and validation

Harness. KWOK (Kubernetes WithOut Kubelet) simulates 1,000 nodes against a real control plane, so the real scheduler runs with no real compute. Node power comes from the §5.1 model, calibrated on hardware. A public production trace (Alibaba cluster-trace or Google Borg 2019) is replayed with arrival times scaled to sweep ρ from 0.2 to 1.6.

Ground truth. A 6-node k3s cluster of mini PCs on a metered PDU. stress-ng sweeps calibrate $P^{\text{idle}}$ and $P^{\max}$ per node, and the meter confirms that model-predicted savings appear at the wall.

Test	Verifies	Pass criterion
VT-1 Latency at scale	AR-2	p99 ≤ 250 ms, KWOK, 100 pods/s
VT-2 Placement property test	AR-4	0 predicate violations in 10⁶ placements
VT-3 Kill-the-sidecar	AR-5	All pods placed ≤ 5 s after the kill
VT-4 ρ sweep vs 4 baselines	AR-3, AR-7	Regime curve reported for every scheduler
VT-5 Wall-power check	AR-3	Metered saving within ±3 points of model

Baselines: default scheduler with LeastAllocated scoring; MostAllocated (bin-packing, the strongest energy baseline); FCFS; and CP-SAT MILP with a 1 s budget per batch.

10. Roadmap

Phase	Deliverable	Exit criterion
0	This design study	Requirements baselined
1	Auction engine as a library, reusing Gossamer's ε-auction	Matches CP-SAT within Jε on random instances
2	Framework plugins + KWOK harness	VT-1, VT-2, VT-3 pass
3	ρ sweep on traces	VT-4: regime curve published
4	Metered cluster	VT-5; write-up: the lunar market on Earth