CS7260: Design and Analysis of Netowrk/Router Algorithms and Hardware

Fall 2008, College of Computing, Georgia Tech
class webpage:  http://www-static.cc.gatech.edu/classes/AY2009/cs7260_fall/

Instructor: Prof. Jun (Jim) Xu

Class meeting times: MW 4:35 to 5:55
Classroom: KCAB 2443

Office: KCAB 3350
Office phone: 52168
Office hours:  1:30pm-2:30pm, Monday
Email: jx@cc.gatech.edu

Teaching Assistant: Nan Hua

Office hours: 3pm-5pm, Friday (pls notify me in advance, many thanks!)
Office: 3rd floor common area, KACB. (to the east of the corridor connecting KACB and CCB)
Email: nanhua@cc.gatech.edu


Table of Contents

Course Information and Objectives

Textbook and additional references

Approximately half of the course material will come from the following textbook:

Network Algorithmics

by George Varghese, Morgan Kaufmann, 2005 (available at the engineering bookstore).

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):

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

The reading list will be updated every week, before we cover the corresponding topic.

Jun Xu, Mukesh Singhal, and Joanne Degroat, "A Novel Cache Architecture to Support Layer-Four Packet Classification at Memory Access Speeds," Proceedings of the IEEE INFOCOM 2000, Tel-Aviv, Israel, March 2000.

Jun Xu and Mukesh Singhal, "Cost-Effective Flow Table Designs for High-Speed Internet Routers: Architecture and Performance Evaluation," IEEE Transactions on Computers, 51(9):1089--1099, September 2002.
          Readings: Varghese chapter-16.2, references [SIPM02] and [RV03] therein, and our counter array paper , and SLIDES (NEW !!!!!!)
          Varghese chapter-10.           Readings: Varghese chapter-11 and Dynamic pipelining: making IP-lookup truly scalable by J.Hasan et al.
Efficient fair queuing using deficit round-robin.
M. Shreedhar, G. Varghese
IEEE Transactions on Networking, 1996. 

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.

WF2Q : Worst-case Fair Weighted Fair Queueing.
J. Bennett, H. Zhang
IEEE Infocom, 1996.

Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms.
D. Stiliadis, A. Varma
IEEE Transaction on Networking, 1998.

On Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithms.
Jun Xu, Richard Lipton

On the Computational Complexity of Maintaining GPS Clock in Packet Scheduling.
Qi Zhao, Jun Xu

Exact GPS Simulation with Logarithmic Complexity, and its Applications to an Optimally Fair Scheduler"
Paolo Valente, Sigcomm 2004.

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

Project milestones:

  1. Form groups, submit 1-page project proposal: DUE ????
  2. Final deadline - final project report submission:  DUE ????
  3. Demos: ??? through ???
The project grade will be determined at the end of the semester taking into account all previous milestones.

Possible project ideas:

1.  Read the paper "Exact GPS Simulation with Logarithmic Complexity, and its Applications to an Optimally Fair Scheduler" by Paolo Valente (U. Pisa) that appeared in Sigcomm 2004. URL: http://www.sigcomm.org/sigcomm2004/papers.html#Exact_GPS    Then think about whether the augmented data structure can be further improved (say by a constant factor) by playing with variants of balanced trees.

2. Read the paper by Hao Wang and Bill Lin, "Pipelined van Emde Boas Tree: Algorithms, Analysis, and Applications," IEEE Infocom,, Anchorage, AK, May 7-11, 2007.  Think about whether other algorithms and data structures that are useful for computer networking can be implemented in hardware (you do NOT need to actually implement it!).


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 several (tentative) such homeworks during the semester. The midterm and final exams will include similar problems with the homeworks.

Homework-1 (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

p397, chapter 16, problems 1, 2, 3, 4
p361, chapter 14, problem 1
p338, chapter 13, problems 3, 4  answers

Grading (tentative)

Course Policies