Queueing Systems
Journal Prestige (SJR): 0.809 Citation Impact (citeScore): 1 Number of Followers: 7 Hybrid journal (It can contain Open Access articles) ISSN (Print) 15729443  ISSN (Online) 02570130 Published by SpringerVerlag [2468 journals] 
 Data flow dissemination in a network

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider the following network model motivated, in particular, by blockchains and peertopeer live streaming. Data packet flows arrive at the network nodes and need to be disseminated to all other nodes. Packets are relayed through the network via links of finite capacity. A packet leaves the network when it is disseminated to all nodes. Our focus is on two communication disciplines, which determine the order in which packets are transmitted over each link, namely RandomUseful (RU) and OldestUseful (OU). We show that RU has the maximum stability region in a general network. For the OU we demonstrate that, somewhat surprisingly, it does not in general have the maximum stability region. We prove that OU does achieve maximum stability in the important special case of a symmetric network, given by the full graph with equal capacities on all links and equal arrival rates at all nodes. We also give other stability results, and compare different disciplines’ performances in a symmetric system via simulation. Finally, we study the cumulative delays experienced by a packet as it propagates through the symmetric system, specifically the delay asymptotic behavior as \(N \rightarrow \infty \) . We put forward some conjectures about this behavior, supported by heuristic arguments and simulation experiments.
PubDate: 20231121

 JoinUpTo(m): improved hyperscalable load balancing

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Various load balancing policies are known to achieve vanishing waiting times in the largescale limit, that is, when the number of servers tends to infinity. These policies either require a communication overhead of one message per job or require job size information. Load balancing policies with an overhead below one message per job are called hyperscalable policies. While these policies often have bounded queue length in the largescale limit and work well when the overhead is somewhat below one, they show poor performance when the communication overhead becomes small, that is, the mean response time tends to infinity when the overhead tends to zero even at low loads. In this paper, we introduce a hyperscalable load balancing policy, called JoinUpTo(m), that remains effective even when the communication overhead tends to zero. To study its performance under general job size distributions, we make use of the “queue at the cavity" approach. We provide explicit results for the first two moments of the response time, the generating function of the queue length distribution and the Laplace transform of the response time. These results show that the mean response time only depends on the first two moments of the job size distribution.
PubDate: 20231115

 Reflected Brownian motion with drift in a wedge

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study reflecting Brownian motion with drift constrained to a wedge in the plane. Our first set of results provides necessary and sufficient conditions for existence and uniqueness of a solution to the corresponding submartingale problem with drift, and show that its solution possesses the Markov and Feller properties. Next, we study a version of the problem with absorption at the vertex of the wedge. In this case, we provide a condition for existence and uniqueness of a solution to the problem and some results on the probability of the vertex being reached.
PubDate: 20231024

 Asymptotic behavior of a system of two coupled queues when the content of
one queue is very high
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider a system of two parallel discretetime singleserver queues, queue 1 and queue 2. The service time of any customer in either queue is equal to 1 time slot. Arrivals during consecutive slots occur independently from slot to slot. However, the arrival streams into both queues are possibly mutually interdependent, i.e., during any slot, the numbers of arrivals in queue 1 and queue 2 need not be statistically independent. Their joint probability generating function (pgf) A(x, y) fully characterizes the queueing model. As a consequence of the possible intraslot correlation in the arrival process, the numbers of customers present (“system contents”) in queues 1 and 2, at any given slot boundary, are not necessarily independent either. In a previous paper, we have already discussed the mathematical difficulty of computing their steadystate joint pgf \(U(z_1,z_2)\) ; explicit closedform results can only be obtained for specific choices of A(x, y). In this paper, we therefore look at the problem from an other angle. Specifically, we study the (asymptotic) conditional steadystate behavior of the system under the condition that the content of queue 1 is (temporarily) very high (goes to infinity). For ease of terminology, we refer to the system as the “asymptotic system” in these circumstances. We prove that the asymptotic system is nearly identical to the original (unconditional) system, but with a modified joint arrival pgf \(A^*(x,y)\) that can be computed explicitly from A(x, y). This fundamental result allows us to determine the stability condition of queue 2 in the asymptotic system, and explicitly compute the classical queueing performance metrics of queue 2, such as the pgf, the moments and the approximate tail distribution of its system content, when this condition is fulfilled. It also leads to accurate approximative closedform expressions for the joint tail distribution of the system contents in both queues, in the original (unconditional) system. We extensively illustrate our methodology by means of various specific (popular) choices of A(x, y). In some examples, where an explicit solution for \(U(z_1,z_2)\) or for the (approximative) joint tail distribution is known, we retrieve the known results easily. In other cases, new results are found for arrival pgfs A(x, y) for which no explicit results were known until now.
PubDate: 20231017

 Editorial introduction: special issue on Gaussian queues

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
PubDate: 20231013

 Open networks of infinite server queues with nonhomogeneous multivariate
batch Poisson arrivals
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we consider the occupancy distribution for an open network of infinite server queues with multivariate batch arrivals following a nonhomogeneous Poisson process, and general service time distributions. We derive a probability generating function for the transient occupancy distribution of the network and prove that it is necessary and sufficient for ergodicity that the expected occupancy time for each batch be finite. Further, we recover recurrence relations for the transient probability mass function formulated in terms of a distribution obtained by compounding the batch size with a multinomial distribution.
PubDate: 20231007

 A fluid approximation for a matching model with general reneging
distributions
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Motivated by a service platform, we study a twosided network where heterogeneous demand (customers) and heterogeneous supply (workers) arrive randomly over time to get matched. Customers and workers arrive with a randomly sampled patience time (also known as reneging time in the literature) and are lost if forced to wait longer than that time to be matched. The system dynamics depend on the matching policy, which determines when to match a particular customer class with a particular worker class. Matches between classes use the headofline customer and worker from each class. Since customer and worker arrival processes can be very general counting processes, and the reneging times can be sampled from any finite mean distribution that is absolutely continuous, the state descriptor must track the ageinsystem for every customer and worker waiting in order to be Markovian, as well as the time elapsed since the last arrival for every class. We develop a measurevalued fluid model that approximates the evolution of the discreteevent stochastic matching model and prove its solution is unique under a fixed matching policy. For a sequence of matching models, we establish a tightness result for the associated sequence of fluidscaled state descriptors and show that any distributional limit point is a fluid model solution almost surely. When arrival rates are constant, we characterize the invariant states of the fluid model solution and show convergence to these invariant states as time becomes large. Finally, again when arrival rates are constant, we establish another tightness result for the sequence of fluidscaled state descriptors distributed according to a stationary distribution and show that any subsequence converges to an invariant state. As a consequence, the fluid and time limits can be interchanged, which justifies regarding invariant states as first order approximations to stationary distributions.
PubDate: 20230926

 Large deviations and longtime behavior of stochastic fluid queues with
generalized fractional Brownian motion input
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study the large deviation behaviors of a stochastic fluid queue with an input being a generalized Riemann–Liouville (R–L) fractional Brownian motion (FBM), referred to as GFBM. The GFBM is a continuous meanzero Gaussian process with nonstationary increments, extending the standard FBM with stationary increments. We first derive the large deviation principle for the GFBM by using the weak convergence approach. We then obtain the large deviation principle for the stochastic fluid queue with the GFBM as the input process as well as for an associated running maximum process. Finally, we study the longtime behavior of these two processes; in particular, we show that a steadystate distribution exists and derives the exact tail asymptotics using the aforementioned large deviation principle together with some maximal inequality and modulus of continuity estimates for the GFBM.
PubDate: 20230913

 Sojourns of fractional Brownian motion queues: transient asymptotics

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We study the asymptotics of sojourn time of the stationary queueing process \(Q(t),t\ge 0\) fed by a fractional Brownian motion with Hurst parameter \(H\in (0,1)\) above a high threshold u. For the Brownian motion case \(H=1/2\) , we derive the exact asymptotics of $$\begin{aligned} {\mathbb {P}} \left\{ \int _{T_1}^{T_2}{\mathbb {I}}(Q(t)>u+h(u))d t>x \Big Q(0) >u \right\} \end{aligned}$$ as \(u\rightarrow \infty \) , where \(T_1,T_2, x\ge 0\) and \(T_2T_1>x\) , whereas for all \(H\in (0,1)\) , we obtain sharp asymptotic approximations of $$\begin{aligned}{} & {} {\mathbb {P}} \left\{ \frac{1}{v(u)} \int _{[T_2(u),T_3(u)]}{\mathbb {I}}(Q(t)\!>\!u\!+\!h(u))dt\!>\!y \Bigl \frac{1}{v(u)} \int _{[0,T_1(u)]}{\mathbb {I}}(Q(t)\!>\!u)dt\!>\!x \right\} ,\\{} & {} \quad x,y >0 \end{aligned}$$ as \(u\rightarrow \infty \) , for appropriately chosen \(T_i\) ’s and v. Two regimes of the ratio between u and h(u), that lead to qualitatively different approximations, are considered.
PubDate: 20230910

 Minimizing the mean slowdown in the M/G/1 queue

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider the optimal scheduling problem in the M/G/1 queue. While this is a thoroughly studied problem when the target is to minimize the mean delay, there are still open questions related to some other objective functions. In this paper, we focus on minimizing mean slowdown among nonanticipating polices, which may utilize the attained service of the jobs but not their remaining service time when making scheduling decisions. By applying the Gittins index approach, we give necessary and sufficient conditions for the jobs’ service time distribution under which the wellknown scheduling policies first come first served and foreground background are optimal with respect to the mean slowdown. Furthermore, we characterize the optimal nonanticipating policy in the multiclass case for certain types of service time distributions. In fact, our results cover a more general objective function than just the mean slowdown, since we allow the holding costs for a job to depend on its own service time S via a generic function c(S). When minimizing the mean slowdown, this function reads as \(c(x) = 1/x\) .
PubDate: 20230904
DOI: 10.1007/s11134023098886

 Proofs of conjectures on the competition between observable and
unobservable servers
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract The impact of information about the quality of service on marketing can be demonstrated by a competition between an observable queue and an unobservable queue. An illustration was given by an earlier paper of Hassin (Manag Sci 42:618–623, 1996), which considers two gas stations located one after the other on a main road. A driver who needs to fill the gas can see the queue length upon arriving at the first station, but not the second one. The driver decides which station to enter based only on this partial information for minimizing the expected waiting time. Via extensive numerical experiments, Hassin showed that the first server enjoys a larger market share, which led him to making a number of challenging conjectures. In this paper, we prove that all the numerical observations and conjectures are true so that the advantage of being the first server is assured.
PubDate: 20230901
DOI: 10.1007/s11134023098877

 On a modified version of the Lindley recursion

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper concerns a modified version of the Lindley recursion, where the recursion equation is given by \(W_{i+1} = [V_{i} W_{i} + Y_{i}]^{+}\) , with \(\{V_i\}_{i=0}^{\infty }\) and \(\{Y_i\}_{i=0}^{\infty }\) being two independent sequences of i.i.d. random variables. Additionally, we assume that the \(V_i\) take values in \((\infty , 1]\) and the \(Y_i\) have a rational Laplace–Stieltjes transform. Under these assumptions, we investigate the transient and steadystate behaviors of the process \(\{W_i\}_{i=0}^{\infty }\) by deriving an expression for the generating function of the Laplace–Stieltjes transform of the \(W_i\) .
PubDate: 20230817
DOI: 10.1007/s11134023098868

 Gaussian limits for scheduled traffic with superheavy tailed
perturbations
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract A scheduled arrival model is one in which the jth customer is scheduled to arrive at time jh but the customer actually arrives at time \(jh + \xi _j\) , where the \(\xi _j\) ’s are independent and identically distributed. It has previously been shown that the arrival counting process for scheduled traffic obeys a functional central limit theorem (FCLT) with fractional Brownian motion (fBM) with Hurst parameter \(H \in (0,1/2)\) when the \(\xi _j\) ’s have a Paretolike tail with tail exponent lying in (0, 1). Such limit processes exhibit less variability than Brownian motion, because the scheduling feature induces negative correlations in the arrival process. In this paper, we show that when the tail of the \(\xi _j\) ’s has a superheavy tail, the FCLT limit process is Brownian motion (i.e., \(H=1/2\) ), so that the heaviness of the tails eliminates any remaining negative correlations and generates a limit process with independent increments. We further study the case when the \(\xi _j\) ’s have a Cauchylike tail, and show that the limit process in this setting is a fBM with \(H=0\) . So, this paper shows that the entire range of fBMs with \(H \in [0,1/2]\) are possible as limits of scheduled traffic.
PubDate: 20230816
DOI: 10.1007/s1113402309884w

 Queueing networks with pathdependent arrival processes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This paper develops a Gaussian model for an open network of queues having a pathdependent netinput process, whose evolution depends on its early history, and satisfies a nonergodic law of large numbers. We show that the Gaussian model arises as the heavytraffic limit for a sequence of open queueing networks, each with a multivariate generalization of a Polya arrival process. We show that the netinput and queuelength processes for the Gaussian model satisfy nonergodic laws of large numbers with tractable distributions.
PubDate: 20230802
DOI: 10.1007/s11134023098859

 Stability of a cascade system with two stations and its extension for
multiple stations
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract We consider a twostation cascade system in which waiting or externally arriving customers at station 1 move to the station 2 if the queue size of station 1 including an arriving customer itself and a customer being served is greater than a given threshold level \(c_{1} \ge 1\) and if station 2 is empty. Assuming that external arrivals are subject to independent renewal processes satisfying certain regularity conditions and service times are i.i.d. at each station, we derive necessary and sufficient conditions for a Markov process describing this system to be positive recurrent in the sense of Harris. This result is extended to the cascade system with a general number k of stations in series. This extension requires certain traffic intensities of stations \(2,3,\ldots , k1\) for \(k \ge 3\) to be defined. We finally note that the modeling assumptions on the renewal arrivals and i.i.d. service times are not essential if the notion of the stability is replaced by a certain sample path condition. This stability notion is identical with the standard stability if the whole system is described by the Markov process which is a Harris irreducible Tprocess.
PubDate: 20230726
DOI: 10.1007/s1113402309883x

 On the speed of convergence of Piterbarg constants

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we derive an upper bound for the difference between the continuous and discrete Piterbarg constants. Our result allows us to approximate the classical Piterbarg constants by their discrete counterparts using Monte Carlo simulations with an explicit error rate.
PubDate: 20230704
DOI: 10.1007/s1113402309882y

 Proof of the conjecture on the stability of a multiclass retrial queue
with constant retrial rates
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract This study considers a multiclass singleserver retrial queue with constant retrial rates in which service times are generally distributed with different service rates for each class. Avrachenkov (Queueing Systems 100:177–179, 2022) formulated the conjecture on the stability of this queueing system. We completely resolve the conjecture by using the fluid limit approach.
PubDate: 20230622
DOI: 10.1007/s1113402309881z

 On the maxima of suprema of dependent Gaussian models

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract In this paper, we study the asymptotic distribution of the maxima of suprema of dependent Gaussian processes with trend. For different scales of the time horizon we obtain different normalizing functions for the convergence of the maxima. The obtained results not only have potential applications in estimating the delay of certain Gaussian forkjoin queueing systems but also provide interesting insights to the extreme value theory for triangular arrays of random variables with rowwise dependence.
PubDate: 20230619
DOI: 10.1007/s11134023098800

 Obituary Narahari Umanath (‘Uma’) Prabhu (April 25th,
1924–October 14th, 2022)
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
PubDate: 20230613
DOI: 10.1007/s11134023098797

 Externalities in the M/G/1 queue: LCFSPR versus FCFS

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Abstract: Abstract Consider a stable M/G/1 system in which, at time \(t=0\) , there are exactly n customers with residual service times equal to \(v_1,v_2,\ldots ,v_n\) . In addition, assume that there is an extra customer c who arrives at time \(t=0\) and has a service requirement of x. The externalities which are created by c are equal to the total waiting time that others will save if her service requirement is reduced to zero. In this work, we study the joint distribution (parameterized by \(n,v_1,v_2,\ldots ,v_n,x\) ) of the externalities created by c when the underlying service distribution is either lastcome, firstserved with preemption or firstcome, firstserved. We start by proving a decomposition of the externalities under the abovementioned service disciplines. Then, this decomposition is used to derive several other results regarding the externalities: moments, asymptotic approximations as \(x\rightarrow \infty \) , asymptotics of the tail distribution, and a functional central limit theorem.
PubDate: 20230608
DOI: 10.1007/s11134023098788
