Sojourn time asymptotics in processor-sharing queues |
| |
Authors: | Sem Borst Rudesindo Núñez-Queija Bert Zwart |
| |
Institution: | (1) CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands;(2) Department of Mathematics & Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands;(3) Bell Laboratories, Lucent Technologies, P.O. Box 636, Murray Hill, NJ 07974, USA |
| |
Abstract: | Over the past few decades, the Processor-Sharing (PS) discipline has attracted a great deal of attention in the queueing literature.
While the PS paradigm emerged in the sixties as an idealization of round-robin scheduling in time-shared computer systems,
it has recently captured renewed interest as a useful concept for modeling the flow-level performance of bandwidth-sharing
protocols in communication networks. In contrast to the simple geometric queue length distribution, the sojourn time lacks
such a nice closed-form characterization, even for exponential service requirements. In case of heavy-tailed service requirements
however, there exists a simple asymptotic equivalence between the sojourn time and the service requirement distribution, which
is commonly referred to as a reduced service rate approximation. In the present survey paper, we give an overview of several
methods that have been developed to obtain such an asymptotic equivalence under various distributional assumptions. We outline
the differences and similarities between the various approaches, discuss some connections, and present necessary and sufficient
conditions for an asymptotic equivalence to hold. We also consider the generalization of the reduced service rate approximation
to several extensions of the M/G/1 PS queue. In addition, we identify a relationship between the reduced service rate approximation
and a queue length distribution with a geometrically decaying tail, and extend it to so-called bandwidth-sharing networks.
The state-of-the-art with regard to sojourn time asymptotics in PS queues with light-tailed service requirements is also briefly
described. Last, we reflect on some possible avenues for further research.
AMS Subject Classification 60K25 (primary), 60F10, 68M20, 90B18, 90B22 (secondary). |
| |
Keywords: | Processor sharing Bandwidth-sharing networks Large deviations Tail asymptotics Reduced service rate approximation Heavy-tailed distributions Light-tailed distributions |
本文献已被 SpringerLink 等数据库收录! |
|