CS/EE 143 Communication Networks (2018 Fall)

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

http://courses.cms.caltech.edu/cs143

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.

Course Description

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

Text and references


There are also many good online classes and materials that you should take advantage of.

Projects

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.

Collaboration Policy

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.

Grading

This is tentative and subject to change.

Late Homework Policy

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.

Course Schedule (tentative)

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
SL

Internet
Principles

Slides: pptx, pdf

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
SL

Ethernet (MAC, STP)
Routing (IP, BGP)

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
Inter-domain routing: transit, peering, path-vector routing
Shortest-path routing: Dijkstra, Bellman-Ford
FEC, network coding

10/15
SL

Internetworking
Transport (TCP, UDP)

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
Putting it all together (W&P, P5.3): BGP, RIP/OSPF, STP (Spanning Tree Protocol)

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
RM

TCP congestion control

Slides: pptx, pdf

Reading: 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
RM

Equilibrium structure I

Reading: SL Ch 2

HW 4: SL Ch 2: Exercises 2.1 - 2.4, 2.7, 2.9, 2.11 - 2.13 (due on 11/21 Wed by 6pm, dropoff box outside ANB 228)

Convex optimization: convex set, convex function, convex program, KKT condition, duality;
Fri class: tutorial for project or homework (TA)

11/5
RM, SL

Equilibrium structure II

Reading: SL Ch 2

Network utility maximization: equilibrium of TCP CC, practical implications
Wed class: Project presentations I (SL)
Fri class: Project presentations II (SL)

11/12
SL, CR

Global stability I

Reading: SL Ch 3

HW 5: SL Ch 3: Exercises 3.1 - 3.6 (due on 11/28 Wed by 6pm, dropoff box outside ANB 228)

Mon class: Project presentations III (SL)

Lyapunov stability theorem, LaSalle's invariance principle.

11/19
CR

Global stability II

Reading: SL Ch 3

Application to TCP CC.
Fri class: No class (Thanksgiving holiday)

11/26
SL

Wireless networks

Reading:


12/3
CR

Security and privacy

Reading:

For the report:

  • Turn in source code (or your link to github repo)
  • Turn in final report
  • Describe full project, including usage
  • Present and describe results for Test Cases 1, 2
  • Present theoretical analysis for Test Case 2
  • Comment on project progress