Instructor: Prof. Jun (Jim) Xu

Teaching Assistants: Bhumik Sanghavi (less than 5 hrs/wk)

Annoucements

• No lecture on 10/24 (Wednesday)
• 1-page project proposal due Oct. 22nd (Monday).

Table of Contents

• Course Information
• Textbook and References
• Syllabus - Schedule
• Project
• Homeworks
• Grading
• Course Policies
• Miscellanea

Course Information and Objectives

• Class meeting times: MW 3:05-4:25
• Classroom: CCB 101

• In this semester, the syllabus will put a major emphasize on router/switch architectures and algorithms. We will study algorithms and protocols used by modern routers/switches to do routing, forwarding, address/prefix lookups, switching, scheduling, counting, flow classification, flow monitoring and measurement, IP traceback and other security functions, etc.  Whenever possible, we focus on general design principles rather than specific choices adopted by particular vendors.
  
• The pre-requisite for this course is CS 4251 here or equivalent (An undergarudate networking course that covers OSI/ISO 7 layers and TCP/IP will suffice).  However, this is a very heavy course because I will cover advanced algorithm techniques and will NOT have time to refresh you on undergraduate algorithms and data structures.  Whenever necessary, students are expected to make up the gap on their own.  The objective is to go well beyond the basic level of understanding that is typically offered at an undergraduate networking course.
• The course also includes a research project. In groups of 3-4 students, you will produce some results that either demonstrate creativity or significant effort.
• Every student MUST fill in the course survey form and print out and submit the "receipt page".
  
• This course reused some materials (including the choice of textbook) from last year's CS6250 taught by Prof. Dovrolis with permissions.

Textbook and additional references

Network Algorithmics

The other half will come from research papers (many by myself). 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):

• M. Crovella and B. Krishnamurthy, Internet Measurement: Infrastructure, Traffic and Applications, 2006
• A. Kumar, D. Manjunath and J. Kuri, Communication Networking, An Analytical Approach , 2004

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

• M. Donahoo and K. Calvert, TCP/IP Sockets in C (or Java): Practical Guide for Programmers, 2000
• W. R. Stevens, UNIX Network Programming, Volume 1 (2nd edition): Networking APIs - Sockets and XTI, 2/e , 1998
• W. R. Stevens, UNIX Network Programming, Volume 2 (2nd edition): Interprocess Communications, 1999

Syllabus - Schedule

First part: Router/switch architectures and algorithms

• Week-1: Introduction, overview of router architectures and hardware
  Readings: Varghese chapters-1 and 2.2,  A brief history of the Internet by B. Liener et al., and IP router architectures, an overview by J. Aweya. 
  

• Week-2: Statistics counter array architectures by Dr. Qi Zhao and multicast protocols by Prof. Mostafa Ammar
  Readings: Varghese chapter-16.2, references [SIPM02] and [RV03] therein, and our counter array paper , and SLIDES (NEW !!!!!!)
  

• Weeks-3 and 4: Internet routing protocols (OSPF etc. + BGP) by Prof. Nick Feamster (see slides below)
  Readings: Varghese chapter-16 (I will cover the whole thing in the fifth week).
  

http://www.cc.gatech.edu/~feamster/tmp/cs6250-fall2007-1.ppt

• Week-5: IP lookup algorithms (i.e., longest prefix match) and some "leftover issues" from weeks 1--4
  Readings: Varghese chapter-11 and Dynamic pipelining: making IP-lookup truly scalable by J.Hasan et al.

• Week-6: Packet classification algorithms
  Readings: Varghese chapter-12

• Week-7:
  Readings: 

• Week-8:  Midterm on Oct 10th (Wed.) in class
  Readings: 

• Week-9 and 10: Packet scheduling algorithms and RED/AQM 
  Readings: Varghese chapter-14 (contents I covered in class and the Virtual Clock scheduling algorithm)
  

• Week-11 and 12: Router algorithms for network measurements (chapter-16, statistics counter array algorithms and trajectory sampling ONLY)
  Readings:
  

• Week-13:  Switching algorithms (chapter-13, only the contents I covered in class)
  Readings: Derivation of the saturation throughput of HOL blocking

• Week-14 (thanksgiving week): Final exam review on Nov. 19th and Project demo on Nov. 21st
  Readings:
  

• Week-15:  Project demo on Nov. 26th (Monday) and 30th (Friday)
  Readings:
  

• Week-16: Project demo on Dec. 3rd, Final exam on Dec. 5th, 2007 in class.
  Readings:

Project (tentative)

Perhaps the most exciting part of this course will be the term project. In groups of 3-4 students, you will specify, design, and implement (if possible) something (an algorithm and/or protocol) that is novel (never been done before).  It might be helpful for your project to be related to the course materials, but that is absolutely not necessary.  Whatever excites you. I suggest that you look at the recent (online) proceedings of conferences such as SIGMETRICS, SIGCOMM, or IMC to get some ideas about novel network protocols and algorithms. 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 finish the project within a couple of months.

Project milestones:

1. Form groups, submit 1-page project proposal: DUE Oct. 22nd, 2007
   
2. Final deadline - final project report submission:  DUE Dec. 5th in class
   
3. Demos: Nov. 21st through Dec. 3rd
   

Homeworks

Grading (tentative)

• Midterm: 25%
• Final : 35%
• Project: 30%
• Homeworks: 10%

Course Policies

• 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:
  1. 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).
  2. 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.