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.     

A Markov Renewal Based Model for Wireless Networks

We propose a queueing network model which can be used for the integration of the mobility and teletraffic aspects that are characteristic of wireless networks. In the general case, the model is an open network of infinite server queues where customers arrive according to a non-homogeneous Poisson process. The movement of a customer in the network is described by a Markov renewal process. Moreover, customers have attributes, such as a teletraffic state, that are driven by continuous time Markov chains and, therefore, change as they move through the network. We investigate the transient and limit number of customers in disjoint sets of nodes and attributes. These turn out to be independent Poisson random variables. We also calculate the covariances of the number of customers in two sets of nodes and attributes at different time epochs. Moreover, we conclude that the arrival process per attribute to a node is the sum of independent Poisson cluster processes and derive its univariate probability generating function. In addition, the arrival process to an outside node of the network is a non-homogeneous Poisson process. We illustrate the applications of the queueing network model and the results derived in a particular wireless network.     

Queueing models for the analysis of communication systems

Queueing models can be used to model and analyze the performance of various subsystems in telecommunication networks; for instance, to estimate the packet loss and packet delay in network routers. Since time is usually synchronized, discrete-time models come natural. We start this paper with a review of suitable discrete-time queueing models for communication systems. We pay special attention to two important characteristics of communication systems. First, traffic usually arrives in bursts, making the classic modeling of the arrival streams by Poisson processes inadequate and requiring the use of more advanced correlated arrival models. Second, different applications have different quality-of-service requirements (packet loss, packet delay, jitter, etc.). Consequently, the common first-come-first-served (FCFS) scheduling is not satisfactory and more elaborate scheduling disciplines are required. Both properties make common memoryless queueing models (M/M/1-type models) inadequate. After the review, we therefore concentrate on a discrete-time queueing analysis with two traffic classes, heterogeneous train arrivals and a priority scheduling discipline, as an example analysis where both time correlation and heterogeneity in the arrival process as well as non-FCFS scheduling are taken into account. Focus is on delay performance measures, such as the mean delay experienced by both types of packets and probability tails of these delays.     

Branching/queueing networks: Their introduction and near-decomposability asymptotics

A new class of models, which combines closed queueing networks with branching processes, is introduced. The motivation comes from MIMD computers and other service systems in which the arrival of new work is always triggered by the completion of former work, and the amount of arriving work is variable. In the variant of branching/queueing networks studied here, a customer branches into a random and state-independent number of offspring upon completing its service. The process regenerates whenever the population becomes extinct. Implications for less rudimentary variants are discussed. The ergodicity of the network and several other aspects are related to the expected total number of progeny of an associated multitype Galton-Watson process. We give a formula for that expected number of progeny. The objects of main interest are the stationary state distribution and the throughputs. Closed-form solutions are available for the multi-server single-node model, and for homogeneous networks of infinite-servers. Generally, branching/queueing networks do not seem to have a product-form state distribution. We propose a conditional product-form approximation, and show that it is approached as a limit by branching/queueing networks with a slowly varying population size. The proof demonstrates an application of the nearly complete decomposability paradigm to an infinite state space. This revised version was published online in June 2006 with corrections to the Cover Date.     

Departure Process of the MAP/SM/1 Queue

We study the departure process of a single server queue with Markovian arrival input and Markov renewal service time. We derive the joint transform of departure time and the number of departures and, based on this transform, we establish several expressions for burstiness (variance) and correlation (covariance sequence) of the departure process. These expressions reveal that burstiness and correlation of the arrival process have very little impact on the departure process when a queueing system is heavily loaded. In contrast, both burstiness and correlation of the service-time process greatly affect those of the departure process regardless of the load of the system. Finally, we show that, even when an arrival process is short-range dependent, the departure process could has long-range dependence if a service-time process is long-range dependent.     

The departure process of discrete-time queueing systems with Markovian type inputs

This paper proposes a unified matrix-analytic approach to characterize the output processes of general discrete-time lossless/lossy queueing systems in which time is synchronized/slotted into fixed length intervals called slots. The arrival process can be continuous- or discrete-time Markovian processes. It can be either renewal or non-renewal. The service of a customer commences at the beginning of a slot, consumes a random number of slots, and completes at the end of a later slot. The service times are independent and follow a common and general distribution. Systems with and without server vacations are both treated in this paper. These queueing systems have potential applications in asynchronous transfer mode (ATM) networks, packet radio networks, etc. Since the output process of a node in a queueing network becomes an input process to some node at the next stage, the results of this paper can be used to facilitate end-to-end performance analysis which has attracted more and more attention in the literature. This revised version was published online in June 2006 with corrections to the Cover Date.     

Towards better multi-class parametric-decomposition approximations for open queueing networks

Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is (GT _i /GI _i )/1 with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric-decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by Bitran and Tirupati [5]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations.     

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.     

TRANSIENT SOLUTION FOR QUEUE-LENGTH DISTRIBUTION OF Geometry/G/1 QUEUEING MODEL

In this paper, the Geometry/G/1 queueing model with inter-arrival times generated by a geometric（parameter p） distribution according to a late arrival system with delayed access and service times independently distributed with distribution {gj }, j≥ 1 is studied. By a simple method （techniques of probability decomposition, renewal process theory） that is different from the techniques used by Hunter（1983）, the transient property of the queue with initial state i（i ≥ 0） is discussed. The recursion expression for u -transform of transient queue-length distribution at any time point n^＋ is obtained, and the recursion expression of the limiting queue length distribution is also obtained.     

Decomposition results for general polling systems and their applications

In this paper we derive decomposition results for the number of customers in polling systems under arbitrary (dynamic) polling order and service policies. Furthermore, we obtain sharper decomposition results for both the number of customers in the system and the waiting times under static polling policies. Our analysis, which is based on distributional laws, relaxes the Poisson assumption that characterizes the polling systems literature. In particular, we obtain exact decomposition results for systems with either Mixed Generalized Erlang (MGE) arrival processes, or asymptotically exact decomposition results for systems with general renewal arrival processes under heavy traffic conditions. The derived decomposition results can be used to obtain the performance analysis of specific systems. As an example, we evaluate the performance of gated Markovian polling systems operating under heavy traffic conditions. We also provide numerical evidence that our heavy traffic analysis is very accurate even for moderate traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

On approximating higher order MAPs with MAPs of order two

We show that the autocorrelation sequence of interarrival times for a Markovian arrival process (MAP) of order two is geometric. We determine the set of feasible values for the autocorrelation decay parameter and the first two or three moments of the interarrival time distribution. A method is derived for matching these parameters to a MAP of order two and some numerical examples are included to illustrate approximating higher dimensional MAPs by two dimensional ones. The numerical examples have helped us pose important questions regarding the significance of correlation in a MAP of order two when it is used as input to a queueing model.     

The advantage of indices of dispersion in queueing approximations

A recent robust queueing approximation for open queueing networks exploits partial characterizations of each arrival process by its rate and index of dispersion for counts (IDC), which is a scaled version of the variance–time curve. Even though only means and variances (as functions of time) are involved, we show that the IDC provides a basis for more accurate approximations than traditional two-moment partial characterizations. For the $GI∕GI∕1$ queue, this approach applied to the arrival and service processes fully characterizes the model.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Approximate analysis of arbitrary configurations of open queueing networks with blocking

An algorithm for analyzing approximately open exponential queueing networks with blocking is presented. The algorithm decomposes a queueing network with blocking into individual queues with revised capacity, and revised arrival and service processes. These individual queues are then analyzed in isolation. Numerical experience with this algorithm is reported for three-node and four-node queueing networks. The approximate results obtained were compared against exact numerical data, and they seem to have an acceptable error level.Supported in part by a grant from CAIP Center, Rutgers University.Supported in part by the National Science Foundation under Grant DCR-85-02540.     

A two-stage queueing network on form postponement supply chain with correlated demands

To ease the conflict between quick response and product variety, more and more business models are developed in supply chains. Among these, the form postponement (FP) strategy is an efficient tool and has been widely adopted. To the supply chain with FP strategy, the design mostly involves two problems: determination of customer order decoupling point (CODP) position and semi-finished product inventory control. In this paper, we develop a two-stage tandem queueing network with MAP arrival to address this issue. Particularly, we introduce a Markov arrival process (MAP) to characterize the correlation of the demand. By using of matrix geometric method, we derive several performance measure of the supply chain, such as inventory level and unfill rate. Our numerical examples show that both the variance and the correlation coefficient of the demand lead to more delayed CODP position and more total cost.     

Computation of the steady state distribution for multi-server retrial queues with phase type service process

We consider a multi-server retrial queueing system with the Batch Markovian Arrival Process and phase type service time distribution. Such a general queueing system suits for modeling and decision making in many real life objects including modern wireless communication networks. Behavior of such a system is described by the level dependent multi-dimensional Markov chain. Blocks of the generator of this chain, which is the block structured matrix of infinite size, can have large size if the number of servers is large and distribution of service time is not exponential. Due to this fact, the existing in literature algorithms allow to compute key performance measures of such a system only for a small number of servers. Here we describe the algorithm that allows to compute the stationary distribution of the system for larger number of servers and numerically illustrate its advantage. Importance of taking into account correlation in the arrival process is numerically demonstrated.     

An MAP/G/1 G-queues with preemptive resume and multiple vacations

In this paper, we consider an MAP/G/1 G-queues with possible preemptive resume service discipline and multiple vacations wherein the arrival process of negative customers is Markovian arrival process (MAP). The arrival of a negative customer may remove the customer being in service. The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service and vacation times are arbitrarily distributed. We obtain the queue length distributions with the method of supplementary variables, combined with the matrix-analytic method and censoring technique. We also obtain the mean of the busy period based on the renewal theory. Finally we provide expressions for a special case.     

THE MATCHED QUEUEING SYSTEM GI。PH/PH/1

ＴＨＥＭＡＴＣＨＥＤＱＵＥＵＥＩＮＧＳＹＳＴＥＭＧＩ。ＰＨ／ＰＨ／１ＸＵＧＵＡＮＣＨＵＩ（ＧＵＡＮＧ－ＨＵＩＨＳＶ）（徐光煇）；ＨＥＱＩＭＩＮＧ（何启明）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙ...