Performance analysis of a GI-Geo-1 buffer with a preemptive resume priority scheduling discipline

In this paper, we analyze a discrete-time GI-Geo-1 preemptive resume priority queue. We consider two classes of packets which have to be served, where one class has preemptive resume priority over the other. We show that the use of generating functions is beneficial for analyzing the system contents and packet delay of both classes. Moments and (approximate) tail probabilities of system contents and packet delay are calculated. The influence of the priority scheduling is shown by some numerical examples.     

A Priority Discrete Queueing Model for Multimedia Multiplexers

Multiplexers have been extensively modeled as discrete time queueing systems. In this article, we model a multimedia multiplexer handling traffic of two classes. One class represents real-time traffic, e.g., packets of live audio or video transmissions, and the other nonreal-time traffic, e.g., packets of file transfer transmissions. These packets arrive into the multiplexer in batches. In each time slot, one batch of each class arrive. The multiplexer gives service priority to class-1 packets over class-2. The demands of each class are in conflict with that of the other, and thus they are treated by the multiplexer differently. The multiplexer is thus modeled as a (preemptive) priority discrete queueing system with simultaneous batch arrivals and geometric service time. The system occupancy is analyzed and the joint probability generating function (PGF) of the number of packets of each class is derived. From this PGF, marginal PGFs of interest are obtained. The results for deterministic service time, most suitable for ATM purposes, are readily obtainable as a special case from the results of this article.     

Discrete-Time Geo X /G/1 Queue with Preemptive Repeat Different Priority

This paper considers a discrete-time Geo ^X /G/1 queue accepting two classes of messages with preemptive repeat different priority. Service times of messages of each priority class are i.i.d. according to a general discrete distribution function that may differ between two classes. The completion time and the stability condition for our system are investigated. By using the supplementary variable method and the generating function technique, we derive the joint system contents distributions at various observation instants and also compute the probability distribution for the unfinished work.     

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.     

Mixing of non-preemptive and preemptive repeat priority disciplines

A single server dispenses service to m priority classes. The arrival process of the ith class, i = 1, 2,…,m, is homogeneous Poisson. Service times of each class are independent, identical, arbitrarily-distributed random variables with a finite second moment. The smaller the index of a class, the higher its priority degree. For i < j, class i has preemptive priority over j if and only if j ? i > d (where d is a predetermined non-negative integer), and non-preemptive priority otherwise. An interrupted service is resumed when the system contains no costomers with higher priority, preemptive and non-preemptive. Within each priority class the FIFO rule is obeyed.The preemptive regimes analyzed are repeat with and without resampling. For a k-customer, k = 1, 2,…,n, steady-state Laplace-Stieltjes transforms, and expectations of the waiting time and the time in the system are calculated.     

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.     

Interdeparture time distributions in ΣiMi/Gi/1 priority queues

This paper reviews existing results for the stationary interdeparture time distribution in the M/G/1 nonpreemptive and preemptive resume queues, and introduces a unified approach which exploits for the first time the common structure for the interdeparture time process that is present in all classical preemptive priority service disciplines. This approach confirms previously known results for the preemptive resume discipline, and presents new results for several variants of the preemptive repeat model. Exact expressions for the squared coefficient of variation of the interdeparture time distribution are also provided. Several numerical examples are given and discussed. This revised version was published online in June 2006 with corrections to the Cover Date.     

An M/G/1 queueing system with multiple priority classes

We consider anM/G/1 queueing system with multiple priority classes of jobs. Considered preemptive rules are the preemptiveresume, preemptive-repeat-identical, and preemptive-repeat-different policies. These three preemptive rules will be analyzed in parallel. The key idea of analysis is based on the consideration of a busy period as a composite of delay cycle. As results, we present the exact Laplace-Stieltjes (L.S.) transforms of residence time and completion time in the system.     

Threshold-based interventions to optimize performance in preemptive priority queues

This paper studies a single-server priority queueing model in which preemptions are allowed during the early stages of service. Once enough service effort has been rendered, however, further preemptions are blocked. The threshold where the change occurs is either a proportion of the service requirement, or time-based. The Laplace–Stieltjes transform and mean of each class sojourn time are derived for a model which employs this hybrid preemption policy. Both preemptive resume and preemptive repeat service disciplines are considered. Numerical examples show that it is frequently the case that a good combination of preemptible and nonpreemptible service performs better than both the standard preemptive and nonpreemptive queues. In a number of these cases, the thresholds that optimize performance measures such as overall average sojourn time are determined. This revised version was published online in June 2006 with corrections to the Cover Date.     

Waiting Time Distributions in the Preemptive Accumulating Priority Queue

We consider a queueing system in which a single server attends to N priority classes of customers. Upon arrival to the system, a customer begins to accumulate priority linearly at a rate which is distinct to the class to which it belongs. Customers with greater accumulated priority levels are given preferential treatment in the sense that at every service selection instant, the customer with the greatest accumulated priority level is selected next for servicing. Furthermore, the system is preemptive so that the servicing of a customer is interrupted for customers with greater accumulated priority levels. The main objective of the paper is to characterize the waiting time distributions of each class. Numerical examples are also provided which exemplify the true benefit of incorporating an accumulating prioritization structure, namely the ability to control waiting times.     

Exact tail asymptotics in a priority queue—characterizations of the non-preemptive model

This is a companion paper to Li and Zhao (Queueing Syst. 63:355–381, 2009) recently published in Queueing Systems, in which the classical preemptive priority queueing system was considered. In the current paper we consider the classical non-preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server serving the two classes of customers at possibly different rates. A complete characterization of the regions of system parameters for exact tail asymptotics is obtained through an analysis of generating functions. This is done for the joint stationary distribution of the queue length of the two classes of customers, for the two marginal distributions and also for the distribution of the total number of customers in the system, respectively. This complete characterization is supplemental to the existing literature, which would be useful to researchers.     

Performance analysis and optimization of cognitive radio networks with retransmission control

In usual cognitive radio networks with buffer settings, secondary user packets that are interrupted by primary user packets will return to the SU buffer for later retransmission. But this may increase the average delay of the SU packets. In this paper, we propose a novel spectrum sharing strategy (SSS) to dynamically control the retransmission of the SU packets by introducing a returning threshold and a returning probability. This will simultaneously guarantee the Quality of Service for the SUs. In this SSS, when the transmission of an SU packet is interrupted, if the number of SU packets already in SU buffer reaches a returning threshold that is set in advance as a system parameter, an interrupted SU packet is admitted to return to the SU buffer with a dynamic returning probability. This returning probability is inversely proportional to the total number of packets in the system. Based on the SSS with retransmission control proposed in this paper, we build a discrete-time preemptive priority queueing model to comply with digital nature of modern networks. Accordingly, by presenting and analyzing a two-dimensional discrete-time Markov chain that represents the system state transition, we obtain the steady-state distribution of the system and then provide the formulas for several system performance measures. Moreover, with numerical results, we show the influence of the returning threshold on different performance measures. Finally, by building a net benefit function, we optimize the system performance for the returning threshold to balance different system performance measures.     

对一类等待空间有限的抢占优先权排队的分析

讨论M/M/1抢占优先权排队模型, 且假设低优先权顾客的等待空间有限. 该模型可以用有限位相拟生灭过程来描述. 由矩阵解析方法, 对该拟生灭过程进行了分析, 并得到排队模型平稳队长的计算公式, 最后还用数值 结果说明了方法的有效性.     

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 preemptive loss priority queues with preemption distance

In a queueing system with preemptive loss priority discipline, customers disappear from the system immediately when their service is preempted by the arrival of another customer with higher priority. Such a system can model a case in which old requests of low priority are not worthy of deferred service. This paper is concerned with preemptive loss priority queues in which customers of each priority class arrive in a Poisson process and have general service time distribution. The strict preemption in the existing model is extended by allowing the preemption distance parameterd such that arriving customers of only class 1 throughp — d can preempt the service of a customer of classp. We obtain closed-form expressions for the mean waiting time, sojourn time, and queue size from their distributions for each class, together with numerical examples. We also consider similar systems with server vacations.     

Packet scheduling in third-generation mobile systems with UTRA-TDD air interface

UTRA-TDD is one of the adopted air interfaces for third-generation mobile communication systems (UMTS). In UTRA-TDD, information packets are transmitted organized into radio frames. A radio frame is divided into a fixed number of time slots and different packets can be sent on the same time slot by means of the Code Division Multiple Access technique. Packets belong to different traffic classes and have different formats and Quality of Service (QoS) requirements in terms of delay, transmission error probability and priority level. In this paper, we address the problem of scheduling packets for downlink transmissions in the time slots of a frame, in such a way that QoS requirements are fulfilled. In particular, exact pseudo-polynomial and heuristic scheduling algorithms are compared in terms of typical performance parameters. Computational results for three traffic classes show that the proposed algorithms are suitable for UTRA-TDD implementation, both for solution quality and computational time. Work carried out under the financial support of MIUR.     

抢占型优先服务机制下多类排队网络的扩散逼近

证明一个满负荷交通极限定理以证实在抢占型优先服务机制下多类排队网络的扩散逼近,进而为该系统提供有效的随机动力学模型．所研究的排队网络典型地出现在现代通讯系统中高速集成服务分组数据网络,其中包含分组数据包的若干交通类型,每个类型涉及若干工作处理类（步骤）,并且属于同一交通类型的工作在可能接受服务的每一个网站被赋予相同的优先权等级,更进一步地,在整个网络中,属于不同交通类型的分组数据包之间无交互路由．     

Exact tail asymptotics in a priority queue—characterizations of the preemptive model

In this paper, we consider the classical preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server serving the two classes of customers at possibly different rates. For this system, we carry out a detailed analysis on exact tail asymptotics for the joint stationary distribution of the queue length of the two classes of customers, for the two marginal distributions and for the distribution of the total number of customers in the system, respectively. A complete characterization of the regions of system parameters for exact tail asymptotics is obtained through analysis of generating functions. This characterization has never before been completed. It is interesting to note that the exact tail asymptotics along the high-priority queue direction is of a new form that does not fall within the three types of exact tail asymptotics characterized by various methods for this type of two-dimensional system reported in the literature. We expect that the method employed in this paper can also be applied to the exact tail asymptotic analysis for the non-preemptive priority queueing model, among other possibilities.     

An Invariance in the Priority Queue with Generalized Server Vacations and Structured Batch Arrivals

Abstract

Shanthikumar (Shanthikumar, J.G. Level crossing analysis of priority queues and a conservation identity for vacation models. Nav. Res. Log. 1989, 36, 797–806) studied the priority M/G/1 queue with server vacations and found that the difference between the waiting time distribution under the non‐preemptive priority (NPP) and that under the preemptive‐resume priority (PRP) is independent of the vacation policy. We extend this interesting property: (i) to the generalized vacations which includes the two vacation policies considered by Shanthikumar; (ii) to the structured batch Poisson arrival process; and (iii) to the discrete‐time queues.     

On the transformation of lexicographic nonlinear multiobjective programs to single objective programs

This paper deals with multiobjective optimization programs in which the objective functions are ordered by their degree of priority. A number of approaches have been proposed (and several implemented) for the solution of lexicographic (preemptive priority) multiobjective optimization programs. These approaches may be divided into two classes. The first encompasses the development of algorithms specifically designed to deal directly with the initial model. Considered only for linear multiobjective programs and multiobjective programs with a finite discrete feasible region, the second one attempts to transform, efficiently, the lexicographic multiobjective model into an equvivalent model, i.e. a single objective programming problem. In this paper, we deal with the second approach for lexicographic nonlinear multiobjective programs.