Analysis of Some Queueing Models Related To N-Policy: Operations Research

This study is about the analysis of some queueing models related to N-policy.The optimal value the queue size has to attain in order to turn on a single server, assuming that the policy is to turn on a single server when the queue size reaches a certain number, N, and turn him off when the system is empty.The operating policy is the usual N-policy, but with random N and in model 2, a system similar to the one described here.This study analyses “ Tandem queue with two servers”.Here assume that the first server is a specialized one.In a queueing system,under N-policy ,the server will be on vacation until N units accumulate for the first time after becoming idle.A modified version of the N-policy for an M│M│1 queueing system is considered here.The novel feature of this model is that a busy service unit prevents the access of new customers to servers further down the line.It is deals with a queueing model consisting of two servers connected in series with a finite intermediate waiting room of capacity k.Here assume that server I is a specialized server.For this model ,the steady state probability vector and the stability condition are obtained using matrix – geometric method.

Queueing Models with Vacations and Working Vacations

The thesis entitled “Queueing Models with Vacations and Working Vacations" consists of seven chapters including the introductory chapter. In chapters 2 to 7 we analyze different queueing models highlighting the role played by vacations and working vacations. The duration of vacation is exponentially distributed in all these models and multiple vacation policy is followed.In chapter 2 we discuss an M/M/2 queueing system with heterogeneous servers, one of which is always available while the other goes on vacation in the absence of customers waiting for service. Conditional stochastic decomposition of queue length is derived. An illustrative example is provided to study the effect of the input parameters on the system performance measures. Chapter 3 considers a similar setup as chapter 2. The model is analyzed in essentially the same way as in chapter 2 and a numerical example is provided to bring out the qualitative nature of the model. The MAP is a tractable class of point process which is in general nonrenewal. In spite of its versatility it is highly tractable as well. Phase type distributions are ideally suited for applying matrix analytic methods. In all the remaining chapters we assume the arrival process to be MAP and service process to be phase type. In chapter 4 we consider a MAP/PH/1 queue with working vacations. At a departure epoch, the server finding the system empty, takes a vacation. A customer arriving during a vacation will be served but at a lower rate.Chapter 5 discusses a MAP/PH/1 retrial queueing system with working vacations.In chapter 6 the setup of the model is similar to that of chapter 5. The signicant dierence in this model is that there is a nite buer for arrivals.Chapter 7 considers an MMAP(2)/PH/1 queueing model with a nite retrial group

Queueing Models with Vacations and Working Vacations

The objective of the study of \Queueing models with vacations and working vacations" was two fold; to minimize the server idle time and improve the e ciency of the service system. Keeping this in mind we considered queueing models in di erent set up in this thesis. Chapter 1 introduced the concepts and techniques used in the thesis and also provided a summary of the work done. In chapter 2 we considered an M=M=2 queueing model, where one of the two heterogeneous servers takes multiple vacations. We studied the performance of the system with the help of busy period analysis and computation of mean waiting time of a customer in the stationary regime. Conditional stochastic decomposition of queue length was derived. To improve the e ciency of this system we came up with a modi ed model in chapter 3. In this model the vacationing server attends the customers, during vacation at a slower service rate. Chapter 4 analyzed a working vacation queueing model in a more general set up. The introduction of N policy makes this MAP=PH=1 model di erent from all working vacation models available in the literature. A detailed analysis of performance of the model was provided with the help of computation of measures such as mean waiting time of a customer who gets service in normal mode and vacation mode.

A ∑GIi/D/1/∞ queue with heterogeneous input/output slot times

In this paper, we present a ∑GIi/D/1/∞ queue with heterogeneous input/output slot times. This queueing model can be regarded as an extension of the ordinary GI/D/1/∞ model. For this ∑GIi/D/1/∞ queue, we assume that several input streams arrive at the system according to different slot times. In other words, there are different slot times for different input/output processes in the queueing model. The queueing model can therefore be used for an ATM multiplexer with heterogeneous input/output link capacities. Several cases of the queueing model are discussed to reflect different relationships among the input/output link capacities of an ATM multiplexer. In the queueing analysis, two approaches: the Markov model and the probability generating function technique, are adopted to develop the queue length distributions observed at different epochs. This model is particularly useful in the performance analysis of ATM multiplexers with heterogeneous input/output link capacities.

Discrete parameter simulation optimization algorithms with applications to admission control with dependent service times

We propose certain discrete parameter variants of well known simulation optimization algorithms. Two of these algorithms are based on the smoothed functional (SF) technique while two others are based on the simultaneous perturbation stochastic approximation (SPSA) method. They differ from each other in the way perturbations are obtained and also the manner in which projections and parameter updates are performed. All our algorithms use two simulations and two-timescale stochastic approximation. As an application setting, we consider the important problem of admission control of packets in communication networks under dependent service times. We consider a discrete time slotted queueing model of the system and consider two different scenarios - one where the service times have a dependence on the system state and the other where they depend on the number of arrivals in a time slot. Under our settings, the simulated objective function appears ill-behaved with multiple local minima and a unique global minimum characterized by a sharp dip in the objective function in a small region of the parameter space. We compare the performance of our algorithms on these settings and observe that the two SF algorithms show the best results overall. In fact, in many cases studied, SF algorithms converge to the global minimum.

Average-Delay Optimal Policies for the Point-to-Point Channel

Average-delay optimal scheduflng of messages arriving to the transmitter of a point-to-point channel is considered in this paper. We consider a discrete time batch-arrival batch-service queueing model for the communication scheme, with service time that may be a function of batch size. The question of delay optimality is addressed within the semi-Markov decision-theoretic framework. Approximations to the average-delay optimal policy are obtained.

Solution of MDPS using simulation-based value iteration

This article proposes a three-timescale simulation based algorithm for solution of infinite horizon Markov Decision Processes (MDPs). We assume a finite state space and discounted cost criterion and adopt the value iteration approach. An approximation of the Dynamic Programming operator T is applied to the value function iterates. This 'approximate' operator is implemented using three timescales, the slowest of which updates the value function iterates. On the middle timescale we perform a gradient search over the feasible action set of each state using Simultaneous Perturbation Stochastic Approximation (SPSA) gradient estimates, thus finding the minimizing action in T. On the fastest timescale, the 'critic' estimates, over which the gradient search is performed, are obtained. A sketch of convergence explaining the dynamics of the algorithm using associated ODEs is also presented. Numerical experiments on rate based flow control on a bottleneck node using a continuous-time queueing model are performed using the proposed algorithm. The results obtained are verified against classical value iteration where the feasible set is suitably discretized. Over such a discretized setting, a variant of the algorithm of [12] is compared and the proposed algorithm is found to converge faster.

Stability of scheduled message communication over degraded broadcast channels

We develop a multi-class discrete-time processor-sharing queueing model for scheduled message communication over a discrete memoryless degraded broadcast channel. The framework we consider here models both the random message arrivals and the subsequent reliable communication by suitably combining techniques from queueing theory and information theory. Requests for message transmissions are assumed to arrive according to i.i.d. arrival processes. Then, (i) we derive an outer bound to the stability region of message arrival rate vectors achievable by the class of stationary scheduling policies, (ii) we show for any message arrival rate vector that satisfies the outer bound, that there exists a stationary "state-independent" policy that results in a stable system for the corresponding message arrival processes, and (iii) under an asymptotic regime, we show that the stability region of information arrival rate vectors is the information-theoretic capacity region of a degraded broadcast channel.

An algorithm for dynamic optimal bandwidth allocation in communication networks

We study the problem of optimal bandwidth allocation in communication networks. We consider a queueing model with two queues to which traffic from different competing flows arrive. The queue length at the buffers is observed every T instants of time, on the basis of which a decision on the amount of bandwidth to be allocated to each buffer for the next T instants is made. We consider a class of closed-loop feedback policies for the system and use a twotimescale simultaneous perturbation stochastic approximation(SPSA) algorithm to find an optimal policy within the prescribed class. We study the performance of the proposed algorithm on a numerical setting. Our algorithm is found to exhibit good performance.

Optimal Parameterized Policies for Resource Allocation in Communication Networks

The problem of finding optimal parameterized feedback policies for dynamic bandwidth allocation in communication networks is studied. We consider a queueing model with two queues to which traffic from different competing flows arrive. The queue length at the buffers is observed every T instants of time, on the basis of which a decision on the amount of bandwidth to be allocated to each buffer for the next T instants is made. We consider two different classes of multilevel closed-loop feedback policies for the system and use a two-timescale simultaneous perturbation stochastic approximation (SPSA) algorithm to find optimal policies within each prescribed class. We study the performance of the proposed algorithm on a numerical setting and show performance comparisons of the two optimal multilevel closedloop policies with optimal open loop policies. We observe that closed loop policies of Class B that tune parameters for both the queues and do not have the constraint that the entire bandwidth be used at each instant exhibit the best results overall as they offer greater flexibility in parameter tuning. Index Terms — Resource allocation, dynamic bandwidth allocation in communication networks, two-timescale SPSA algorithm, optimal parameterized policies. I.

Tradeoff of average service cost and average delay for the state dependent M/M/1 queue

The optimal tradeoff between average service cost rate and average delay, is addressed for a M/M/1 queueing model with queue-length dependent service rates, chosen from a finite set. We provide an asymptotic characterization of the minimum average delay, when the average service cost rate is a small positive quantity V more than the minimum average service cost rate required for stability. We show that depending on the value of the arrival rate, the assumed service cost rate function, and the possible values of the service rates, the minimum average delay either a) increases only to a finite value, b) increases without bound as log(1/V), or c) increases without bound as 1/V, when V down arrow 0. We apply the analysis to a flow-level resource allocation model for a wireless downlink. We also investigate the asymptotic tradeoff for a sequence of policies which are obtained from an approximate fluid model for the M/M/1 queue.

A Bayesian Approach for TCP to Distinguish Congestion from Wireless Losses

(This Technical Report revises TR-BUCS-2003-011) The Transmission Control Protocol (TCP) has been the protocol of choice for many Internet applications requiring reliable connections. The design of TCP has been challenged by the extension of connections over wireless links. In this paper, we investigate a Bayesian approach to infer at the source host the reason of a packet loss, whether congestion or wireless transmission error. Our approach is "mostly" end-to-end since it requires only one long-term average quantity (namely, long-term average packet loss probability over the wireless segment) that may be best obtained with help from the network (e.g. wireless access agent).Specifically, we use Maximum Likelihood Ratio tests to evaluate TCP as a classifier of the type of packet loss. We study the effectiveness of short-term classification of packet errors (congestion vs. wireless), given stationary prior error probabilities and distributions of packet delays conditioned on the type of packet loss (measured over a larger time scale). Using our Bayesian-based approach and extensive simulations, we demonstrate that congestion-induced losses and losses due to wireless transmission errors produce sufficiently different statistics upon which an efficient online error classifier can be built. We introduce a simple queueing model to underline the conditional delay distributions arising from different kinds of packet losses over a heterogeneous wired/wireless path. We show how Hidden Markov Models (HMMs) can be used by a TCP connection to infer efficiently conditional delay distributions. We demonstrate how estimation accuracy is influenced by different proportions of congestion versus wireless losses and penalties on incorrect classification.

Retrial Queues with Orbital Search

Queueing system in which arriving customers who find all servers and waiting positions (if any) occupied many retry for service after a period of time are retrial queues or queues with repeated attempts. This study deals with two objectives one is to introduce orbital search in retrial queueing models which allows to minimize the idle time of the server. If the holding costs and cost of using the search of customers will be introduced, the results we obtained can be used for the optimal tuning of the parameters of the search mechanism. The second one is to provide insight of the link between the corresponding retrial queue and the classical queue. At the end we observe that when the search probability Pj = 1 for all j, the model reduces to the classical queue and when Pj = 0 for all j, the model becomes the retrial queue. It discusses the performance evaluation of single-server retrial queue. It was determined by using Poisson process. Then it discuss the structure of the busy period and its analysis interms of Laplace transforms and also provides a direct method of evaluation for the first and second moments of the busy period. Then it discusses the M/ PH/1 retrial queue with disaster to the unit in service and orbital search, and a multi-server retrial queueing model (MAP/M/c) with search of customers from the orbit. MAP is convenient tool to model both renewal and non-renewal arrivals. Finally the present model deals with back and forth movement between classical queue and retrial queue. In this model when orbit size increases, retrial rate also correspondingly increases thereby reducing the idle time of the server between services

Queues with Customer Induced Interruption

In this thesis we have introduced and studied the notion of self interruption of service by customers. Service interruption in queueing systems have been extensively discussed in literature (see, Krishnamoorthy, Pramod and Chakravarthy [38]) for the most recent survey. So far all work reported deal with cases in which service interruptions are generated by sources other than customers. However, there are situations where interruptions are due to the customers rather than the system. Such situations are especially arise at doctors clinic, banks, reservation counter etc. Our attempt is to quantify a few of such problems. Systematically we have proceed from single server queue (in Chapter 2) to multi-server queues (Chapter 3). In Chapte 4, we have studied a very general multiserver queueing model with service interruption and protection of service phases. We also introduced customer interruption in a retrial setup (in Chapter 5). All models (from Chapter 2 to Chapter 4) that were analyzed involve 'non-preemptive priority' for interrupted customers where as in the model discussed in Chapter 5 interruption of service by customers is not encouraged. So the interrupted customers cannot access the server as long as there are primary customers in the system. In Chapter 5 we have obtained an explicit expression for the stability condition of the system. In all models analyzed in this thesis, we have assumed that no more than one interruption is allowed for a customer while in service. Since the models are not analytically tractable, a large number of numerical illustrations were given in each chapter it illustrate the working of the systems. We can extend the models discussed in this thesis to several directions. For example some of the models can be analyzed with both server induced and customer induced interruptions the results for which are not available till date. Another possible extension of work is to the case where there is no bound on the number of interruptions a customer is permitted to have before service completion. More complex is the case where a customer is permitted to have a nite number (K ≥ 2) of We can extend the models discussed in this thesis to several directions.

Subgeometric rates of convergence for a class of continuous-time Markov process

Let (Phi(t))(t is an element of R+) be a Harris ergodic continuous-time Markov process on a general state space, with invariant probability measure pi. We investigate the rates of convergence of the transition function P-t(x, (.)) to pi; specifically, we find conditions under which r(t) vertical bar vertical bar P-t (x, (.)) - pi vertical bar vertical bar -> 0 as t -> infinity, for suitable subgeometric rate functions r(t), where vertical bar vertical bar - vertical bar vertical bar denotes the usual total variation norm for a signed measure. We derive sufficient conditions for the convergence to hold, in terms of the existence of suitable points on which the first hitting time moments are bounded. In particular, for stochastically ordered Markov processes, explicit bounds on subgeometric rates of convergence are obtained. These results are illustrated in several examples.