Table of contents
1 Mathematical Foundations of Computer Networking

1.1 Motivation
1.2 Course outline

2 Lecture videos

2.1 A Tourist's Guide to Optimization
2.2 A Short Introduction to Probability
2.3 Foundations of Queueing Theory
2.4 Game Theory
2.5 Statistics

3 Chapters to come

Mathematical Foundations of Computer Networking

Fall 2008

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.

Motivation

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 theoretical foundations.

Course outline

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).

Administrative announcements

Lecture videos

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

Topics:

  • System modeling
  • Optimization
  • Linear programming
  • Integer linear programming
  • Non-linear optimization - constrained and unconstrained
  • Lagrangian optimization
  • Hill-climbing, Simulated annealing, and Genetic algorithms


Reviewers


Lecture videos

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).


Miscellaneous information:

  • A brief biography of Fibonacci (http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Fibonacci.html)

A Short Introduction to Probability

Topics:

  • 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


Reviewers


Lecture videos

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)

References:

  • 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

Reviewers


Lecture videos

  • 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)

References

  • 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)

Game Theory

  • Preferences and Utilities
  • Terminology
  • Solution concepts
  • Mechanism design

Reviewers

Lecture videos

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)

References

  • 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.

Statistics

  • Sampling a population
  • Describing a sample parsimoniously
  • Inferring population parameters
  • Comparing outcomes
  • Fitting a distribution
  • Inferring independence and dependence
  • Dealing with large data sets

Reviewers

Lecture videos

  • 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

References

  • 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.

Retrieved from "http://blizzard.cs.uwaterloo.ca/keshav/mediawiki-1.4.7/index.php/Mathematical_Foundations_of_Computer_Networking"

This page has been accessed 15222 times. This page was last modified 17:23, 13 Jun 2012. Content is available under GNU Free Documentation License 1.2.


Log in