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

Linux (contd), wireless scheduling and alpha fairness (throughput, proportional, max-min)

  1. Notions of fairness II

Multi resource fairness

  1. Notions of fairness III

FairCloud + RCS

  1. Caching replacement policies I
    LRU analysis
  2. Cache replacement policies II

Other practical concerns

  1. Incorporating ML in systems I

Competitive caching

  1. Incorporating ML in systems II

Statistical power of data

  1. Incorporating ML in systems III

Safe ML

  1. Computational complexity in practice I

P: traffic engineering

  1. Computational complexity in practice II
    NP: optimization problems in computer systems, Gurobi, Z3
  2. Computational complexity in practice II

Beyond NP: Program synthesis, two-player games and beyond

  1. Congestion control I

Classical: AIMD, Vegas, RCP

  1. Congestion control II

Control theory: RCP, DCTCP

  1. Congestion control III

Modern congestion control + CCAC

  1. Performance verification I

fPerf, verilay

  1. Performance verification II

MetaOpt

  1. Bounding performance I

Performal, Hoffman’s work

  1. Abstractions that aid performance I

PIFO

  1. Abstractions that aid performance II

Network slicing

  1. Project presentations I
  2. Project presentations II