DESCRIPTION:

In designing computer systems one is usually constrained by certain performance requirements. For example, certain response times or throughput might be required of the system. On the other hand, one often has many choices: One fast disk, or two slow ones? What speed CPU will suffice? Should we invest our money in more buffer space, or a faster processor? Which migration policy will work best? Which task assignment policy will work best? How can we redesign the scheduling policy to improve the system performance?

Often answers to these questions are counter-intuitive. Ideally, one would like to have answers to these questions before investing the time and money to build a system. This class will introduce students to analytic stochastic modeling with the aim of answering questions such as those above.

Topics covered include:

• Operational Laws: Little's Law, response-time law, asymptotic bounds, modification analysis, performance metrics;
• Markov Chain Theory: discrete-time Markov chains, continuous-time Markov chains, renewal theory, time-reversibility; Poisson Process: memorylessness, Bernoulli splitting, uniformity, PASTA;
• Queueing Theory: open networks, closed networks, M/M/1, M/M/k, M/M/k/k, Burke's theorem, Jackson networks, classed networks, load-dependent servers, BCMP result and proof, M/G/1 full analysis, M/G/k, G/G/1;
• Simulations: time averages versus ensemble averages, confidence intervals, generating random variables for simulation, Inspection Paradox;
• Empirical Workload Measurements: heavy-tailed property, Pareto distributions, self-similarity, heavy-tailed distributions;
• Analysis of Scheduling: FCFS, non-preemptive priorities, preemptive priorities, PS, LCFS, FB, SJF, SRPT;
• Applications: Web servers, database management systems, supercomputing server farms, call centers, web server farms, disks.

The techniques studied in this class are useful to students in Computer Science, ECE, Mathematics, ACO, Tepper, Statistics, and Engineering. This course is packed with open problems -- problems which if solved are not just interesting theoretically, but which have huge applicability to the design of computer systems today. Class Reviews

PREREQUISITES:

Recommended for those with strong background in probability. Assumes knowledge of continuous and discrete distributions, conditional probability, conditional expectation, moments, and some previous exposure to Markov Chains. Assumed material can be found in: "Introduction to Probability Models" by Sheldon M. Ross, Chapters 1-3. You can borrow this book from my office. Highly recommended for CS, ECE, ACO, Tepper, and Mathematics students.