Instructor: Prof. Jun (Jim) Xu

Annoucements

• Course materials are essentially the same as CS6250 in Fall 2007.  Therefore, no students from that class are allowed to enroll here!
  

Table of Contents

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

Course Information and Objectives

• In this semester, the syllabus will put a major emphasize on so-called network algorithmics (a.k.a. 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 (see below).
  

• Every student MUST fill in the course survey form and print out and submit the "receipt page".
  

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 book (you don't need to purchase it):

• A. Kumar, D. Manjunath and J. Kuri, Communication Networking, An Analytical Approach , 2004

Syllabus - Tentative schedule (copied from last year and subject to change)

• Week-1 (Jan. 11th through 15th): Introduction, overview of router architectures and hardware
  
• Introduction
• George Varghese's Slide
• CRC
• Varghese Chapter 9.2
• Sparse CRC intermediate polynomial computation programs (gap-simple.cpp, main.c) authored by Prof. Xu in 2001.
  
• "Fast CRC calculation", by Glaise, R.J.   Jacquart, X. , published in IEEE ICCD'93.
  
• Satistics Counters in Network Measurement (to be cont')
  
• Varghese Chapter 16.1

• Week-2 (Jan. 20, Jan. 22)
• Counter Slides (our counter array paper , and SLIDES)
  
• Varghest Chapters 16.2 through 16.9

• Week-3 (Jan. 25 through Jan. 29)
• Counters Continued. (BRICK paper and slides)

• Week-4 (Feb. 1st trough 5th)
• DRAM counters (paper and slides)
  H. Zhao, H. Wang, B. Lin, and J. Xu
  Design and Performance Analysis of a DRAM-based Statistics Counter Array Architecture
  ANCS 2009
• Motwani and Raghavan, Randomized Algorithms, Problem 4.6

• Week-5 (Feb. 8th through 12th)
• Exact Lookups and Prefix-Match IP Lookups
• Readings: Varghese chapters 10 and 11

• Week-6 and 7 (Feb. 15th through 26th)
  
• Prefix-Match IP Lookups and Packet classification algorithms
  
• Readings: Varghese chapter 12

• Homework-1 (No need to turn it in) (solution): p15 problem 1-1, p232 problem 10-1, p267 problems 11-1, 11-2, 11-3, 11-5, 11-14, p397 problems 16-2, 16-3, 16-4, p300 problems 12-1, 12-2, 12-3, 12-4, 12-6, 12-7,
  
• Hints for problem 16-4, Sec. 4.2 of the following paper offered a solution: Zhao, Q., Kumar, A., Wang, J., Xu, J., "Data Streaming Algorithms for Accurate and Efficient Measurement of Traffic and Flow Matrices", Proc. of ACM Sigmetrics 2005, Banff, Canada, June 2005, p.350--361.  ps pdf
• Supplemental problem 1: What is the remainder when we divide the binary polynomial (257, 231, 200, 179, 150, 130} by the generator polynomial in the CRC paper G(x) = (32, 26, 23, 22, 16, 12, 11, 10, 8, 7 , 5, 4, 2, 1, 0)?

• Week-8 (March 1st through 5th)
• Midterm on March 3rd

• Week-9 and 10 (March 8th through 19th)
• Packet scheduling and QoS, Programmable Priority Encoder
<>Readings: Varghese chapter 14, 2.2
<>
<>
<>
<>


A generalized processor sharing approach to flow control in integrated services networks : The Single-Node case.
A. Parekh and R. Gallager.
IEEE Transacting on Networking, 1993.  (We only talked about Theorems 1 and 2 in class) <>
WF2Q : Worst-case Fair Weighted Fair Queueing.
J. Bennett, H. Zhang
IEEE Infocom, 1996.  (We talked about the scheduler and its equivalence to WFQ under certain traffic conditions)

Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms.
D. Stiliadis, A. Varma
IEEE Transaction on Networking, 1998.  (We talked about the definition of latency rate servers in class)

• Week-11 (March 22nd through 26th is the Spring Break)

• Week-12 (March 29th through April 2nd)
• Network data streaming
• Readings:

• Week-13 (April 5th through 9th)
• Network data streaming (cont'd), IP traceback
<>Readings:

• Week-14 (April 12th through 16th)
"Practical network support for IP traceback"
Stefan Savage, David Wetherall, Anna Karlin, Tom Anderson, Sigcomm 2000.
"Advanced and Authenticated Marking Schemes for IP Traceback"
Dawn Xiaodong Song, Adrian Perrig, Infocom 2001.  (This is where 5 out of 8 colors in coupon coding comes from)
“Hash-Based IP Traceback"
Alex C. Snoeren, et al, Sigcomm 2004.
"IP Traceback-based Intelligent Packet Filtering  : A Novel Technique for Defending Against Internet DDoS Attacks"
Minho Sung, Jun Xu, ICNP 2002 (We proved Theorem 1 in class)
“Large-Scale IP Traceback in High-Speed Internet: Practical Techniques and Theoretical Foundation" (ppt)
Jun Li, Minho Sung, Jun Xu, Li Li, S&P 2004.

• Week-15 and 16 (April 19th through 30th)

• Switching algorithms and project presentations
  

• Week-1
• Book 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  & Exact IP Lookup

• Weeks-3,4: Prefix-Match IP Lookup and some "leftover issues"

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

• Week-7: 

• Week-8 and 9: Packet scheduling algorithms and RED/AQM 
  Readings: Varghese chapter-14, Midterm exam on Oct. 15th (Wed.), Oct 13-14 (Mon - Tu) is the midterm recess.
  

• Week-10: IP Traceback
  
  

• Week-11 and 12: Router algorithms for network measurements (traffic matrix estimation, data streaming introduction, trajectory sampling)
  
  "Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads"
  Yin Zhang, Matthew Roughan, Nick Duffield and Albert Greenberg, Sigmetrics 2003
  "Robust Traffic Matrix Estimation with Imperfect Information: Making Use of Multiple Data Sources"
  Qi Zhao, Zihui Ge, Jia Wang and Jun Xu, Sigmetrics 2006.
  Reading material: Chapter 6.5, Probability, Random Process, and Estimation Theory for Engineers. pdf
  

• Week-13 and 14:
  Exact Statistic Counters (pdf)(slides)(Possion Approximation(Reading Material))
  "Tracking join and self-join sizes in limited storage"
  Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy, PODS 1999.
  "Data Streaming Algorithms for Estimating Entropy of Network Traffic"
  Ashwin Lall, Vyas Sekar, Mitsunori Ogihara, Jun Xu and Hui Zhang,  SIGMETRICS 2006
  
  "Data Streaming Algorithms for Efficient and Accurate Estimation of Flow Distribution"
  Kumar, A., Sung, M., Xu, J., Wang, J. Sigmetrics 2004
  
  

• Week-15:  Project demo on ????
  Readings:
  

• Week-16: Project demo on ????, 
  Readings:
• Final term: official final term calender (2 Hours, open to books, notes and papers. No computers.)
  

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/or implement (if possible) something (an algorithm, hardware/software system, or protocol) that is novel and/or requires significant effort.  This project must be related to network algorithmics.  I suggest that you look at the recent (online) proceedings of conferences such as SIGMETRICS, SIGCOMM, ANCS, or IMC to get some ideas about novel network algorithmics.  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 ????
   
2. Final deadline - final project report submission:  DUE ????
   
3. Demos: ??? through ???
   

Homeworks (copied from last year's -- subject to change -- please ignore it till further notice)

Grading (tentative)

• Midterm: 17% (scheduled on 3/3/2010, Wednesday, from 1:05 to 1:55)
• Final : 33% (scheduled on 5/5/2010, Wednesday, from 2:50 to 4:40)
• Project: 30%
• Homeworks (including course evaluation): 20% (at least half of this 20% goes to filling in course evaluation)
  

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.