A survey on retrial queues

Queueing systems in which arriving customers who find all servers and waiting positions (if any) occupied may retry for service after a period of time are called retrial queues or queues with repeated orders. Retrial queues have been widely used to model many problems in telephone switching systems, telecommunication networks, computer networks and computer systems. In this paper, we discuss some important retrial queueing models and present their major analytic results and the techniques used. Our concentration is mainly on single-server queueing models. Multi-server queueing models are briefly discussed, and interested readers are referred to the original papers for details. We also discuss the stochastic decomposition property which commonly holds in retrial queues and the relationship between the retrial queue and the queue with server vacations.     

A Heuristic Procedure for Leasing Channels in Telecommunications Networks

Rapid advances in computing and communications technology have made distributed computing an attractive alternative for geographically dispersed organizations. A telecommunication sub-network forms the backbone of these distributed systems. In general, this paper focuses on the assignment of communication channel capacities in the presence of time variant usage patterns. Specifically, we concentrate on long-range capacity planning for organizations that construct networks by leasing communication channels from telecommunication companies. We formulate the capacity assignment problem as a 0-1 integer program that seeks to minimize total leasing cost subject to communication delay restrictions. Unlike previous models that include a single-system wide-average delay constraint, our model allows the flexibility of specifying delay restrictions by communicating node pairs. We propose an efficient heuristic, and a Lagrangian relaxation based procedure to obtain performance guarantees on the solution obtained from the heuristic.     

Models for planning capacity expansion in local access telecommunication networks

The rapid progress of communications technology has created new opportunities for modeling and optimizing the design of local telecommunication systems. The complexity, diversity, and continuous evolution of these networks pose several modeling challenges. In this paper, we present an overview of the local telephone network environment, and discuss possible modeling approaches. In particular, we (i) discuss the engineering characteristics of the network, and introduce terminology that is commonly used in the communications industry and literature; (ii) describe a general local access network planning model and framework, and motivate different possible modeling assumptions; (iii) summarize various existing planning models in the context of this framework; and (iv) describe some new modeling approaches. The discussion in this paper is directed both to researchers interested in modeling local telecommunications systems and to planners interested in using such models. Our goal is to present relevant aspects of the engineering environment for local access telecommunication networks, and to discuss the relationship between engineering issues and the formulation of economic decision models. We indicate how changes in the underlying switching and transmission technology affect the modeling of the local telephone network. We also review various planning issues and discuss possible optimization approaches for treating them.This research was initiated through a grant from GTE Laboratories, IncorporatedSupported in part by an AT&T research award.Supported in part by Grant No. ECS-8316224 from the Systems Theory and Operations Research Program of the National Science Foundation.     

Reliability Analysis of the Retrial Queue with Server Breakdowns and Repairs

Retrial queues have been widely used to model many problems arising in telephone switching systems, telecommunication networks, computer networks and computer systems, etc. It is of basic importance to study reliability of retrial queues with server breakdowns and repairs because of limited ability of repairs and heavy influence of the breakdowns on the performance measure of the system. However, so far the repairable retrial queues are analyzed only by queueing theory. In this paper we give a detailed analysis for reliability of retrial queues. By using the supplementary variables method, we obtain the explicit expressions of some main reliability indexes such as the availability, failure frequency and reliability function of the server. In addition, some special queues, for instance, the repairable M/G/1 queue and repairable retrial queue can be derived from our results. These results may be generalized to the repairable multi-server retrial models.     

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.     

On the Finite Buffer Queue with Renewal Input and Batch Markovian Service Process: GI/BMSP/1/N

We consider a finite-buffer single-server queue with renewal input where the service is provided in batches of random size according to batch Markovian service process (BMSP). Steady-state distribution of number of customers in the system at pre-arrival and arbitrary epochs have been obtained along with some important performance measures. The model has potential applications in the areas of computer networks, telecommunication systems, and manufacturing systems, etc.      

Output feedback stabilization for a class of nonlinear time-evolution systems

A variety of problems in nonlinear time-evolution systems such as communication networks, computer networks, manufacturing, traffic management, etc., can be modelled as min–max-plus systems in which operations of min, max and addition appear simultaneously. Systems with only maximum (or minimum) constraints can be modelled as max-plus system and handled by max-plus algebra which changes the original nonlinear system in the traditional sense into linear system in this framework. Min-max-plus systems are extensions of max-plus systems and nonlinear even in the max-plus algebra view. Output feedback stabilization for min–max-plus systems with min–max-plus inputs and max-plus outputs is considered in this paper. Max-plus projection representation for the closed-loop system with min–max-plus output feedback is introduced and the formula to calculate the cycle time is presented. Stabilization of reachable systems with at least one observable state and a further result for reachable and observable systems are worked out, during which max-plus output feedbacks are used to stabilize the systems. The method based on the max-plus algebra is constructive in nature.     

A new perspective on the normalization of invariant measures for loss networks and other product form systems

Loss networks have proved to be a vital tool in the study of telecommunication networks, computer performance, and resource allocation problems. For a large subset of these models, the invariant measure is of a product form. The existence of efficient procedures to normalize a product-form invariant measure is essential for analysis of the underlying system.Choudhury et al. [1—4] have recently presented a number of algorithms based upon Fourier analysis for the normalization of product-form invariant measures for specific systems. Bean and Stewart [5] discussed related work for the normalization of product-form invariant measures for closed queueing networks. In this paper, we present a simple unifying framework within which to study these algorithms. This framework is significant as it suggests a number of extensions to these algorithms and simplifies their derivation.     

A class of renewal Interrupted Poisson Processes and applications to queueing systems

Switched Poisson Processes and Interrupted Poisson Processes are often employed to characterize traffic streams in distributed computer and communications systems, especially in investigations of overflow processes in telecommunication networks. With these processes, input streams having inter-segment correlations and high variance as well as state-dependent traffic can properly be modelled. In this paper we first derive an approximation method to describe the Generalized Switched Poisson processes in conjunction with a renewal assumption. As a special case of this class of processes, the class of Interrupted Poisson processes is also included in the investigation. As a result, a generalization of the well-known class of Interrupted Poisson processes is obtained. It is shown that the renewal property is also given for this general class of Interrupted Poisson processes having generally distributed off-phase. To illustrate the accuracy of the presented renewal approximation of Generalized Switched Poisson processes and to show the major properties of the General Interrupted Poisson processes, applications to some basic queueing systems are discussed by means of numerical results.This work was done while the author was with Institute of Communications Switching and Data Technics, University of Stuttgart, Seidenstrasse 36, D-7000 Stuttgart 1, FRG.     

具有相型服务分布的排队系统的性能灵敏度分析

具有非线数服务分布的排队网络已被广泛应用于许多领域,如通讯网络和管理系统。本文借助于无穷小说矩阵摄动方法,研究了M/PH/1排队系统的稳态性能灵敏度分析问题,给出了性能灵敏度公式,并表明了稳态性能灵敏度很容易通过系统势能进行计算。同时,给出一种计算势能及性能导数的算法。这个算法可直接用于系统的控制与优化,因为它基于分析系统的一条单一样本轨道。最后提供一个数值例子来表明这个算法的应用。