Past academic year courses: bottom page

Welcome to the 2018-19 web site of Simulation and Performance Evaluation.

This year the course is again in the second semester and we keep trying to improve it and making it more accessible and interesting for students. We use Google Classroom for a more dynamic and agile on-line interaction and for the assignment of personal projects. This site remains the main entry point of the course, but it is a one-way communication channel, and its access is public, thus here you only find public information and official information.

**Google Classroom works by invitation. You have to send me an e-mail (via your official @unitn.it account) and I will invite you to participate.**
In Classroom you will find the course material that is not available here, and also an on-line course I registered as rehearsal of Probability Theory ... useful for those who have never taken a good course on the subject or ... have forgotten it.

You can interact (with some parsimony, please!) both with the Classroom socials and sending me e-mails. You will generally be answered NBD. Please, use e-mails for personal communications and Classroom for topics (e.g., clarification requests) that are of general interest and may sparkle discussions also among you. Remember that the best place to take questions and answers remains the (physical) classroom.

The billboard below is used to convey messages and announcements also to those that cannot be in class, so please check it regularly, though "urgent" matters will be sent via Classroom mailing list.

Slides and other teaching material (including assignments) will be posted in Classroom in due time. Remember that:

1) Classroom does not substitute lessons;

2) Those not registered in Classroom will not be assigned the ... assignments, so they will not be able to take the exam.

Monday 16.30-18.30, Room A108; Wednesday 11.30-13.30, Room A108

**Lessons we will loose (for different reasons)**

- Monday February 25, Monday March 11, Wednesday March 13, ... and possibly others
- We will probably need to find some slots to recover these lessons

**Friday April 26: The lesson on Monday April 29 will be held regularly contrary to what was originally planned.**- April 1: (not a joke!) next wednesday April 3 teaching is suspended for the career days.
- March 17: remember next week we do not have lessons because teaching is suspended for the graduations.
- March 8: next Monday March 11 the lesson is suspended.
- February 20: Remember that next Monday the lesson is suspended.

Please, refer to ESSE3 and the syllabus relative to Simulation and Performance Evaluation for the official course content.

This said, let's try to understand a bit better the course goals and the course content, which, up to some point, will also be twisted and tweked based on how we came to know each other during the first few lessons. Performance Evaluation (PE for short) is central to all systems design, and ICT systems are no exception. Event driven simulations or just Simulations to be brief, are one of the means to evaluate performance, but since very often the term "simulation" is used with different meanings, and since it is unfortunately widespread to think about simulations in bery vifferent terms, we explicit it in the title of the course that Simulation techniques and methodologies are part of this course.

The main objective of the course is defining what PE means, what are the applications areas, and why it is (or should be) a centerpiece of any system design ... including computers, software, the Internet, and applications in general. Very often performance is just seen as speed ("how fast is your system"?), but it is not a great intellectual feat to understand that speed alone is not sufficient: even a racing car can be the fastest of the lot, but if it breaks down it does not win the race! So reliability is part of performance, availability too, and dependability even more, specially for mission-critical systems.

One of the major issues we will have to clarify is that performance is rarely (if ever) a simple number, but it has to be expressed in stochastic terms, and often as complex vectors of time-dependent variables, and this explain why the starting point of our course is some reasonable knowledge of Probability and Statistics (which in turn imply some reasonable knowledge of Analysis). And we give for granted that, as you all are graduate students of Computer Science, you are all much better than me in programming techniques and software engineering, so that the implementation of simple algorithms, drawing some graphs and manipulating matrices and programs outputs is not a problem.

We will try to make a logical path that starts from systems, simple or complex as they are; understand, given the system, what are the relevant metrics that define their perfromance, and what are the dependencies between different metrics and different subsystems. Once we have understood what are the metrics of interest and their relationships, we have to take a tough decision to evaluate performance: shall we measure them on the real system (possibly building it), simulate the system, or devise an analytical model?

We will start from measures, or better, from the interpretation of measure points and from the design of a correct experimental setup do do the measures. We will use a simulator as if it were a real system, because this gives us more flexibility ... and makes experiments much, much cheaper!

Next we will introduce simulations, understand what they really are from a mathematical point of view, and learn the basics to design a simulator.

Finally we will make some examples of systems that are prone to an analytical modeling and how these models can be solved to yield results that are otherwise impossible to obtain.

We do not have an official textbook, because the course covers the enormously vast topic of Perfroamcne Evaluation with a "breadth first" approach, so that we would end up using chapters of many different books, and it is not worth buying them. However, I report here some selected books that for one reason or another are relevant for the course ... and try to explain why.

**Book No. 1:**

K.S. Trivedi,
**"Probability and Statistics with Reliability, Queuing, and Computer Science Applications", **

ISBN: 0-471-33341-7

can be bought on-line at Amazon or directly from the Wiley Web Site .

2-3 copies are available in the University Libraries;

The first five Chapters plus Chapter 10 of this book contain all the background in probability and statistics we need for the course. Indeed, I think there is much more than what you already know, but I do not have control on the courses you took at the Bachelor, thus I cannot be more precise. In conclusion: don't be too scared if some of the material looks new or if some details are beyond your knowledge, we'll rehearse these more advanced parts. If instead you have problems with Bayes rule, feel uncomfortable with percentiles and find difficult to compute the probability that an exponential RV with mean μ is larger than 2μ, then it is probably better to devote some time to study these Chapters.

**Book No. 2: **

R. Jain,

**"The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling,"**

Wiley-Interscience, 1991,

ISBN:0471503361

This book is very old, so I do not advise to buy it, but it is still the only one I'm aware of that tackles the entire range of Performance Analysis techniques in the context of Computer Science, thus it is a good reference for the subject as a whole, while taking examples are "real cases" is today a bit outdated.

**Book No. 3: **

G. Bolch, S. Greiner, H. de Meer, K.S. Trivedi,
**"Queueing Networks and Markov Chains: Modeling and Performance Evaluation With Computer Science Applications"**,
*Wiley-Interscience; 1998*

ISBN: 0-471-19366-6

(can be bought on-line AT Amazon or directly from the Wiley Web Site).

This is a very good and advanced book on the use of Markov Chains and Queueing Networks for performance evaluation, but it is definitely not needed for our course, where analytical modeling will be at most 1/3 of the course: this book covers all what we do in just a few pages.

The exam is composed of the **assignments we give you during the course through the Google Classroom platform**, plus an oral discussion and colloquium.
All assignments are individual, meaning that each of you have to deliver a report (limited in length, to avoid that you write too much).
There will be 2 assignments during the course; the first one (on data analysis) should take about 8-10 hours to complete,
the second one is devoted to simulations and it is longer. It will take 20-30 hours depending (mainly) on your programming skills. Further details will be given later on.

The oral discussion can include clarifications on the assignements and reports and questions on analytical modeling techniques, from markov Chains to Queues and Queueing Networks. The outcome is a blend of the quality of your reports and the oral discussion; however, you cannot come with assignments perfectly done to the oral, and then be unable to even discuss what is their meaning, in this case the oral dominates, and you may even fail the exam.

All reports must be written in English and also the clarity of the language is part of the evaluation, while the oral can be taken both in English or in Italian as you prefer. Michele Segata will help me with assignments and their evaluation.

**How to pass your exam.**
As described above you have to do your assignments. You have to deliver themo on-time. The first assignment within 30 days from the assignment and the second one within June 30. Once you deliver them we can agree on a date for the oral discussion. The oral can be anytime, we do not have to do it on the official date of the exam on ESSE3, those are only formal dates to let students register for the exam. In general my preference is that you do not let too much time pass between the assignments and the oral, but it is perfectly fine to do the assignments during the course and then take the oral in July or September. Indeed, once the assignments have a positive evaluation they are valid forever ... well, let's say until I retire!

When you ask for the oral date, please keep in mind that I might be unable to offer a "slot immediately", so try to send me an e-mail at leasty 7-10 days in advance.

**Forthcoming Official Dates**

- June, July and September 2019

Refer to ESSE3 for the remaining burocracy.

**Please remember to register for the exam before delivering your material and reserve for the oral discussion!**

The slides are provided to help taking notes. "Reading" the slides is definitely not enough to study the course. Additional material, if present, normally refers to somthing we discussed in class, but may have different notation or cover more than we actually did.

Here you only find the course presentation (slides and a short video) and introduction, the rest of the material is available in Google Classroom once you logged in.

**Google Classroom works by invitation. You have to send me an e-mail (via your official @unitn.it account) and I will invite you to participate.**

Course introduction: a short video, mainly for students coming from other Universities ... but not only.

- Course presentation, rules, exams, and the program at large.
- The systems we consider for performance evaluation, the need for a model, an example of possible systems with many facets, common concetual mistakes in PE, the three methodologies for PE: Measures, Simulations, Analysis.
- Overview of Stochastic Processes. At this point we must be familiar (very familiar!) with probabilities. The key concepts we rely upon are presented in the five videos in Classroom. As stochatic processes are time functions of random variables, lack of understanding of probabilities or weaknesses in manipulating RVs, distributions, and key concepts as moments, means, mode value, median, percentiles may hamper further understanding.
- Measures as outcomes of an SP: Population and Sample. Plotting data, finding model parameters through functions (moments) of the data, point estimates and bias, data correlation, confidence intervals and examples of distribution models.
- Some basic notions on MLE and Regression; it is a very fast excursus to have the fundamental notion on when to use and when not to use MLE.
- A primer on 'R'
- PDF Slides
- .csv file for the exercises
- .R file with the examples used in class

- The art of modeling: how do we build a mathematical model starting from a system? How good is a model? Examples from different areas.
- Solving and Using Markov Chains: the theory that allows finding closed form solutions for the steady state distribution of MC (both DT and CT), and how to use this to predict performance.
- Foundation of discrete event simulations and DES design principles, examples and presentation of the simulator we'll use for the second assignment.
- A "primer" on trivial MAC protocols we'll use for Assignment 2 and 3, and explanation of Assignment 2.
- Single station queueing systems: Solution of Makovian queues and beyond.
- Queueing Networks: Systems of Interconnected queues, form Jackson queues to the BCMP theorem
- Here we have a collection of markovian modeling examples, starting from a selection of most influential ones, meaning those that have influenced the course of technology and society, followed by some examples drawn from my experience and that of some colleagues; you may be required to "discuss" one of this models at the exam, meaning to be able to explain, paper at hand, what technique has been used and what are its key contributions and results.
- THE FIVE GREATEST APPLICATIONS OF MARKOV CHAINS a paper presenting the 5 most relevant applications of Markov theory (in the authors' opinion); it appeared on the 100th anniversary of Markov Chain "invention".
- The Classical Bianchi's Model one of the most cited papers in Computer Science ever, disclosing the behavior and efficiency of 802.11 in saturation conditions. Here's the link to the publisher official page
- A Markovian Model to generate packet-level Internet traffic. An MMPP model is a Markov Chain that modulated Poisson arrivals; making a long paper short, an MMPP allows introducing memory into the rate of the packet generation process, thus approximating, with a high degreee of accuracy, the Long Range Dependence (an autocorrelation function with slow decay) exibited by the Internet traffic. Here's the link to the publisher official page
- A sequel of papers that use BCMP queueing networks to model the dynamic behavior of closed loop tranport layer protocols (TCP) over the Internet. There is a progression of accuracy in modeling, starting from the basic idea, to modeling long-lived connections over a single bottlenek, to finite flows and multiple bottlenecks. The first one is pretty easy and does not require to know details about TCP.

The assignments are parte of the exam, indeed a large part of it. We have two different assignemnts, the first one requiring 8-10 hours of work and the second one, longer, 20-30 hours of work ... provided you have already studied the relative theory! The first one is on simple measures and data statistics; the second one is on simulation. The exam is however a single "entity" and the grade will be assigned only at the end of the oral discussion. You can, however, have support and feedback on the assignments.

- A template in LaTex explaining how to write a decent (if not good) report. You are free to use any word processor you like, but don't complain or blame it on us if the result is bad and/or the format requested difficult to achieve.

**Google Classroom works by invitation. You have to send me an e-mail (via your official @unitn.it account) and I will invite you to participate.**

**Assignment 1 is available in Classroom****Assignment 2 is available in Classroom**