EE 641 Queueing Theory: for Performance Evaluation

Course Index: 25214
Section Number: 1

Date: 8/13/98

Brief Description: This is a graduate level course on queueing theory. Queueing theory is a mathematical (and operations research) discipline of studying of how server(s) serve jobs. It can be applied to the performance evaluation of communication networks and computer systems. In this course we will examine some of the classical and current techniques of queueing theory and other performance evaluation methods, with an emphasis on applications to network and computer systems.

Prerequisite: EE 342 (undergraduate probability) or equivalent, and EE 150 (programming in C) or equivalent.

Instructor: Galen Sasaki

• Office: Holmes 436
• Office Hrs: MWF 10:30-11:30am
• Email: sasaki@spectra
• Tel: 956-6103

Classes:

• Room: Holmes 241.
• Time: MWF 9:30-10:20am

Textbook:

• Queueing Theory Vol. 1 by L. Kleinrock.
• High-Performance Communication Networks by J. Walrand and P. Varaiya

Topics: (This list, especially latter half, is subject to change depending on how we progress.)

1. Review of Undergraduate Probability [ 1 week ]
2. Markov Chains [ 2 weeks ]
   • Discrete time
   • Continuous time
   • Applications: e.g., reliability
   • Simulation and numerical analysis methods
3. Elementary Queueing Theory [3 weeks ]
   • Little's Theorem
   • Poisson arrival process
   • Birth-death proceses, e.g., M/M/1, M/M/m/m,...
   • Application: leaky-bucket analysis
   • Application: circuit switched networks
   • Discrete event simulation, confidence intervals
4. Intermediate Queueing Theory [ 2 weeks ]
   • Renewal Processes
   • M/G/1 queue and variations (e.g., vacations, priority queueing)
   • Networks of Queues (e.g., reversibility and product-form solutions)
5. Other Performance Evaluation Methods [ 5 lectures ]
   • Momemt matching approximations (1 week)
     • Application: Head-of-line blocking
     • Application: Overflow traffic in circuit switched networks
   • Markov decision processes (brief) (1 week)
   • Deterministic traffic models (sigma-rho traffic) (2 weeks)
     • sigma-rho traffic model and basic network elements
     • QoS service policies, e.g., GPS, PGPS (WFQ), Virtual Clock Service,...
   • Self-similar traffic (brief, 1 or 2 lectures)

Assignments

• Midterm 1 (20%)
• Midterm 2 (20%)
• Final Exam (20%)
• Final Project (20%): Project will include reading of a research(s) paper and giving
  • Oral presentation
  • Written report (around 12 pages)
  The purpose of the project is to familiarize students with current research literature and issues. It also provides opportunity for polishing communication skills.
• Homework, includes computer simulation programming (20%): Since there will be computer programming in this class, all students will be required to know the C programming language and UNIX. See below for the types of programming that can be expected.

Types of programming assignments to expect (though these may not be the actual ones assigned):

• Random number generator (discrete and continuous random variables), and confidence intervals (1 week)
• Random b-matching (1 week)
• Discrete time Markov chain (1 week)
• Continuous time Markov chain, discrete event simulation (1 week)
• Multiple M/G/1 queues by discrete event simulation (1 week)
• Circuit switched network (2 weeks)
• Packet switch (or switched network) (2 weeks)