Biased Diffusion and Universality in Model Queues

Abstract

We study the structure and robustness of universality classes for queueing, deriving analytic results for priority-based models with continuous-valued priorities. By mapping one model onto the problem of biased diffusion, we show that its distribution of waiting times, $P(\ensuremath{\tau})$, decreases for large times $\ensuremath{\tau}$ as $P(\ensuremath{\tau})\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}3/2}$ or as $P(\ensuremath{\tau})\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}5/2}\mathrm{exp}(\ensuremath{-}\ensuremath{\tau}/{\ensuremath{\tau}}_{0})$ in different parameter regimes. In a second model, introducing a cost for switching between different classes of tasks substantially changes the asymptotic behavior of $P(\ensuremath{\tau})$.