|
|
Date |
Lecture Topic |
|
|
|
|
Discussion Section | |
|---|---|---|---|---|---|---|---|---|
| 1 | Jan. 9 |
|
Introduction to class and logistics. | McKeown | #1 ppt, pdf #2 Color ppt, pdf #2 Black & White pdf |
Homework 1 ps, pdf Homework 1 Solutions ps, pdf Due 4pm Wednesday Jan 23 Help on SIM |
Basic Probability Theory ppt, pdf, |
|
| 2 | Jan 14 |
Overview of Packet Switches and their evolution | McKeown | #3 ppt, pdf | ||||
| 3 | Jan. 16 |
|
What is output queueing? M/D/1 model, Good properties: minimize expected delay, work-conservation, ability to control bw and delay. | McKeown | #4 ppt, pdf | Discrete Time
Markov Chains ppt, pdf |
||
| 4 |
Jan. 23 |
Output link scheduling: fairness, weighted fairness, FQ and WFQ, providing delay guarantees, leaky-bucket constraints, Parekh/Gallager results, GPS, DRR approximation. | McKeown | |||||
| 5 |
Jan. 28 | McKeown | Paper 1 |
Quiz 1 solutions ps, pdf Homework 2 ps, pdf Homework 2 Solutions ps, pdf Due 4pm Thursday Feb 7 |
Poisson Processes
ppt, pdf |
|||
| 6 |
Jan. 30 | Practical
difficulties: memory bandwidth and capacity scaling. Some approaches: -Definition of Emulation -Parallel packet buffers as standalone shared memory, with design example. -Routers with a single stage of buffering and constraint sets, PSM, DSM. -PPS, versions 1 and 2. -Output link scheduling in DSM. |
McKeown | #5 ppt, pdf | Paper 2 Paper 3 |
|||
| 7 |
Feb. 4 | McKeown | #6 ppt, pdf | Continuous Time
Markov Chains and Basic Queueing Theory ppt, pdf |
||||
| 8 | Feb. 6 | McKeown | #7 ppt, pdf | Paper 4 |
||||
| 9 | Feb. 11 | CIOQ switches, stable marriage
matchings |
Prabhakar | #8 pdf, ps | Paper 5 Paper 9 |
Quiz 2 Solutions ps, pdf Homework 3 ps, pdf Homework 3 Solutions ps, pdf Due 4pm Thursday Feb 21 |
||
| 10 | Feb. 13 | CIOQ S=4, S=2 result. | Prabhakar | #9 pdf, ps | Paper 6 Paper 7 |
Midterm review Take home midterm: Out: Feb. 25 Due In: Feb. 27 in class. |
||
| 11 | Feb. 20 | HoL blocking. Balls and bins.
Throughput with flushing. A queueing formula. |
Prabhakar | #10 pdf, ps | Paper 8 | |||
| 12 | Feb. 25 | PART-II: Input- Queued Switches |
Karol's 2-sqrt(2)
result. VOQs and
scheduling. Switch scheduling and bipartite graph matching. Definition of 100% throughput. Algorithms for 100% throughput: When traffic is uniform - simple RR and randome matchings; When traffic matrix is known - Birkhoff-von Neuman decomposition; When traffic is not known - Lyapunov stability. |
Prabhakar | #11 pdf, ps | Homework 4 ps, pdf Homework 4 Solutions ps, pdf Midterm ps, pdf Due 4pm Thursday Mar 6 Midterm Solutions ps, pdf |
||
| 13 | Feb. 27 | Prabhakar | #12 pdf, ps | |||||
| 14 | Mar. 3 | Prabhakar | ||||||
| 15 | Mar. 5 | Prabhakar | #13 pdf, ps |
Paper 10 | ||||
| 16 | Mar. 10 | Stability of network systems: Foster's criterion, Application to M/M/1 queue. | Prabhakar | #14 pdf, ps |
Paper 11 Paper 12 |
Homework 5 ps, pdf Homework 5 Solutions: ps, pdf Due 4pm Friday Mar 14 |
||
| 17 | Mar. 12 |
Intro to stability of IQ switches: MSM counterexample, Intuitive proof that MWM gives 100% throughput. | Prabhakar | #15 pdf, ps | Final review session Review session problems [pdf] |
|||
|
Final
Exam: Thursday, March 20, 8:30am-11:30am
|
||||||||