Queueing Petri nets with product form solution

The product form results recently published for stochastic Petri nets are combined with the well-known product form results for queueing networks in the model formalism of queueing Petri nets yielding the class of product form queueing Petri nets. This model class includes stochastic Petri nets with product form solution and BCMP queueing networks as special cases. We introduce an arrival theorem for the model class and present an exact aggregation approach extending known approaches from queueing networks.     

New Linear Program Performance Bounds for Closed Queueing Networks

We develop new linear program performance bounds for closed reentrantqueueing networks based on an inequality relaxation of the averagecost equation. The approach exploits the fact that the transitionprobabilities under certain policies of closed queueing networksare invariant within certain regions of the state space. Thisinvariance suggests the use of a piecewise quadratic functionas a surrogate for the differential cost function. The linearprogramming throughput bounds obtained are provably tighter thanpreviously known bounds at the cost of increased computationalcomplexity. Functional throughput bounds parameterized by thefixed customer population N are obtained, alongwith a bound on the limiting throughput as N + .We show that one may obtain reduced complexity bounds while stillretaining superiority.     

Customer-Oriented Finite Perturbation Analysis for Queueing Networks

We consider queueing networks for which the performance measureJ ( ) depends on a parameter , which can be a service time parameter or a buffer size, and we are interested in sensitivity analysis of J ( ) with respect to . We introduce a new method, called customer-oriented finite perturbation analysis (CFPA), which predicts J ( + ) for an arbitrary, finite perturbation from a simulation experiment at . CFPA can estimate the entire performance function (by using a finite number of chosen points and fitting a least-squares approximating polynomial to the observation) within one simulation experiment. We obtain CFPA by reformulating finite perturbation analysis (FPA) for customers. The main difference between FPA and CFPA is that the former calculates the sensitivities of timing epochs of events, such as external arrivals or service time completions, while the latter yields sensitivities of departure epochs of customers. We give sufficient conditions for unbiasedness of CFPA. Numerical examples show the efficiency of the method. In particular, we address sensitivity analysis with respect to buffer sizes and thereby give a solution to the problem for which perturbation analysis was originally built.     

Queues in DOCSIS cable modem networks

In this paper we determine the optimal fraction c^*$c^{*}$ of the uplink channel capacity that should be dedicated to the contention channel in a DOCSIS cable network in order to minimize its mean response time. For this purpose, we have developed an open queueing network with a non-standard form of blocking consisting of tens to hundreds of nodes. The network contains several types of customers that enter the network at various points according to a Markovian arrival process with marked customers. One of the main building blocks of the model exists in capturing the behavior of the conflict resolution algorithm by means of a single processor sharing queue. To assess the performance characteristics of this open queueing network we rely on an advanced decomposition technique that is specifically designed to deal with the Markovian nature of the arrival pattern. Several simulations are run to confirm the accuracy of the decomposition technique. We also explore the impact of a variety of systems parameters, e.g., the number of cable modems, the initial backoff window size, the correlation structure of the arrival process, the mean packet sizes, etc., on the optimal fraction c^*$c^{*}$.     

Stochastic Simulation Methods Applied to a Secure Electronic Voting Model

We demonstrate a novel simulation technique for analysing large stochastic process algebra models, applying this to a secure electronic voting system example. By approximating the discrete state space of a PEPA model by a continuous equivalent, we can draw on rate equation simulation techniques from both chemical and biological modelling to avoid having to directly enumerate the huge state spaces involved. We use stochastic simulation techniques to provide traces of course-of-values time series representing the number of components in a particular state. Using such a technique we can get simulation results for models exceeding 10¹⁰⁰⁰⁰ states within only a few seconds.     

Queueing network software for systems modelling

Several requirements are placed on queueing models of computer systems. These include credibility, accuracy, timeliness and cost. Modelling software can have critical impact on all of these requirements. We survey the characteristics of major pieces of queueing software. Based on this survey we synthesize a set of design objectives for queueing software. Finally, we discuss our own queueing network software, the Research Queueing Package (RESQ), in light of these objectives.     

Product-forms and functional rates

A recent result of Fourneau et al. derives conditions under which the joint state of a set of Markov chains with functional rates has a product-form solution for its equilibrium state probabilities, when they exist. The present note shows how the Reversed Compound Agent Theorem (RCAT) obtains the same result in a few lines. In fact a more general result also follows.     

Component aggregation for PEPA models: An approach based on approximate strong equivalence

Approximate aggregation for PEPA components involves the construction of a smaller component that approximates the behaviour of the original one. Such an approximation at the component level can be very efficient and it can also result in a considerable reduction of the state-space for the underlying continuous-time Markov chain. We propose an approximate PEPA component aggregation strategy that relies on an approximate form of strong equivalence. The notion of strong equivalence captures behavioural similarity between components of different size. This quality renders approximate strong equivalence appropriate as a criterion to aggregate the state-space of PEPA components. We compare our newly proposed approach with previous work on component aggregation, where only a part of the component behaviour has been used as a criterion for aggregation. Our method requires fewer assumptions regarding the form of the components, and is therefore readily applicable to a larger family of PEPA models.     

Product form solution for a class of PEPA models

The advantages of the compositional structure within the Markovian process algebra PEPA for model construction and simplification have already been demonstrated. In this paper we show that for some PEPA models this structure may also be used to advantage during the solution of the model. Several papers offering product form solutions of stochastic Petri nets have been published during the last 10 years. In [R. Boucherie, A characterisation of independence for competing Markov chains with applications to stochastic Petri nets, IEEE Trans. Software Engrg. 20 (7) (1994) 536–544], Boucherie showed that these solutions were a special case of a simple exclusion mechanism for the product process of a collection of Markov chains. The results presented in this paper take advantage of his observation. In particular we show that PEPA models that generate such processes may be readily identified and show how the product form solution may be obtained. Although developed here in the context of PEPA the results presented can be easily generalised to any of the other Markovian process algebra languages.     

Performance Analysis of Retrial Queueing Systems Using Generalized Stochastic Petri Nets

We consider retrial queueing systems, in which an arriving customer finding the server busy, may repeat his call after a random duration. The consideration of repeated calls introduces great analytical difficulties. In fact, detailed analytical results exist for some special retrial queueing systems, while for many others, the performance evaluation is limited to numerical algorithms, approximation methods and simulation. Retrial queues have been widely used to model many problems in telephone switching systems, telecommunication and computer networks. In this paper, we show a method of modelling and analysing retrial queueing systems, using the Generalized Stochastic Petri nets (GSPNs).     

Performance Analysis of a Client–Server System Using Queueing Networks: A Case Study

Queueing networks have been widely used to evaluation performance of mainframe computer systems. In contrast, few results have been reported for modern open systems, so it was not clear whether queueing networks are useful for modern systems or not. We think this situation has partly been due to lack of handy evaluation tools. This paper presents tow tools that we developed to evaluate open system performance. On is a measuring tool that is capable of accurately obtaining the service times of system resources requested by an application transaction. The other is an estimating tool which calculates various performance measures based on queueing network models. This paper also describes a case study in which the performance of a medium-sized UNIX client–server system (up to 24 clients) is estimated using the tools and these estimates are then compared with experimental results. The estimates closely agree with the measured results and are accurate enough for practical applications. Based on this, we conclude that queueing network models are also useful for modern systems.     

A Brownian control problem for a simple queueing system in the Halfin–Whitt regime

We consider a formal diffusion limit for a control problem of a multi-type multi-server queueing system, in the regime proposed by Halfin and Whitt. This takes the form of a control problem where the dynamics are driven by a Brownian motion. In one dimension, a pathwise minimum is obtained and is characterized as the solution to a stochastic differential equation. The pathwise solution to a special multi-dimensional problem (corresponding to a multi-type system) follows.     

基于PEPA的云计算资源分配算法性能评价

资源分配是云计算的核心之一,对云计算资源分配算法的性能进行评价可为云计算平台设计提供指导.讨论了两种云计算资源分配算法,提出了一种基于PEPA的资源分配算法的性能评价模型,该模型通过建立云计算系统中各组件之间的交互关系进行形式化分析和推理,获得了云计算系统性能的评价指标.实验通过分析资源分配过程中不同参数变化对系统性能的影响,结果表明,PEPA模型方法可以直接评估资源分配算法性能的优劣,并能够确定算法性能提升的关键因素,从而减少云平台设计过程的周期.     

Smoothed Perturbation Analysis for Stationary Single-Server Queues with Multiple Customer Classes

Recently, Konstantopoulos and Zazanis (1992, 1994) and Brémaud and Lasgouttes (1993) derive the infinitesimal perturbation analysis (IPA) estimators for the stationary and ergodic G/G/1/ queue using Palm calculus, where neither regenerative structure nor convex property are required and the strong consistency is ensured by ergodic theorem. This work has been motivated by them and derives the smoothed perturbation analysis (SPA) estimator on the stationary and ergodic framework. The problem here is how to treat the catastrophic jumps on the sample path of the steady state and this is solved cleverly by using the Palm calculus. We deal with multi-class queues in this paper but our key formula is expected to be useful to any systems to which the SPA is applicable.     

Effective Routing and Scheduling in Adversarial Queueing Networks

In an adversarial queueing network, the incoming traffic is decided by an adversary, who operates under a reasonable rate restriction. This model provides a valuable, complementary point of view to that of the traditional queueing network model in which arrivals are modeled by stochastic processes. As a result, the adversarial queueing network model has attracted much attention in recent years, especially as a way of modeling packet injections into a communication network. Our main result is a simple, effective packet routing and scheduling algorithm with a provably good performance. Specifically, our algorithm keeps the system stable (bounded number of packets in the system), with the bound on the number of packets in the system that is O((1 - r)^-1), where r can be interpreted as the arrival rate of the packets into the communication network. This improves upon the work of Gamarnik, who designed an algorithm for which the number of packets in the system is O((1 - r)^-2); moreover, our result matches the traditional queueing-theoretic number-in-system bound.     

Fork—Join排队网络的建模与稳定性

本文利用极大代数方法，建立了一类Ｆｏｒｋ—Ｊｏｉｎ排队网络的线性状态方程，分析了系统的稳定性。     

Bio-PEPA: An Extension of the Process Algebra PEPA for Biochemical Networks

In this work we introduce Bio-PEPA, a process algebra for the modelling and the analysis of biochemical networks. It is a modification of PEPA to deal with some features of biological models, such as stoichiometry and the use of generic kinetic laws. Bio-PEPA may be seen as an intermediate, formal, compositional representation of biological systems, on which different kinds of analysis can be carried out. Finally, we show a representation of a model, concerning a simple genetic network, in the new language.     

随机进程代数新技术综述

本文以PEPA语言为例,对近年来发展起来的随机进程代数的缓解状态空间爆炸问题的新技术做一个综述．     

Optimal adaptive server allocation in a network

This paper considers an adaptive version of the problem of Klimov. There are N nodes with a Bernoulli routing and exogenous Poisson arrival processes. The service times are independent and are identically distributed in each node, with an unknown distribution. There is a single server to be allocated in a nonpre-emptive way to the customers. The problem is to minimize the long term average waiting cost per unit of time, for given cost rates in the nodes.The result is that the certainty equivalence controller, that assigns the server optimally assuming that the sample means of the service times are the correct means, is optimal.The analysis is based on results about last exit times of random walks.