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

Spring 2010, College of Computing, Georgia Tech
class webpage:  http://www-static.cc.gatech.edu/classes/AY2010/cs7260_spring

Instructor: Prof. Jun (Jim) Xu

Class meeting times: MWF  1:05 to 1:55
Classroom: KACB  1447

Office:  KACB 3350
Office phone:  404-385-2168
Office hours:  TBD
Email:  jx@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 - Tentative schedule (copied from last year and subject to change)

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

Streaming Algorithms for Counting Distinct Elements (Slides)

"A sketch algorithm for estimating two-way and multi-way associations"
Ping Li and Kenneth W. Church, Computational Linguistics 33(3), 305-354, 2007

Tutorial 1 Tutorial 2

Varghese chapter 13.

Derivation of the saturation throughput of HOL blocking 
-----------------------Old Syllabus Materials-----------------------------------
          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.

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

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.

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

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