Retrials in Loss Systems: Mean-Field Analysis, Erlang Bounds, and Power-of-$d$ Comparison

Abstract

We consider a system of $N$ parallel, homogeneous servers, each with finite capacity $C$. Jobs requiring one unit of capacity arrive according to a Poisson process with total rate $N\lambda$ and have exponential service times with rate $\mu$. We study a decentralized random--retrial policy with $d$ attempts: upon arrival, a job is assigned to a uniformly chosen server; if the server is full, the job is reassigned to another uniformly chosen server, for at most $d$ attempts; if all $d$ attempts fail, the job is rejected. In the mean-field limit, we prove that the stationary blocking probability is characterized by the unique solution of a fixed-point equation involving the Erlang-B loss function, and we establish global convergence of the fluid model to this equilibrium. We also compare the mean-field stationary blocking probability with the analogous quantity in the power-of-$d$ model under the same parameters $(C,\lambda ,\mu )$. For the same $d$, we show, via coupling techniques, that the blocking probability under power-of-$d$ is always less than or equal to the blocking under retrial-of-$d$; but if we consider $d$ and $\tilde{d}$ with $\tilde{d}>d$, then the retrial-of-$\tilde{d}$ policy achieves a strictly lower blocking than the power-of-$d$ policy when $\rho =\lambda /\mu$ is sufficiently large. Moreover we show that for some specific cases, like $C=2$, $d=2$ and $\tilde{d}=3$, it occurs for all $\rho >0$, not only for $\rho$ sufficiently large. We complement the analysis with simulations that estimate the load level above which retrial-of-$\tilde{d}$ outperforms power-of-$d$ in terms of blocking.