Mathematical Foundations of Computer Networking
Note: I am no longer updating this page. Please refer to this page (http://blizzard.cs.uwaterloo.ca/keshav/mediawiki-1.4.7/index.php/2ed-details) for updates.
Graduate students today
often require concise introductions to theoretical foundations of networking.
Many students lack a 'feel' for probability, statistics,
optimization, game theory, control theory, and queueing theory. However, unlike discrete algebra and, to some degree calculus and linear algebra, these subjects are not taught in a typical CS curriculum. Graduate students
confronted by papers using these ideas are at a loss, and it is impractical
to require remedial courses of every student.
This course addresses the problem by taking
an intuitive approach to these topics. The depth of coverage provided here is not a substitute for
standard textbooks. Rather, I hope to provide enough intuition to
allow a student to grasp the essence of a research paper that uses these
This course will cover five topics that are relevant for researchers in the area of computer networking: Optimization, Probability, Queueing Theory, Game Theory, and Statistics. The depth of coverage will be sufficient to allow students to read and understand papers that use these standard techniques. Ideas will be taught through intuition, mathematically correct formalization, and detailed numerical examples. Students are expected to have a first-year undergraduate level of understanding of calculus and linear algebra. Grading will be based on homework assignments. There is no assigned text: lecture notes will be made available in PDF format prior to class. Videos of the lectures in WMV format are also available at the bottom of this page (or look at the table of contents).
I am providing this content here under the Creative Commons Attribution-Noncommercial-Share Alike 2.5 Canada License (http://creativecommons.org/licenses/by-nc-sa/2.5/ca/)
A Tourist's Guide to Optimization
- System modeling
- Linear programming
- Integer linear programming
- Non-linear optimization - constrained and unconstrained
- Lagrangian optimization
- Hill-climbing, Simulated annealing, and Genetic algorithms
- Video of lecture 1 on September 9, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/lec1.wmv) Introduction, Optimization, Overview of Linear programming
- Video of lecture 2 on September 11, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/lec2.wmv) Linear programming, Using Linear programming for network flow
- Video of lecture 3 on September 16, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav3.wmv) Integer Linear Programming, Maximal Weighted Matching, Dynamic Programming, Floyd-Warshall algorithm
- Video of lecture 4 on September 18, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav4.wmv) Non-linear optimization, Lagrangian optimization, KKT conditions, Heuristic algorithms
Homework assignment (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/Optimization-homework.pdf)
- Solution (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/solution1.pdf) (please attempt the homework before reading this).
- A brief biography of Fibonacci (http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Fibonacci.html)
A Short Introduction to Probability
- Basic concepts: probability and conditional probability
- Bayes' rule
- Discrete and continuous random variables
- Density and cumulative distributions
- Expectations and properties of expectations
- Standard discrete distributions: Bernoulli, Binomial, Geometric, Poisson
- Standard continuous distributions: Gaussian, Exponential, Power-law
- Useful theorems
- Joint distributions, marginals
- Bayesian networks
- Video of lecture 5 on September 23, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav5.wmv) Probability, Random Variables, Conditional probability
- Video of lecture 6 on September 25, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav6.wmv) Expectations, Properties of Expectations, Common distributions: Bernoulli and Binomial
- Video of lecture 7 on September 30, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav7.wmv) Geometric, Poisson, Gaussian, Exponential distributions
- Video of lecture 8 on October 2, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav8.wmv)Power distribution, Tail bounds and limit theorems, Bayesian networks.
Homework assignment (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/Homework_A2.pdf)
- Solution (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/Solution_A2.pdf) (updated 10/17)
- Ross, A First Course in Probability, Seventh Edition, Prentice Hall, 2006.
Foundations of Queueing Theory
- Stochastic processes
- Markov processes
- Markov analysis
- M/M/1 queues
- Variations on the M/M/1 queue
- Video of lecture 9 on October 7, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav9.wmv) Queueing theory, Little's Law, Determinstic and Stochastic processes
- Video of lecture 10 on October 9, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav10.wmv) Stochastic processes, Markov processes, Homogeneity, Recurrence, Reducibility, Periodicity, Ergodicity, Stationary probabilities, Two theorems.
- Video of lecture 11 on October 14, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav11.wmv) Recurrence, Stationary probability of a discrete time Markov chain, Computing stationary probabilities, Continuous-time Markov chains, Introduction to birth-death processes.
- Video of lecture 12 on October 16, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav12.wmv) Birth-death processes, Poisson process, General equilibrium solution.
- Video of lecture 13 on October 21, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav13.wmv) The M/M/1 queue
- Video of lecture 14 on October 23, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav14.wmv) Variations on the M/M/1 queue: M/M/1/K, M/M/infinity, queueing networks
Homework assignment (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/Homework_A3.pdf)
- Solution (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/Solution_A3.pdf)
- Primary reference: Kleinrock Vol 1 (http://www.amazon.com/Queueing-Systems-Theory-Leonard-Kleinrock/dp/0471491101)
- More on recurrence (http://cnx.org/content/m10852/latest/)
- A textbook on Markov chains (http://books.google.ca/books?hl=en&id=IHn7Lx15ifUC&dq=markov+chains+bremaud&printsec=frontcover&source=web&ots=_HQv7GV-wu&sig=Nzu_G5DYIbPN4jhO-oNfPGmPbUc&sa=X&oi=book_result&resnum=1&ct=result#PPT1,M1)
- Preferences and Utilities
- Solution concepts
- Mechanism design
- Video of lecture 15 on October 28, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav15.wmv) Introduction and Preference theory
- Video of lecture 16 on October 30, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav16.wmv) Concepts and Terminology
- Video of lecture 17 on November 4, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav17.wmv) Solution concepts (dominant, minimax, Nash)
- Video of lecture 18 on November 6, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav18.wmv) Correlated equilibria, Introduction to mechanism design
- Video of lecture 19 on November 11, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav19.wmv) Mechanism design: Arrow theorem, Gibbard-Satterthwaite Theorem, Quasi-linear utilities, Direct revelation principle
- Video of lecture 20 on November13, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav20.wmv) Mechanism design: VCG mechanism, problems with mechanism design, Limitations of Game Theory
Homework assignment (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/Homework_A4.pdf)
Solutions: Version of 12/09/08 (http://blizzard.cs.uwaterloo.ca/keshav/home/Papers/data/08/SolutionsA4.pdf)
- Luce and Raiffa, "Games and Decisions," 1957.
- Rasmussen, "Games and Information: An Introduction to Game Theory," 1994.
- D. Parkes, "Mechanism Design," [www.eecs.harvard.edu/~parkes/pubs/ch2.pdf Chapter 2 of Parkes's Ph.D. thesis]
- Nisan et al, "Algorithmic Game Theory," 2007.
- Sampling a population
- Describing a sample parsimoniously
- Inferring population parameters
- Comparing outcomes
- Fitting a distribution
- Inferring independence and dependence
- Dealing with large data sets
- Lecture 21 on November 18, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav21.wmv) Moments, Moment Generating Functions, Normal Distribution revisited, Central Limit Theorem
- Lecture 22 on November 20, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav22.wmv) Populations, Statistics, Sampling, Sample Mean
- Lecture 23 on November 25, 2008 (http://blizzard.cs.uwaterloo.ca/keshav/home/cs798/videos/keshav23.wmv) Sample variance, Inferring population parameters
- Bulmer, "Principles of Statistics," Dover 1979.
Chapters to come
- Linear algebra
- Signals and systems (transform domain techniques)
- Information theory
- Control theory
- Graph theory
I am no longer updating this page. Please refer to this page (http://blizzard.cs.uwaterloo.ca/keshav/mediawiki-1.4.7/index.php/2ed-details) for updates.