Delay analysis of discrete-time priority queue with structured inputs

This paper investigates a discrete-time priority queue with multi-class customers. Applying a delay-cycle analysis, we explicitly derive the probability generating function of the waiting time for an individual class in a geometric batch input queue under preemptive-resume and head-of-the-line priority rules. The conservation law and waiting time characterization for a general class of discrete-time queues are also presented. The results in this paper cover several previous results as special cases.     

Delay analysis of multiclass queues with correlated train arrivals and a hybrid priority/FIFO scheduling discipline

We analyze the delay experienced in a discrete-time priority queue with a train-arrival process. An infinite user population is considered. Each user occasionally sends packets in the form of trains: a variable number of fixed-length packets is generated and these packets arrive to the queue at the rate of one packet per slot. This is an adequate arrival process model for network traffic. Previous studies assumed two traffic classes, with one class getting priority over the other. We extend these studies to cope with a general number M of traffic classes that can be partitioned in an arbitrary number N of priority classes (1 ≤ N ≤ M). The lengths of the trains are traffic-class-dependent and generally distributed. To cope with the resulting general model, an (M × )∞-sized Markovian state vector is introduced. By using probability generating functions, moments and tail probabilities of the steady-state packet delays of all traffic classes are calculated. Since this study can be useful in deciding how to partition traffic classes in priority classes, we demonstrate the impact of this partitioning for some specific cases.     

Delay and partial system contents for a discrete-time G-D-c queue

We consider a discrete-time multiserver queueing system with infinite buffer size, constant service times of multiple slots and a first-come-first-served queueing discipline. A relationship between the probability distributions of the partial system contents and the packet delay is established. The relationship is general in the sense that it doesn’t require knowledge of the exact nature of the arrival process. By means of the relationship, results for the distribution of the partial system contents for a wide variety of discrete-time queueing models can be transformed into corresponding results for the delay distribution. As a result, a separate full analysis of the packet delay becomes unnecessary.      

Analysis of a discrete-time preemptive resume priority buffer

In this paper, we analyze a discrete-time preemptive resume priority queue. We consider two classes of customers which have to be served, where customers of one class have preemptive resume priority over customers of the other. Both classes contain customers with generally distributed service times. We show that the use of probability generating functions is beneficial for analyzing the system contents and customer delays of both classes. It is shown (theoretically as well as by some practical procedures) how moments and approximate tail probabilities of system contents and customer delays are calculated. The influence of the priority scheduling discipline and the service time distributions on the performance measures is shown by some numerical examples.     

A preemptive discrete-time priority buffer system with partial buffer sharing

This paper considers a Geo/Geo/1 discrete-time queue with preemptive priority. Both the arrival and service processes are Bernoulli processes. There are two kinds of customers: low-priority and high-priority customers. The high-priority customers have a preemptive priority over low-priority customers. If the total number of customers is equal or more than the threshold (k), the arrival of low-priority customers will be ignored. Hence the system buffer size is finite only for the low-priority customers. A recursive numerical procedure is developed to find the steady-state probabilities. With the aid of recursive equations, we transform the infinite steady-state departure-epoch equations set to a set of (k + 1) × (k + 2)/2 linear equations set based on the embedded Markov Chain technique. Then, this reduced linear equations set is used to compute the steady-state departure-epoch probabilities. The important performance measures of the system are calculated. Finally, the applicability of the solution procedure is shown by a numerical example and the sensitivity of the performance measures to the changes in system parameters is analyzed.     

Two competing discrete-time queues with priority

This paper considers a class of two discrete-time queues with infinite buffers that compete for a single server. Tasks requiring a deterministic amount of service time, arrive randomly to the queues and have to be served by the server. One of the queues has priority over the other in the sense that it always attempts to get the server, while the other queue attempts only randomly according to a rule that depends on how long the task at the head of the queue has been waiting in that position. The class considered is characterized by the fact that if both queues compete and attempt to get the server simultaneously, then they both fail and the server remains idle for a deterministic amount of time. For this class we derive the steady-state joint generating function of the state probabilities. The queueing system considered exhibits interesting behavior, as we demonstrate by an example.     

Exact tail asymptotics for a discrete-time preemptive priority queue

In this paper, we consider a discrete-time preemptive priority queue with different service completion probabilities for two classes of customers, one with high-priority and the other with low-priority. This model corresponds to the classical preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server. Due to the possibility of customers’ arriving and departing at the same time in a discrete-time queue, the model considered in this paper is more complicated than the continuoustime model. In this model, we focus on the characterization of the exact tail asymptotics for the joint stationary distribution of the queue length of the two types of customers, for the two boundary distributions and for the two marginal distributions, respectively. By using generating functions and the kernel method, we get the exact tail asymptotic properties along the direction of the low-priority queue, as well as along the direction of the high-priority queue.     

The discrete-time preemptive repeat identical priority queue

Priority queueing systems come natural when customers with diversified delay requirements have to wait to get service. The customers that cannot tolerate but small delays get service priority over customers which are less delay-sensitive. In this contribution, we analyze a discrete-time two-class preemptive repeat identical priority queue with infinite buffer space and generally distributed service times. Newly arriving high-priority customers interrupt the on-going service of a low-priority customer. After all high-priority customers have left the system, the interrupted service of the low-priority customer has to be repeated completely. By means of a probability generating functions approach, we analyze the system content and the delay of both types of customers. Performance measures (such as means and variances) are calculated and the impact of the priority scheduling is discussed by means of some numerical examples.     

Analysis of discrete-time queueing systems with priority jumps

This text is a summary of the author’s PhD thesis supervised by Herwig Bruneel and Joris Walraevens, and defended on 5 March 2009 at Ghent University. The thesis is written in English and is available from the author upon request. The work deals with several priority scheduling disciplines with so-called priority jumps. An efficient priority scheduling discipline is of great importance in modern telecommunication devices. Static priority scheduling achieves maximum service differentiation between different types of traffic, but may have a too severe impact on the performance of lower-priority traffic. Introducing priority jumps aims for a more gradual service differentiation. In the thesis, we propose several (types of) jumping mechanisms, and we analyse their effect on the performance of a discrete-time queueing system.     

Reliability analysis of a warm standby repairable system with priority in use

In this paper, a warm standby repairable system consisting of two dissimilar units and one repairman is studied. In this system, it is assumed that the working time distributions and the repair time distributions of the two units are both exponential, and unit 1 is given priority in use. After repair, both unit 1 and unit 2 are “as good as new”. Moreover, the transfer switch in the system is unreliable, and the function of the switch is: “as long as the switch fails, the whole system fails immediately”. Under these assumptions, using Markov process theory and the Laplace transform, some important reliability indexes and some steady state system indexes are derived. Finally, a numerical example is given to illustrate the theoretical results of the model.     

A discrete-time priority queue with two-class customers and bulk services

This paper studies the behavior of a discrete queueing system which accepts synchronized arrivals and provides synchronized services. The number of arrivals occurring at an arriving point may follow any arbitrary discrete distribution possessing finite first moment and convergent probability generating function in ¦ z ¦ 1 + with > 0. The system is equipped with an infinite buffer and one or more servers operating in synchronous mode. Service discipline may or may not be prioritized. Results such as the probability generating function of queue occupancy, average queue length, system throughput, and delay are derived in this paper. The validity of the results is also verified by computer simulations.The work reported in this paper was supported by the National Science Council of the Republic of China under Grant NSC1981-0404-E002-04.     

Delay performance in stochastic processing networks with priority service

We evaluate the delay performance of an open multi-class stochastic processing network of multi-server resources with preemptive-resume priority service. We show that the stationary distribution of aggregate queue lengths has product form. For each service class we derive explicit expressions for the following stationary performance measures: The mean and, under feedforward routing, the Laplace transform of the delay distribution at each resource. We show that these measures are the same as if the resources were operating in isolation.     

Complex dynamic behaviors of a discrete-time predator-prey system

The dynamics of a discrete-time predator-prey system is investigated in detail in this paper. It is shown that the system undergoes flip bifurcation and Hopf bifurcation by using center manifold theorem and bifurcation theory. Furthermore, Marotto''s chaos is proved when some certain conditions are satisfied. Numerical simulations are presented not only to illustrate our results with the theoretical analysis, but also to exhibit the complex dynamical behaviors, such as the period-6, 7, 8, 10, 14, 18, 24, 36, 50 orbits, attracting invariant cycles, quasi-periodic orbits, nice chaotic behaviors which appear and disappear suddenly, coexisting chaotic attractors, etc. These results reveal far richer dynamics of the discrete-time predator-prey system. Specifically, we have stabilized the chaotic orbits at an unstable fixed point using the feedback control method.     

A sufficient condition and a necessary condition for the diffusion approximations of multiclass queueing networks under priority service disciplines

We establish a sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. The sufficient condition relates to a sufficient condition for the weak stability of the fluid networks that correspond to the queueing networks under consideration. In addition, we establish a necessary condition for the network to have a continuous diffusion limit; the necessary condition is to require a reflection matrix (of dimension equal to the number of stations) to be completely-S. When applied to some examples, including generalized Jackson networks, single station multiclass queues, first-buffer-first-served re-entrant lines, a two-station Dai–Wang network and a three-station Dumas network, the sufficient condition coincides with the necessary condition.     

A critically loaded multiclass Erlang loss system

We consider a generalization of the classical Erlang loss model to multiple classes of customers. Each of the J customer classes has an associated Poisson arrival process and an arbitrary holding time distribution. Classj customers requireM _j servers simultaneously. We determine the asymptotic form of the blocking probabilities for all customer classes in the regime known as critical loading, where both the number of servers and offered load are large and almost equal. Asymptotically, the blocking probability of classj customers is proportional toM _j . This asymptotic result provides an approximation for the blocking probabilities which is reasonably accurate. We also consider the behavior of the Erlang fixed point (reduced load approximation) for this model under critical loading. Although the blocking probability of classj customers given by the Erlang fixed point is again asymptotically proportional toM _j , the Erlang fixed point typically gives the wrong limit. Next we show that under critical loading the throughputs have a pleasingly simple form of monotonicity with respect to arrival rates: the throughput of classi is increasing in the arrival rate of classi and decreasing in the arrival rate of classj forji. Finally, we compare two simple control policies for this system under critical loading.     

Analysis of a discrete-time queueing system with time-limited service

We analyze a discrete-time, single-server queueing system in which the length of each service period is limited. The server takes a vacation when the limit expires or the queue empties, whichever occurs first. In the former case, the preempted service is resumed after the vacation without loss or creation of any work. This system models the transmission of message frames from a station on timed-token local-area networks (for example, FDDI and IEEE 802.4 token bus). We study the process of the unfinished work and the joint process of the queue size and the remaining service time. By using the technique of discrete Fourier transforms to determine some unknown functions in the governing equations, we numerically obtain exact mean waiting times.A part of the work of H. Takagi was done while he was with IBM Research, Tokyo Research Laboratory.     

Bifurcation analysis on a discrete-time tabu learning model

In this paper, we consider a discrete-time tabu learning single neuron model. After investigating the stability of the given system, we demonstrate that Pichfork bifurcation, Flip bifurcation and Neimark–Sacker bifurcation will occur when the bifurcation parameter exceed a critical value, respectively. A formula is given for determining the direction and stability of Neimark–Sacker bifurcation by applying the normal form theory and the center manifold theorem. Some numerical simulations for justifying the theoretical results are also provided.