Search

We consider a discrete-time two-dimensional quasi-birth-and-death process (2d-QBD process for short) { (X n , J n) } on Z + 2 × S 0 , where X n = (X 1 , n , X 2 , n) is the level state, J n the phase state (background state) and S 0 a finite set, and study asymptotic properties of the stationary tail distribution. The 2d-QBD process is an extension of usual one-dimensional QBD process. By using the matrix analytic method of the queueing theory and the complex analytic method, we obtain the asymptotic decay rate of the stationary tail distribution in an arbitrary direction. This result is an extension of the corresponding result for a certain two-dimensional reflecting random work without background processes, obtained by using the large deviation techniques and the singularity analysis methods. We also present a condition ensuring the sequence of the stationary probabilities geometrically decays without power terms, asymptotically. Asymptotic properties of the stationary tail distribution in the coordinate directions in a 2d-QBD process have already been studied in the literature. The results of this paper are also important complements to those results. [ABSTRACT FROM AUTHOR]

We consider Palm distributions arising in a Markov process with time homogeneous transitions which is jointly stationary with multiple point processes. Motivated by a BAR approach studied in the recent paper (Braverman et al. in the BAR approach for multi-class queueing networks with SBP service policies, 2023), we are interested in two problems; when this Markov process inherits the same Markov structure under the Palm distributions, and how the state changes at counting instants of the point processes can be handled to derive stationary equations when there are simultaneous counts and each of them influences the state changes. We affirmatively answer the first problem, and propose a framework for resolving the second problem, which is applicable to a general stationary process, which is not needed to be Markov. We also discuss how those results can be applied in deriving BAR’s for the diffusion approximation of queueing models in heavy traffic. In particular, as their new application, the heavy traffic limit of the stationary distribution is derived for a single-server queue with a finite waiting room. [ABSTRACT FROM AUTHOR]

This work deals with the stationary analysis of two-dimensional partially homogeneous nearest-neighbour random walks. Such random walks are characterized by the fact that the one-step transition probabilities are functions of the state-space. We show that stationary behaviour is investigated by solving a finite system of linear equations, two matrix functional equations, and a functional equation with the aid of the theory of Riemann (–Hilbert) boundary value problems. This work is strongly motivated by emerging applications in flow level performance of wireless networks that give rise in queueing models with scalable service capacity, as well as in queue-based random access protocols, where the network's parameters are functions of the queue lengths. A simple numerical illustration, along with some details on the numerical implementation are also presented. [ABSTRACT FROM AUTHOR]

Stochastic networks with complex structures are key modelling tools for many important applications. In this paper, we consider a specific type of network: retrial queueing systems with priority. This type of queueing system is important in various applications, including telecommunication and computer management networks with big data. The system considered here receives two types of customers, of which Type-1 customers (in a queue) have non-pre-emptive priority to receive service over Type-2 customers (in an orbit). For this type of system, we propose an exhaustive version of the stochastic decomposition approach, which is one of the main contributions made in this paper, for the purpose of studying asymptotic behaviour of the tail probability of the number of customers in the steady state for this retrial queue with two types of customers. Under the assumption that the service times of Type-1 customers have a regularly varying tail and the service times of Type-2 customers have a tail lighter than Type-1 customers, we obtain tail asymptotic properties for the numbers of customers in the queue and in the orbit, respectively, conditioning on the server's status, in terms of the exhaustive stochastic decomposition results. These tail asymptotic results are new, which is another main contribution made in this paper. Tail asymptotic properties are very important, not only on their own merits but also often as key tools for approximating performance metrics and constructing numerical algorithms. [ABSTRACT FROM AUTHOR]

A Markovian single-server queue is studied in an interactive random environment. The arrival and service rates of the queue depend on the environment, while the transition dynamics of the random environment depend on the queue length. We consider in detail two types of Markov random environments: a pure jump process and a reflected jump diffusion. In both cases, the joint dynamics are constructed so that the stationary distribution can be explicitly found in a simple form (weighted geometric). We also derive an explicit estimate for the exponential rate of convergence to the stationary distribution via coupling. [ABSTRACT FROM AUTHOR]

We suggest a method for constructing a positive harmonic function for a wide class of transition kernels on Z + . We also find natural conditions under which this harmonic function has a positive finite limit at infinity. Further, we apply our results on harmonic functions to asymptotically homogeneous Markov chains on Z + with asymptotically negative drift which arise in various queueing models. More precisely, assuming that the Markov chain satisfies Cramér's condition, we study the tail asymptotics of its stationary distribution. In particular, we clarify the impact of the rate of convergence of chain jumps towards the limiting distribution. [ABSTRACT FROM AUTHOR]

In this paper, we investigate exact tail asymptotics for the stationary distribution of a fluid model driven by the M / M / c queue, which is a two-dimensional queueing system with a discrete phase and a continuous level. We extend the kernel method to study tail asymptotics of its stationary distribution, and a total of three types of exact tail asymptotics are identified from our study and reported in the paper. [ABSTRACT FROM AUTHOR]

We consider a discrete-time two-dimensional process {(X1,n,X2,n)} on Z+2 with a supplemental process {Jn} on a finite set, where the individual processes {X1,n} and {X2,n} are both skip-free. We assume that the joint process {Yn}={(X1,n,X2,n,Jn)} is Markovian and that the transition probabilities of the two-dimensional process {(X1,n,X2,n)} are modulated depending on the state of the supplemental process {Jn}. This modulation is space homogeneous except for the boundaries of Z+2. We call this process a discrete-time two-dimensional quasi-birth-and-death process. Under several conditions, we obtain the exact asymptotic formulae of the stationary distribution in the coordinate directions. [ABSTRACT FROM AUTHOR]

This paper considers a special class of continuous-time Markov chains of level-dependent M/G/1-type, where block matrices representing downward jumps in the infinitesimal generator are nonsingular. This special class naturally arises in the analysis of BMAP/M/ $$\infty $$ queues and BMAP/M/c queues with exponential impatience times (BMAP/M/c+M). We first formulate the boundary probability vector in terms of a solution of a system of infinitely many linear inequalities. We then reveal that in the above special class, this infinite system is regarded as a nested sequence of simplices, and we identify their vertices. Based on these results, we develop a simple yet efficient computational algorithm for the stationary distribution conditioned that the level is not greater than a predefined N. Note that for a large N, the conditional distribution will provide a good approximation to the stationary distribution. Some numerical examples for BMAP/M/ $$\infty $$ and BMAP/M/c+M queues are shown. [ABSTRACT FROM AUTHOR]

Markov modulation is versatile in generalization for making a simple stochastic model, which is often analytically tractable, more flexible in application. In this spirit, we modulate a two-dimensional reflecting skip-free random walk in such a way that its state transitions in the boundary faces and interior of a nonnegative integer quadrant are controlled by Markov chains. This Markov-modulated model is referred to as a 2d-QBD process according to Ozawa (Queueing Syst 74:109-149, ). We are interested in the tail asymptotics of its stationary distribution, which have been well studied when there is no Markov modulation. Ozawa studied this tail asymptotics problem, but his answer is not analytically tractable. We think this is because Markov modulation is so free to change a model even if the state space for Markov modulation is finite. Thus, some structure, say, extra conditions, would be needed to make the Markov modulation analytically tractable while minimizing its limitation in application. The aim of this paper is to investigate such structure for the tail asymptotic problem. For this, we study the existence of a right-subinvariant positive vector, called a superharmonic vector, of a nonnegative matrix with QBD block structure, where each block matrix is finite dimensional. We characterize this existence under a certain extra assumption. We apply this characterization to the 2d-QBD process and derive the tail decay rates of its marginal stationary distribution in an arbitrary direction. This solves the tail decay rate problem for a two-node generalized Jackson network, which has been open for many years. [ABSTRACT FROM AUTHOR]

The model is motivated by the problem of load distribution in large-scale cloud-based data processing systems. We consider a heterogeneous service system, consisting of multiple large server pools. The pools are different in that their servers may have different processing speeds and/or different buffer sizes (which may be finite or infinite). We study an asymptotic regime in which the customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to some scaling parameter n. Arriving customers are assigned to the servers by a 'router,' according to a pull-based algorithm, called PULL. Under the algorithm, each server sends a 'pull-message' to the router, when it becomes idle; the router assigns an arriving customer to a server according to a randomly chosen available pull-message, if there are any, or to a random server, otherwise. Assuming subcritical system load, we prove asymptotic optimality of PULL. Namely, as system scale $$n\rightarrow \infty $$ , the steady-state probability of an arriving customer experiencing blocking or waiting, vanishes. We also describe some generalizations of the model and PULL algorithm, for which the asymptotic optimality still holds. [ABSTRACT FROM AUTHOR]

We extend to Markov-modulated Brownian motion (MMBM) the renewal approach which has been successfully applied to the analysis of Markov-modulated fluid models. It has been shown recently that MMBM may be expressed as the limit of a parameterized family of Markov-modulated fluid models. We prove that the weak convergence also holds for systems with two reflecting boundaries, one at zero and one at $$b >0$$ , and that the stationary distributions of the approximating fluid models converge to the stationary distribution of the two-sided reflected MMBM. In so doing, we obtain a new representation for the stationary distribution. It is factorised into a vector determined by the phase behaviour when the fluid is either at the level 0 or the level $$b$$ , and a matrix expression characteristic of the process when the fluid is in the open interval $$(0,b)$$ . [ABSTRACT FROM AUTHOR]

We consider $$GI/Ph/n+M$$ parallel-server systems with a renewal arrival process, a phase-type service time distribution, $$n$$ homogenous servers, and an exponential patience time distribution with positive rate. We show that in the Halfin-Whitt regime, the sequence of stationary distributions corresponding to the normalized state processes is tight. As a consequence, we establish an interchange of heavy-traffic and steady-state limits for $$GI/Ph/n+M$$ queues. [ABSTRACT FROM AUTHOR]

We consider a two-dimensional skip-free reflecting random walk on the non-negative integers, which is referred to as a 2-d reflecting random walk. We give necessary and sufficient conditions for the stationary distribution to have a product-form. We also derive simpler sufficient conditions for the product-form for a restricted class of 2-d reflecting random walks. We apply these results and obtain a product-form approximation of the stationary distribution through a suitable modification of the parameters of the random walk. [ABSTRACT FROM AUTHOR]

We consider an M/M/1 queueing system with inventory under the $$(r,Q)$$ policy and with lost sales, in which demands occur according to a Poisson process and service times are exponentially distributed. All arriving customers during stockout are lost. We derive the stationary distributions of the joint queue length (number of customers in the system) and on-hand inventory when lead times are random variables and can take various distributions. The derived stationary distributions are used to formulate long-run average performance measures and cost functions in some numerical examples. [ABSTRACT FROM AUTHOR]

We are concerned with an $$M/M$$-type join the shortest queue ( $$M/M$$-JSQ for short) with $$k$$ parallel queues for an arbitrary positive integer $$k$$, where the servers may be heterogeneous. We are interested in the tail asymptotic of the stationary distribution of this queueing model, provided the system is stable. We prove that this asymptotic for the minimum queue length is exactly geometric, and its decay rate is the $$k$$th power of the traffic intensity of the corresponding $$k$$ server queues with a single waiting line. For this, we use two formulations, a quasi-birth-and-death (QBD for short) process and a reflecting random walk on the boundary of the $$k+1$$-dimensional orthant. The QBD process is typically used in the literature for studying the JSQ with two parallel queues, but the random walk also plays a key roll in our arguments, which enables us to use the existing results on tail asymptotics for the QBD process. [ABSTRACT FROM AUTHOR]

We present three sets of results for the stationary distribution of a two-dimensional semimartingale-reflecting Brownian motion (SRBM) that lives in the non-negative quadrant. The SRBM data can equivalently be specified by three geometric objects, an ellipse and two lines, in the two-dimensional Euclidean space. First, we revisit the variational problem (VP) associated with the SRBM. Building on Avram et al. (Queueing Syst. 37: 259-289, ), we show that the value of the VP at a point in the quadrant is equal to the optimal value of a linear function over a convex domain. Depending on the location of the point, the convex domain is either $$\mathcal{D}^{(1)}$$ or $$\mathcal{D}^{(2)}$$ or $$\mathcal{D}^{(1)}\cap \mathcal{D}^{(2)},$$ where each $$\mathcal{D}^{(i)},$$ $$i=1, 2,$$ can easily be described by the three geometric objects. Our results provide a geometric interpretation for the value function of the VP and allow one to see geometrically when one edge of the quadrant has influence on the optimal path traveling from the origin to a destination point. Second, we provide a geometric condition that characterizes the existence of a product form stationary distribution. Third, we establish exact tail asymptotics of two boundary measures that are associated with the stationary distribution; a key step in our proof is to sharpen two asymptotic inversion lemmas in Dai and Miyazawa (Stoch. Syst. 1:146-208, ) which allow one to infer the exact tail asymptotic of a boundary measure from the singularity of its moment-generating function. [ABSTRACT FROM AUTHOR]

We consider a discrete-time two-dimensional process $\{(L_{n}^{(1)},L_{n}^{(2)})\}$ on $\mathbb{Z}_{+}^{2}$ with a background process { J} on a finite set, where individual processes $\{L_{n}^{(1)}\}$ and $\{L_{n}^{(2)}\}$ are both skip free. We assume that the joint process $\{Y_{n}\}=\{(L_{n}^{(1)},L_{n}^{(2)},J_{n})\}$ is Markovian and that the transition probabilities of the two-dimensional process $\{(L_{n}^{(1)},L_{n}^{(2)})\}$ are modulated depending on the state of the background process { J}. This modulation is space homogeneous, but the transition probabilities in the inside of $\mathbb{Z}_{+}^{2}$ and those around the boundary faces may be different. We call this process a discrete-time two-dimensional quasi-birth-and-death (2D-QBD) process, and obtain the decay rates of the stationary distribution in the coordinate directions. We also distinguish the case where the stationary distribution asymptotically decays in the exact geometric form, in the coordinate directions. [ABSTRACT FROM AUTHOR]

Motivated by applications in biological systems, we show for certain multiclass queueing networks that time-dependent distributions for the multiclass queue-lengths can have a factorized form which reduces the problem of computing such distributions to a similar problem for related single-class queueing networks. We give an example of the application of this result to an enzymatic processing network. [ABSTRACT FROM AUTHOR]

A Markovian model for intermittent connections of various classes in a communication network is established and investigated. Any connection alternates between being OFF (idle) or ON (active, with data to transmit), and evolves in a way depending only on its class and the state of the network, in particular for the routes it uses among the network nodes to transmit data. The congestion of a given node is a functional of the throughputs of all ON connections going through it, and causes losses to these connections. Any ON connection reacts to its losses by self-adapting its throughput in TCP-like fashion so as to control network congestion. The connections interact through this feedback loop. The system constituted of their states (either OFF, or ON with some throughput) evolves in Markovian fashion, and since the number of connections in each class is potentially huge, a mean-field limit result with an adequate scaling is proved so as to reduce dimensionality. The limit is a nonlinear Markov process given by a McKean-Vlasov equation, of dimension the number of classes. It is then proved that the stationary distributions of the limit can be expressed in terms of the solutions of a finite-dimensional fixed-point equation. [ABSTRACT FROM AUTHOR]

We are concerned with the stationary distribution of a d-dimensional semimartingale reflecting Brownian motion on a nonnegative orthant, provided it is stable, and conjecture about the tail decay rate of its marginal distribution in an arbitrary direction. Due to recent studies, the conjecture is true for d=2. We show its validity for the skew symmetric case for a general d. [ABSTRACT FROM AUTHOR]

In this paper we present a detailed analysis of a single server Markovian queue with impatient customers. Instead of the standard assumption that customers perform independent abandonments, we consider situations where customers abandon the system simultaneously. Moreover, we distinguish two abandonment scenarios; in the first one all present customers become impatient and perform synchronized abandonments, while in the second scenario we exclude the customer in service from the abandonment procedure. Furthermore, we extend our analysis to the M/ M/ c queue under the second abandonment scenario. For these models we carry out an extensive analysis including the stationary, the busy period and the conditional sojourn time distributions deriving exact formulas and iterative algorithmic schemes. We also obtain explicit results under various limiting regimes that demonstrate the effect of the level of synchronization on the performance of the systems. [ABSTRACT FROM AUTHOR]

Recently Gamarnik and Zeevi (Ann. Appl. Probab. 16:56–90, ) and Budhiraja and Lee (Math. Oper. Res. 34:45–56, ) established that, under suitable conditions, a sequence of the stationary scaled queue lengths in a generalized Jackson queueing network converges to the stationary distribution of multidimensional reflected Brownian motion in the heavy-traffic regime. In this work we study the corresponding problem in multiclass queueing networks (MQNs). In the first part of this work we consider the MQNs for which the fluid stability is valid, state-space collapse is exhibited under suitable initial conditions and a heavy traffic limit theorem holds. For such MQNs we establish that, under the assumption of the tightness of a sequence of stationary scaled workloads, the sequence converges to the stationary distribution of semimartingale reflecting Brownian motion in the heavy-traffic regime. The key to the proof is to show that state-space collapse occurs in the heavy-traffic regime in stationarity under the assumption of tightness. In the second part, using the result obtained, it is shown that such a convergence of stationary workload holds for a multiclass single-server queue with feedback routing, where the tightness is proved by the Lyapunov function method developed in (Gamarnik and Zeevi in Ann. Appl. Probab. 16:56–90, ). [ABSTRACT FROM AUTHOR]

In this paper we investigate the monotonicity properties of an unreliable M/G/1 retrial queue using the general theory of stochastic ordering. We show the monotonicity of the transition operator of the embedded Markov chain relative to the strong stochastic ordering and increasing convex ordering. We obtain conditions of comparability of two transition operators and we obtain comparability conditions of the number of customers in the system. Inequalities are derived for the mean characteristics of the busy period, number of customers served during a busy period, number of orbit busy periods and waiting times. Inequalities are also obtained for some probabilities of the steady-state distribution of the server state. An illustrative numerical example is presented. [ABSTRACT FROM AUTHOR]

In this paper we analyze the M/ M/ c retrial queue using the censoring technique. This technique allows us to carry out an asymptotic analysis, which leads to interesting and useful asymptotic results. Based on the asymptotic analysis, we develop two methods for obtaining approximations to the stationary probabilities, from which other performance metrics can be obtained. We demonstrate that the two proposed approximations are good alternatives to existing approximation methods. We expect that the technique used here can be applied to other retrial queueing models. [ABSTRACT FROM AUTHOR]

We consider piecewise-deterministic Markov processes that occur as scaling limits of discrete-time Markov chains that describe the Transmission Control Protocol (TCP). The class of processes allows for general increase and decrease profiles. Our key observation is that stationary results for the general class follow directly from the stationary results for the idealized TCP process. The latter is a Markov process that increases linearly and experiences downward jumps at times governed by a Poisson process. To establish this connection, we apply space–time transformations that preserve the properties of the class of Markov processes. [ABSTRACT FROM AUTHOR]

In this paper we present a detailed analysis of queueing models with vacations and impatient customers, where the source of impatience is the absence of the server. Instead of the standard assumption that customers perform independent abandonments, we consider situations where customers abandon the system simultaneously. This is, for example, the case in remote systems where customers may decide to abandon the system, when a transport facility becomes available. [ABSTRACT FROM AUTHOR]

We consider the M/ G/1 queueing system in which customers whose admission to the system would increase the workload beyond a prespecified finite capacity limit are not accepted. Various results on the distribution of the workload are derived; in particular, we give explicit formulas for its stationary distribution for M/ M/1 and in the general case, under the preemptive LIFO discipline, for the joint stationary distribution of the number of customers in the system and their residual service times. Furthermore, the Laplace transform of the length of a busy period is determined. Finally, for M/ D/1 the busy period distribution is derived in closed form. [ABSTRACT FROM AUTHOR]

This paper focuses on product form and related tractable stationary distributions in a general class of stochastic networks with finite numbers of nodes such that their network states are changed through signal transfers as well as internal transitions. Signals may be customers in traditional queueing applications, but we do not make any restriction on their effects at departing as well as arriving nodes. They may also instantaneously move around among different nodes. Furthermore, signal routing may depend on the whole network state. For analytical simplicity, we assume that the state space is countable. For such a network, we propose an abstract model, called a stochastic transfer network, and consider the stationary distribution of the network state. We introduce conditional traffic rates for arrivals and departures. Using them, we consider when the network has product form or some other tractable stationary distributions. [ABSTRACT FROM AUTHOR]

Motivated by recent traffic control models in ATM systems, we analyse three closely related systems of fluid queues, each consisting of two consecutive reservoirs, in which the first reservoir is fed by a two-state (on and off) Markov source. The first system is an ordinary two-node fluid tandem queue. Hence the output of the first reservoir forms the input to the second one. The second system is dual to the first one, in the sense that the second reservoir accumulates fluid when the first reservoir is empty, and releases fluid otherwise. In these models both reservoirs have infinite capacities. The third model is similar to the second one, however the second reservoir is now finite. Furthermore, a feedback mechanism is active, such that the rates at which the first reservoir fills or depletes depend on the state (empty or nonempty) of the second reservoir. The models are analysed by means of Markov processes and regenerative processes in combination with truncation, level crossing and other techniques. The extensive calculations were facilitated by the use of computer algebra. This approach leads to closed-form solutions to the steady-state joint distribution of the content of the two reservoirs in each of the models. [ABSTRACT FROM AUTHOR]

We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i 0 ∈ {1,..., K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i 0 asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i 0. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered. [ABSTRACT FROM AUTHOR]

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability pi, it serves the next customer; with probability 1-pi, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. [ABSTRACT FROM AUTHOR]

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. [ABSTRACT FROM AUTHOR]