(Mahanti:L01, Fall 2005)

- Announcements
- Administrative Details
- Textbooks
- CSIM Software
- Syllabus (Outline, Notes)
- Examples
- Evaluation: Assignments, Midterm, and Final

05/12/05: The final exam review session will be on Thursday, December 8, 2005. Attend if you can.

05/12/05: Lecture notes for the

- Instructor: Professor Anirban Mahanti, ICT 745
- Session/Lectures: L01, TR 15:30 - 16:45 hours, TRB 101
- Office Hours: Thursday 09:30 - 11:30 hours, ICT 745, or by appointment
- Prerequisites: Please refer to the CPSC 531 calendar entry

- T01, WF 11:00 hours in ENC 123, Nadim Parvez
- T02, MW 13:00 hours in ST 55, Sean Boyden

- Discrete-Event System Simulation (Fourth Edition), Banks, Carson, Nelson, and Nicol, Prentice-Hall, 2005. Henceforth, referred to as [BCNN05].
- Simulation Modeling and Analysis (Third Edition), Law and Kelton, McGraw Hill, 2000. Henceforth, referred to as [LK00].

- [Jain91] The Art of Computer Systems Performance Evaluation, Raj Jain, John Wiley and Sons, Inc., 1991.
- [LZGS84] Computer Systems Analysis Using Network Models, Edward Lazowska, John Zahorjan, Scott Graham, and Kenneth Sevcik, Prentice-Hall Inc., 1984. (out-of-print, but available online)
- [Kl75] Queueing Systems - Volume I: Theory, Leonard Kleinrock, John Wiley and Sons, Inc., 1975.
- [DS02] Probability and Statistics (Third Edition), Morris H. DeGroot and Mark J. Schervish, Addision-Wesley, 2002.

**Introduction (1 week)**What is simulation, when to use simulation, simulation terminology, application areas, model classification, types of simulation, steps in a simulation study, advantages/disadvantages of a simulation study

Lecture slides: Introduction (PPT, PDF)

__Readings__: Chapter 1 (omit Sections 1.3-1.5) from [LK00] or [BCNN05]**General Principles and Examples (1.5 weeks)**Concepts of discrete-event simulation, list processing, examples: single-server queueing simulation, time-shared computer model, multi-teller bank with jokeying, job-shop model

Lecture slides: Discrete-event simulation (PPT, PDF), single-server simulation (PPT, PDF), time-shared computer model, multi-teller bank (PPT, PDF)

__Readings__: Section 1.3, Section 1.4, and Chapter 2 from [LK00] or Chapters 2 and 3 from [BCNN05]**Statistical Models (1.5 weeks)**Review of basic probability and statistics, discrete distributions, continuous distributions, empirical distributions

Lecture slides: Probability review part I (PPT, PDF), probability review part II (PPT, PDF), discrete and continuous distributions (PPT, PDF)

__Readings__: Chapter 4, Sections 6.1, 6.2, 6.12 from [LK00] or Chapter 5 from [BCNN05]**Queueing Models (2 weeks)**Queueing systems, important random processes, birth-death queueing systems, Markovian queues in equilibrium

Lecture slides: Introduction to Queueing Systems (PPT, PDF)

__Readings__: Our discussion on the Operational Laws is based on Chapter 33 of [Jain91] and Chapter 3 of [LZGS84]. The second text is available online. Please follow this link.**Generating Random-Numbers (1 week)**Properties of random numbers, techniques for generating random numbers, testing random number generators

Lecture slides: Random-Number Generation (PPT, PDF)

__Readings__: Chapter 7 from [LK00] or [BCNN05]**Generating Random-Variates (1 week)**Inverse-transform technique, acceptance-rejection technique, composition, convolution

Lecture slides: Random-Variate Generation (PPT, PDF)

__Readings__: Sections 8.1,8.2, and 8.3 from [LK00]; Cahpet 8 from [BCNN05]

**Input Modelling (1 week)**Data collection, assessing sample independence, hypothesizing distribution family with data, parameter estimation, goodness-of-fit tests, selecting input models in absence of data, models of arrival processes

Lecture slides: Input modeling (PPT, PDF)

__Readings__: Sections 6.4-6.6, 6.11, and 6.12 from [LK00] or Sections 9.1-9.4, and 9.6 from [BCNN05]**Output Data Analysis (1 week)**Transient and steady-state behaviour of a stochastic process, types of simulations with regard to output analysis, statistical analysis for steady-state parameters

Lecture slides: Input modeling (PPT, PDF)

__Readings__: Sections 9.1-9.5 from [LK00] or Chapter 11 from [BCNN05]**Experiment Design and Sensitivity Analysis (1.5 weeks)**Common mistakes in experimentation, types of experiment design, 2^k factorial designs, coping with many factors

Lecture slides: Experiment design, performance evaluation, graphing tips etc. (PPT, PDF)

**NOTE**: The example used in the lecture notes is derived from the paper Locality Characteristics of Web Streams Revisited by Aniket Mahanti, Anirban Mahanti, and Carey Williamson. This paper appeared in the Proceedings of the SCS Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS), Philadelphia, PA, July 2005.

__Readings__: Sections 12.1-12.3 from [LK00]; additional material will be drawn from [Jain91].

- M/M/1 Simulation in C. Source: Chapter 1 [LK00]
- M/M/1 Simulation using simlib. Source: Chapter 2 [LK00]. Added: Makefile, mm1smlc.c (eliminates the server LIST)
- Input Modeling using Excel

**Assignments (30%)**There will be four assignments in this course. The assignments will consist of a mix of paper & pencil questions, and programming projects.

- Assignment 1, due by
11:59 pm on October 16, 2005. You may find the paper
Quantifying the Properties of SRPT Scheduling by Mingwei Gong and
Carey Williamson relevant and interesting. This paper appeared in the
Proceedings of
IEEE/ACM MASCOTS 2003.

Solution Key (part II) - Assignment 2, due by 11:59 pm on October 31, 2005.
- Assignment 3, due by
11:59 pm on Novermber 18, 2005.

__Credits__: Inspiration for this assignment comes from the extensive literature on Stream Tapping and Patching techniques, including the paper Improving Video-on-Demand Server Efficiency through Stream Tapping by Steven Carter and Darrell Long. This paper appeared in the Proceedings of the IC3N Conference, September 1997. This assignment (more specifically the traffic models and their description) is also inspired by Dr. Carey Williamson's traffic modeling assignment in CPSC 641. - Assignment 4, due by 11:59 pm on December 3, 2005. Solution Key

- Assignment 1, due by
11:59 pm on October 16, 2005. You may find the paper
Quantifying the Properties of SRPT Scheduling by Mingwei Gong and
Carey Williamson relevant and interesting. This paper appeared in the
Proceedings of
IEEE/ACM MASCOTS 2003.
**Midterm Examination (30%)**A 75-minute "closed-book" (no books, no notes) in-class midterm examination will be held on Thursday

**November 3, 2005**. Exam and Solution Key**Final Examination (40%)**This course will have a 120-minute closed-book final examination, scheduled by the Registrar's office. Thursday December 15, from 3:30-5:30 PM at ST 141.