|
Units |
9
(3-3-3) |
|
Lectures |
MWF
9:00 - 9:55am, Rm 213 Annenberg |
|
Prerequisites |
Ma 2,
Ma 3, CS 24 and CS 38 (or instructor permission)
|
|
(desirable: Ma 108a Classical Ananlysis I)
|
|
|
URL |
|
|
Instructors |
Steven Low <slow@caltech.edu>, CMS/EE, x6767, Rm 219 Annenberg |
|
Richard Murray <murray@caltech.edu>, CDS/BE, x6460, Rm 109 Steele
|
|
|
Claire Ralph <clairer@caltech.edu>, CMS, x8711, Rm 244 Annenberg
|
|
|
Admin. Assistant |
Christine
Ortega <cortega@caltech.edu>, 245 Annenberg |
|
TAs |
Project: Daniel Guo <lguo@caltech.edu>, CMS;
Zach Lee < zlee@caltech.edu>, EE;
Fengyu Zhou < f.zhou@caltech.edu>, EE
|
|
Homework:
Jing Yu <jing@caltech.edu>, CDS;
Chen Liang <cliang2@caltech.edu>, CMS
|
|
|
Office Hours |
Instructors: by email appointment
|
|
TA
(project): schedule weekly meetings with your TA
|
|
|
TA
(homework): Mondays 7-9pm, Steele House conference room at the back.
|
This course focuses on the link layer (two) through the transport layer (four) of Internet protocols. It has two distinct components: project and analytical.
Project component. The first three weeks of lectures and homework summarize basic protocols that provide the background knowledge for the project. The students then work in teams on a significant software project. The default project is to build a simulator of Internet routing and congestion control algorithms. Other projects on energy and electric vehicles are available too (more information below). This part is primarily on software development and students mainly work with their team members and project TAs.
Analytical component. The lectures and homework after week 3 develop analytical methods for Internet congestion control. We will also give an overview on other topics such as wireless networking, security and privacy. The congestion control mechanism has been responsible for maintaining stability as the Internet scaled up in size, speed, traffic, volume, coverage, and complexity by many orders of magnitude over the last three decades. We will explain: (1) How to model congestion control algorithms? (2) Are the models well defined? (3) How to characterize the equilibrium points of a congestion control model? (4) How to prove the stability of the equilibrium points? We will study basic results in ordinary differential equations, convex optimization, Lyapunov stability theorems. We will apply these results to prove equilibrium and stability properties of the congestion control models and explore their practical implications.
The analytical part is highly mathematical and will closely follow the lecture notes on TCP congestion control and the text on feedback systems. Our primary goal is to develop a coherent theory of Internet congestion control from the ground up to help understand and design the equilibrium and stability properties of large-scale networks under end-to-end control. In addition, we have two broader purposes in mind. First we wish to introduce a set of system theoretic tools and illustrate their application to concrete problems. Second we wish to demonstrate in depth the entire process of understanding a physical system, building mathematical models of the system, analyzing the models, exploring the practical implications of the analysis, and using the insights to improve a design. Even though our development is carried out in the context of congestion control, these analytical tools and the research process are much more broadly applicable.
Computer networks is a rich and diverse subject, spanning mathematical modeling and analysis, algorithm design, implementation and experiments. A single course necessarily only samples a very small cross section. The goal of this course is to, on the one hand, introduce an analytical perspective to networking, and on the other hand, provide a hands-on experience through a significant project.
This course can be combined with CS/EE 144 Networks: structure and economics (Winter) and CS/EE 145 Projects in networking (Spring) to satisfy the project requirement for CS undergraduate degree, though CS/EE 143 is not a prerequisite for either CS/EE 144 or CS/EE 145.
There are also many good online classes and materials that you should take advantage of.
Each project team usually consists of 4 students, plus or minus 1. Each team can either work on the network simulator project or one of the special projects.
For homework, you should try to solve the problems yourself first. Only after that should you discuss with your fellow students. You must however write up your own solution independently. Do not look at previous years' solutions; this includes completed assignments from past students.
For projects, each group is expected to submit work that is entirely that group's work. Do not look at previous years' repositories (codes, reports, presentations). Referring to other documentation/online question and answer forums is allowed and often helpful, but all code submitted must still be entirely written by you. Don't plagiarize. If a resource is heavily referenced, provide a citation.
Caltech's Honor Code "No member of the Caltech community shall take unfair advantage of any other member of the Caltech community" is a critical pillar of campus life. We expect everyone to abide by the Honor Code. In case of doubt, please ask. Any issues with the honor code should be brought to the Instructors or directly to Caltech's Board of Conduct.
This
is tentative and subject to change.
You can have up to 1 homework set late for up to 5 days without penalty. After that, each late homework will be accepted and graded with 10% discount/day of the total points of that homework set, for up to 5 days, after which the homework set will receive 0 point.
The first half of the course will have more homework; the second half less homework so you can spend more time on your project. You should be able to start on your project after week 3, and we will cover all the networking concepts you need for the network simulator project around mid October.
The following schedule gives a roadmap of the course and it will be updated as we progress through the course, so do check back from time to time. (WP = 1st Ed of Walrand and Parekh, 2010)
|
Week |
Topic |
Assignment |
Notes (continuously
updated) |
|
10/1 |
Reading: WP Ch 1, 2 HW 1: HW1
(due on 10/8 Mon in class)
|
Basic concepts: host, router, link, packet switching, addressing, DNS. Routing. Error detection. ARQ. Congestion control. Sharing. Metrics. Little's Theorem, M/M/1 queue. Scalability. Layering. Application topology: client-server, p2p, CDN, cloud computing. |
|
|
10/8 |
Ethernet (MAC, STP) Slides: |
Reading: WP Ch 3, 5 HW 2: HW2 (due on 10/17 Wed by 6pm, dropoff box outside ANB 228) |
Ethernet: Aloha (CSMA), cable Ethernet (CSMA/CD), hub, switch; binary exponential backoff algorithm, Spanning-Tree Protocol, maximum throughput of slotted and unslotted CSMA. Layer 3 routing: AS, BGP, shortest-path routing |
|
10/15 |
Internetworking Slides: |
Reading: WP Ch 6, 7 HW 3: HW3 (due on 10/24 Wed by 6pm, dropoff box outside ANB 228) |
Internetworking: addresses, subnets, subnet masks, gateway router, ARP;
DHCP, NAT Transport basics: ports, flow ID, header, connection setup; ARQ: stop-and-go, go-back-N, selective repeat, timeout; Congestion control: Window control (ARQ, ack-clocking), flow vs congestion control, AIMD, slow-start, FR/FR, TCP Reno, TCP Vegas. Fri class: project tutorial: network simulator tutorial slide |
|
10/22 |
TCP congestion control |
Reading: FBS Section 5.1-5.3;
SL Ch 1 |
Mathematical models of TCP Reno, Vegas, FAST. Dynamical systems basics: existence and uniqueness of solution of ODE, definitions of equilibrium and stability. |
|
10/29 |
Equilibrium structure I |
Reading: SL Ch 2
HW 4: HW4 (due on 11/14 Wed by 6pm, dropoff box outside ANB 228) |
Convex optimization: convex set, convex function, convex program, KKT condition, duality; |
|
11/5 |
Equilibrium structure II |
Reading: SL Ch 2
|
Network utility maximization: equilibrium of TCP CC, practical implications |
|
11/12 |
Global stability I |
Reading: FBS 5.3 and 5.4; SL Ch 3 HW 5: SL Ch 3: Exercises 3.1 - 3.6 (due on 12/5 Wed by 6pm, dropoff box outside ANB 228) |
Mon class: Project presentations III (SL) Lyapunov stability theorem, LaSalle's invariance
principle. |
|
11/19 |
Global stability II |
Reading: SL Ch 3 |
Application to TCP CC. |
|
11/26 |
Wireless networks |
Reading: WP Ch 4 |
Stability proofs for dual algorithms (SL Ch 3.2) and primal-dual algorithms (SL Ch 3.3).
|
|
12/3 |
Security and privacy |
Reading: |
For the report:
|