Second‐order performance analysis of discrete‐time queues fed by DAR(2) sources with a focus on the marginal effect of the additional traffic parameter

Discrete autoregressive process of order 1 (DAR(1)) has been used as a popular stochastic model for correlated traffic sources because it parsimoniously uses a single parameter to capture the desirable correlation structure. In contrast with DAR(1), discrete autoregressive process of order 2 (DAR(2)) uses one more parameter to provide a much richer pattern in the autocorrelation function and is able to capture slower decay rate and longer memory. To investigate how the additional traffic parameter in DAR(2) influences the queueing performance, this paper provides an analysis of the discrete‐time DAR(2)/D/1 queue. The performance measures concerned are the mean and second‐order statistics of queue size, which are both important in the queueing systems seen in telecommunication networks. Under a mild condition, these performance indices are derived in closed form that allows for efficient computing. An approximate version of these results is also developed to relax the condition and cover more general sources, and both versions serve as a simple tool set for performance evaluation. The numerical examples use this tool to demonstrate that the DAR(2) source may cause up to 30% poorer performance than DAR(1) when the traffic is heavy, bursty, and highly correlated. This indicates that the effect from slower decay rate in autocorrelation is not negligible and using the extra parameter is necessary particularly when the queue is heavily loaded with correlated traffic. Copyright © 2012 John Wiley & Sons, Ltd.     

Analysis of a busy period queuing system with balking,reneging and motivating

Queuing model is widely applied in production, inventory and service industries. It is fundamental to improve the performance of queuing model by characterizing the practical queuing characteristics. In this paper, we consider impatient behaviors of customers who possibly balk and renege in a multi-server busy period queuing system, and study strategic behavior of the service provider who attempts to improve service rate when the system is busy. The piecewise curves with threshold structure are used to construct the dynamic inputting probability, dynamic service degree and dynamic reneging rate, and they are introduced to model the balking, motivating and reneging behaviors of the busy queue. The steady-state probabilities and the performance measures of the proposed model are derived. Finally, an empirical example is given to show the effectiveness of the proposed model by comparing it with the queuing model in literature.     

Competitive queue policies for differentiated services

We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume that the packets are tagged as either being a high priority packet or a low priority packet. Outgoing links in the network are serviced by a single FIFO queue.Our model gives a benefit of α1 to each high priority packet and a benefit of 1 to each low priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it sends.We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider. We believe that competitive analysis gives important insight to the performance of these queuing policies.     

An NTU value under complement reduced game

The paper follows Kalai and Samet’s (Econometrica 53:307–327, 1985) construction to define a possible extension of the equal allocation of nonseparable costs (EANSC) to games without transferable utilities. We offer a characterization of the EANSC based on the axiom of independence of irrelevant monotonic transformation [Chang and Hwang (Int J Game Theory 32:253–271, 2003) introduced this axiom, and they named it independence of irrelevant expansions. The referee points out that the terminology is inappropriate. So, we change the name.] introduced by Chang and Hwang (Int J Game Theory 32:253–271, 2003) as well as on several familiar axioms. Specifically, we show that the EANSC is the only solution to satisfy Pareto optimality, translation covariance, anonymity, TU-bilateral consistency (or TU-converse consistency), aggregate monotonicity, and independence of irrelevant monotonic transformation.     

A preemptive repeat priority queue with resampling: Performance analysis

In this paper, we analyze a discrete-time preemptive repeat priority queue with resampling. High-priority packets have preemptive repeat priority, and interrupted low-priority packets are subjected to independent retransmission attempts. Both classes contain packets with generally distributed transmission times. We show that the use of generating functions is beneficial for analyzing the system contents and packet delay of both classes. The influence of the priority scheduling on the performance measures is illustrated by some numerical examples. This work has been supported by the Interuniversity Attraction Poles Programme–Belgian Science Policy.     

Regularly varying tails in a queue with discrete autoregressive arrivals of order p

We consider a discrete time single server queueing system where the service time of a customer is one slot, and the arrival process is governed by a discrete autoregressive process of order p (DAR(p)). For this queueing system, we investigate the tail behavior of the queue size and the waiting time distributions. Specifically, we show that if the stationary distribution of DAR(p) input has a tail of regular variation with index −β−1, then the stationary distributions of the queue size and the waiting time have tails of regular variation with index −β. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

A reinforcement-depletion urn model: A contiguity case

Summary An urn contains balls ofs different colors. The problem of the reinforcement of a specified color and random depletion of balls has been considered by Bernard (1977,Bull. Math. Biol.,39, 463–470) and Shenton (1981,Bull. Math. Biol.,43, 327–340), (1983,Bull. Math. Biol.,45, 1–9). Here we consider a special relation between a reinforcement and depletion, leading to a hypergeometric distribution. Research sponsored in part by the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy under contract DE-AC05-840R21400 with the Martin Marietta Energy Systems, Inc.     

Rate of convergence to ergodic distribution for queue length in systems of the type <Emphasis Type="Italic">M</Emphasis><Superscript>θ</Superscript>/<Emphasis Type="Italic">G</Emphasis>/1/<Emphasis Type="Italic">N</Emphasis>

For finite-capacity queuing systems of the type M ^θ/G/1, convenient formulas for the ergodic distribution of the queue length are found, an estimate for the rate of convergence of the distribution of the queue length in the transient mode to the ergodic distribution is obtained, and computational algorithms for finding the rate of convergence are presented. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 9, pp. 1169–1178, September, 2007.     

User equilibria for a parallel queueing system with state dependent routing

Consider a system of two queues in parallel, one of which is a ⋅|M|1 single-server infinite capacity queue, and the other a ⋅|G ^(N)|∞ batch service queue. A stream of general arrivals choose which queue to join, after observing the current state of the system, and so as to minimize their own expected delay. We show that a unique user equilibrium (user optimal policy) exists and that it possesses various monotonicity properties, using sample path and coupling arguments. This is a very simplified model of a transportation network with a choice of private and public modes of transport. Under probabilistic routing (which is equivalent to the assumption that users have knowledge only of the mean delays on routes), the network may exhibit the Downs–Thomson paradox observed in transportation networks with expected delay increasing as the capacity of the ⋅|M|1 queue (private transport) is increased. We give examples where state-dependent routing mitigates the Downs–Thomson effect observed under probabilistic routing, and providing additional information on the state of the system to users reduces delay considerably.     

具有一阶离散自回归到达和服务器中断的离散时间排队系统分析

研究一类到达服从一阶离散自回归过程,服务器有可能中断的离散排队系统.着重考虑在到达流具有相关性的情况下,排队系统的性能表现.文章通过概率母函数的方法,得到了系统队长的概率母函数,并由此导出系统平均队长.最后通过数值实验可以看出系统的性能对到达过程的相关性非常敏感.     

The heterogeneous multiscale finite element method for elliptic homogenization problems in perforated domains

In this contribution we analyze a generalization of the heterogeneous multiscale finite element method for elliptic homogenization problems in perforated domains. The method was originally introduced by E and Engquist (Commun Math Sci 1(1):87–132, 2003) for homogenization problems in fixed domains. It is based on a standard finite element approach on the macroscale, where the stiffness matrix is computed by solving local cell problems on the microscale. A-posteriori error estimates are derived in L ²(Ω) by reformulating the problem into a discrete two-scale formulation (see also, Ohlberger in Multiscale Model Simul 4(1):88–114, 2005) and using duality methods afterwards. Numerical experiments are given in order to numerically evaluate the efficiency of the error estimate.     

A note on meromorphic functions that share a set with their derivatives

In this paper, we study a problem of meromorphic functions that share an arbitrary set having three elements with their derivatives. A uniqueness result is derived which is an improvement of some related theorems given by Fang and Zalcman (J. Math. Anal. Appl. 280 (2003), 273–283) and Chang, Fang, and Zalcman (Arch. Math. 89 (2007), 561–569). As an application, we generalize the famous Brück conjecture with the idea of sharing a set.     

On the Exact Analysis of a Discrete-Time Queueing System with Autoregressive Inputs

In this paper, we provide an exact analysis of a discrete-time queueing system driven by a discrete autoregressive model of order 1 (DAR(1)) characterized by an arbitrary marginal batch size distribution and a correlation coefficient. Closed-form expressions for the probability generating function and mean queue length are derived. It is shown that the system performance is quite sensitive to the correlation of the arrival process. In addition, a comparison with traditional Markovian processes shows that arrival processes of DAR(1) type exhibit larger queue length as compared with the traditional Markovian processes when the marginal densities and correlation coefficients are matched.     

The throughput performance of a prioritized LIFO service discipline

The LIFO service discipline maximizes throughput for certain queuing systems with delay-dependent customer behavior. To study the effects of priorities in such a system, we obtain delay distributions for each customer class of a K-class, single server system with nonpreemptive priorities and LIFO within each queue.     

推广的M~x/G(M/G)/1(M/G)可修排队系统(I)── 一些排队指标

考虑Ｍｘ／Ｇ（Ｍ／Ｇ）／１（Ｍ／Ｇ）可修排队系统,且把该系统推广到休假时间、服务时间、修理时间和延误休假时间都为任意分布（不一定连续）,利用服务员忙期和拉普拉斯交换,我们直接获得队长瞬态分布的Ｌ变换递推式和稳态分布的递推式,以及队长的概率母函数,同时指出了１９９４年史定华文中存在的错误．     

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 simple proof for the constructions of optical priority queues

Constructions of optical queues by optical Switches and fiber Delay Lines (SDL) have received a lot of attention lately. In this short paper, we provide a simple proof for the construction of a priority queue with a switch and fiber delay lines in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006). Our proof not only gives the insights needed to understand why such a construction works, but also leads to a more general result that recovers the result in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006) as a special case. This research was supported in part by the National Science Council, Taiwan, ROC, under Contract NSC-93-2213-E-007-040, Contract NSC-93-2213-E-007-095, Contract NSC-94-2213-E-007-046, and the Program for Promoting Academic Excellence of Universities NSC 94-2752-E-007-002-PAE.     

Equivalent single-queue–single-server model for a Pentium processor

In this paper, a Pentium processor is represented as a queuing network. The objective of this paper is to deduce an equivalent single-queue–single-server model for the original queuing network. Closed-form expressions for the equivalent service rate, equivalent queue lengths, equivalent response and waiting times of the equivalent single-queue–single-server model are derived and plotted. For large values of arrival rate, queue lengths increase faster than the response times and waiting times for both the cases. Performance measures like, queue lengths, response times and waiting times are higher for lower service rates and lower for higher service rates (which is expected) of the different servers in the original queuing network. Also, the reliability in estimating performance measures for homogeneous workloads is much better than that for heterogeneous workloads.     

推广的M~x/G(M/G)/1(M/G)可修排队系统(I)── 一些排队指标

考虑M     

SOME ASPECTS OF M/G/1 QUEUE WITH TWO DIFFERENT VACATION TIMES UNDER MULTIPLE VACATION POLICY

This paper deals with the steady state behavior of an M/G/1 queuing system with two different vacation times under multiple vacation policy, where length of the first vacation is different from the second and subsequent vacations. In this paper, attempts have been made to obtain the additional queue size distribution, distribution of additional delay and waiting time distribution of this model. Also, we obtain some important measures of this model.