Loss rates in the singleserver queue with complet

Authors: Bert Zwart

Publish Date: 2015/03/14

Volume: 81, Issue: 3, Pages: 299-315

PDF Link

Abstract

Consider the singleserver queue in which customers are rejected if their total sojourn time would exceed a certain level K A basic performance measure of this system is the probability P K that a customer gets rejected in steady state This paper presents asymptotic expansions for P K as Krightarrow infty If the service time B is lighttailed and interarrival times are exponential it is shown that the loss probability has an exponential tail The proof of this result heavily relies on results on the twosided exit problem for Lévy processes with no positive jumps For heavytailed subexponential service times and generally distributed interarrival times the loss probability is shown to be asymptotically equivalent to the trivial lower bound PBKUnfortunately such a simple program cannot be carried out for the singleserver queue with complete rejection even when we restrict ourselves to the M/G/1 case The main problem is the intractable distribution of the amount of work in the system when a customer is rejected In the case of partial rejection this amount of work is always K Another problem with this queueing model is that its driving recursion 11 fails to be monotone in its main argument W Kn This rules out the possibility of relating P K to a first passage probability using the framework of Asmussen and Sigman 1996 This approach has been proven quite fruitful when considering queues with partial rejection see eg Bekker and Zwart 2005Not surprisingly the methods we use to prove the asymptotic expansions for P K strongly depend on whether service times are lighttailed or heavytailed In the lighttailed case we heavily rely on results on the twosided exit problem for completely asymmetric Lévy processes ie Lévy processes with no positive or no negative jumps this is also the main reason that we restrict to exponentially distributed interarrival times In present form these results are known since Suprun 1976 who approached the problem using WienerHopf factorization The results of Suprun 1976 came available to a wider audience in Bertoin 1997 The latter paper attacks the twosided exit problem using excursion theory A survey containing martingale proofs is Kyprianou and Palmowski 2004 More recent papers on Lévy processes queues and partial rejection mechanisms are Asmussen and Pihlsgaard 2007 Debicki and Mandjes 2012 Norvang Andersen 2011The results which are of direct use for us are collected in Sect 4 Using these results we are able to obtain an expression for the distribution of the amount of work right before a loss occurs This distribution provides the key to deriving the asymptotics When service times are heavytailed the main point is to show that the system workload is mathrmO1 as the buffer size Krightarrow infty when a customer is rejected This is possible by exploiting some estimates due to Asmussen 1998 and Foss and Zachary 2003 The methods we use here allow for generally distributed interarrival timesThis paper is organized as follows a detailed model description of the singleserver queue with complete rejection as well as some auxiliary results on the singleserver queue with infinite buffer size are given in Sect 2 We present our main results in Sect 3 Section 4 is devoted to the twosided exit problem for Lévy processes with no positive jumps These results are then applied in Sect 5 to obtain a proof of the asymptotics for P K in the lighttailed case A proof of the heavytailed asymptotics can be found in Sect 6 Section 7 puts our results in perspective by comparing them with other rejection disciplinesOur analysis partly relies on several results for the standard single server queue In particular we need the tail behavior of the waitingtime distribution and the tail behavior of the distribution of the maximum workload during a busy cycle these results are gathered in this section

Keywords: