Analysis of a finite capacity non preemptive priority queue

In this paper a finite capacity priority queue with multiple servers and non preemptive service discipline is analysed. The arrival and service processes were assumed Markovian and only two priority classes were considered. An analytical solution for blocking probabilities for the customers in the two classes is obtained under the assumption that a high priority customer upon arrival can displace a low priority customer from the waiting line if the queue is full.     

非强占有限优先权M/G/1排队系统

针对部分数据帧有完全优先权发送的计算机网络数据服务系统存在的网络拥塞风险问题,提出了一种非强占有限优先权M/G/1排队系统模型的方法。该系统模型引入控制完全优先权的参数n,使得数据帧的完全优先权变成有限优先权,考虑了不同优先级队伍之间的公平性,降低了计算机网络数据服务系统拥塞的风险,使得网络系统在有限优先权下有较好的稳定性。在模型研究中,运用全概率拆解方法获得各级队伍平均等待时间、平均逗留时间和平均队长的理论结果。对模型采用Matlab 2010a软件实验仿真,实验得到的各级队伍平均等待时间和理论平均等待时间的平均绝对误差为0.951%。实验中,有限优先权条件下各级顾客的平均等待时间比值显著小于完全优先权条件下各级顾客的平均等待时间比值。实验结果表明对非强占有限优先权M/G/1排队系统模型研究的理论结果是正确的,该模型具有更稳定的系统特性。     

基于排队论的呼叫中心ACD技术研究

本文首先阐述了ACD的排队理论;其次对先到先服务、优先级服务的排队策略,基于负载均衡、座席技能级别、客户信息和经验的路由算法进行了详细地分析;最后提出可根据呼叫到达时间、主叫号码、DNIS、用户可接受的等待时间、客户等级多项参数进行线性加权确定优先级的排队算法策略,根据系统规模、服务效率、客户信息等来综合地确定路由分配方法,真正实现合理的排队和智能的路由分配。     

A queuing model for CPU functional unit and issue queue configuration

In a superscalar processor, instructions of various types flow through an execution pipeline, traversing hardware resources which are mostly shared among many different instruction types. A notable exception to shared pipeline resources is the collection of functional units, the hardware that performs specific computations. In a trade-off of cost versus performance, a pipeline designer must decide how many of each type of functional unit to place in a processor’s pipeline. In this paper, we model a superscalar processor’s issue queue and functional units as a novel queuing network. We treat the issue queue as a finite-sized waiting area and the functional units as servers. In addition to common queuing problems, customers of the network share the queue but wait for specific servers to become ready (e.g., addition instructions wait for adders). Furthermore, the customers in this queue are not necessary ready for service, since instructions may be waiting for operands. In this paper we model a novel queuing network that provides a solution to the expected queue length of each type of instruction. This network and its solution can also be generalized to other problems, notably other resource-allocation issues that arise in superscalar pipelines.     

Priority queuing in an operating system

The analysis of a preemptive priority queuing system with K(⩾2) classes of jobs is undertaken. The system consists of a single processor representing a model of discrete dynamic scheduling problems associated with M_k/G_k/1/∞ endogenous priority queues. The processor schedules jobs which arrive according to a Markov arrival process. The process of service is arbitrary. With each job are associated particular endogenous dynamic priorities, called scheduling by “mean bounded priorities with arrival pattern” (MBPAP). The main goal is, for the case of an arrival pattern of jobs, to present an original scheduling strategy, to derive the waiting time w_k(t) and to discuss the implementation of the priorities. This queuing system is investigated.     

Fuzzy-Based Dynamic Distributed Queue Scheduling for Packet Switched Networks

Addressing the problem of queue scheduling for the packet-switched system is a vital aspect of congestion control. In this paper, the fuzzy logic based decision method is adopted for queue scheduling in order to enforce some level of control for traffic of different quality of service requirements using predetermined values. The fuzzy scheduler proposed in this paper takes into account the dynamic nature of the Internet traffic with respect to its time-varying packet arrival process that affects the network states and performance. Three queues are defined, viz low, medium and high priority queues. The choice of prioritizing packets influences how queues are served. The fuzzy scheduler not only utilizes queue priority in the queue scheduling scheme, but also considers packet drop susceptibility and queue limit. Through simulation it is shown that the fuzzy scheduler is more appropriate for the dynamic nature of Internet traffic in a packet-switched system as compared with some existing queue scheduling methods. Results show that the scheduling strategy of the proposed fuzzy scheduler reduces packet drop, provides good link utilization and minimizes queue delay as compared with the priority queuing (PQ), first-in-first-out (FIFO), and weighted fair queuing (WFQ).     

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.     

A tandem queue with general bulk service and servers' “vacation”

This paper analyses two queueing models consisting of two units I and II connected in series, separated by a finite buffer of size N. In both models, unit I has only one exponential server capable of serving customers one at a time and unit II consist of c parallel exponential servers, each of them serving customers in groups according to general bulk service rules. When the queue length in front of unit II is less than the minimum of batch size, the free servers take a vacation. On return from vacation, if the queue length is less than the minimum, they leave for another vacation in the first model, whereas in the second model they wait in the system until they get the minimum number of customers and then start servicing. The steady-state probability vector of the number of customers waiting and receiving service in unit I and waiting in the buffer is obtained for both the models, using the modified matrix geometric method. Numerical results are also presented.     

Approximating performance measures for public services

This paper deals with estimating performance measures, such as average response time for spatially distributed networks. Demands are generated stochastically at the nodes and the service units are stationed at service centers when available. Whenever a call arrives, a service unit will travel to the call's location. When there are no available servers, the call will enter an infinite capacity queue at that node. The service units will travel from node to node serving the calls and return to the service center only when there are no more calls waiting. In most cases, exact models are too complicated to analyze. This paper presents approximations which are tested using simulation and found to give good results.     

多优先级业务流多通道并行传输

针对已有的多业务流多通道并行传输不支持业务流之间优先级的问题,将业务的优先级映射到多个通道,建立了具有优先级保证的多业务流多通道数据传输模型。基于排队论知识将模型抽象成多维Markov链,并使用两阶段的PH分布将多维Markov链近似成一维Markov链,采用矩阵分析方法对模型进行定量分析,推导出系统的平均队长和平均等待时间。通过数值分析与简单多业务流单通道、多优先级业务流单通道、简单多业务流多通道这三种传输模型进行了比较。结果表明,不管业务流达到率如何变化,多优先级业务流多通道并行传输模型中的高优先级数据包均能够获得较高的处理能力,说明了该模型能够支持多通道并行传输中业务流之间的优先控制。     

Numerical method for the analysis of queuing models with priority jumps1

An algorithmic approach to study queuing models with common finite and infinite buffer and jump priorities is developed. It is assumed that upon arrival of a low-priority call, one call of such kind can be transferred with some probability to the end of the queue of high-priority calls. The transition probability depends on the state of the queue of heterogeneous calls. The algorithms are proposed to calculate the quality of service metrics of such queuing models.     

Heavy traffic queue with stochastic arrival and service rates

A new approach is proposed to model heavy traffic queuing behaviour by stochasticizing in various ways the arrival and service rates so as to incorporate the random effect of the environment. This approach yields for the queue size a differential equation with stochastic parameters. The corresponding Fokker-Planck equation for the probability density function of the queue size is employed to analyse the queuing system. In this framework we consider the arrival and service rates to be subject to gaussian, white-noise perturbations and obtain the probability density function of the queue size and the distribution of the busy period. The study is generalized by considering the effect of coloured-noise perturbations in these rates. The effect of the white-noise perturbations on the state-dependent service rate is also investigated.     

Approximate method for analysis of queuing models with jump priorities

An approximate method for analysis of the queuing models with jump priorities was developed. It is assumed that upon arrival of a low-priority call one call of such kind might be immediately transferred to the end of the queue of the high-priority calls. The transfer probabilities depend on the state of the queue of heterogeneous calls. Consideration was given both to the models with separate and common queues. Algorithms to calculate the quality of service metrics of such queuing models were described, and the results of the numerical experiments were presented.     

Information theoretic approximations for M/G/1 and G/G/1 queuing systems

Summary This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.     

Analysis and optimization of Guard Channel Policy in cellular mobile networks with account of retrials

A multi-server retrial queue with two types of calls (handover and new calls) is analyzed. This queue models the operation of a cell of a mobile communication network. Calls of two types arrive at the system according to the Marked Markovian Arrival Process. Service times of both types of the calls are exponentially distributed with different service rates. Handover calls have priority over new calls. Priority is provided by means of reservation of several servers of the system exclusively for service of handover calls. A handover call is dropped and leaves the system if all servers are busy at the arrival epoch. A new call is blocked if all servers available to new calls are busy. Such a call has options to balk (to leave the system without getting the service) or to retry later on. The behavior of the system is described by the four-dimensional Markov chain belonging to the class of the asymptotically quasi-Toeplitz Markov chains (AQTMC). In the paper, a constructive ergodicity condition for this chain is derived and the effective algorithm for computing the stationary distribution is presented. Based on this distribution, formulas for various performance measures of the system are obtained. Results of numerical experiments illustrating the behavior of key performance measures of the system depending on the number of the reserved servers under the different shares of the handover and the new calls are presented. An optimization problem is considered and high positive effect of server's reservation is demonstrated.     

Cyclic-waiting systems

The paper analyzes a queuing system where customers are accepted for service either at the time of arrival (if the server if idle) or at the times that differ from it by intervals multiple of cycle time T. Formulas are derived to find the number of customers in the system, waiting time, and the existence condition for ergodic distribution.     

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 analysis of general loop systems

This paper is concerned with general loop systems in which each of several buffered units may exchange data with any other unit via a single oneway loop channel. The traffic is described in terms of stationary stochastic processes with independent increments. The queues of data waiting for transmission which develop at the different units are investigated. The queueing discipline assumed here accords data with longer transmission paths preemptive priority over those with shorter paths. For such systems expected queue lengths and waiting times in the steady state are calculated for all units and priority classes. An equivalence is established between general loop systems and systems of a much simpler structure and is used in the derivation.     

T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks

We propose a new priority discipline called the T-preemptive priority discipline. Under this discipline, during the service of a customer, at every T time units the server periodically reviews the queue states of each class with different queue-review processing times. If the server finds any customers with higher priorities than the customer being serviced during the queue-review process, then the service of the customer being serviced is preempted and the service for customers with higher priorities is started immediately. We derive the waiting-time distributions of each class in the M/G/1 priority queue with multiple classes of customers under the proposed T-preemptive priority discipline. We also present lower and upper bounds on the offered loads and the mean waiting time of each class, which hold regardless of the arrival processes and service-time distributions of lower-class customers. To demonstrate the utility of the T-preemptive priority queueing model, we take as an example an opportunistic spectrum access in cognitive radio networks, where one primary (licensed) user and multiple (unlicensed) users with distinct priorities can share a communication channel. We analyze the queueing delays of the primary and secondary users in the proposed opportunistic spectrum access model, and present numerical results of the queueing analysis.     

连续时间完全服务与门限服务两级轮询系统性能研究

在信息分组以连续时间规律到达系统的基础上，对于轮询系统中不同优先级的业务问题，提出区分优先级的两级轮询服务模型。首先，在该模型中，低优先级站点采用门限服务，高优先级站点采用完全服务；然后，在高优先级转低优先级时，将传输服务与转移查询并行处理来降低服务器在查询转换期间所耗费的时间，提高轮询系统的效率；最后，运用马尔可夫链和概率母函数的方法建立了系统的数学模型，通过对数学模型精确解析，得到了连续时间两级服务系统每个站点的平均排队队长和平均等待时间的表达式，精确解析出平均排队队长和平均等待时间的值。仿真实验结果表明：理论计算值与实验仿真值近似相等，说明理论分析正确合理。该模型既能保障低优先级站点服务质量，又能为高优先级站点提供优质服务。