REQUIRED TEXTBOOK:  Raj Jain, The Art of Computer Systems Performance Analysis, Wiley, 1991.    Most readings for the course are in the form of research papers and will be supplied in class or online.

COURSE GOALS: The goal of this course is to familiarize students with the state of the art and current results of workload characterization.   It is about understanding complex computer systems (including their interaction with their users) as if they were natural systems. What are the “natural laws” in this domain and how do they affect the design and implementation of systems?  The coursefocuses on how we can measure, analyze, model, and predict the dynamic behavior of distributed computing environments, including their networks, hosts, applications, and their users.

The course prepares students for research in workload characterization, performance analysis, and systems in general, and provides an opportunity to propose, investigate, and present a related project.   The course also gives students an opportunity to learn how to critically read, analyze, and present research papers.

Detailed information can be found at http://www.cs.northwestern.edu/~pdinda/predclass

COURSE COORDINATOR: Peter Dinda

PREREQUISITES: Requires EECS 213 or (EECS 205 and EECS 231) or equivalent computer systems course.   Familiarity with basic statistics and probability are strongly recommended.  Undergraduates are welcome.

PREREQUISITE FOR: None

DETAILED COURSE TOPICS:

  1. Introduction to performance analysis and workload characterization
    1. Perspective of adaptive systems
    2. Perspective of queuing theory
    3. Perspective of signal processing
    4. Basic statistical tools
  2. Important workload characteristics and their impacts
    1. Independence and correlation in space and time
    2. Ergodicity
    3. Memoryless distributions
    4. Power laws and heavy tails
    5. Self-similarity and long-range dependence
    6. Non-stationarity
    7. Predictability
  3. Introduction to time-series analysis and prediction
    1. Time and frequency domain
    2. FFTs and power spectra
    3. Wavelets
    4. Impulse response
    5. Wold decomposition
    6. Classical ARIMA modeling
    7. Fractional ARIMAs
    8. Threshold autoregressives and other nonlinear models
  4. Introduction to event prediction
    1. Markov models
    2. Genetic programming
  5. Processes on hosts
    1. Exponential versus power-law service times
    2. Prediction of process resource demand
  6. Host availability and load
    1. Distributional models
    2. Time series models
    3. Heavy tails and self-similarity and their impact on load balancing and provisioning
    4. Predictability and prediction strategies
  7. Individual host and aggregated network traffic
    1. Heavy tails and self-similarity and their impact on network and router design
    2. Debate over stationarity
    3. Predictability and prediction strategies
    4. Prediction systems
  8. Network topology
    1. Power laws of Internet topology and their implications
    2. Explanations
  9. Web workloads
    1. Power laws and SRPT scheduling
    2. Zipf’s rule
  10. Peer to Peer workloads
    1. Small worlds
    2. Examinations of BitTorrent and other P2P systems
    3. Lifetimes and churn
  11. File systems
    1. Contents
    2. Predicting file access patterns for prefetch
  12. Users
    1. Wireless network behavior
    2. Chat system behavior
    3. Games
    4. Concept of direct user feedback in systems

READINGS/PRESENTATIONS:  Before each class session, students are expected to read 1-3 research papers.  In the class session, one student presents the papers formally, and the entire group discusses them.   Students should expect to read 2-6 research papers per week, write short summaries of each paper for submission to the instructor, participate in the discussion of the papers they have read, and formally present papers twice in the quarter.

PROJECT:  Over the course of the quarter, each student will propose, carry out, and report on a research project related to the course.   Students may work in groups.  Project topics are approved by the instructor.  A written project proposal and weekly updates are required.  At the end of the quarter students will document their projects in high quality  papers, and a conference-style presentation open to all interested parties.

more news