CS6250: Advanced Computer Networks
This semester's main theme:
Router architectures and algorithms
Fall 2006, College of Computing, Georgia Tech
Office: 218 GCATT
Office phone: 5-4205
Office hours: TR 11-12 (after class)
Email: dovrolis at cc
Teaching Assistant: Ikpeme Erete
Office hours: Thursday 2-4 at CCB lounge
Email: ierete3 at mail gatech edu
What's New - Reminders
- Instead of a final exam, you are given a take-home exam.
The due date is Friday Dec 8, 5pm (electronic submission only,
in Word or PDF format).
- Swiki page
Table of Contents
- Class meeting times: TR 9:35-10:55
- Classroom: CCB 101
- In this semester, the syllabus puts a major emphasis on
router/switch architectures and algorithms. We will study algorithms
used by modern routers to do forwarding, address lookups, switching, scheduling,
flow classification, flow monitoring and measurement, etc. We will also
understand in depth various router architectures and attempt to reverse-engineer
some existing routers.
- Additionally, the course will cover some fundamental concepts in routing
and addressing, transport protocols and congestion control, emerging distributed
applications, and wireless networking. The objective is to go beyond the basic level of
understanding that is typically offered at an undergraduate networking course.
- The course also includes a "heavy-weight" design project. In groups of 3-4
students, you will design, specify, implement and demonstrate a network protocol
(or a distributed application) of your choice.
In the first half of the semester we will primarily rely on the following textbook:
by George Varghese, Morgan Kaufmann, 2005.
In the second half of the semester we will mostly use research papers.
We will also cover parts of the following books (you don't need to
purchase them, but I highly recommend them if you are serious about networking):
Additional good references:
- W. R. Stevens,
TCP/IP Illustrated, Volume 1: The Protocols, 1994.
- G. R. Wright and W. R. Stevens,
TCP/IP Illustrated, Volume 2: The Implementation, 1995.
- B. Krishnamurthy and J. Rexford,
Web Protocols and Practice: HTTP/1.1, Networking Protocols, Caching, and Traffic Measurement, 2001
The following books are excellent references for UNIX network programming,
you may need them for the course project, and you will find them useful for years to come.
The reading list will be updated every week, before we cover the corresponding
topic.
First part: Router/switch architectures and algorithms
- Week-1:
Introduction, overview of router architectures
Readings:
A brief history of the Internet by B. Liener et al., and
IP
router architectures, an overview by J. Aweya.
- Week-2:
Exact-match address lookups
Readings: Varghese chapter-10 (required), and
The GIGAswitch control processor by R.J.Walsh et al. (optional).
- Week-3:
Prefix-match address lookups
Readings: Varghese chapter-11 (required), and
Dynamic pipelining: making IP-lookup truly scalable by J.Hasan et al. (optional).
- Week-4:
Packet classification
Readings: Varghese chapter-12 (required), and
Algorithms for Advanced Packet Classification with Ternary CAMs by K. Lakshminarayanan et al. (optional).
- Week-5:
Switching packets
Readings: Varghese chapter-13 (required), and
Routers with a Single Stage of Buffering by S. Iyer et al. (optional).
- Week-6:
Scheduling packets
Readings: Varghese chapter-14 (required), and
Proportional Delay Differentiation by C.Dovrolis et al. (optional).
- Week-7:
Traffic monitoring and measurement
Readings: Varghese chapter-16 (required), and
Building a Better NetFlow by C.Estan et al. (optional).
- Week-8:
Router algorithms for network security
Readings: Varghese chapter-17 (required), and
Automated Worm Fingerprinting by S.Singh et al. (optional).
- Week-9:
Midterm week
Second part: Advanced concepts in computer networks
Design, specify, implement and demonstrate a novel protocol
Perhaps the most exciting part of this course will be the term project.
In groups of 3-4 students, you will design, specify,
implement, and demonstrate a protocol of your choice. It may be
a performance-driven routing protocol that selects network paths based
on measured delays or throughput. Or, a p2p large-transfer application
(like BitTorrent) that is optimized for the transfer of relatively
rare content. Or, a secure routing protocol that can function correctly
even when some routers are malicious or compromised.
Or, a transport protocol that performs better than TCP in networks that
experience high loss rate.
Whatever excites you.
I suggest that you look at the recent (online) proceedings of
conferences such as SIGCOMM or NSDI to get some ideas about novel
network protocols and distributed applications.
So, start thinking about project partners and cool project ideas!
There are some constraints however:
- Your project proposal will need to be approved by the instructor.
Talk to the instructor whenever you have a concrete idea. Do not
wait for the first project milestone.
- The project will need to be sufficiently complex and appropriate
for this course. Something like a simple client-server program or
a basic routing protocol would not be challenging enough.
- On the other hand, it must not be too hard either.
It should be feasible for 3-4 students
to implement and test the project within a couple of months.
- The project will need to be implemented in software. You can
emulate point-to-point network links using UDP sockets.
For more details about this approach see the first couple of sections
from the following
previous course project.
- Hardware or measurement projects are not recommended.
If you are determined to do such a project however,
one option is that you use an existing resource or testbed.
For example, WUSTL's Open Network Lab,
Stanford's VNS,
or Utah's Emulab.
Keep in mind however that there is always a slow learning
curve when using such testbeds, and there is a
chance that your project will not be successful because
of limitations (or bugs) of these resources.
Frequently-Asked-Questions (FAQ) about the project
Project milestones:
- Form groups, submit 2-pages project proposal: Sep 8
- Design report and protocol specification: Oct 3
- Mid-semester progress report and demo: Nov 7
- Final deadline - code submission: Dec 1, 5pm
- Demos: During the last week of the semester (Dec 4-8)
The project grade will be determined at the end of the semester
taking into account all previous milestones.
These are "paper-and-pencil" problems, based both on material
we cover at the lectures and on references that you will be
asked to study on your own. We will have 3-4 such homeworks
during the semester. The midterm and final exams will include
similar problems with the homeworks.
- Homework-1: Textbook problems 10-1, 11-1, 11-2, 11-3, 11-14.
Due Thursday, Sep 14.
- Homework-2: Textbook problems 12-1, 12-2, 12-9, 13-4, 13-6.
Due Thursday, Oct 12.
- Homework-3: Textbook problems 14-4, 14-6, 16-3, 16-4, 17-2, 17-5.
Due Tuesday, Oct 31.
- Midterm: 25%
- Final (take-home exam): 25%
- Project: 40%
- Homeworks: 10%
- All work for this class, except the group project, is to be done individually.
You are strongly urged to familiarize yourselves with the
GT Student Honor Code
rules.
Specifically, the following is not allowed:
- Copying, with or without modification, someone else's work when this work is
not meant to be publicly accessible (e.g., a classmate's program or solution).
- Submission of material that is wholly or substantially identical to that
created or published by another person or persons, without adequate credit
notations indicating authorship (plagiarism).
You are encouraged to discuss problems and papers with others as long as this
does not involve copying of code or solutions. Any public material that you
use (open-source software, help from a text, or substantial help from a
friend, etc...) should be acknowledged explicitly in anything you submit to us.
If you have any doubt about whether something is legal or not please do
check with the class Instructor or the TA.
- No late homeworks, assignments, or projects will be accepted.
The deadline for each homework/assignment/project will be specified at the
corresponding handout.