Predicting departure times in multi-stage queueing systems

We develop an approximation model for the state-dependent sojourn time distribution of customers or orders in a multi-stage, multi-server queueing system, when interarrival and service times can take on general distributions. The model can be used to make probabilistic statements about the departure time of a customer or order, given the number and location of customers currently in process or waiting, and these probabilities can be recomputed while waiting at any point during the sojourn time. The model uses phase-type distributions and a new method to estimate the remaining processing times of customers in service when the sojourn time distribution is computed.     

Analysis of a finite-buffer bulk-service queue under Markovian arrival process with batch-size-dependent service

We consider a finite capacity single server queue in which the customers arrive according to a Markovian arrival process. The customers are served in batches following a ‘general bulk service rule’. The service times, which depend on the size of the batch, are generally distributed. We obtain, in steady-state, the joint distribution of the random variables of interest at various epochs. Efficient computational procedures in the case of phase type services are presented. An illustrative numerical example to bring out the qualitative nature of the model is presented.     

Impact of class clustering in a multiclass FCFS queue with order-dependent service times

In multi-class queueing systems, customers of different classes can enter the system. When studying such systems, it is traditionally assumed that the different classes of customers occur randomly and independently in the arrival stream of customers in the system. This is often in contrast to the actual situation. Therefore, we study a multi-class system with so-called class clustering in the customer arrival stream, i.e., (Markovian) correlation occurs in the classes of consecutive customers. The system under investigation consists of one server that is able to serve two classes of customers. In addition, the service-time distribution of a customer depends on the equality or non-equality of its class with the class of the previous customer. This latter feature occurs frequently in practice. For instance, execution of the same task again can lead to both faster or slower processing times. The first case can occur when the execution of a different task entails resetting a machine, or loading new data, et cetera. The opposite situation appears, for instance, when execution of the same task requires postprocessing (such as cooling down or reinitialization of a machine). We deduce the probability generating function (pgf) of the system content, from which we can extract various performance measures, among which the mean values of the system content and the customer delay. We demonstrate that class clustering has a tremendous impact on the system performance, which highlights the necessity to include it in the performance assessment of any system in which it occurs.     

An asymptotic study of a stationary queue for generalized arrival times

Cybernetics and Systems Analysis -     

Computing steady state probabilities in λ(n)/G/1/K queue

In this paper a recursive method is developed to obtain the steady state probability distribution of the number in system at arbitrary and departure time epochs of a single server state-dependent arrival rate queue λ(n)/G/1/K in which the arrival process is Markovian with arrival rates λ(n) which depend on the number of customers n in the system and general service time distribution. It is assumed that there exists an integer K such that λ(n) > 0 for all 0 n < K and λ(n) = 0 for all n K. Numerical results have been presented for many queueing models by suitably defining the function λ(n). These include machine interference model, queues with balking, queues with finite waiting space and machine interference model with finite waiting space. These models have wide application in computer/communication networks.     

Loss behavior in space priority queue with batch Markovian arrival process — discrete-time case

This paper applies matrix-analytic approach to the examination of the loss behavior of a space priority queue. In addition to the evaluation of the long-term high-priority and low-priority packet loss probabilities, we examine the bursty nature of packet losses by means of conditional statistics with respect to critical and non-critical periods that occur in an alternating manner. The critical period corresponds to having more than a certain number of packets in the buffer; non-critical corresponds to the opposite. Hence there is a threshold buffer level that splits the state space into two. By such a state-space decomposition, two hypothesized Markov chains are devised to describe the alternating renewal process. The distributions of various absorbing times in the two hypothesized Markov chains are derived to compute the average durations of the two periods and the conditional high-priority packet loss probability encountered during a critical period. These performance measures greatly assist the space priority mechanism for determining a proper threshold. The overall complexity of computing these performance measures is of the order O(K²m₁³m₂³), where K is the buffer capacity, and m₁ and m₂ are the numbers of phases of the underlying Markovian structures for the high-priority and low-priority packet arrival processes, respectively. Thus the results obtained are computationally tractable and numerical results show that, by choosing a proper threshold, a space priority queue not only can maintain the quality of service for the high-priority traffic but also can provide the near-optimum utilization of the capacity for the low-priority traffic.     

Analysis of finite-buffer discrete-time batch-service queue with batch-size-dependent service

Over the last two decades there has been considerable growth in digital communication systems which operate on a slotted system. In several applications, transmission of packets over the network takes place in batches of varying size, and transmission time depends upon the size of the batch. Performance modelling of these systems is usually done using discrete-time queues. In view of this, we consider a single-server queue with finite-buffer in a discrete-time domain where the packets are transmitted in batches (of varying size) according to minimum and maximum threshold limit, usually known as general batch service rule. The transmission time (in number of slots) of these batches depends on the number of packets within the batch under transmission, and is arbitrarily distributed. We obtain, in steady-state, distribution of the number of packets waiting in the queue and in service (those being transmitted in batches). In addition, we also obtain average number of packets waiting in queue, in the system, with the server, rejection probabilities, etc. Finally, computational experiences with a variety of numerical results have been discussed by introducing a cost model which gives optimum value of the lower threshold limit.     

A batch arrival queue with a vacation time under single vacation policy

We consider an M^x/G/1 queueing system with a vacation time under single vacation policy, where the server takes exactly one vacation between two successive busy periods. We derive the steady state queue size distribution at different points in times, as well as the steady state distributions of busy period and unfinished work (backlog) of this model.Scope and purposeThis paper addresses issues of model building of manufacturing systems of job-shop type, where the server takes exactly one vacation after the end of each busy period. This vacation can be utilized as a post processing time after clearing the jobs in the system. To be more realistic, we further assume that the arrivals occur in batches of random size instead of single units and it covers many practical situations. For example in manufacturing systems of job-shop type, each job requires to manufacture more than one unit; in digital communication systems, messages which are transmitted could consist of a random number of packets. These manufacturing systems can be modeled by M^x/G/1 queue with a single vacation policy and this extends the results of Levy and Yechiali, Manage Sci 22 (1975) 202, and Doshi, Queueing Syst 1 (1986) 29.     

Reduction of queue oscillation in the next generation Internet routers

The Internet routers employing the random early detection (RED) algorithm for congestion control suffer from the problem of chaotic queue oscillation. It is well known that the slowly varying nature of the average queue size computed using an exponentially weighted moving average (EWMA) used in the RED scheme causes this chaotic behavior. This paper presents a new mathematical function to model the weighting parameter used in the EWMA. The proposed weighting function incorporates the knowledge of the dynamic changes in the congestion characteristics, traffic characteristics and queue normalization. Using this pragmatic information eliminates the slowly varying nature of the average queue size. It is evident from our simulations that the proposed approach not only reduces the chaotic queue oscillation significantly but also provides predictable low delay and low delay jitter with high throughput gain and reduced packet loss rate even under heavy load of traffic conditions.     

控制时延的主动队列管理算法

针对现有的主动队列管理(AQM)算法造成的队列时延无法满足VoIP、音视频等流媒体传输需求的问题,提出一种直接控制队列时延的主动队列管理算法--DCQA。该算法使用PID控制器计算路由器缓存的数据包丢弃概率,用其对即将进入缓存排队的数据包做丢包判断并采取相应动作,以控制队列时延在期望值以下。实验仿真了3种网络环境下DCQA的性能,链路利用率分别是99.93%、99.88%和99.95%。并且,队列时延分别有50.45%、51.59%、52.4%被控制在期望值以下,比CoDel算法分别提高了3.6%、40.53%、50.69%。实验结果表明,DCQA在不同的网络环境中都可以获得较高的链路利用率,而且控制队列时延的能力优于CoDel算法,适用于流媒体的传输。     

Analysis of a finite-capacity M/G/1 queue with a resume level

In order to model the buffer pool behavior in a data communication component, an M/G/1/K queue where input is shut down when the queue size (number of messages) attains K until it decreases to a specified level is analyzed. By use of semi-Markov process approach, the queue length distribution at an arbitrary time is found, and the resultant performance measures (utilization, loss probability, and mean response time) are computed.     

The departure process of an N/G/1 queue

The departure process of an N/G/1 queue is investigated. The arrival process called an N process is a versatile point process and includes, for example, a Markov-modulated Poisson process, which is comprised of models of packetized voice and video traffic arrival processes. The first passage analysis yields LSTs of distributions of the interdeparture times. Emphasis is on the interdeparture times of an N/D/1 queue. Numerical examples show that correlation of interarrival times is likely to be preserved in interdeparture times, and that the departure of a voice packet multiplexer can be expected to be smoothed for a normal load. The result in this paper enables evaluation of the smoothing effect of burst traffic through nodes in Asynchronous Transfer Mode networks.     

基于QoS的路由器队列管理

新一代互联网必然要满足服务质量(QoS)的要求，本文讨论了新一代互联网路由器输入端缓冲区队列管理和内存管理的一个方案，提出了二级队列的基本结构拥塞控制与门限值的设定方法，使所提方案能够支持多级QoS和动态内存分配。     

循环队列存储空间的动态回收方法

循环队列充分利用向量空间而提出并广泛使用。在数据结构与算法和任何其它文献中没有研究过循环队列中闲置存储空间的回收问题。本文研究并实现了循环队列中闲置存储空间的动态回收,成功避免了循环队列中存储空间的浪费。     

Equations for the angles of arrival and departure for multivariable root loci using frequency-domain methods

Frequency-domain methods are used to study the angles of arrival and departure for multivariable root loci. Explicit equations are obtained. For a special class of poles and zeros, some simpler equations that are generalizations of the single-input-single-output equations are presented.     

Accuracy of approximating queueing network departure processes with independent renewal processes

A distributed and fully symmetric solution is presented for the distributed termination problem. In contrast to the existing solutions, the above solution does not require a predesignated process to detect termination. The case of asynchronous communications is also discussed.     

Decomposing the queue length distribution of processor-sharing models into queue lengths of permanent customer queues

We obtain a decomposition result for the steady state queue length distribution in egalitarian processor-sharing (PS) models. In particular, for multi-class egalitarian PS queues, we show that the marginal queue length distribution for each class equals the queue length distribution of an equivalent single class PS model with a random number of permanent customers. Similarly, the mean sojourn time (conditioned on the initial service requirement) for each class can be obtained by conditioning on the number of permanent customers. The decomposition result implies linear relations between the marginal queue length probabilities, which also hold for other PS models such as the egalitarian PS models with state-dependent system capacity that only depends on the total number of customers in the system. Based on the exact decomposition result for egalitarian PS queues, we propose a similar decomposition for discriminatory processor-sharing (DPS) models, and numerically show that the approximation is accurate for moderate differences in service weights.     

Seismic inverse problems: determining seismic wave speeds using arrival times

The speeds of propagation of seismic waves are computed by detecting the effect of the waves that propagate when a pulse of energy, in the form of a small explosion, is released near the surface of the ground. The pulse is detected and recorded by underground sensors. The times between the initiation of the pulse and the point when it reaches the various sensors are denoted the travel times. In this paper we consider two questions. Is it possible to compute the wave speed profile from accurately measured travel times? If so, how can this be done?     

A non-equilibrium analysis and control framework for active queue management

We present a non-equilibrium analysis and control approach for the Active Queue Management (AQM) problem in communication networks. Using simplified fluid models, we carry out a bifurcation study of the complex dynamic queue behavior to show that non-equilibrium methods are essential for analysis and optimization in the AQM problem. We investigate an ergodic theoretic framework for stochastic modeling of the non-equilibrium behavior in deterministic models and use it to identify parameters of a fluid model from packet level simulations. For computational tractability, we use set-oriented numerical methods to construct finite-dimensional Markov models, including control Markov chains and hidden Markov models. Subsequently, we develop and analyze an example AQM algorithm using a Markov Decision Process (MDP) based control framework. The control scheme developed is optimal with respect to a reward function, defined over the queue size and aggregate flow rate. We implement and simulate our illustrative AQM algorithm in the ns-2 network simulator. The results obtained confirm the theoretical analysis and exhibit promising performance when compared with well-known alternative schemes under persistent non-equilibrium queue behavior.