Lecture Performance Evaluation Techniques
Summer 2005
Lecture
Lecturer
Contents
Subsequent courses
News (last update: June 17, 2005)
Materials
Problem assignments
Recommended Literature
Poster Papers
Internet Resources
Lecture
Title
|
Performance Evaluation Techniques
|
Time
|
Monday, 13.30 - 15.00
(Lecture)
Monday, 15.15 - 16.45 (Lecture, Tutorial)
|
First lecture
|
Monday, April 11, 2005
|
Place
|
HPI A-1.1
|
SWS
|
3 SWS Lecture, 1 SWS Tutorial
|
ECTS Credit Points
|
6
|
Enrollment date / Belegungsfrist
|
May 2, 2005
|
Grading criteria
|
bi-weekly problem assignments
50%, oral exam 50%, both parts must be passed separately
|
Examination date
|
to be negotiated
|
Lecturer:
Dr.-Ing. Andreas Willig
Telecommunication Networks Group (TKN)
Technical University of Berlin
Einsteinufer 25
10587 Berlin
Contents:
To start with a quote:
Performance is a key
criterion in the design, procurement, and use of computer [and
communication, AW] systems. As such, the goal of computer systems
engineers, [software engineers, AW], scientists, analysts, and users is
to get the highest performance for a given cost. To achieve that goal,
computer systems professionals need, at least, a basic knowledge of
performance evaluation terminology and techniques. Anyone associated
with computer systems should be able to state the performance
requirements of their systems and should be able to compare different
alternatives to find the one that best meets their requirements.
--- Raj Jain, 1991
The lecture gives an introduction to the field of performance
evalution. The goal is to evaluate certain performance measures
(throughput, delay, response times, number of transactions per unit
time, ...) for existing or future systems. We discuss the three main
techniques for this: measurements can be applied to already existing
systems, while analytical modeling and simulation modeling work for
both
existing as well as future systems. The larger part of the lecture
focuses on simulation modeling. We concentrate on discrete-event
simulations, as they are often appropriate when investigating computer
and communication systems. The lecture provides also an introduction to
analytical techniques. As analytical modeling tool we discuss, after a
brief introduction to stochastic processes including Markov chains, the
subject of queueing theory (QT). In QT the goal is to determine certain
performance measures like system response times for systems where
customers / tasks / packets / ... compete for a single resource
(service
station, processor, communications link, ...) and are enqueued into a
waiting line when the resource is busy.
While the lecture presents the theoretical issues, the tutorial adds
examples and issues of practical interest. Although the performance
evaluation techniques discussed in the lecture are useful in many
different areas (computer systems, communication networks, inventory
systems, manufacturing systems, transportation systems etc.), we will
focus mainly on examples from the areas of computer systems and
communication networks.
A more detailed breakdown of the lecture topics is:
- Introduction, Organization
- Performance evaluation: the big picture
- Measurement-based techniques
- Probability theory and statistics refresher
- Stochastic processes: notion
- Renewal processes, Poisson process
- Markov chains: discrete-time, continuous time (including some
topics of semi-Markov processes)
- Simulation: Introduction, simulation software
- Simulation: Fundamental algorithms (future event set management,
generation of pseudo-random numbers and -variates
- Simulation: workload modeling and generation
- Simulation: specific workload and error models
- Simulation: evaluation of results and run-length control
- Simulation: comparison of systems
- Simulation: experiment planning
- Simulation: selected topics (rare-event simulation, MRIP/SRIP,
variance reduction)
- Intro to queueing theory, Little's law
- Simple Markovian queueing systems
- The M/G/1 system
Subsequent Courses:
I have left the HPI and do not offer own subsequent courses. The
communication systems group
offers a number of lectures and courses in the area of communication
systems. The telecommunication networks group (TKN) at TU Berlin provides also
several courses in the networking area.
News:
- June 17, 2005: The third (and final!) problem sheet is available
- June 12, 2005: Submission of second problem sheet is postponed by
a week, it is now due on Monday, June 20, 2005
- May 28, 2005: The second problem sheet is available
- The lecture from May 2, 2005 was omitted due to sickness, the
lecture from May 9, 2005 was omitted to avoid conflicts with the HPI
ceremony for master and bachelor students. The next lecture will take
place in the week after pentecost, i.e. on May 23, 2005. We will catch
up the omitted lectures. The first problem sheet is due on May 30, 2005.
Materials:
There is a script written by me, covering
most
of the stuff in the lecture in some more detail. As this script is used
the second time for the lecture, significant parts of it are reasonably
stable. However, i might add corrections or new material to the script.
The script itself contains as one of the first chapters a list of
changes and you can check this to see whether you need to download a
new
version. The slides will often change immediately before they are going
to be presented -- after their presentation they will not be changed
anymore and their title is marked with italics.
If you find errors in the script or think of this or that being
crap, an email will be highly appreciated.
Slides:
Problem Assignments:
You are expected to solve a sheet of problem assignments on your own.
The assignments will be handed out in the tutorial, and the solutions
have to be submitted two weeks later, also in the tutorial.
Recommended Literature:
The following books are the most important ones, which cover most of
the material presented in the lecture. You can find further references
in the script.
Fundamentals of Performance Evaluation, Measurements:
- Raj Jain, "The Art of Computer Systems Performance Analysis --
Techniques for Experimental Design, Measurement, Simulation and
Modeling", Wiley, 1991
Simulation Modeling:
- Averill M. Law and W. David Kelton, "Simulation Modeling and
Analysis, 3rd Edition", McGraw-Hill, 2000
- Jerry Banks and John S. Carson and Barry L. Nelson and David M.
Nicol, "Discrete-Event System Simulation", Prentice-Hall, 2000
- Reuven Y. Rubinstein and Benjamin Melamed, "Modern Simulation and
Modeling", Wiley, 1998
Probability Theory, Stochastic Processes and Queueing Theory (suitable
for engineers):
- Leonard Kleinrock, "Queueing Systems -- Volume 1: Theory", Wiley,
1975
- Gunter Bolch, Stefan Greiner, Hermann de Meer and Kishor Trivedi,
"Queueing Networks and Markov Chains -- Modeling and Performance
Evaluation with Computer Science Applications", Wiley, 1998
- Sheldon Ross, "Applied Probability Models with Optimization
Applications", Dover Publications, 1992
- William Feller, "An Introduction to Probability Theory and Its
Applications -- Volume I", 3rd Edition, Wiley, New York, 1968
- Samuel Karlin and Howard M. Taylor, "A First Course in Stochastic
Processes", 2nd Edition, Academic Press, San Diego 1975
- Athanasios Papoulis and S. Unnikrishna Pillai, "Probability,
Random Variables, and Stochastic Processes", 4th Edition, McGraw-Hill,
Boston, 2002
Poster Papers:
I have collected some papers which are interesting for several reasons,
either because they provide nice surveys or they show interesting
performance studies or introduce interesting techniques. For legal
reasons i do not want to put the pdf files directly on the website. If
you want to have one of them, just drop me an email.
- This contains a nice overview on certain stochastic processes
frequently used in traffic modeling of communication networks:
David L. Jagerman, Benjamin Melamed and Walter Willinger, "Stochastic
Modeling of Traffic Processes"; in: J. H. Dshalalow (Editor),
"Frontiers
in Queueing: Models, Methods and Problems", CRC Press 1996
- This contains even more information about traffic modeling in
communication networks (its more a reference paper, in parts tough to
read)
Herman Michiel, Koen Laevens, "Teletraffic Engineering in a Broad-Band
Era", Proceedings of the IEEE, Vol. 85 (1997), No. 12 (Dec), pp.
2007-2033
- A nice study comparing different implementations of a
Web-Proxy-Cache:
Evangelos Markatos, Dionisios Pnevmatikatos, Michail Flouris and
Manolis Katevenis, "Web-Conscious Storage Management for Web Proxies",
IEEE/ACM Transactions on Networking, Vol. 10 (2002), No. 6 (Dec)
- This paper explains how to construct stochastic processes with
desired first and second order statistics:
Glenn Eric Johnson, "Constructions of Particular Random Processes",
Proceedings of the IEEE, Vol. 82 (1994), No. 2 (Feb), pp. 270-285
- This paper shows that much of contemporary research in
communications networks is not without methodological flaws:
Krzystof Pawlikowski, Hae-Duck Joshua Jeong and Jong-Suk Ruth Lee, "On
Credibility of Simulation Studies of Telecommunication Networks", IEEE
Communications Magazine, Vol. 40 (2002), No. 1 (Jan), pp. 132-139
Internet Resources
Simulation tools:
- OMNet++ is a
free simulation tool developed by Andras Varga at the Budapest
University of Technology and Economics. Models are developed in C++ and
the so-called model topology is described in a dedicated language
(called NED). OMNet++ is not focused toward specific applications.
- ns2 (Network Simulator)
is a discrete-event simulator which implements a lot of protocols from
the TCP/IP world. It is programmed in Tcl/Tk and C++.
- GloMoSim
(Global Mobile Information Systems Simulation Library)
- Ptolemy, a
multi-purpose simulation tool with different computational models
Web pages on queueing theory and performance evaluation:
Other resources: