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

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

Instructor: Prof. Jun (Jim) Xu

Office:  KACB 3350
Office phone:  404-385-2168
Office hours:  MW 2 to 3pm
Email:  jx@cc.gatech.edu


TA: Maria Konte
Office: Networking group lab at KACB 3337 (at the northwest corner)
Office hours: Fridays 9 to 11am
Email: mkonte@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 Engineer's 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 (subject to adjustments)

The reading list will be updated every week, before we cover the corresponding topic.  The schedule is approximate and subject to changes.


P. Valente, “Exact GPS simulation with logarithmic complexity, and its application to an optimally fair scheduler“, IEEE/ACM Transactions on Networking (ToN), February 2008.
We just talked about the example presented in its Figure 1 in class.
Zhao, Q., Xu, J. ``On the Computational Complexity of Maintaining GPS Clock in Packet Scheduling'', in Proc. of IEEE Infocom 2004.

Xu, J., and Lipton, R. 2002. ``On Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithms'' , ACM SIGCOMM'2002, Pittsburgh, PA, August 2002.  

A paper of mine about re-use distance and caching:

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.

Chapter 14 of  this book is devoted to the topic of augmented data structures.

 
Streaming Algorithms for Counting Distinct Elements (Slides)

I could not find the "Walmart example" I covered in class.  This one is close enough or even better.

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



Special Homework Assignment

1. Each student is required to scribe one lecture and submit the scribe notes, including both the source (Word or LaTeX and figure files if applicable) and the PDF files, one week after the lecture via T-square.  Please include your full name, but NOT your GTID, in the scribe notes. 

2. Each student is required to design a nontrivial exercise problem (typically related to the content of the lecture he or she scribes) that has the same level of sophistication as the example problems I are going to show you in class.  You need only to design one and have almost a whole semester to do it so I expect it to be of high quality.  You will learn a lot from designing just a high-quality exercise problem.  Needless to say, you also have to type up the solution.  Please submit both the source and the PDF files via T-square.   Please include your full name and your GTID.

Homeworks

A couple of regular homework assignments will be distributed during the semester.

Grading (tentative)

Course Policies