PERFORMANCE '96

Lausanne, October 7-11, 1996

International Conference on Performance Theory, Measurement
and Evaluation of Computer and Communication Systems
(Organised by IFIP WG7.3)


Programme




TUTORIALS

Monday 7 October

14:00 - 15:30 / 16:00 - 17:30 : TUTORIAL 1:
Issues in Trace-Driven Simulation
David R. Kaeli, Northeastern University
Richard A. Uhlig, Intel Microcomputer Research Lab., Portland

Considerable effort has been devoted to the development of accurate trace-driven simulation models of today's computer systems. Unfortunately many modelers do not carefully inspect the input to their models. The fact is that the output of any model is only as good as the input to that model.

We present many of the issues related to the input traces used in trace-driven simulation. A description of the different types of traces is provided, followed by survey and discussion of the following trace issues:

Some more theoretical aspects of trace-driven simulation will be discussed. Recent work on marked point process synthetic trace modeling will be presented.

The aim of this tutorial is to equip modelers with enough information about the different trace types and tracing methodologies, so that they can be more critical of the quality of the input traces used in their trace-driven simulations.

This tutorial is designed for both the investigative computer scientist as well as the practicing computer designer.




14:00 - 15:30 : TUTORIAL 2

Error Bound Analysis for Queueing Networks
Nico M. van Dijk, University of Amsterdam

Queueing Networks are known to provide a useful modelling and evaluation tool for a variety of practical systems, most notably in manufacturing, telecommunications and computer performance evaluation. Practical features such as finite capacities, breakdowns, dynamic routing and non- exponentiality usually prohibit analytic solutions.

then become of natural interest, all of which are often based upon some form of a system modification or rather a comparison of a system under different conditions. This tutorial aims to describe and survey a technique to conclude comparison results and error bounds for comparing performance measures of a system under different circumstances. Most notably, this includes: The advantages and disadvantages of this technique, which is based on recursive or dynamic Markov reward structures, compared with the standard stochastic comparison or simple path approach will be outlined. To illustrate and support the results a number of practical queueing network applications will be presented. These applications cannot be solved analytically, but it will be shown how simple performance bounds or approximations with analytic error bounds can be provided. The applications include simple expressions for Some recent extensions to non-exponential queueing networks are given such as leading to simple bounds for GIlGlclctm-systems, finite tandem queues with non-exponential input, or non-exponential Jacksonian networks.




16:00 - 17:30 : TUTORIAL 3

Queueing Networks with Finite Capacity Queues and Blocking

Simonetta Balsamo, University of Udine, Department of Mathematics and Computer Science

Queueing network models with finite capacity queues and blocking are used to represent systems with finite capacity resources and with resource constraints, such as computer and communication systems, production and manufacturing systems. This tutorial introduces queueing networks with finite capacity queues and blocking, their properties and the main solution methodologies for their analysis. We present and define the model and various blocking types, which represent different behaviours of real systems with limited resources. We provide some application examples of this class of models to distributed computer systems, communication networks and production systems. We give a survey of the main analytical exact and approximate solution methods proposed in the literature for queueing networks with finite capacities. We focus on the class of product form networks with finite capacities, which include both homogeneous and non-homogeneous models. Equivalence and insensitivity properties between queueing network models with blocking are presented, including the comparison between models with and without blocking and between models with different blocking types both homogeneous and non-homogeneous. Finally, we present some equivalence results, properties and solution techniques for the passage time distribution in closed models.


Tuesday 8 October

9:00 - 10:30 / 11:00 - 12:30 : TUTORIAL 4
Parallel Simulation Algorithms and Software
Richard M. Fujimoto, Georgia Tech, College of Computing
Philip Heidelberger, IBM T.J. Watson Research Center

This tutorial surveys selected topics in parallel discrete event simulation. We emphasize the key algorithms required to support parallel simulations and publically available software tools that can be used to build parallel simulation models. Both conservative and optimistic approaches will be covered. Examples will be given illustrating both the range of speedups that have been obtained using these tools and the major factors affecting speedup. Part I will cover introductory material, optimistic techniques, and the GTW (Georgia Tech. Time Warp) system. Part II will cover conservative techniques, The Utilitarian Parallel Simulator (U.P.S.) and other parallel simulation software systems such as SPEEDES and MAISIE.




11:00 - 12:30 : TUTORIAL 5

Discrete Time Queueing Networks: Recent Developments:
Hans Daduna, Universitaet Hamburg, Institut fur Mathematische Statistik

The emerging new techniques for broadband communication systems revived discrete time queueing theory, especially queueing networks as a tool for modeling and evaluating such systems. The tutorial will be centered around explicit expressions for the steady-state behaviour of discrete time queueing networks. Three classes of networks which show a product-form equilibrium will be discussed in detail:

  1. Linear networks (closed cycles and open tandems) of single server FCFS Bernoulli nodes.
  2. Networks of doubly-stochastic queues (which are discrete time analoga of Kelly's symmetric servers): Customers of different types move through the network governed by a general routing mechanism and request for service according to general distributions.
  3. Networks with batch movements of customers and batch service. The service and routing mechanism is defined on the basis of an abstract transition scheme. We shall discuss computational algorithms for the standard performance measures and present results on the end-to-end-delay distributions and their moments. Open problems and directions for further research will be sketched.




14:00 - 15:30 : TUTORIAL 6

Structured Analysis Approaches for Large Markov Chains
Peter Buchholz, Universitaet Dortmund, Informatik IV

Analysis of Markov chains is a common approach to analyze the performance, dependability and performability of computer and communication systems. Unfortunately, models of realistic systems often yield extremely large state spaces which can not be analyzed with standard means on contemporary workstation equipment.

Recently new analysis methods have been proposed to exploit the structure of the model for the numerical analysis of the resulting Markov chain. These structured analysis approaches need significantly less memory than conventional methods andallow the analysis of very large Markov chains. Structured analysis techniques have now reached an established state and first modeling tools including the techniques are available. The tutorial introduces the basic ideas of structured analysis, presents efficient analysis algorithms and reviews current research topics in this area.




14:00 - 15:30 : TUTORIAL 7

Benchmarking
Reinhold Weicker, Siemens Nixdorf

Benchmark results play an important role, both as one of the foundations for customer purchasing decisions, and as the source of input data for statistical modelling. For informed decisions, users should therefore know what they measure and what they don't measure. The tutorial covers the following topics:

  1. A look back at the experiences with older standard benchmarks like Dhrystone, Whetstone, Linpack
  2. Current CPU benchmark suites: SPEC95, SPEC HPC, SPEC92
  3. Benchmarks for transaction-oriented systems: TPC benchmarks
  4. SPEC's system benchmarks: SDM, SFS, Web server benchmarks
  5. Critical issues with the current use (and possibly misuse) of the SPEC CPU benchmarks
The author draws mainly from his experience with the SPEC benchmarking group. However, the opinions expressed are his own and not necessarily official positions of SPEC.




16:00 - 17:30 : TUTORIAL 8

An Introduction to Large Deviations and its Applications to Teletraffic Engineering:
John Trevor Lewis and Raymond Russell
Dublin Intitute for Advanced Studies, Applied Probability Group

In a queue with finite buffer-size, why does the frequency of buffer-overflow fall off exponentially with increasing buffer-size? What determines the exponential rate of decrease? These and other questions of importance for the management of traffic on high-speed networks are answered by the THEORY OF LARGE DEVIATIONS. Large Deviation Theory is one of the most active research areas in probability theory and its use of mathematics can appear forbidingly difficult. However, the underlying ideas are very simple. This tutorial provides an exposition of those ideas which addresses the concerns of teletraffic engineers. We begin with a discussion of the law of large numbers for coin-tossing, using visual aids to examine the rate at which the limit is approached. This leads easily to the concept of a RATE-FUNCTION. We explore the ideas behind VARADHAN'S THEOREM, leading to the concept of the SCALED CUMMULANT GENERATING FUNCTION (SCGF). We explore the GLYNN-WITT THEOREM, which answers the questions we began with, and discuss EFFECTIVE-BANDWIDTH. We take a brief look at the estimation of the rate-function of traffic on a high-speed network and finish by reviewing some recent Large Deviation results in this area.





CONFERENCE

Wednesday, October 9, 1996

Thursday, October 10, 1996

Friday, October 11, 1996



Laboratoire de Réseaux de Communication

Back to Performance '96 homepage...

Form more information contact : perf96-info@lrc.epfl.ch.