The BMAP/G/1 Queue with Level-Dependent Arrivals – An Overview

The BMAP/G/1 queue is a field of intensive research since several years. We generalize the BMAP/G/1 queue by allowing the arrival process to depend on the state (level) of the queue, i.e., on the number of customers in the system. This will be called a BMAP/G/1 queueing system with level-dependent arrivals. A suitable arrival process is defined by nesting a countable number of BMAPs.We give conditions for the level-dependent BMAP/G/1 queue to be stable, i.e., in equilibrium. By analysing the fundamental periods, which now depend on their starting level, we determine the stationary queue length at service completion times and at an arbitrary time.     

Stationary characteristics of MX/M/1 systems with two-speed service

An M^X/M/1 queueing system with threshold switching of service regimes at the instant of a change in the number of customers and the same system with threshold blocking of the flow of customers are considered. For these systems, an algorithm is proposed for determination of the stationary distribution of the number of customers and stationary characteristics (the mean queue length, the mean time of waiting in a queue, the variance of the queue length, the probability of the customer service for a system with blocking). For the case when the minimal number of incoming customers in a group is comparable with threshold value h, the stationary characteristics are found in an explicit form. For the system with threshold switching of service regimes (without blocking), two problems of optimal synthesis are solved. In these problems, the optimal values of threshold h and of the service intensity in the post-threshold regime are determined. The obtained results are verified with the help of simulation models developed with the help of the GPSS World software.     

带优先权与不耐烦顾客排队模型的模拟仿真

考虑一个有两类顾客到达的单服务台的排队系统。两类顾客的到达过程均为泊松过程,第一类顾客较第二类顾客具有强占优先权,且第二类顾客由于第一类顾客的到达而变得不耐烦,其＂耐性时间＂服从负指数分布。两类顾客的服务时间服从相同参数的负指数分布,服务规则是强占优先服务,在高负荷条件下用Matlab编程对此排队系统进行模拟仿真,为处理此类排队问题提供了一个新方法。     

On the M/G/1 queueing system with multiclass customers and fixed feedback

The M/G/1 queueing system with multiclass customer arrivals, fixed feedback, and first come first served policy is considered, where different classes of customers have different arrival rates, service-time distributions, and feedback numbers. The joint probabifity generation function of queue size of each class and the Laplace-Stieltjes transform of the total sojourn time of a customer in each class are presented, which extended the results obtained by Choi B D. The mean queue size of each class and mean total sojourn time of a customer in each class are obtained with this result. The results can be used in computer and communication networks for their performance analysis.     

Stationary characteristics of MX/M/1 systems with hysteretic switching of the service intensity

An M^X/M/1 queueing system with two-threshold hysteretic switching of the service intensity at the instants when the number of customers exceeds h ₂ and, then, decreases to the value h ₁ < h ₂ and the same system with the threshold locking of a flow of customers are considered. An algorithm is proposed for determination of the stationary distribution of the number of customers and stationary characteristics (the mean queue length, the mean time of waiting in a queue, the variance of the queue length, and the probability of the service of a customer for the system with blocking). Restrictions are imposed on the distribution of the number of incoming customers in a group to facilitate the determination of the stationary characteristics in an explicit form. The results are verified with the help of simulation models developed with the use of the GPSS World tools.     

Stationary characteristics of an M 2 X /M/n queue with hysteretic control of the input flow intensity

A multichannel queueing system with an unlimited queue length is considered. In the system, the service time and time intervals between arrivals of customer batches are characterized by exponential distributions and a hysteretic mechanism is applied to control the input flow intensity. The system receives two independent types of flows of customers one of which is blocked in the overload mode. An algorithm for determination of the stationary distribution of the number of customers and the stationary characteristics (the mean queue length, the mean time of waiting in the queue, the probability of a loss of customers) is proposed. The obtained results are verified with the help of a simulation model developed with the help of the GPSS World tools.     

Jitter analysis of an IPP tagged traffic stream in an {IPP,M}/M/1 queue

We study a single server queue with two different arriving streams, a tagged arrival process and a background arrival process. The tagged traffic is assumed to be an interrupted Poisson process (IPP) and the background traffic is Poisson. The service time is exponentially distributed, and customers are served in a FIFO manner. We obtain numerically the probability density function of the inter-departure time of the IPP tagged arrival process, from which we calculate its jitter, defined as a percentile of the inter-departure time. Numerical results of the 95th percentile and the squared coefficient of variation of the tagged inter-departure time are given as a function of the arrival rate of the background traffic.     

The M/G/1 queue with permanent customers

The authors examine an M/G/1 FCFS (first come, first served) queue with two types of customers: ordinary customers, who arrive according to a Poisson process, and permanent customers, who immediately return to the end of the queue after having received a service. The influence of the permanent customers on queue length and sojourn times of the Poisson customers is studied using results from queuing theory and from the theory of branching processes. In particular, it is shown that, when the service time distributions of the Poisson customers and all K permanent customers are negative exponential with identical means, the queue length and sojourn time distributions of the Poisson customers are the (K+1)-fold convolution of those for the case without permanent customers     

Optimal synthesis problems for Markovian queueing systems with several given characteristics

For an M/M/1/r queueing system and an M/M/1 system with threshold switching of service modes at the instant of the change in the number of customers as well as for the same system with threshold blocking of the flow of customers, the monotonic dependence of stationary characteristics (the mean number of serviced customers per unit time, the mean service cost per unit time, the probability of system downtime, and the mean waiting time of a customer in the queue) on the system parameters (the buffer size, the system usage, and the threshold of switching between the service modes) is used to solve the optimal synthesis problems for systems with several given stationary characteristics. The solution of a particular optimal synthesis problem is the optimum value of one of the above parameters.     

Stochastic model of k-parallel service channels

With the enhanced rate of inflow of units, especially in randomly distributed batch sizes, service through parallel channels appears to be the optimal course for relieving congestion and reducing the waiting time of customers. Keeping this fact in view, this paper involves k-parallel service channels which operate together for dealing with the situation of bulk arrivals. The time-dependent and steady state behaviour of the queueing system is dealt with at length. Laplace transforms of the probability generating functions for queue length distributions are obtained and the steady state results are derived therefrom. Finally, some particular cases which can be derived from the main theorem are also discussed.     

Mθ/G/1/m and Mθ/G/1 queues with operating parameters depending on the queue length

M^θ/G/1/m and M^θ/G/1 queues are considered in the case when the service time and input flow parameters depend on the queue length and are determined at the instants of completion of the service of customers. With the help of an approach based on the idea of Korolyuk’s potential method, the Laplace transforms are found for the distribution of the number of customers in a system within the busy period and for the distribution function of the busy period. The mean duration of the busy period and the stationary distribution of the number of customers in a system are determined. An M^θ/G/1 system with one threshold of functioning mode switching is considered as a particular case. The obtained results are verified with the help of simulation models developed with the use of the GPSS World tools.     

Traffic management in a multicode CDMA system supporting softhandoffs

A traffic management scheme is proposed in a multicode code-division multiple-access system supporting soft handoff that uses guard channels and a queue for real-time traffic. Preemptive queue control gives priority to queued handoff calls. Handoff traffic is derived as a function of the new call arrival rate, the size of the soft handoff region, mobile speed, the new call blocking probability, and the handoff failure probability. System performance with K types of calls is analyzed by introducing a concept of effective channel. The effects of the number of guard channels, the number of effective channels, system capacity, and other factors are numerically investigated. The effectiveness of the proposed queue control scheme is also observed in terms of handoff processing delay     

OFDMA系统随机服务模型及呼叫接纳控制策略的研究

该文在分析OFDMA系统容量的基础上,提出了适用于自适应OFDMA系统的随机服务模型,即M| M| m| n马尔可夫排队模型,根据这个模型,我们提出了基于系统吞吐量和用户QoS要求的呼叫接纳控制策略。理论分析和仿真结果表明,当系统中只有FTP业务时,M| M| m| n模型与自适应OFDMA系统的随机服务特征非常相似,应用这个模型对系统的阻塞概率和文件的服务时间进行定量分析,其结果与实际系统的性能基本吻合。     

Optimizing the Number of Robots for Web Search Engines

Robots are deployed by a Web search engine for collecting information from different Web servers in order to maintain the currency of its data base of Web pages. In this paper, we investigate the number of robots to be used by a search engine so as to maximize the currency of the data base without putting an unnecessary load on the network. We use a queueing model to represent the system. The arrivals to the queueing system are Web pages brought by the robots; service corresponds to the indexing of these pages. The objective is to find the number of robots, and thus the arrival rate of the queueing system, such that the indexing queue is neither starved nor saturated. For this, we consider a finite-buffer queueing system and define the cost function to be minimized as a weighted sum of the loss probability and the starvation probability. Under the assumption that arrivals form a Poisson process, and that service times are independent and identically distributed random variables with an exponential distribution, or with a more general service function, we obtain explicit/numerical solutions for the optimal number of robots to deploy.     

M θ/G/1/m and M θ/G/1 systems with the service time dependent on the queue length

The M ^θ/G/1/m and M ^θ/G/1 queueing systems, in which the service time depends on the queue length and is determined at the beginning of service of a customer, are investigated. The average busy period and the stationary distribution of the number of customers in the system have been found via the approach based on the idea of V.S. Korolyuk’s potential method. As a special case, the M ^θ/G/1 queue with a single threshold of switching of service modes is examined. The results are checked using the simulation model constructed with the use of GPSS World software tools.     

Stationary characteristics of M 2|G|1|r system with hysteretic policy for arrival rate control

A finite queuing system with one server, Poisson input flow, arbitrary service time distribution, and hysteretic policy for arrival rate control is considered. An analytical method is proposed for determination of the stationary distribution of the number of customers in the system. Several numerical examples are given.     

The Effect of Idle Server First Random Routing on the Behavior of a Finite Queue

This paper studies the effect of routing on the behavior of a finite queue which accepts batch Poisson inputs and receives service from multiple synchronous servers. Upon the arrival of a group of customers idle or pseudoidle servers will be considered first in routing decisions. Otherwise routing will be determined randomly in accordance with a preset probability distribution. Results obtained include state probability, blocking probability, delay, and throughput. Validity of analysis has been verified by computer simulations. These results can he used in evaluating the performance of a computer communication network.     

Optimal control of a removable server in an M/Ek/1 queueing system with finite capacity

This paper deals with the economic behavior of a removable server in the N policy M/E_k/1 queueing system with finite capacity. Expressions for the probability mass functions of the number of customers in the system are derived and taken in closed-form. As special cases, the probability mass functions of the number of customers for the N policy M/M/1 queueing system, the ordinary M/K_k/1 queueing system, and the ordinary M/M/1 queueing system are obtained. The cost structure includes a holding cost per unit time spent in the system for each customer, costs per unit time for keeping the server on or off, a server start-up cost, a server shut-down cost, and fixed cost for every lost customer. Following the construction of the total expected cost per unit time, we determine the optimal operating policy at minimum cost.     

Exact analysis of a class of GI/G/1-type performability models

We present an exact decomposition algorithm for the analysis of Markov chains with a GI/G/1-type repetitive structure. Such processes exhibit both M/G/1-type & GI/M/1-type patterns, and cannot be solved using existing techniques. Markov chains with a GI/G/1 pattern result when modeling open systems which accept jobs from multiple exogenous sources, and are subject to failures & repairs; a single failure can empty the system of jobs, while a single batch arrival can add many jobs to the system. Our method provides exact computation of the stationary probabilities, which can then be used to obtain performance measures such as the average queue length or any of its higher moments, as well as the probability of the system being in various failure states, thus performability measures. We formulate the conditions under which our approach is applicable, and illustrate it via the performability analysis of a parallel computer system.     

The convexity of loss rate in an Erland loss system and sojourn inan Erlang delay system with respect to arrival and service rates

The Erlang loss system is a system in which customers arriving in a Poisson stream of arrival rate λ are served by a group of n servers, with a mean service time of 1/μ. Arrivals that find all servers busy are blocked and cleared from the system. The Erlang delay system is a system in which customers who find all servers busy wait in a queue until served by the first available server. Proofs of joint-convexity results in the Erlang delay system and Erlang loss system are presented, using induction on the number of servers and making use of the relation between the Erlang B and the Erlang C functions. The approach leads to a straightforward algebraic analysis of the properties of the performance measures of interest and avoids cumbersome manipulations