Sample-path analysis of queues with batch arrivals

In this article we give a deterministic sample path general relationship that relates workload and batch delays, and use it to extend the Pollaczek–Khintchine formula for a batch arrival single-server queueing model. We also give a conservation law for the same system with multiple classes that leads to new versions of conservation laws for Poisson batch arrival models. Our results are completely rigorous and hold under weaker assumptions than those given in the literature. We do not make stochastic assumptions, so the results hold almost surely on every sample path of the stochastic process that describes the system evolution. The article is self contained in that it gives a brief review of necessary background material.     

Optimal control of parallel queues with impatient customers

We consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process with an arrival rate which is a non-increasing function of the number of customers in the system. Upon arrival, a customer must join a server’s queue according to a stationary state-dependent policy, where the state is taken to be the number of customers in servers’ queues. No jockeying among queues is allowed. Each arriving customer is limited to a generally distributed patience time after which it must depart the system and is considered lost. Two models of customer behavior are considered: deadlines until the beginning of service and deadlines until the end of service. We seek an optimal policy to assign an arriving customer to a server’s queue. We show that, when the distribution of customer impatience satisfies certain property, the policy of joining shortest queue (SQ) stochastically minimizes the number of lost customers during any finite interval in the long run. This property is shown to always hold for the case of deterministic customer impatience.     

Bayesian nearest-neighbor analysis via record value statistics and nonhomogeneous spatial Poisson processes

This article proposes record value statistics and nonhomogeneous spatial Poisson processes as new nearest-neighbor approaches for detecting spatial patterns. A Markov chain Monte Carlo method with data augmentation was developed to compute the Bayes estimates of posterior quantities of interest. Simulation studies showed that the new approaches yield high detection rates and low false positive rates. We applied the new approaches to detect localized clusters of specific trees and to outline seismic faults in the study space.     

Closed-form analysis of end-to-end network delay with Markov-modulated Poisson and fluid traffic

This paper develops a method for using traffic sources modelled as a Markov-modulated Poisson process (MMPP) and Markov-modulated fluid process (MMFP) in the framework of the bounded-variance network calculus, a novel stochastic network calculus framework for the approximated analysis of end-to-end network delay. The bounded-variance network calculus is an extension to multi-hop end-to-end paths of the Choe’s and Shroff’s Central-Limit-Theorem-based analysis of isolated network nodes. The input of the analysis is the statistical traffic envelope of sources, which is not available for generic MMPP and MMFP sources. The paper provides two statistical traffic envelopes, named two-moment and linear envelope, for general MMPP and MMFP sources, which can be used as an input of Central-Limit-Theorem-based frameworks for the analysis of network delay and, in turn, make it possible to use the rich collection of MMPP and MMFP models of voice, audio, data and video sources available in the literature. In this way, it is possible to avoid the computational complexity of traditional Markov analysis of end-to-end delay with MMPP and MMFP sources. With the linear envelope we can use simple analytical closed-form solutions for many important schedulers.     

Identification of positive linear systems with Poisson output transformation

We study the identification problem for third-order linear time invariant positive systems in experiments where the output is a Poisson process. The problem well-posedness is investigated when the input-output model is described by a sum of real exponentials. A maximum likelihood procedure is then proposed and the admissible set for the unknown parameters is characterized. The novelty of the approach consists in solving a constrained maximum likelihood problem to estimate residues and eigenvalues based on theoretical results on minimality of positive realizations recently obtained in the literature. Numerical results are also provided.     

A multi-server queueing model with retrial connection arrivals as a model for optimisation of the traffic control

We consider a multi-server queueing model with a finite buffer and requests arriving in connections. The number of requests in a connection is random and unknown at the connection initiation instant. Requests, which belong to the connection, arrive in accordance with a Poisson process. Admission of connections to the system is regulated by means of so-called tokens. The pool of tokens is finite. If a connection arrives and there are no tokens available, it leaves the system forever or joins the orbit and retries for access later on. The steady-state distribution of the system is analysed. The problem of the throughput maximisation under the constraint that the request loss probability does not exceed a predefined value is numerically solved. The effect of the retrial intensity, correlation and variation in the arrival process and the probability to leave the system if tokens are not available is numerically highlighted.     

Approximate analysis of a discrete-time tandem network of cut-through queues with blocking and bursty traffic

A discrete-time tandem network of cut-through queues is presented. The model allows finite capacity queues, blocking, and bursty traffic. A new bursty arrival process, IBK(k), for cut-through traffic is introduced. The tandem network is analyzed using single-node decomposition. Each queue is analyzed numerically in isolation assuming that its arrival and service processes are known. The parameters of the arrival and service processes of the queues are obtained using an iterative scheme. The results obtained are approximate and validation tests have shown that the model has good accuracy. Using this model, the packet loss, throughput, and queue length distributions were obtained for different traffic parameters and queue sizes.     

Fluid limits and diffusion approximations for networks of multi-server queues in heavy traffic

A Functional Strong-Law-of-Large-Numbers (known as fluid limit or fluid approximation) and a Functional Central Limit Theorem (known as diffusion approximation) are proved for both open and closed networks of multi-server queues in heavy traffic. The fluid limit is a reflected piecewise linear deterministic process, and the diffusion limit is a reflected Brownian motion; both limiting processes are on the nonnegative orthant for open networks and on the nonnegative unit simplex for closed networks. The results generalize the existing ones for networks of single-server queues.     

Transient analysis of packet discarding policies in ATM networks with correlated arrivals

In this paper, we investigate several dynamic congestion control strategies in ATM networks. We present an analytic model to observe the transient behavior of correlated fixed sized cell arrivals into a congested buffer. We derive the transient and time-averaged cell loss probabilities for several packet discarding policies, and we also derive the moments of the first passage time from a congested state to a threshold below which the buffer is considered in a non-congested state. We present numerical results for arrival processes having the same marginal distributions, but differing by autocorrelation coefficient only, thus isolating the effects of correlation on transient behavior. We conjecture how these results affect buffer congestion management procedures.     

Mean-value analysis of multi-facility blocking models with state-dependent arrivals

A new mean-value type of algorithm is developed for analyzing multi-facility blocking models with state-dependent arrival rates. It can be applied to a broad class of blocking systems with simultaneous resource possession including, for example, circuit-switched networks. The underlying recursion is cast in terms of blocking probabilities and marginal state probabilities. The developments made here generalize previous results that were restricted to the case of constant arrival rates.     

Mixture Poisson regression models for heterogeneous count data based on latent and fuzzy class analysis

In this paper we propose a new approach, called a fuzzy class model for Poisson regression, in the analysis of heterogeneous count data. On the basis of fuzzy set concept and fuzzy classification maximum likelihood (FCML) procedures we create an FCML algorithm for fuzzy class Poisson regression models. Traditionally, the EM algorithm had been used for latent class regression models. Thus, the accuracy and effectiveness of EM and FCML algorithms for estimating the parameters are compared. The results show that the proposed FCML algorithm presents better accuracy and effectiveness and can be used as another good tool to regression analysis for heterogeneous count data.This work was supported in part by the National Science Council of Taiwan under Grant NSC-89-2213-E-033-007.     

Approximate synthesis of optimal control over quasilinear stochastic differential equations with a small parameter and Poisson perturbations

The authors obtain successive approximations to the optimal control over a quasilinear system of stochastic functional-differential equations with Poisson disturbances and a quadratic quality functional. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 39–45, May–June 2008.     

Computational analysis of a Markovian queueing system with geometric mean-reverting arrival process

In the queueing literature, an arrival process with random arrival rate is usually modeled by a Markov-modulated Poisson process (MMPP). Such a process has discrete states in its intensity and is able to capture the abrupt changes among different regimes of the traffic source. However, it may not be suitable for modeling traffic sources with smoothly (or continuously) changing intensity. Moreover, it is less parsimonious in that many parameters are involved but some are lack of interpretation. To cope with these issues, this paper proposes to model traffic intensity by a geometric mean-reverting (GMR) diffusion process and provides an analysis for the Markovian queueing system fed by this source. In our treatment, the discrete counterpart of the GMR arrival process is used as an approximation such that the matrix geometric method is applicable. A conjecture on the error of this approximation is developed out of a recent theoretical result, and is subsequently validated in our numerical analysis. This enables us to calculate the performance measures with high efficiency and precision. With these numerical techniques, the effects from the GMR parameters on the queueing performance are studied and shown to have significant influences.     

Poisson modes and general nonlinear constitutive models in the large displacement analysis of beams

Most existing formulations for structural elements such as beams, plates and shells do not allow for the use of general nonlinear constitutive models in a straightforward manner. Furthermore, such structural element models, due to the nature of the generalized coordinates used, do not capture some Poisson modes such as the ones that couple the deformation of the cross section of the structural element and stretch and bending. In this paper, beam models that employ general nonlinear constitutive equations are presented using finite elements based on the nonlinear absolute nodal coordinate formulation. This formulation relaxes the assumptions of the Euler–Bernoulli and Timoshenko beam theories, and allows for the use of general nonlinear constitutive models. The finite elements based on the absolute nodal coordinate formulation also allow for the rotation as well as the deformation of the cross section, thereby capturing Poisson modes which can not be captured using other beam models. In this investigation, three different nonlinear constitutive models based on the hyper-elasticity theory are considered. These three models are based on the Neo–Hookean constitutive law for compressible materials, the Neo–Hookean constitutive law for incompressible materials, and the Mooney–Rivlin constitutive law in which the material is assumed to be incompressible. These models, which allow capturing Poisson modes, are suitable for many materials and applications, including rubber-like materials and biological tissues which are governed by nonlinear elastic behavior. Numerical examples that demonstrate the implementation of these nonlinear constitutive models in the absolute nodal coordinate formulation are presented. The results obtained using the nonlinear and linear constitutive models are compared in this study. These results show that the use of nonlinear constitutive models can significantly enhance the performance and improve the computational efficiency of the finite element models based on the absolute nodal coordinate formulation. The results also show that when linear constitutive models are used in the large deformation analysis, singular configurations are encountered and basic formulas such as Nanson’s formula are no longer valid. These singular deformation configurations are not encountered when the nonlinear constitutive models are used.     

塔线体系脱冰瞬态响应分析与相似验证

运用ANSYS软件建立了三塔两跨塔线体系试验模型及其原型的有限元计算模型,并对它们在各种脱冰工况下的瞬态响应进行了分析和比较.结果表明,不仅响应的特征参数满足动力相似,而且整个时程响应曲线吻合良好,模型试验结果能够反映原型的动力特性,试验数据具备良好的互推性.本文的研究和结论不仅验证了试验模型设计的正确性,而且为试验模型的制作以及脱冰跳跃模型试验提供了理论指导.     

Delay analysis of a unidirectional bus network with an erasure station

Fiber-based unidirectional bus networks offer attractive solutions for very high speed multiaccess communications over local and metropolitan areas. The transmission capacity of such networks can be increased considerably through the use of erasure stations that enable reuse of slots that have passed their destinations on the bus. An analysis of the mean packet delay performance of a unidirectional bus network with one erasure station is presented. The two bus sections separated by the erasure station are modeled as coupled queues. A functional equation for the joint generating function of the queue sizes in steady state is obtained and used to evaluate the mean packet delay under Poisson arrivals.     

Infinitesimal perturbation analysis of a queueing system with bursty traffic

We study aG/G/1 queueing system with a bursty arrival process. Based on a general model for such a bursty process, we derive infinitesimal perturbation analysis (IPA) derivative estimators of the mean system time with respect to various parameters of interest. The cases of both complete and partial state information are considered. To ensure unbiasedness and strong consistency of the estimators, different sample path representations are developed such that sample functions are continuous with respect to the particular parameter of interest. Some of these representations are applicable to a wider class of gradient estimation problems where sample path discontinuities arise. Simulation results are included to compare the convergence rates and variance properties of the different IPA estimators developed.     

Markov-chain model and algorithmic procedure for the performance analysis of closed cyclic queues

This paper presents a model and an algorithmic procedure to analyze closed cyclic queues that are subject to blocking. We consider the first two moments of the processing time and present the fitting of phase-type distributions such that the number of phases and transitions is minimal. Using phase-type distributions, we enable the analysis of queueing systems with processing times with any coefficient of variation. We model the closed cyclic queues subject to blocking as continuous-time Markov chains. The implementation procedure covers the state-space generation and the determination of the infinitesimal generator matrix. Apart from rounding errors, we obtain exact results for the queueing model this way. The results are useful as reference values for the output of approximate approaches. Further, the algorithmic procedure enables a repeated analysis of different configuration alternatives as needed in optimization procedures. Though the method is very fast for small cyclic queues, it takes a long computation time for larger systems. Furthermore, the size of the queueing model to be analyzed is restricted due to the limited working memory with its present-day capacity. In a numerical study, the computation times for different configurations are investigated, limits in the size of the applicable queueing model are given, and numerical results of the performance measures are provided.     

具有输入时滞和外部扰动的线性系统的过渡过程估计

给同了具有输入时滞和外部扰动的一类线性系统的过渡过程的估计,理论分析和仿真结果表明,文中的主要结论为时滞系统稳定性的定量分析提供了一种有效的分析方法。