Winter Term (Jan – April) 2004

Instructor: Murray Woodside…. Room 4484 ME, tel 520-5721,email cmw@sce.carleton.ca

The fundamentals of creating and solving Markov Chain models for reliability and performance, in computer systems and communications networks, will be covered. Techniques using Petri Nets and Queueing nets will be included in the scope.

Discrete-state models are essential for understanding and designing all kinds of computer and communications systems. They describe the movement of messages and jobs, contention for processing and transmitting, and the occurrence of failures, reconfigurations and repairs. The basic models for these systems are Markov Chains based on the state of the system, and changes of state. These lead to Queueing Network models, and Stochastic Petri Net models, for practical model building and solving. The models are used to understand performance, quality-of-service, availability and reliability.

The course will introduce the fundamentals of Markov Chains, Stochastic Petri Nets and Queueing Networks, and will emphasize how to choose an approach and how to build a model for a given problem. Practical modelling will be given equal emphasis with theory, and students will learn how to approximate and understand complex systems as assemblies of parts with simple models.

Assumed prerequisites: an introduction to probability, or equivalent experience; basic linear algebra and calculus. To understand modeling problems stated in plain language, a good reading understanding of English will be essential.

K.S. Trivedi, "Probability and Statistics, with Reliability, Queuing and Computer Science Applications", Wiley, 2^nd edition. This book is strong on the basics, and will be supplemented with more advanced material.

A.O. Allen, "Probability, Statistics and Queueing Theory with Computer Science Applications" Academic Press, 1990. (more material on basic concepts)

F. Bause and P. Kritzinger, Stochastic Petri Nets. Wiesbaden: Vieweg, 2002. (QA 267 B38) Basic theory

R. German, "Performance Analysis of Communications Systems", Wiley. (TK5105.5 G47) Applications

Course Outline

• Brief review of probability concepts, random variables, distributions.
• Markov chains in discrete and continuous time, processes, first passage times, simple examples of failures and repairs, and performance measures.
• Stochastic Petri Nets (modelling, PN semantics, tools), examples
• Markovian queues and queueing networks, examples
• Advanced topics: large systems, model decomposition, fork-join systems (as time permits)

Assignments (30%), Midterm exam (20%), Final exam (50%)

Assignments must be done individually, no sharing of solutions.

The course material will be defined by the classroom presentation, and classroom notes will extend the text material in many ways. Thus attendance at lectures is essential to completing the course.

Course handouts