M/G/1 queue with event-dependent arrival rates

Motivated by experiments on customers’ behavior in service systems, we consider a queueing model with event-dependent arrival rates. Customers’ arrival rates depend on the last event, which may either be a service departure or an arrival. We derive explicitly the performance measures and analyze the impact of the event-dependency. In particular, we show that this queueing model, in which a service completion generates a higher arrival rate than an arrival, performs better than a system in which customers are insensitive to the last event. Moreover, contrary to the M/G/1 queue, we show that the coefficient of variation of the service does not necessarily deteriorate the system performance. Next, we show that this queueing model may be the result of customers’ strategic behavior when only the last event is known. Finally, we investigate the historical admission control problem. We show that, under certain conditions, a deterministic policy with two thresholds may be optimal. This new policy is easy to implement and provides an improvement compared to the classical one-threshold policy.     

成批到达排队系统的随机比较

本文研究成批到达排队系统中队长过程的随机比较问题．利用随机比较方法我们对成批到达指数服务的多服务台排队系统进行分析,得到了该排队系统中队长过程的随机比较以及队长函数关于时间的凹性和凸性．同时我们也给出了成批到达一般服务的单服务台排队系统队长过程、稳态队长的随机比较以及队长函数关于时间的凹性和凸性．     

Tandem behavior of a telecommunication system with finite buffers and repeated calls

The tandem behavior of a telecommunication system with finite buffers and repeated calls is modeled by the performance of a finite capacityG/M/1 queueing system with general interarrival time distribution, exponentially distributed service time, the first-come-first-served queueing discipline and retrials. In this system a fraction of the units which on arrival at a node of the system find it busy, may retry to be processed, by merging with the incoming arrival units in that node, after a fixed delay time. The performance of this system in steady state is modeled by a queueing network and is approximated by a recursive algorithm based on the isolation method. The approximation outcomes are compared against those from a simulation study. Our numerical results indicate that in steady state the non-renewal superposition arrival process, the non-renewal overflow process, and the non-renewal departure process of the above system can be approximated with compatible renewal processes.     

Analysis of the BMAP/PH/N queueing system with backup servers

We consider a novel multi-server queueing system that is potentially useful for optimizing real-world systems, in which the objectives of high performance and low power consumption are conflicting. The queueing model is formulated and investigated under the assumption that an arrival flow is defined by a batch Markovian arrival process and random values characterizing customer processing have the phase-type distribution. If the service time of some customer by a server exceeds a certain random bound, this server receives help from a so-called backup server from a finite pool of backup servers. The behavior of the system is described by a quite complicated multi-dimensional continuous-time Markov chain that is successfully analyzed in this paper. Examples of the potential use of the obtained results in managerial decisions are presented.     

Analysis of G/D/1 Queueing Systems with Inputs Satisfying Large Deviation Principle under Weak* Topology

The large deviation principle (LDP) which has been effectively used in queueing analysis is the sample path LDP, the LDP in a function space endowed with the uniform topology. Chang [5] has shown that in the discrete-time G/D/1 queueing system under the FIFO discipline, the departure process satisfies the sample path LDP if so does the arrival process. In this paper, we consider arrival processes satisfying the LDP in a space of measures endowed with the weak^* topology (Lynch and Sethuraman [12]) which holds under a weaker condition. It is shown that in the queueing system mentioned above, the departure processes still satisfies the sample path LDP. Our result thus covers arrival processes which can be ruled out in the work of Chang [5]. The result is then applied to obtain the exponential decay rate of the queue length probability in an intree network as was obtained by Chang [5], who considered the arrival process satisfying the sample path LDP.     

A multi-class discrete-time queueing system under the FCFS service discipline

The problem with the FCFS server discipline in discrete-time queueing systems is that it doesn’t actually determine what happens if multiple customers enter the system at the same time, which in the discrete-time paradigm translates into ‘during the same time-slot’. In other words, it doesn’t specify in which order such customers are served. When we consider multiple types of customers, each requiring different service time distributions, the precise order of service even starts to affect quantities such as queue content and delays of arbitrary customers, so specifying this order will be prime. In this paper we study a multi-class discrete-time queueing system with a general independent arrival process and generally distributed service times. The service discipline is FCFS and customers entering during the same time-slot are served in random order. It will be our goal to search for the steady-state distribution of queue content and delays of certain types of customers. If one thinks of the time-slot as a continuous but bounded time period, the random order of service is equivalent to FCFS if different customers have different arrival epochs within this time-slot and if the arrival epochs are independent of customer class. For this reason we propose two distinct ways of analysing; one utilizing permutations, the other considering a slot as a bounded continuous time frame.     

An EM algorithm for platoon arrival processes in discrete time

The platoon arrival process (PAP), a special case of Markovian arrival process (MAP), occurs in several practical queueing systems. Developing procedures for estimating its parameters is essential in order to successfully use it for representing arrival processes in real systems. We present an EM-based procedure for estimating the parameters of a PAP.     

Naor’s model with heterogeneous customers and arrival rate uncertainty

This paper examines an extension of Naor’s observable queueing model in which the arrival rate is not known with certainty by either customers or the system manager. Further, customers are heterogeneous in terms of their service valuation and waiting time cost. We analyze the stability of the system and properties of the revenue maximizing fee and socially optimal fee.     

Perturbation Analysis of the GI/M/s Queue

This paper investigates the M/M/s queueing model to predict an estimate for the proximity of the performance measures of queues with arrival processes that are slightly different from the Poisson process. Specifically, we use the strong stability method to obtain perturbation bounds on the effect of perturbing the arrival process in the M/M/s queue. Therefore, we build some algorithms based on strong stability method to predict stationary performance measures of the GI/M/s queue. Some numerical examples are sketched out to illustrate the accuracy of the proposed method.     

On the distributions of infinite server queues with batch arrivals

Queues that feature multiple entities arriving simultaneously are among the oldest models in queueing theory, and are often referred to as “batch” (or, in some cases, “bulk”) arrival queueing systems. In this work, we study the effect of batch arrivals on infinite server queues. We assume that the arrival epochs occur according to a Poisson process, with treatment of both stationary and non-stationary arrival rates. We consider both exponentially and generally distributed service durations, and we analyze both fixed and random arrival batch sizes. In addition to deriving the transient mean, variance, and moment-generating function for time-varying arrival rates, we also find that the steady-state distribution of the queue is equivalent to the sum of scaled Poisson random variables with rates proportional to the order statistics of its service distribution. We do so through viewing the batch arrival system as a collection of correlated sub-queues. Furthermore, we investigate the limiting behavior of the process through a batch scaling of the queue and through fluid and diffusion limits of the arrival rate. In the course of our analysis, we make important connections between our model and the harmonic numbers, generalized Hermite distributions, and truncated polylogarithms.

     

A note on the distributional Little’s law for discrete-time queues with D-MAP arrivals and its application

For a class of discrete-time FIFO queueing systems with D-MAP (discrete-time Markovian arrival process), we present a distributional Little’s law that relates the distribution of the stationary number of customers in system (queue) with that of the stationary number of slots a customer spends in system (queue). Taking the multi-server D-MAP/D/c queue as an example, we demonstrate how this relation can be utilized to get the desired distribution of the number of customers. Sample numerical results are presented at the end.     

Many-Sources Delay Asymptotics with Applications to Priority Queues

In this paper, we study discrete-time priority queueing systems fed by a large number of arrival streams. We first provide bounds on the actual delay asymptote in terms of the virtual delay asymptote. Then, under suitable assumptions on the arrival process to the queue, we show that these asymptotes are the same. As an application of this result, we then consider a priority queueing system with two queues. Using the earlier result, we derive an upper bound on the tail probability of the delay. Under certain assumptions on the rate function of the arrival process, we show that the upper bound is tight. We then consider a system with Markovian arrivals and numerically evaluate the delay tail probability and validate these results with simulations.     

Some notes on the reduction of network dimensionality in nested open queueing networks

In this paper, we study an open and nested tandem queueing network, where the population constraint within each subnetwork is controlled by a semaphore queue. The total number of customers that may be present in the subnetwork can not exceed a given value. Each node has a constant service time and the arrival process to the queueing network follows an arbitrary distribution.A major characteristic of this queueing network is that the low layer flow is halted by the state of the high layer. We develop a simple and equivalent queueing network that has the same performance characteristics as the original queueing network. Using this model, the waiting time on the queueing network can be easily derived. It is interesting to see how the simplification process can be applied to multi-layered queueing network.     

On effects of arrival rate and burstiness in the queueing system: Analysis ofLb/D/1

This paper studies a single-server queueing system with deterministic service time in which arrivals are regulated by the leaky-bucket mechanism. This paper intends to improve quantitative understanding of the effects of arrival rate and burstiness on the average delay of queueing systems. The study is directed toward identifying the worst traffic of arrivals allowed by the leaky-bucket regulation and clarifying the effects of the leaky bucket parameters (which represent the arrival rate and burstiness) on the average queueing delay. The arrival traffic that maximizes the average queueing delay is characterized as the repetition of the following three phases: bulky arrival, greedy arrival for a specified length of interval, and then no arrival till the token bucket is full. The average queueing delay for the worst traffic is expressed as a function the leaky bucket parameters.Research was partially supported by the NSF under grant ECS-8552419. Research was conducted at the Laboratory for Information and Decision Systems of the Massachusetts Institute of Technology and the U.S. Naval Research Laboratory.     

Analysis of finite capacity discrete-time <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">Geo</Emphasis>/1 queueing system with multiple vacations

This paper investigates a discrete-time single-server finite-buffer queueing system with multiple vacations in which arrivals occur according to a discrete-time renewal process. Service and vacation times are mutually independent and geometrically distributed. We obtain steady-state system length distributions at prearrival, arbitrary and outside observer's observation epochs under the late arrival system with delayed access and early arrival system. The analysis of actual waiting-time for both the systems has also been carried out. The model has potential application in high-speed computer network, digital communication systems and other related areas.     

The two-moment three-parameter decomposition approximation of queueing networks with exponential residual renewal processes

We propose a two-moment three-parameter decomposition approximation of general open queueing networks by which both autocorrelation and cross correlation are accounted for. Each arrival process is approximated as an exponential residual (ER) renewal process that is characterized by three parameters: intensity, residue, and decrement. While the ER renewal process is adopted for modeling autocorrelated processes, the innovations method is used for modeling the cross correlation between randomly split streams. As the interarrival times of an ER renewal process follow a two-stage mixed generalized Erlang distribution, viz., MGE(2), each station is analyzed as an MGE(2)/G/1 system for the approximate mean waiting time. Variability functions are also used in network equations for a more accurate modeling of the propagation of cross correlations in queueing networks. Since an ER renewal process is a special case of a Markovian arrival process (MAP), the value of the variability function is determined by a MAP/MAP/1 approximation of the departure process. Numerical results show that our proposed approach greatly improves the performance of the parametric decomposition approximation of open queueing networks.     

Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

Data and queueing analysis of a Japanese air-traffic flow

Congestion is a major cause of inefficiency in air transportation. A question is whether delays during the arrival phase of a flight can be absorbed more fuel-efficiently in the future. In this context, we analyze Japan’s flow strategy empirically and use queueing techniques in order to gain insight into the generation of the observed delays. Based on this, we derive a rule to balance congestion delays more efficiently between ground and en-route. Whether fuel efficiency can be further improved or not will depend on the willingness to review the concept of runway pressure.     

System delay versus system content for discrete-time queueing systems subject to server interruptions

This paper concerns discrete-time queueing systems operating under a first-come-first-served queueing discipline, with deterministic service times of one slot and subject to independent server interruptions. For such systems, we derive a relationship between the probability generating functions of the system content during an arbitrary slot and of the system delay of an arbitrary customer. This relationship is valid regardless of the nature of the arrival process. From this relationship we derive a relationship between the first- and second-order moments of the distributions involved. It is shown that the relationship also applies to subsystems of the queueing system being discussed, and to the waiting time and queue content of a multi-server queueing system with geometric service times and uninterrupted servers.