CS 395T: Performance Analysis of Networked Systems


Instructor: Venkat Arun

Course Goal: This graduate-level reading seminar will survey how theoretical analyses of computer system performance have informed the design of real-world systems. The objectives of the course are:

The course is structured around lectures by the instructor and paper readings/presentations by the students with open discussion. Students will form a project group and conduct a research project combining theory and systems.

Syllabus: Applications of queuing and control theory, randomized load balancing and routing algorithms, notions of fairness, beyond worst-case analysis for online scheduling and caching algorithms, performance verification, use of constraint solvers, and practical implications of complexity theory.

Canvas

Where? GDC 6.816

When? Mondays and Wednesdays at 2-2:30PM

Schedule (tentative)

  1. Introduction + Switch load balancing I
    Types of theory

The switching/routing problem, PIM algorithm

    Optional: How to read a paper

  1. Switch load balancing II

iSLIP

    Optional: PLB, Conga

  1. Switch load balancing III

Valiant load balancing, birthday paradox

  1. Application load balancing II

Power of two choices vs random vs full visibility

Optional: Queuing theoretic analysis of power of two choices, Survey of the theory, Small amount of memory helps load balance

  1. Application load balancing III

Overload control (Breakwater)

  1. Process scheduling I

Work stealing theoretical analysis, Cilk programming model, Empirical analysis that concludes work stealing is best

  1. Process scheduling II

Decades of wasted cores in Linux
Optional: Scheduler in Linux v4.6.8.1, More bugs discovered through verification

  1. Notions of fairness I

Book with the basic definitions of fairness (chapter 1)
Optional: Paper analyzing proportionally fair wireless schedulers, Frank-Wolfe algorithm

  1. Notions of fairness II

Dominant Resource Fairness
Optional: Tetris

  1. Notions of fairness III

FairCloud + RCS

  1. Caching replacement policies I
    LRU analysis (Section 5), Tim Roughgarden's history of LRU analysis
    Roughgarden's notes on above proof
  2. Cache replacement policies II
    Caching with delayed hits, caching when objects are of different sizes
  1. Incorporating ML in systems I

Competitive caching with learned advice
Optional: Competitive analysis of the randomized marking paging algorithm

  1. Incorporating ML in systems II

Contextual bandits (off-policy evaluation)

  1. Incorporating ML in systems III

Learning to optimize TE (TEAL)

  1. Computational complexity in practice

No reading. Just comment on your practical experiences with computational complexity

  1. Tasting menu of signal processing I
    In-body localization (example of the effect of non-linearity)
  2. Tasting menu of signal processing II

Resolution limits using angular spectrum representation

  1. Congestion control I

Chiu-Jain analysis of AIMD, the classic congestion control algorithm (CCA)
Optional: Generalizing AIMD: Binomial congestion control

  1. Congestion control II

Network Utility Maximization (Chapter 3 of book)
Optional: BBR: A Modern CCA

  1. Congestion control III

Starvation in congestion control
Optional: Verifying CCAs

  1. Performance verification I

Synthesizing provably performant controllers

  1. Performance verification II

MetaOpt: Identifying performance gaps in heuristics

  1. Performance verification III

FPerf: synthesizing workloads, Bounding resource consumption

  1. Abstractions that aid performance

Customizable network slicing schedulers

  1. Abstractions that aid performance II

PIFO

  1. Project presentations I
  2. Project presentations II