Throughput Optimality

We prove that BPE achieves throughput-optimal payment allocation within the capacity region, following the Lyapunov drift framework of Neely (Neely, 2010).

Capacity Region

The capacity region Λ∗\Lambda^* is the set of arrival rate vectors λ=(λτ)τ∈T\boldsymbol{\lambda} = (\lambda_\tasktype)_{\tasktype \in \mathcal{T}} such that there exists a feasible allocation {F(k,τ)}\{F(k, \tasktype)\} satisfying:

∑k∈KτF(k,τ)=λτ∀τ∈TF(k,τ)≤Cˉ(k,τ)∀k,τF(k,τ)≥0∀k,τ\begin{align} \sum_{k \in K_\tasktype} F(k, \tasktype) &= \lambda_\tasktype &&\forall \tasktype \in \mathcal{T} \\ F(k, \tasktype) &\leq \Csmooth(k, \tasktype) &&\forall k, \tasktype \\ F(k, \tasktype) &\geq 0 &&\forall k, \tasktype \end{align}

Lyapunov Function

Define the Lyapunov function as the sum of squared virtual queue backlogs:

L(t)=∑τ∈T∑k∈KτQ(k,t,τ)2L(t) = \sum_{\tasktype \in \mathcal{T}} \sum_{k \in K_\tasktype} Q(k, t, \tasktype)^2

The one-step conditional Lyapunov drift is:

Δ(t)=E[L(t+1)−L(t)  ∣  Q(t)]\Delta(t) = \E\bigl[L(t+1) - L(t) \;\big|\; \mathbf{Q}(t)\bigr]

Main Result

Theorem (Throughput Optimality)

For any arrival rate vector λ\boldsymbol{\lambda} strictly inside the capacity region Λ∗\Lambda^* (i.e., λ∈(1−ϵ)Λ∗\boldsymbol{\lambda} \in (1-\epsilon)\Lambda^* for some ϵ>0\epsilon > 0), the BPE max-weight payment routing stabilizes all virtual queues. Specifically:

lim sup⁡T→∞1T∑t=0T−1∑k,τE[Q(k,t,τ)]≤Dϵ\limsup_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \sum_{k,\tasktype} \E\bigl[Q(k, t, \tasktype)\bigr] \leq \frac{D}{\epsilon}

where DD is a constant depending on maximum arrival and capacity rates.

Proof sketch.

Following Neely, we bound the Lyapunov drift. From the queue dynamics:

Q(k,t+1,τ)2≤Q(k,t,τ)2+F(k,t,τ)2+Cˉ(k,t,τ)2+2Q(k,t,τ)[F(k,t,τ)−Cˉ(k,t,τ)]\begin{align} Q(k, t+1, \tasktype)^2 &\leq Q(k, t, \tasktype)^2 + F(k, t, \tasktype)^2 + \Csmooth(k, t, \tasktype)^2 \notag \\ &\quad + 2Q(k, t, \tasktype)\bigl[F(k, t, \tasktype) - \Csmooth(k, t, \tasktype)\bigr] \end{align}

Summing over all (k,τ)(k, \tasktype) and taking conditional expectations:

Δ(t)≤D+2∑k,τQ(k,t,τ)⋅E[F(k,t,τ)−Cˉ(k,t,τ)  ∣  Q(t)]\Delta(t) \leq D + 2 \sum_{k, \tasktype} Q(k, t, \tasktype) \cdot \E\bigl[F(k, t, \tasktype) - \Csmooth(k, t, \tasktype) \;\big|\; \mathbf{Q}(t)\bigr]

where D=∑k,τ[Fmax⁡2+Cmax⁡2]D = \sum_{k,\tasktype} \bigl[F_{\max}^2 + C_{\max}^2\bigr].

The max-weight rule minimizes the right-hand side over all feasible allocations. Since λ∈(1−ϵ)Λ∗\boldsymbol{\lambda} \in (1-\epsilon)\Lambda^*, there exists a stationary randomized policy with E[F(k,t,τ)]≤Cˉ(k,τ)−ϵ′\E[F(k,t,\tasktype)] \leq \Csmooth(k,\tasktype) - \epsilon' for some ϵ′>0\epsilon' > 0. The max-weight policy achieves drift at least as negative, yielding:

Δ(t)≤D−ϵ′∑k,τQ(k,t,τ)\Delta(t) \leq D - \epsilon' \sum_{k,\tasktype} Q(k, t, \tasktype)

By the Foster–Lyapunov criterion (Meyn & Tweedie, 2009), the queue process is positive recurrent, and the time-averaged backlog bound follows from telescoping the drift inequality. ◻

Overflow Buffer Bound

Theorem (Overflow Buffer Bound)

Under the same conditions as Theorem (Throughput Optimality), the overflow buffer satisfies:

lim sup⁡T→∞1T∑t=0T−1E[B(τ,t)]≤DBϵ\limsup_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \E\bigl[B(\tasktype, t)\bigr] \leq \frac{D_B}{\epsilon}

for a constant DBD_B depending on the maximum arrival-capacity gap.

Proof sketch.

Augment the Lyapunov function with the buffer: L~(t)=L(t)+∑τB(τ,t)2\tilde{L}(t) = L(t) + \sum_\tasktype B(\tasktype, t)^2. The buffer dynamics mirror a virtual queue with service rate equal to total available capacity. The drift bound carries through identically. ◻

The no-drop constraint distinguishes BPE from standard backpressure. In data networks, excess packets are dropped; here excess payments are buffered. The buffer bound guarantees that this does not cause unbounded accumulation under sufficient aggregate capacity.