Menu

Important Dates

Important Dates

Sponsors

IFIP WG7.3 workshop

On Friday October 21, there will be a one-day IFIP WG7.3 workshop for IFIP WG7.3 members, co-colated to Performance 2011. You are cordially invited to attend, free of charge. If you plan to attend, please register.

For questions regarding the workshop, please contact Rob van der Mei or Susanne van Dam.

Time schedule

09.30-10.00:	Coffee
10.00-10.30:	Uri Yechiali
10.30-11.00:	Hideaki Takagi
11.00-11.15:	Coffee break
11.15-11.45:	Benny van Houdt
11.45-12.15:	Guang Nguyen
12.15-14.00:	Lunch in restaurant "Polder"
14.00-14.30:	Mark Squillante
14.30-15.00:	Lydia Chen
15.00-15.15:	Refreshments
15.15-15.45:	Giuseppe Serazzi
15.45-16.15:	Don Gaver

Talk 1: Uri Yechiali

Tandem Markovian Queues with Unbounded Batch Service

Inspired by the biological process of gene translation and its modeling as a flow of particles through a tandem array of unit-capacity 'servers' - known in biophysics as the Totally Asymmetric Exclusion Process (TASEP), we devise and analyze a new model: the Totally Asymmetric Inclusion Process (TASIP). The TASIP (or ASIP) is a system of n Markovian queues in tandem, each with unbounded batch service. That is, when service is completed at queue k, all particles present at that queue move simultaneously to queue k+1. Equations for the multi-dimensional time-dependent Probability Generating Function (PGF) of the system-state (occupancy) vector at arbitrary time instants, as well as for the PGF at 'event epochs' (arrival or service completion), are derived. We show that, at steady state, the two PGFs coincide - implying a PASTA-type phenomenon. We then explicitly derive the PGFs for systems with n=2, or with n=3, tandem queues, and construct an iterative procedure to derive the PGF for any larger number of queues. We also explicitly compute the mean of the system-state vector at steady state, and establish a Little-type law. Furthermore, we explicitly compute the PGF of the TASIP's total load in steady state, and obtain a stochastic decomposition result, leading to a product-form solution. In addition, we show that the total load variable is independent of the order of the queues. Numerical calculations further demonstrate that the process is highly correlated. Finally, we show that TASIP models with identical service rates are, under various perspectives, optimal.

Talk 2: Hideaki Takagi

Analysis of a Queueing Model for a Call Center with Impatient Customers and After-Call Work

Two essential features needed for queueing models of call centers are impatient customers and after-call work (ACW) of operators. Their effects on the performance are comparable to those of service times. We propose and analyze a queueing model of a call center with impatient customers and ACW. We consider a two-dimensional birth-and-death process for the state combining the number of calls waiting or being served in the system and the number of operators working on ACW. The steady-state distribution is obtained numerically, from which we compute a variety of performance measures, including the blocking probability, the probability of wait, the mean waiting time, the ratio of getting service and abandonment, and the fraction of operators who are serving customers, working on ACW, or being idle at an arbitrary time. Furthermore, we show a method of finding the mean waiting time for those customers who get served and for those who abandon while waiting. Our analysis is validated by numerical examples for a call center model of realistic size, namely 40 operators and 30 incoming telephone lines.

Talk 3: Benny van Houdt

Analysis of Multi-type Queues with Adaptive Arrivals and General Impatience

In this talk we introduce the adaptive MMAP[K] arrival process and analyze the adaptive MMAP[K]/PH[K]/1 queue. In such a queueing system, customers of K different types with Markovian inter-arrival times and possibly correlated customer types, are fed to a single server queue that makes use of r thresholds. Service times are phase-type and depend on the type of customer in service. Type k customers are accepted with some probability a_{i,k} if the current workload is between threshold i - 1 and i. The manner in which the arrival process changes its state after generating a type k customer also depends on whether the customer is accepted or rejected. The solution method exists in reducing the joint workload and arrival process to a fluid queue with r thresholds, the steady state of which is expressed using matrix analytic methods. The time and memory complexity of this approach is also shown to be linear in the number of thresholds, allowing us to study systems with thousands of thresholds. Markovian multi-type queues with customer impatience form a subclass of the queues considered in this talk. A numerically exact method for the probability of abandonment and the waiting time distribution is provided if the patience distributions have finite support, while in the general case numerical examples show that accurate approximate results can be obtained using a step-function approach. Systems with adaptive resources that model certain types of admission and congestion control can also be captured using this framework.

Talk 4: Guang Nguyen

Markov Processes with Denumerably Infinite State Spaces

The modeling and simulation of real-life systems very often require Markov processes with denumerably infinite state spaces. Unless these Markov processes have special structures, it is difficult to compute various performance measures. In such cases, one has to approximate the infinitely-many-state systems by considering their truncated (and possibly augmented) versions and increasing the truncation size until relevant convergence is observed. Even where the sequence of numerical property obtained from the truncated versions converges, there is no guarantee that this limit coincides with the corresponding value of the originally infinite system. In fact, there are established cases in the literature that attest to this lack of continuity, one of which is the tandem Jackson network (Kroese et al. 2004). We investigate the question of whether there is a congruity between the properties of infinite systems and their finite approximations, in two main topics: Quasi-Birth-and-Death processes with both the level and the phase being infinite, and branching processes with infinitely many phases. We focus, in the former, on the convergence of the decay rate of the stationary distribution, and, in the latter, on the convergence of the extinction criteria and the extinction probability vectors. This is joint work with Guy Latouche, Peter Taylor, and Sophie Hautphenne.

Talk 5: Mark Squillante

What About Rob?

Motivated by the 1991 film with a similar name (adjusted to accommodate one of our Dutch hosts), we consider important problems that arise in systems involving complex (and annoying) human behaviors and present a collection of stochastic models and optimization methods that address these problems. The talk will be self-contained and, in particular, no knowledge of the 1991 film will be required.

Talk 6: Lydia Y. Chen

On the Convergence to Fairness in Overloaded FIFO Systems

Many of today's computing and communication systems are based on FIFO queues whose performance, e.g., in terms of throughput and fairness, is highly impacted by load fluctuations, especially in the case of short-term overload. This paper analytically proves that overloaded FIFO queues are fair in the sense that each flow or aggregate of flows tend to receive a proportional fair share of the service rate. The analysis is quite general as it applies to transient/asymptotic time scales for both Markovian and heavy-tailed/self-similar arrival models. These different models are shown to yield fundamentally different convergence rates to the fair shares, i.e., exponentially fast and as a power law, respectively.

Talk 7: Giuseppe Serazzi

Bottlenecks Identification and Performance Optimization in Open/Closed multiclass systems

In this talk we will focus on the bottleneck analysis of closed/open multiclass queueing networks. Algorithms for the identification of the mix of customer classes that lead multiple stations to saturate simultaneously are presented. The optimal operational point at which the system operates satisfying the performance objectives is derived. Asymptotic values of the performance indexes are obtained.

Talk 8: Don Gaver

Towards Performance Analysis of Cloud Computing

This preliminary working paper provides a description of a specific cloud computing architecture, and introduces analytical models for quality of service (QoS); this includes latency. The fluid models represent service that is essentially first-come first-served, but also processor sharing. Numerical examples illustrate the theory.