ECE 673: Simulation and Evaluation of Computer Systems and Networks

 
Instructor: C.M. Krishna.

e-mail: krishna@ecs.umass.edu.

Phone: (413) 545-0766.  
 


General Description

This course covers three main topics: (a) How to write programs to simulate computer systems and networks, (b) Statistical tools to analyze the data obtained from simulation models, and (c) Queueing theory to model computers and networks. This course may be useful to graduate students working in computer networks, distributed systems, real-time computers, fault-tolerant computing, and (to a lesser extent) computer architecture.

You should have some prior knowledge of probability theory. ECE 603 would be an excellent source for probability; however, most undergraduate probability courses should also provide enough background. Since there will be a few (two or three) small simulation assignments, you should know how to program in some high-level language. It is also expected that you know the basics of computer organization: this is something covered in most undergraduate curricula.

Grading 
               Test 1........................................22
               Test 2........................................22
               Final examination.............................36
               Homework......................................20
 
 
Main Topics
  • M/M/1, M/M/m, M/G/1 queues (Kleinrock: Chapters 3 and 5).



    • Announcements


    Test 2 Solutions

    Final Exam Solutions



    Test 1 from 2005 Solutions

    Some typos crept into the posted solutions for the 2005 Test 1 and Homework 2: here is a list.

    Test 2 from 2005 Solutions (Note: We have not yet covered some topics that were included on the test last year. For example, we have not studied time reversibility or Markov decision theory.)


    Readings
    We will use two textbooks. I have asked the Integrated Sciences Library to place them both on reserve.
    • S. M. Ross, Simulation, Academic Press. (Either the 2nd or 3rd edition would work.)

    • L. Kleinrock, Queueing Systems Vol 1, Wiley, 1975.
  • Analytical Cache Model
  • Product Form Networks paper


    Lecture Coverage


    When downloading copyrighted material (mostly papers from the literature), please be mindful of copyright restrictions.

    • Lecture 1. Chapter 6 of Ross.
    • Lecture 2. Sections 4.1 to 4.4; 5.1 of Ross.
    • Lecture 3. Sections 4.5, 4.6; 5.2, 5.4, 5.5 of Ross.
    • Lecture 4. Sections 9.1 and 7.1 of Ross.
    • Lecture 5. Sections 7.1 and 7.2 of Ross.
    • Lecture 6. Section 2.5 (up to page 63) of Kleinrock.
    • Lecture 7. Section 3.1 (skip page 94) and Sections 3.2 and 3.5 of Kleinrock. Also review the coverage of z-transforms in Appendix I.2 and II.4 (pages 384-385).
    • Lecture 8. Pages 149-150 of Kleinrock.
    • Lecture 9. Use Buzen's paper as a reference for his convolution algorithm. Here is the reference you should use for operational techniques.
    • Lecture 10. Transform techniques. It may help to review Appendix I and II of Kleinrock before the lecture. In particular, see I.3 and II.4 for a discussion of the Laplace transform. After that, the next topic will be M/G/1 queues: see Sections 5.1 to 5.10 of Kleinrock.
    • Lectures 11, 12, 13: M/G/1 queue. Read Sections 5.1 to 5.10 of Kleinrock. Also look through Section 4.7.
    • Lectures 14, 15, 16: Token-ring networks and vacation systems. Reference: Extracts from Kuehn and from Gallager. Modeling of multistage networks.
    • Lecture 17: Models of multistage networks and of slotted ALOHA.
    • Lecture 18: Random graphs: Modeling sensor and peer-to-peer networks (another application of z-transforms).
    • Lecture 19: Cache model. Reference: Agrawal, Horowitz and Hennessy.
    • Lectures 20, 21, 22, 23: Variance reduction. See Chapter 8 of Ross.
    • Lecture 24: Two-sample problem. See Chapter 9.
    • Lecture 25: Markov decision processes. Hastings-Metropolis Algorithm; Gibbs Sampler (See Chapter 10).


    Homework