Interpolation approximations for steady-state performance measures

Resumen

Abstract:The analysis of the steady-state performance in many queuing systems is complexand closed-form results are available only in particular cases. We therefore set out todevelop approximations for important performance measures in steady-state such as thequeue length vector, waiting time and sojourn time. We first analyse the performance in alight-traffic and heavy-traffic regime. We then show how to develop an interpolation-basedapproximation that is valid for any load in the system. An advantage of the approach taken isthat it is not model dependent and hence could potentially be applied to other complexqueuing models. We apply this technique to three widely used models in the performanceevaluation of stochastic networks: The supermarket model, the Discriminatory-Processor-Sharing (DPS) queue and the Relative Priority (RP) queue. The supermarket model is amulti-server queue where upon arrival of a customer two servers are selected at randomfrom the available pool of servers. The Join-the-Shortest-Queue policy is then used inisolation with these two servers. DPS and RP are both single-server multi-class queues thatimplement relative priorities among customers of the various classes. The DPS disciplineserves all customers simultaneously while RP serves one customer at a time in a nonpreemptiveway. We show that in some instances the interpolation approximation is exact.We then use the approximation to draw structural insights onto the performance of thesystem, and we carry out numerical experiments that illustrate that the interpolationapproximation is accurate over a wide range of parameters. // Abstract:The analysis of the steady-state performance in many queuing systems is complexand closed-form results are available only in particular cases. We therefore set out todevelop approximations for important performance measures in steady-state such as thequeue length vector, waiting time and sojourn time. We first analyse the performance in alight-traffic and heavy-traffic regime. We then show how to develop an interpolation-basedapproximation that is valid for any load in the system. An advantage of the approach taken isthat it is not model dependent and hence could potentially be applied to other complexqueuing models. We apply this technique to three widely used models in the performanceevaluation of stochastic networks: The supermarket model, the Discriminatory-Processor-Sharing (DPS) queue and the Relative Priority (RP) queue. The supermarket model is amulti-server queue where upon arrival of a customer two servers are selected at randomfrom the available pool of servers. The Join-the-Shortest-Queue policy is then used inisolation with these two servers. DPS and RP are both single-server multi-class queues thatimplement relative priorities among customers of the various classes. The DPS disciplineserves all customers simultaneously while RP serves one customer at a time in a nonpreemptiveway. We show that in some instances the interpolation approximation is exact.We then use the approximation to draw structural insights onto the performance of thesystem, and we carry out numerical experiments that illustrate that the interpolationapproximation is accurate over a wide range of parameters.