Bufferless queue

A queue which retains no unfinished work between slots. Given nonnegative input $A$ and capacity $c$, its bufferless queue output is $\min (A,c)$ and its lost work is $(A-c{)}^{+}$.

For fixed Poisson mean $\lambda >0$ and capacity $c\to \infty$, set $m=\lfloor c\rfloor +1$. The optimized Chernoff bound gives $\log \mathbb{P}(X\ge m)\le -I_P(m)$. The lower bound by $\mathbb{P}(X=m)$ and Stirling's formula differs by only $O(\log m)$. Rounding $m$ to $c$ changes the cost by $O(\log c)$, proving the displayed formula and the leading scale $-c\log c$.

The work served in one slot is capped at the service rate of a queue. The remainder is lost, so output is input minus its positive part above capacity. Every downstream threshold below the cap has exactly the same overflow event for input and output; thresholds at or above the cap cannot be exceeded by the output.

For $\lambda ,C>0$ and $0<\beta <1$, clip Poisson input of mean $L\lambda$ at $L\lambda +C{L}^{(1+\beta )/2}$. The Poisson moderate deviation principle and contraction principle for large deviations give the displayed output rate at the clipping scale. At smaller exponents the output retains the original rate by moderate deviations below a bufferless queue cap. At larger positive-deviation scales every overflow event is eventually impossible because the requested threshold exceeds the cap.

Let $S_L$ have a Poisson distribution with mean $L\lambda$, where $\lambda >0$, and put $u_L=L\lambda +C{L}^{(1+\beta )/2}$ with $C>0$. Assume $0<\alpha <\beta <1$. The upper restriction is essential: this is a moderate deviation, with a threshold shift larger than $\sqrt{L}$ but smaller than $L$.

For an input rate $\lambda +\delta$, the Poisson rate function isTaking $\delta =C{L}^{(\beta -1)/2}$ givesThe expansion follows directly from the Poisson weights and Stirling's formula. Because $\beta >\alpha$, clipping has superexponentially small probability at speed $L^{\alpha }$. In particular, for every $\epsilon >0$,This is the relevant exponential equivalence. More directly, every threshold $r_L<u_L$ gives identical events $\{\min (S_L,u_L)>r_L\}=\{S_L>r_L\}$. At $\beta =1$, the full Poisson rate function replaces its quadratic approximation.