Retrial queues with balanced call blending: analysis of single-server and multiserver model

In call centers, call blending consists in the mixing of incoming and outgoing call activity, according to some call blending balance. Recently, Artalejo and Phung-Duc have developed an apt model for such a setting, with a two way communication retrial queue. However, by assuming a classical (proportional) retrial rate for the incoming calls, the short-term blending balance is heavily impacted by the number of incoming calls, which may be undesired, especially when the balance between incoming and outgoing calls is vital to the service offered. In this contribution, we consider an alternative to classical call blending, through a retrial queue with constant retrial rate for incoming calls. For the single-server case (one operator), a generating functions approach enables to derive explicit formulas for the joint stationary distribution of the number of incoming calls and the system state, and also for the factorial moments. This is complemented with a stability analysis, expressions for performance measures, and also recursive formulas, allowing reliable numerical calculation. A correlation study enables to study the system’s short-term blending balance, allowing to compare it to that of the system with classical retrial rate. For the multiserver case (multiple operators), we provide a quasi-birth-and-death process formulation, enabling to derive a sufficient and necessary condition for stability in this case (in a simple form), a numerical recipe to obtain the stationary distribution, and a cost model.     

Compound Transient Phenomena in Multiphase Queuing Systems. III

The author continues the work on functional limit theorems in multiphase queuing systems (QS) under heavy traffic. In this paper there are proved theorems for the waiting time of a job when at phases of a system various conditions of heavy traffic are satisfied (compound transient phenomena).     

About the Sojourn Time Process in Multiphase Queueing Systems

Multiphase queueing systems (MQS) (tandem queues, queues in series) are of special interest both in theory and in practical applications (packet switch structures, cellular mobile networks, message switching systems, retransmission of video images, asembly lines, etc.). In this paper, we deal with approximations of MQS and present a heavy traffic limit theorems for the sojourn time of a customer in MQS. Functional limit theorems are proved for the customer sojourn time – an important probability characteristic of the queueing system under conditions of heavy traffic.      

A generalization of the Erlang formula of traffic engineering

Calls arrive at a switch, where they are assigned to any one of the available idle outgoing links. A call is blocked if all the links are busy. A call assigned to an idle link may be immediately lost with a probability which depends on the link. For exponential holding times and an arbitrary arrival process we show that the conditional distribution of the time to reach the blocked state from any state, given the sequence of arrivals, is independent of the policy used to route the calls. Thus the law of overflow traffic is independent of the assignment policy. An explicit formula for the stationary probability that an arriving call sees the node blocked is given for Poisson arrivals. We also give a simple asymptotic formula in this case.Work on this paper was done while the author was at Bellcore and at Berkeley.     

The persistence of ideal shock waves

Local-in-time piecewise smooth solutions to hyperbolic systems of conservation laws are constructed by means of Li-Yu theory. The novelty consists in the application of this approach to shock waves for which the number of outgoing modes is at least as big as the number of incoming modes (undercompressive shocks), the motivation in a possible interpretation from the zero dissipation limit point of view.     

A network of priority queues in heavy traffic: One bottleneck station

In this paper we consider an open queueing network having multiple classes, priorities, and general service time distributions. In the case where there is a single bottleneck station we conjecture that normalized queue length and sojourn time processes converge, in the heavy traffic limit, to one-dimensional reflected Brownian motion, and present expressions for its drift and variance. The conjecture is motivated by known heavy traffic limit theorems for some special cases of the general model, and some conjectured “Heavy Traffic Principles” derived from them. Using the known stationary distribution of one-dimensional reflected Brownian motion, we present expressions for the heavy traffic limit of stationary queue length and sojourn time distributions and moments. For systems with Markov routing we are able to explicitly calculate the limits.     

The FCFS service discipline: Stable network topologies, bounds on traffic burstiness and delay, and control by regulators

We consider the well-known First Come First Serve (FCFS) scheduling policy under bursty arrivals. This policy is commonly used in scheduling communication networks and manufacturing systems. Recently it has been shown that the FCFS policy can be unstable for some nonacyclic network topologies.We identify some network topologies under which FCFS is stable for all arrival and service rate vectors within the system's capacity. This is done by determining a sharp bound on the burstiness of traffic exiting from a tandem section of the system, in terms of the burstiness of the incoming traffic. This burstiness bound further allows us to provide a bound on the maximum number of parts in the system, and the maximum delay. It also enables us to analyze the performance of some systems controlled by the use of traffic smoothing regulators. The maximum delay can remain bounded even in the heavy traffic limit, when all stations are 100% utilized.     

Diffusion approximation of systems with repeated calls and an unreliable server

We consider single-server queueing systems with repeated calls and an unreliable server, which may fail both when free and when busy. A central limit theorem and a diffusion approximation theorem are obtained for the queue as a time-dependent process in the case of a low rate of repeated calls.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 74, pp. 78–80, 1992;     

Phase-type models for cellular networks supporting voice, video and data traffic

This paper presents an analytical model for cellular networks supporting voice, video and data traffic. Self-similar and bursty nature of the incoming traffic causes correlation in inter-arrival times of the incoming traffic. Therefore, arrival of calls is modeled with Markovian arrival process as it allows for the correlation. Call holding times, cell residence times and retrial times are modeled as phase-type distributions. We consider that the cells in a cellular network are statistically homogeneous, so it is enough to investigate a single cell for the performance analysis of the entire networks. With appropriate assumptions, the stochastic process that describes the state of a cell is a Quasi-birth–death (QBD) process. We derive explicit expressions for the infinitesimal generator matrix of this QBD process. Also, expressions for performance measures are obtained. Further, complexity involved in computing the steady-state probabilities is discussed. Finally, queueing examples are provided that can be obtained as particular cases of the proposed analytical model.     

多类顾客多服务台队列网络的高负荷极限定理

多类顾客多服务台队列网络广泛地应用到计算机网络、通讯网络和交通网络 .由于系统的复杂性 ,其数量指标的精确解很难求出 .为了寻求逼近解 ,本文用概率测度弱收敛理论对进行了研究 ,在高负荷的条件下 ,我们获得了网输入过程、闲时过程和负荷过程的极限定理 .     

The uniqueness of limit cycles for Liénard system

In monographs [Theory of Limit Cycles, 1984] and [Qualitative Theory of Differential Equations, 1985], eleven propositions by several mathematicians are listed on the uniqueness of limit cycles for equations of type (I), (II), and (III) of the quadratic ordinary differential systems. In this paper, we first point out that all these propositions were not completely proved since the equations under consideration do not satisfy the conditions of the theorems used to guarantee the uniqueness of limit cycles. Then we give a new set of theorems that guarantee the uniqueness of limit cycles for the Liénard systems, which not only can be applied to complete the proof of the propositions mentioned above but generalize many other uniqueness theorems as well. The conditions in these uniqueness theorems, which are independent and were obtained by different methods, can be combined into one improved general theorem that is easy to apply. Thus many of the most frequently used theorems on the uniqueness of limit cycles are corollaries of the results in this paper.     

A Nonself-Adjoint 1D Singular Hamiltonian System with an Eigenparameter in the Boundary Condition

In this paper, we study a nonself-adjoint singular 1D Hamiltonian (or Dirac type) system in the limit-circle case, with a spectral parameter in the boundary condition. Our approach depends on the use of the maximal dissipative operator whose spectral analysis is adequate for the boundary value problem. We construct a self-adjoint dilation of the maximal dissipative operator and its incoming and outgoing spectral representations so that we can determine the scattering matrix of dilation. Moreover, we construct a functional model of the dissipative operator and specify its characteristic function using the solutions of the corresponding Hamiltonian system. Based on the results obtained by the theory of the characteristic function, we prove theorems on completeness of the system of eigenvectors and associated vectors of the dissipative operator and Hamiltonian system.     

On the Full Idle Time in Multiphase Queueing Systems

The modern queueing theory is a powerful tool for a quantitative and qualitative analysis of communication systems, computer networks, transportation systems, and many other technical systems. The paper is designated to the analysis of queueing systems arising in the network theory and communications theory (such as the so-called multiphase queueing systems, tandem queues, or series of queueing systems). We present heavy traffic limit theorems for the full idle time in multiphase queueing systems. We prove functional limit theorems for values of the full idle time of a queueing system, which is its important probability characteristic. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 367–386, July–September, 2005.     

Light traffic in a cellular system with mobile subscribers and its applications

This paper is concerned with a cellular system with mobile subscribers (customers). This system consists of a cell, called the tagged cell, and its adjacent cells. Each cell has some finite number of channels. The sojourn times of customers in the tagged cell have an exponential distribution. Customers in the adjacent cells move to the tagged cell according to a Poisson process whose rate depends on the number of customers in the tagged cell. Each customer without call in progress generates his call according to an exponential distribution and the channel holding times of calls at each cell have a common exponential distribution. We first show that under some restriction, the light traffic limit for the stationary state distribution in the tagged cell is given by a mixture of a Poisson and binominal distributions. Based on the limit, we develop formulae for evaluating the hand-off and blocking probabilities and the mean number of busy channels in the tagged cell. Several numerical examples are presented that demonstrate the practical usefulness of the formulae.     

Non‐self‐adjoint singular second‐order dynamic operators on time scale

In this study, maximal dissipative second‐order dynamic operators on semi‐infinite time scale are studied in the Hilbert space , that the extensions of a minimal symmetric operator in limit‐point case. We construct a self‐adjoint dilation of the dissipative operator together with its incoming and outgoing spectral representations so that we can determine the scattering function of the dilation as stated in the scheme of Lax‐Phillips. Moreover, we construct a functional model of the dissipative operator and identify its characteristic function in terms of the Weyl‐Titchmarsh function of a self‐adjoint second‐order dynamic operator. Finally, we prove the theorems on completeness of the system of root functions of the dissipative and accumulative dynamic operators.     

Busy period distributions in the steady state single-server queue and their applications

A method of generating probability distributions of the number of customers served in a busy period of a steady state single-server queueing system with univariate and multivariate inputs is described. A few moments in terms of the moments of the input distributions are derived. Some applications of the busy period distributions to such areas as branching processes, traffic flows, first passage problems, ballot theorems and waiting time distributions are briefly mentioned.     

Compound transient phenomena in multiphase queuing systems. II

The paper continues the article by the author on functional limit theorems in queuing systems under heavy traffic. Theorems are proved for the virtual process of serving jobs when at phases of the queuing system various conditions of heavy traffic are satisfied (compound transient phenomena). Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 39, No. 3, pp. 343–356, July–September, 1999. Translated by Z. Kryžius     

On the single server retrial queue with priority customers

We consider anM ₂/G ₂/1 type queueing system which serves two types of calls. In the case of blocking the first type customers can be queued whereas the second type customers must leave the service area but return after some random period of time to try their luck again. This model is a natural generalization of the classicM ₂/G ₂/1 priority queue with the head-of-theline priority discipline and the classicM/G/1 retrial queue. We carry out an extensive analysis of the system, including existence of the stationary regime, embedded Markov chain, stochastic decomposition, limit theorems under high and low rates of retrials and heavy traffic analysis.Visiting from: Department of Probability, Mechanics and Mathematics, Moscow State University, Moscow 119899, Russia.     

On extreme values in open queueing networks

This paper presents heavy traffic limit theorems for the extreme virtual waiting time of a customer in an open queueing network. In this paper, functional limit theorems are proved for extreme values of important probability characteristics of the open queueing network investigated as the maximum and minimum of the total virtual waiting time of a customer, and the maximum and minimum of the virtual waiting time of a customer. Also, the paper presents the previous related works for extreme values in queues and the virtual waiting time in heavy traffic.