Proof of stability conditions for token passing rings by Lyapunovfunctions

A token passing ring can be described as a system of M queues with one server that rotates around the queues sequentially. Georgiadis-Szpankowski (1992) considered rings where the token (server) performs x ∇ l_j services on queue j, where x is the size of queue j upon arrival of the token, and l_j is a fixed limit of service for queue j. The token then spends some random time switching to the next queue. For j=1, ..., M, arrivals to queue j are Poisson with rate λ_j, and service times have mean s _j and are independent of the arrival and switchover processes. The purpose of this paper is to give an alternate and simpler proof of the stability conditions given by Georgiadis-Szpankowski using Lyapunov functions. An additional assumption is made about the second moments of the service and switchover times being finite     

Analysis of a multi-server queue with two priority classes and (M, N)-threshold service schedule I: non-preemptive priority

In this paper, we propose an ( M , N )-threshold non-preemptive priority service schedule for a queueing system consisting of two-parallel queues and a multi-server. The arrival process for each queue is Poisson, and the service times are exponentially distributed with different means. We derive the generating functions of the stationary joint queue-length distribution, and then obtain the mean queue length and the mean waiting time for each queue.     

Approximate analysis of reader/writer queues

We analyze the performance of queues that serve readers and writers. Readers are served concurrently, while writers require exclusive service. We approximately analyze a first-come-first-serve (FCFS) reader/writer queue, and derive simple formulae for computing waiting times and capacity under the assumption of Poisson arrivals and exponential service. We extend the analysis to handle a one writer queue, and a queue that includes write intention locks. The simple analyses that we present can be used as rules of thumb for designing concurrent systems     

Matrix analytical model of an ATM output buffer with self-similar traffic

Renewal processes with asymptotically hyperbolic interarrival time distributions are shown to exhibit self-similar behavior. An output buffer of an ATM switch is modeled as a discrete time queue with a single server, deterministic service times and self-similar renewal process input. A matrix geometric solution is found for the stationary distribution of states. For the case of hyperbolically distributed interarrival times, the mean and standard deviation of queue length are plotted for various values of the queue utilization and the self-similarity parameter of the arrival process. The self-similarity is found to have a significant impact on the performance of the queue.     

A polynomial factorization approach to the discrete time GI/G/1/(N) queue size distribution

The queue of a single server is considered with independent and identically distributed interarrivai and service times and an infinite (GI/G/1) or finite (GI/G/1/N) waiting room. The queue discipline is non-preemptive and independent of the service times.

A discrete time version of the system is analyzed, using a two-component state model at the arrival and departure instants of customers. The equilibrium equations are solved by a polynomial factorization method. The steady state distribution of the queue size is then represented as a linear combination of geometrical series, whose parameters are evaluated by closed formulae depending on the roots of a characteristic polynomial.

Considering modified boundary constraints, systems with finite waiting room or with an exceptional first service in each busy period are included.     

A conservation law based approximate analysis for a class of simultaneous resource possession problems

In this paper we analyze a single server queueing model in which there are two types of jobs, one of which must wait in an external queue until a token is available, and only then may join the service queue. The interarrival times and service requirements for both types of jobs are assumed to be independent and exponentially distributed.

We derive the stability condition for such a model where the service queue discipline is either FCFS (First-Come-First-Serve) or PS (Processor-Sharing). We then propose analytic approximations for the mean waiting times for both types of jobs, relying heavily on the M/G/1 conservation law. Numerical results show that our approximations are very accurate (within a few percent of the simulated results) even when the system is heavily loaded. The approximations are also shown to be asymptotically exact as the number of tokens N → ∞.     

Throughput in Processor-Sharing Queues

Processor-sharing queues are often used to model file transmission in networks. While sojourn time is a common performance metric in the queueing literature, average transmission rate is the more commonly discussed metric in the networking literature. Whereas much is known about sojourn times, there is little known about the average service rate experienced by jobs in processor-sharing queues. We first define the average rate as observed by users and by the queue. In an M/M/1 processor-sharing queue, we give closed-form expressions for these average rates, and prove a strict ordering amongst them. We prove that the queue service rate (in bps) is an increasing function of the minimum required average transmission rate, and give a closed-form expression for the marginal cost associated with such a performance requirement. We then consider the effect of using connection access control by modeling an M/M/1/K processor-sharing queue. We give closed-form expressions for average transmission rates, and discuss the relationship between the queue service rate (in bps), the queue limit, the average rate, and the blocking probability     

Queueing analysis of manufacturing systems with set ups

A manufacturing system with one server (machine), two classes of jobs, finite buffer sizes, and non-negligible set-up times is analysed. A cycling service discipline with a ’wait and see‘ set-up policy is invoked by the server. The state of the machine, whether in set up or in processing, is explicitly considered in the model. Utilization, mean queue length, and cycle time are derived using markovian analysis, first under a fixed lot size environment and then with random lot sizes. With lot sizes fixed, increasing arrival rates, set-up times, and service times generally increase the utilization, cycle time, and queue lengths. When lot sizes are random, there are negligible variations in the cycle time result, with somewhat smaller queue lengths compared to the fixed lot size case. An approximate mean value analysis is also developed and results are compared to those of the markovian analysis. Numerical studies show the robustness of the mean value analysis for most of the system parameters tested.     

Finite capacity priority queues with potential health applications

The queuing processes of interest in this paper are that of waiting lines with two priorities and multiple service channels. The arrival process is assumed Poison and the service time distribution is negative exponential. Arriving units enter service if there is at least one idle channel, otherwise they join a finite queue and are served according to a non-preemptive priority discipline. If a low priority arriving unit finds the queue full, it is not allowed to enter the system and is considered “blocked” or lost. In the first model a high priority arrival may displace a low priority unit from the full queue and may be “blocked” if the queue consists of high priority units only. In the second model the high priority unit may still displace a low priority unit from the full queue but it will never be “blocked” and may wait “outside” the system if the system is full. Thus far there has been no discussion of such models in queuing theory literature. In this paper analytical expressions for average waiting times have been obtained for the two models. Two potential applications of the models are described and the usefulness of the models is illustrated by numerical examples.     

Optimal control of a queueing system with two heterogeneous servers

The problem considered is that of optimally controlling a queueing system which consists of a common buffer or queue served by two servers. The arrivals to the buffer are Poisson and the servers are both exponential, but with different mean service times. It is shown that the optimal policy which minimizes the mean sojourn time of customers in the system is of threshold type. The faster server should be fed a customer from the buffer whenever it becomes available for service, but the slower server should be utilized if and only if the queue length exceeds a readily computed threshold value.     

A Two-Queue Polling Model with Two Priority Levels in the First Queue

In this paper we consider a single-server cyclic polling system consisting of two queues. Between visits to successive queues, the server is delayed by a random switch-over time. Two types of customers arrive at the first queue: high and low priority customers. For this situation the following service disciplines are considered: gated, globally gated, and exhaustive. We study the cycle time distribution, the waiting times for each customer type, the joint queue length distribution at polling epochs, and the steady-state marginal queue length distributions for each customer type.     

Violation Probability in Processor-Sharing Queues

Processor-sharing queues are often used to model file transmission in networks. While sojourn time is a common performance metric in the queueing literature, average transmission rate is the more commonly discussed metric in the networking literature. Whereas much is known about sojourn times, there is little known about the average service rate experienced by jobs in processor-sharing queues. We focus here upon performance requirements in the form of an upper bound on the probability of failing to achieve a specified minimum transmission rate or a specified minimum average rate. For an M/G/l processor-sharing queue, we give a closed-form expression for this violation probability. We derive closed-form expressions for the marginal service rate with respect to the violation probability and to the minimum transmission rate, and characterize when each is binding. We then consider the effect of using connection access control by modeling an M/G/l/K processor-sharing queue, and discuss the relationship between queue service rate, queue limit, violation probability, and blocking probability. Finally, we consider a two-class discriminatory processor-sharing queue, and discuss what combinations of class weighting and service rate can be used to achieve specified minimum rate violation probabilities for both classes.     

Regulating an M/G/1 queue when customers know their demand

Customers do not necessarily join a queue at a socially optimal rate. Hence, queueing systems may call for regulation. For customers in an M/G/1 unobservable (not necessarily FCFS) queue and homogeneous with respect to waiting costs and service rewards, we show how queueing systems can be regulated by imposing an entry fee, a holding fee (based on time in the system), or a service fee (based on the required service time) when customers know their service requirements. We start with a unified approach and state the socially optimal fees. We show that customers are always worse off under a flat entry fee in comparison with holding and service fees. As for holding vs. service fees, the answer depends on the queueing regime and/or the service length itself. For example, under FCFS, service fees are preferred by all. Details are given on some common service regimes. We also review the case where customers know only the common distribution of service times, but not their actual requirements.     

Reducing congestion in bulk-service finite-buffer queueing system using batch-size-dependent service

In the design and analysis of any queueing system, one of the main objectives is to reduce congestion which can be achieved by controlling either arrival-rates or service-rates. This paper adopts the latter approach and analyzes a single-server finite-buffer queue where customers arrive according to the Poisson process and are served in batches of minimum size a with a maximum threshold limit b. The service times of the batches are arbitrarily distributed and depends on the size of the batches undergoing service. We obtain the joint distribution of the number of customers in the queue and the number with the server, and distributions of the number of customers in the queue, in the system, and the number with the server. Various performance measures such as the average number of customers in the queue (system) and with the server etc. are obtained. Several numerical results are presented in the form of tables and graphs and it is observed that batch-size-dependent service rule is more effective in reducing the congestion as compared to the one when service rates of the batches remain same irrespective of the size of the batch. This model has potential application in manufacturing, computer-communication network, telecommunication systems and group testing.     

Proportional loss rate differentiation in a FIFO queue

The relative differentiated service model is one of several models proposed for service differentiation in networks [IEEE Network Sept/Oct (1999) 26]. In this model, an assurance is given that ‘higher classes will be better, or at least no worse than lower classes.’ This paper describes a relative loss rate differentiation scheme based on RED. The scheme is used for differentially dropping packets in a FIFO queue during times of congestion. The main idea is, if packet losses are unavoidable in the FIFO queuing system, then they should be distributed among the different service classes in the queue in inverse proportion to the service price or weight assigned to each class. The simulation studies using TCP traffic show that the scheme is very effective in ensuring relative loss rate differentiation between service classes.     

中心队列二次门限服务的轮询系统分析

采用嵌入Markov链和概率母函数的方法对门限服务优先级排队系统进行分析,提出普通队列和高优先级队列分别采用基本门限和二级门限的服务机制,得出了平均排队队长和平均查询周期的解析式。     

Activity routing in a distributed supply chain: Performance evaluation with two inputs

In this paper, an industrial system is represented as a 2-input, three-stage queuing network. The two input queuing network receives orders from clients, and the orders are waiting to be served. Each order comprises (i) time of occurrence of the orders and (ii) quantity of items to be delivered in each order. The objective of this paper is to compute the minimum response time for the delivery of items to the final destination along the three stages of the network. The average number of items that can be delivered with this minimum response time constitute the optimum capacity of the queuing network. After getting serviced by the last node (a queue and its server) in each stage of the queuing network, a decision is made to route the items to the appropriate node in the next stage which can produce the least response time. Performance measures such as average queue lengths, average response times, and average waiting times of the jobs in the 2-input network are derived and plotted. Closed-form expressions for the equivalent service rate, equivalent average queue lengths, and equivalent response and waiting times of a single queue with a single server representing the 2-input queuing network are also derived and plotted.     

Queueing systems with random service rate

We consider a queue with the arrival process, the service time process and the service rate process as regenerative processes. We provide conditions for its stability, rates of convergence, finiteness of moments and functional limit theorems. This queue can model a queue serving ABR and UBR traffic in an ATM switch; a multiple access channel with TDMA or CDMA protocol and fading; a queue holding best effort or controlled and guaranteed traffic in a router in the integrated service architecture (ISA) of IP-based Internet and a scheduler in the router of a differentiated service architecture. In the process we also provide results for a queue with a leaky bucket controlled bandwidth scheduler. This result is of independent interest. We extend these results to feed-forward networks of queues. We also obtain the results when the arrival rate to the queue can be feedback controlled based on the congestion information in the queue (as in ABR service in the ATM networks or in the real time applications controlled by RTCP protocol in the Internet).     

认知网络中基于服务信息的队列管理算法

通过感知网络外部环境,认知网络能够自主地调节并分配网络资源,从而保证网络服务的正常运行。当发生网络拥塞时,当前普遍应用的主动队列管理算法只能从数据层面对数据包进行丢弃,不具备服务QoS对底层队列的调控。本文针对以上问题,提出了一种综合服务等级以及服务传输特点的队列管理算法,引入了服务对数据队列的参与调节模型,保证了在网络拥塞环境下特定服务的服务质量。使用Matlab对算法进行仿真,表明该算法在发生网络拥塞时,能够依据服务等级和服务传输特点对数据队列进行调节,从数据层面体现了服务层面的优先策略,从而保证了高级别服务的服务质量。     

中心站点和普通站点完全服务排队系统分析

通过对具有最高优先级的排队轮询系统的分析,用物理方法及其机理原理,提出最高优先级及普通队列都采用完全服务的统一服务机制,得出系统平均排队长和平均查询周期的解析式。