Markovian bulk service queue with delayed vacations

An M/M(a, b)/1 queueing system with multiple vacations is studied, in which if the number of customers in the queue is a - 1 either at a service completion epoch or at a vacation completion point, the server will wait for an exponential time in the system which is called the changeover time. During this changeover time if there is an arrival the server will start service immediately, otherwise at the end of the changeover time the server will go for a vacation. The duration of vacation is also exponential. This paper is concerned with the determination of the stationary distribution of the number of customers in the queue and the waiting time distribution of an arriving customer. The expected queue length is also obtained. Sample numerical illustrations are given.     

Performance evaluation of multicast communication in packet-switched networks

In this paper we describe the theoretical background and practical application of QNA-MC (queueing network analyser supporting multicast), a tool for the analytical evaluation of multicast protocols. QNA-MC is based on the QNA method, which (approximately) analyses open networks of GI|G|m queues. In contrast to standard QNA, QNA-MC allows for the specification and evaluation of multicast routes. As in real multicast communication, packets leaving a particular node can be copied and deterministically routed to several other nodes. In order to analyse such queueing networks, QNA-MC converts the multicast routes to a suitable input for standard QNA. From the results delivered by QNA, QNA-MC then derives several performance measures for multicast streams in the network. A validation of QNA-MC, via a comparison to simulation results, shows that QNA-MC yields very good results. Finally, we give a detailed application example by evaluating different multicast routing algorithms for a realistic video conferencing scenario in the European MBONE.     

Performance evaluation of a multithreaded RTS using a synchronous reactive model

Synchronous reactive modelling provides an optimal framework for the modular decomposition of programs that engage in complex patterns of deterministic interaction, such as many real-time and communication entities. This paper presents an approach which includes performance modelling techniques in the synchronous reactive modelling method supported by ESTEREL. It defines a methodology based on timing and probabilistic quantitative constructs that complete the synchronous reactive models. A monitoring mechanism allows the computation of performance results during the simulation. This methodology is applied to study a multithreaded runtime system for a distributed functional programming language. Performance metrics are computed and validated with experimental results.     

Modelling congestion in closed queueing networks

We will consider the problem of identifying regions of congestion in closed queueing networks with state-dependent service rates. A particular queue will be called a bottleneck if the number of customers in that queue grows without bound as the total number of customers in the network becomes large. We will review methods for identifying potential bottlenecks, with a view to controlling congestion. We will see that the problem of identifying bottlenecks can be reduced to one of finding them in an isolated subnetwork with suitably modified routing intensities. Several special cases will be studied, illustrating a range of behaviour. For example, it is possible for a subnetwork to be congested, yet each queue in that subnetwork is not strictly a bottleneck.     

A Taxonomy of Inference in Simulation Models

Simulation models have become increasingly popular in economics in the last two decades, because they can deal with a wide range of research questions. The set-up and analysis of simulation models can range from very specific to very general and can be underpinned by different combinations of theoretical considerations and empirical data. We offer a taxonomy of existing simulation approaches and show how their results can be used to explain observed economic features, examine economic systems and predict future economic processes. Moreover, we offer a new type of method that helps to better exploit empirical findings in simulation models.      

On priority queues with priority jumps

In this paper, we investigate a simplified head-of-the-line with priority jumps (HOL-PJ) scheduling discipline. Therefore, we consider a discrete-time single-server queueing system with two priority queues of infinite capacity and with a newly introduced HOL-PJ priority scheme. We derive expressions for the probability generating function of the system contents and the packet delay. Some performance measures (such as mean and variance) of these quantities are derived and are used to illustrate the impact and significance of the HOL-PJ priority scheduling discipline in an output queueing switch. We compare this dynamic priority scheduling discipline with a first-in, first-out (FIFO) scheduling and a static priority scheduling (HOL) and we investigate the influence of the different parameters of the simplified HOL-PJ scheduling discipline.     

Conditioned asymptotics for tail probabilities in large multiplexers

Consider a buffer whose input is a superposition of L independent identical sources, and which is served at rate sL. Recent work has shown that, under very general circumstances, the stationary tail probabilities for the queue of unfinished work Q in the buffer have the asymptotics P[Q > Lb] ≈ e^−LI(b) for large L. Here the shape function, I, is obtained from a variational expression involving the transient log cumulant generating function of the arrival process.

In this paper, we extend this analysis to cover time-dependent asymptotics for Markov arrival processes subject to conditioning at some instant. In applications we envisage that such conditioning would arise due to knowledge of the queue at a coarse-grained level, for example of the number of current active sources. We show how such partial knowledge can be used to predict future tail probabilities by use of a time dependent, conditioned shape function. We develop some heuristics to describe the time-dependent shape function in terms of a reduced set of quantities associated with the underlying arrivals process and show how to calculate them for renewal arrivals and a class of ON-OFF arrivals. This bypasses the full variational calculation of the shape function for such models.     

A queueing theoretic approach for performance evaluation of low-power multi-core embedded systems

With Moore’s law supplying billions of transistors on-chip, embedded systems are undergoing a transition from single-core to multi-core to exploit this high transistor density for high performance. However, the optimal layout of these multiple cores along with the memory subsystem (caches and main memory) to satisfy power, area, and stringent real-time constraints is a challenging design endeavor. The short time-to-market constraint of embedded systems exacerbates this design challenge and necessitates the architectural modeling of embedded systems to reduce the time-to-market by expediting target applications to device/architecture mapping. In this paper, we present a queueing theoretic approach for modeling multi-core embedded systems that provides a quick and inexpensive performance evaluation both in terms of time and resources as compared to the development of multi-core simulators and running benchmarks on these simulators. We verify our queueing theoretic modeling approach by running SPLASH-2 benchmarks on the SuperESCalar simulator (SESC). Results reveal that our queueing theoretic model qualitatively evaluates multi-core architectures accurately with an average difference of 5.6% as compared to the architectures’ evaluations from the SESC simulator. Our modeling approach can be used for performance per watt and performance per unit area characterizations of multi-core embedded architectures, with varying number of processor cores and cache configurations, to provide a comparative analysis.     

Time-bounded reachability in tree-structured QBDs by abstraction

This paper studies quantitative model checking of infinite tree-like (continuous-time) Markov chains. These tree-structured quasi-birth death processes are equivalent to probabilistic pushdown automata and recursive Markov chains and are widely used in the field of performance evaluation. We determine time-bounded reachability probabilities in these processes-which with direct methods, i.e., uniformization, result in an exponential blow-up-by applying abstraction. We contrast abstraction based on Markov decision processes (MDPs) and interval-based abstraction; study various schemes to partition the state space, and empirically show their influence on the accuracy of the obtained reachability probabilities. Results show that grid-like schemes, in contrast to chain- and tree-like ones, yield extremely precise approximations for rather coarse abstractions.     

Modeling parallel and distributed systems with finite workloads

In studying or designing parallel and distributed systems one should have available a robust analytical model that includes the major parameters that determine the system performance. Jackson networks have been very successful in modeling computer systems. However, the ability of Jackson networks to predict performance with system changes remains an open question, since they do not apply to systems where there are population size constraints. Also, the product-form solution of Jackson networks assumes steady-state and exponential service centers or certain specialized queueing discipline. In this paper, we present a transient model for Jackson networks that is applicable to any population size and any finite workload (no new arrivals). Using several non-exponential distributions we show to what extent the exponential distribution can be used to approximate other distributions and transient systems with finite workloads. When the number of tasks to be executed is large enough, the model approaches the product-form solution (steady-state solution). We also, study the case where the non-exponential servers have queueing (Jackson networks cannot be applied). Finally, we show how to use the model to analyze the performance of parallel and distributed systems.     

A systematic modelling and simulation approach for JIT performance optimisation

Robust computer aided simulation and modelling tools help to visualise, analyse and optimise complex production processes with a reasonable amount of time and investment. A review of the literature shows that simulation and modelling have not been extensively applied in just-in-time (JIT) manufacturing environments. Also there remains a lack of a comprehensive mechanism to identify the most significant JIT drivers for the purpose of system process optimisation. The prime objective of this study is to close this gap by applying computer based simulation tools and linear mathematical modelling to identify the impact of selected key JIT parameters on performance in an automotive component-manufacturing environment. Research shows that variables such as inconsistent task distribution, variation on operator performance, misconception of total quality management philosophy and lack of set-up time elimination plans disrupt ideal JIT production. In this study, ProModel simulation and modelling software is used to model and simulate different experimental scenarios in order to understand and quantify the impact of selected input key JIT variables on objective functions (i.e. process time and takt time). The outcome is a robust mathematical model that highlights the significance of JIT drivers in the manually operated mixed-model assembly lines.     

Markov chain representations of discrete distributions applied to queueing models

We present applications of Markov chain based representations of discrete renewal distributions to queueing models, and extend the notion of that representation to some non-renewal discrete distributions. Two representations are considered; one based on remaining time, the other on elapsed time. These representations make it easier to use matrix-analytic methods for several stochastic models, especially queueing models, thereby allowing us to develop better algorithmically tractable procedures for their analysis. Specifically, they allow us to capitalize on the resulting special structures. We first discuss some key measures of these distributions using phase type distribution results, including some time reversibility relations between the elapsed and remaining time representations. We then show applications to the MAP/G/1, the GI/MSP/1 and the GI/G/1 systems, and briefly explain how the representations of the non-renewal types of discrete distributions can be used for the MRP/SMP/1 system. The emphasis of this paper is about efficient procedures for the R and G matrices associated with these queueing models.     

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.     

基于排队网络的容量分析与模拟

客户机／服务器模型（Client/Server)是当前计算机网络系统应用最广泛的模型。为了提高系统的服务等级（Degree of Servier),找到制约系统性能的瓶颈,对系统进行分析以及模拟就显得十分的重要。基于排队网络建立了客户机／服务器模型。介绍了排队网络的MVA算法,并提出了一个近似的算法。并且,结合一个实例介绍了如何进行系统性能分析;最后,用离散事件模拟工具（Discrete Events Simulation Tool)OMNET进行了模拟,验证了分析的可靠性。     

再访GI/M/1排队

通过构造两个向量马氏过程重新探讨了GI/M/1排队,某些新结果如忙期和闲期的联合分布被得到了.这一方法容易推广到服务时间为无限位相型分布的GI/SPH/1排队.     

Probabilistic weak simulation is decidable in polynomial time

This paper considers a weak simulation preorder for Markov chains that allows for stuttering. Despite the second-order quantification in its definition, we present a polynomial-time algorithm to compute the weak simulation preorder of a finite Markov chain.     

Optimal resource allocation for time-reservation systems

This paper studies the optimal resource allocation in time-reservation systems. Customers arrive at a service facility and receive service in two steps; in the first step information is gathered from the customer, which is then sent to a pool of computing resources, and in the second step the information is processed after which the customer leaves the system. A central decision maker has to decide when to reserve computing power from the pool of resources, such that the customer does not have to wait for the start of the second service step and that the processing capacity is not wasted due to the customer still being serviced at the first step. The decision maker simultaneously has to decide on how many processors to allocate for the second processing step such that reservation and holding costs are minimized. Since an exact analysis of the system is difficult, we decompose the system into two parts which are solved sequentially leading to nearly optimal solutions. We show via dynamic programming that the near-optimal number of processors follows a step function with as an extreme policy the bang-bang control. Moreover, we provide new fundamental insights in the dependence of the near-optimal policy on the distribution of the information gathering times. Numerical experiments demonstrate that the near-optimal policy closely matches the performance of the optimal policy of the original problem.     

Tail Asymptotics for Discrete Event Systems

In the context of communication networks, the framework of stochastic event graphs allows a modeling of control mechanisms induced by the communication protocol and an analysis of its performances. We concentrate on the logarithmic tail asymptotics of the stationary response time for a class of networks that admit a representation as (max,plus)-linear systems in a random medium. We are able to derive analytic results when the distribution of the holding times are light-tailed. We show that the lack of independence may lead in dimension bigger than one to non-trivial effects in the asymptotics of the sojourn time. We also study in detail a simple queueing network with multipath routing.

Performance analysis using Petri nets

The purpose of this paper is to focus on the implementation issues associated with using Petri nets for the performance analysis of discrete event dynamic systems while demonstrating several applications in manufacturing systems. Practical modeling issues will be discussed and several applications will be presented that illustrate the advantages and limitations of this methodology. These issues lead to the definition of several research problems in Petri nets for performance analysis.