A matrix-analytic solution for the DBMAP/PH/1 priority queue

Priority queueing models have been commonly used in telecommunication systems. The development of analytically tractable models to determine their performance is vitally important. The discrete time batch Markovian arrival process (DBMAP) has been widely used to model the source behavior of data traffic, while phase-type (PH) distribution has been extensively applied to model the service time. This paper focuses on the computation of the DBMAP/PH/1 queueing system with priorities, in which the arrival process is considered to be a DBMAP with two priority levels and the service time obeys a discrete PH distribution. Such a queueing model has potential in performance evaluation of computer networks such as video transmission over wireless networks and priority scheduling in ATM or TDMA networks. Based on matrix-analytic methods, we develop computation algorithms for obtaining the stationary distribution of the system numbers and further deriving the key performance indices of the DBMAP/PH/1 priority queue. AMS subject classifications: 60K25 · 90B22 · 68M20 The work was supported in part by grants from RGC under the contracts HKUST6104/04E, HKUST6275/04E and HKUST6165/05E, a grant from NSFC/RGC under the contract N_HKUST605/02, a grant from NSF China under the contract 60429202.     

TheM/G/1 retrial queue with the server subject to starting failures

In this paper, we study a retrial queueing model with the server subject to starting failures. We first present the necessary and sufficient condition for the system to be stable and derive analytical results for the queue length distribution as well as some performance measures of the system in steady state. We show that the general stochastic decomposition law forM/G/1 vacation models also holds for the present system. Finally, we demonstrate that a few well known queueing models are special cases of the present model and discuss various interpretations of the stochastic decomposition law when applied to each of these special cases.Partially supported by the Natural Sciences and Engineering Research Council of Canada, grant OGP0046415.Partially supported by internal research grant of Mount Saint Vincent University.     

Little laws for utility processes and waiting times in queues

Little's law for queueing systems isL=W: the average queue length equals the average arrival rate times the average waiting time in the system. This study gives further insights into techniques for establishing such laws (i.e. establishing the existence of the terms as limiting averages or expectations) and it presents several basic laws for systems with special structures. The main results concern (1) general necessary and sufficient conditions for Little laws for utility processes as well as queueing systems, (2) Little laws for systems that empty out periodically or, more generally, have regular departures and (3) Little laws tailored to regenerative, Markovian and stationary systems.This research was supported in part by the Air Force Office of Scientific Research under contract 91-0013 and NSF grant DDM-9224520.     

Modeling circulation systems in buildings using state dependent queueing models

Circulation systems within buildings are analyzed using M/G/C/C queueing models. Congestion aspects of the traffic flow are represented by introducing state dependent service rates as a function of the number of occupants in each region of the circulation system. Analytical models for unidirectional and multi-source/single sink flows are presented. Finally, use of the queueing models to analytically determine the optimal size and capacity of the links of the circulation systems is incorporated into a series of software programs available from the authors.This material is based upon work supported by the National Science Foundation under grant #MSM-8417942 and #MSM-8715152.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

Proto-derivative formulas for basic subgradient mappings in mathematical programming

Subgradient mappings associated with various convex and nonconvex functions are a vehicle for stating optimality conditions, and their proto-differentiability plays a role therefore in the sensitivity analysis of solutions to problems of optimization. Examples of special interest are the subgradients of the max of finitely manyC ² functions, and the subgradients of the indicator of a set defined by finitely manyC ² constraints satisfying a basic constraint qualification. In both cases the function has a property called full amenability, so the general theory of existence and calculus of proto-derivatives of subgradient mappings associated with fully amenable functions is applicable. This paper works out the details for such examples. A formula of Auslender and Cominetti in the case of a max function is improved in particular.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under grant OGP41983 for the first author and by the National Science Foundation under grant DMS-9200303 for the second author.     

Convexity of single stage queueing systems with bulk arrival

In this paper we study the convexity of the waiting time, workload and the number of jobs in single stage queueing systems with respect to the bulk size of the arrival process. In particular we show that the number of jobs in a single server queueing systemG ^[x ]/GI/1 and in a multiple server queueing systemG ^[x]/M/c with bulk sizesx=(x ₁ ,x ₂ ,x ₃ ,...) is componentwise convex inx. This is in the sense of the sample path convexity introduced in Shaked and Shanthikumar [11]. These results have applications in the stochastic comparison of bulk arrival queueing systems.Research supported in part by NSF grant DDM-9113008.     

Analyzing the discrete-timeG (G)/Geo/1 queue using complex contour integration

In this paper, a discrete-time single-server queueing system with an infinite waiting room, referred to as theG ^(G)/Geo/1 model, i.e., a system with general interarrival-time distribution, general arrival bulk-size distribution and geometrical service times, is studied. A method of analysis based on integration along contours in the complex plane is presented. Using this technique, analytical expressions are obtained for the probability generating functions of the system contents at various observation epochs and of the delay and waiting time of an arbitrary customer, assuming a first-come-first-served queueing discipline, under the single restriction that the probability generating function for the interarrival-time distribution be rational. Furthermore, treating several special cases we rediscover a number of well-known results, such as Hunter's result for theG/Geo/1 model. Finally, as an illustration of the generality of the analysis, it is applied to the derivation of the waiting time and the delay of the more generalG ^(G)/G/1 model and the system contents of a multi-server buffer-system with independent arrivals and random output interruptions.Both authors wish to thank the Belgian National Fund for Scientific Research (NFWO) for support of this work.     

A two-server queueing system with periodic and credit-based server availabilities

A discrete-time, two-server queueing system is studied in this paper. The service time of a customer (cell) is fixed and equal to one time unit. Server 1 provides for periodic service of the queue (periodT). Server 2 provides for service only when server 1 is unavailable and provided that the associated service credit is nonzero. The resulting system is shown to model the queueing behavior of a network user which is subject to traffic regulation for congestion avoidance in high speed ATM networks. A general methodology is developed for the study of this queueing system, based on renewal theory. The dimensionality of the developed model is independent ofT;T increases with the network speed. The cell loss probabilities are computed in the case of finite capacity queue.Research supported by the National Science Foundation under grant NCR-9011962.     

Performance analysis approximation in a queueing system of type M/G/1

In this work, we apply the strong stability method to obtain an estimate for the proximity of the performance measures in the M/G/1 queueing system to the same performance measures in the M/M/1 system under the assumption that the distributions of the service time are close and the arrival flows coincide. In addition to the proof of the stability fact for the perturbed M/M/1 queueing system, we obtain the inequalities of the stability. These results give with precision the error, on the queue size stationary distribution, due to the approximation. For this, we elaborate from the obtained theoretical results, the STR-STAB algorithm which we execute for a determined queueing system: M/Coxian − 2/1. The accuracy of the approach is evaluated by comparison with simulation results.     

A sample path relation for the sojourn times in G/G/1−PS systems and its applications

For the single server system under processor sharing (PS) a sample path result for the sojourn times in a busy period is proved, which yields a sample path relation between the sojourn times under PS and FCFS discipline. This relation provides a corresponding one between the mean stationary sojourn times in G/G/1 under PS and FCFS. In particular, the mean stationary sojourn time in G/D/1 under PS is given in terms of the mean stationary sojourn time under FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of these results suggest an approximation of the mean stationary sojourn time in G/GI/1 under PS in terms of the mean stationary sojourn time under FCFS. Mathematics Subject Classification (MSC 2000) 60K25· 68M20· 60G17· 60G10 This work was supported by a grant from the Siemens AG.     

A Geometric Programming Framework for Univariate Cubic L 1 Smoothing Splines

Univariate cubic L ₁ smoothing splines are capable of providing shape-preserving C ¹-smooth approximation of multi-scale data. The minimization principle for univariate cubic L ₁ smoothing splines results in a nondifferentiable convex optimization problem that, for theoretical treatment and algorithm design, can be formulated as a generalized geometric program. In this framework, a geometric dual with a linear objective function over a convex feasible domain is derived, and a linear system for dual to primal conversion is established. Numerical examples are given to illustrate this approach. Sensitivity analysis for data with uncertainty is presented. This work is supported by research grant #DAAG55-98-D-0003 of the Army Research Office, USA.     

Duality for Multiple Objective Fractional Subset Programming with Generalized (, ρ, σ, θ)-V-Type-I Functions

In this paper, we use a new class of generalized convex n-set functions, called (,ρ, σ, θ)-V-Type-I and related non-convex functions to establish appropriate duality theorems for three parametric and three semi-parametric dual models to the primal problem. This work extends an earlier work of Zalmai [Computer and Mathematics with Applications 43 (2002) 1489–1520] to a wider class of functions.This research is supported by the Department of Science and Technology, Ministry of Science and Technology, Government of India, under the Fast Track Scheme for Young Scientist through grant No. SR/FTP/MS-22/2001     

A resource allocation queueing fairness measure: properties and bounds

Fairness is an inherent and fundamental factor of queue service disciplines in a large variety of queueing applications, ranging from airport waiting lines to computer queueing systems. We study a newly proposed measure, a Resource Allocation Queueing Fairness Measure (RAQFM), first introduced in Raz, Levy, and Avi-Itzhak (Perform. Eval. Rev. 32(1):130–141, 2004). We analyze the properties of RAQFM and tie them to intuition, provide bounds for its values, and discuss briefly how it yields to analysis. This work was supported in part by the Israeli Ministry of Science and Technology, grant number 380-801, and by EURO-NGI network of excellence.     

On the decomposition of infinitely divisible characteristic functions of several variables

Summary We prove here some theorems describing infinitely divisible characteristic functions defined on R ⁿ which have positive Poisson spectrum and belong to the class I ₀ of characteristic functions without indecomposable factor. These theorems are generalizations to the case of several variables of results due to I.V. Ostrovskiy in the case of one variable.This work was supported by the National Science Foundation under grant NSF-GP-6175.     

Queues with hysteretic control by vacation and post-vacation periods

The paper investigates the queueing process in stochastic systems with bulk input, batch state dependent service, server vacations, and three post-vacation disciplines. The policy of leaving and entering busy periods is hysteretic, meaning that, initially, the server leaves the system on multiple vacation trips whenever the queue falls below r (⩾1), and resumes service when during his absence the system replenishes to N or more customers upon one of his returns. During his vacation trips, the server can be called off on emergency, limiting his trips by a specified random variable (thereby encompassing several classes of vacation queues, such as ones with multiple and single vacations). If by then the queue has not reached another fixed threshold M (⩽ N), the server enters a so-called “post-vacation period” characterized by three different disciplines: waiting, or leaving on multiple vacation trips with or without emergency. For all three disciplines, the probability generating functions of the discrete and continuous time parameter queueing processes in the steady state are obtained in a closed analytic form. The author uses a semi-regenerative approach and enhances fluctuation techniques (from his previous studies) preceding the analysis of queueing systems. Various examples demonstrate and discuss the results obtained. This revised version was published online in June 2006 with corrections to the Cover Date.     

Workload in queues having priorities assigned according to service time

System designers often implement priority queueing disciplines in order to improve overall system performance; however, improvement is often gained at the expense of lower priority cystomers. Shortest Processing Time is an example of a priority discipline wherein lower priority customers may suffer very long waiting times when compared to their waiting times under a democratic service discipline. In what follows, we shall investigate a queueing system where customers are divided into a finitie number of priority classes according to their service times.We develop the multivariate generating function characterizing the joint workload among the priority classes. First moments obtained from the generating function yield traffic intensities for each priority class. Second moments address expected workloads, in particular, we obtain simple Pollaczek-Khinchine type formulae for the classes. Higher moments address variance and covariance among the workloads of the priority classes.This work was supported in part by National Science Foundation Grant DDM-8913658.     

CR Runge Sets on Hypersurface Graphs

This work contains an improvement of earlier results of Boggess and Dwilewicz regarding global approximation of CR functions by entire functions in the case of hypersurface graphs. In this work, we show that if ω, an open subset of a real hypersurface in ℂ ⁿ , can be graphed over a convex subset in ℝ²ⁿ⁻¹, then ω is CR-Runge in the sense that continuous CR functions on ω can be approximated by entire functions on ℂ ⁿ in the compact open topology of ω. Examples are presented to show that this approximation result does not hold for graphed CR submanifolds in higher codimension. R. Dwilewicz is partially supported by the Polish Science Foundation (KBN) grant N201 019 32/805.     

Biconvex sets and optimization with biconvex functions: a survey and extensions

The problem of optimizing a biconvex function over a given (bi)convex or compact set frequently occurs in theory as well as in industrial applications, for example, in the field of multifacility location or medical image registration. Thereby, a function is called biconvex, if f(x,y) is convex in y for fixed x∈X, and f(x,y) is convex in x for fixed y∈Y. This paper presents a survey of existing results concerning the theory of biconvex sets and biconvex functions and gives some extensions. In particular, we focus on biconvex minimization problems and survey methods and algorithms for the constrained as well as for the unconstrained case. Furthermore, we state new theoretical results for the maximum of a biconvex function over biconvex sets. J. Gorski and K. Klamroth were partially supported by a grant of the German Research Foundation (DFG).     

Differentiability of convex measures

In this paper we consider convex measures on finite-dimensional spaces. We prove the differentiability of convex measures in the Skorokhod sense (and under some natural conditions, in the Fomin sense also). Simultaneously we give some additional results on differentiability of convex measures.Translated fromMatematicheskie Zametki, Vol. 58, No. 6, pp. 862–871, December, 1995.This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-01556, by the Ministry of Science under grant No. M38300 and by the International Science Foundation under grant No. M38000.