CS7260: Internetworking Architectures and Protocols

(Design and Analysis of Network/Router Algorithms and Hardware)

  Spring 2019, College of Computing, Georgia Tech
class webpage:  http://www-static.cc.gatech.edu/classes/AY2019/directory-TBD

Class time: TTh 1:30 to 2:45
Classroom: Klaus 2443


Instructor: Prof. Jun (Jim) Xu

Office:  KACB 3350
Office phone:  404-385-2168
Office hours:  Thursdays from 10 to 11, or by appointment.
Email:  jx@cc.gatech.edu


TA: Long Gong
TA Office hours: Fridays from 2 to 3 in the common area near Klaus 3332

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.

The ``standard" GPS simulator code, the caveats of which are explained in the above paper.

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.

My Sigmetrics'07 tutorial slides on network data streaming: 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



Project

 Students shall form groups of 3 to 4 people each to work on group projects. Every group project MUST be focused on a Network Algorithmics topic. Project reports on unrelated or marginally related topics (e.g., TCP congestion control mechanisms or BGP routing protocols) will receive little or no credit. A group project can take any of the following three different forms.

1. A research project that produces new network algorithmics solutions, e.g., new packet classfication techniques for SDN applications or new switching algorithms.

2. An in-depth survey of a core or emerging network algorithmics topic, e.g., how single root I/O virtuation technology can be used for building future network algorithmics solutions.

3. A set of 3 to 4 nontrivial exercise problems -- focused on a single core algorithmics topic and balanced across the subtopics -- that have the same level of sophistication as the example problems I are going to show you in class.  Since a group has almost a whole semester to do it, I expect this set to be of very high quality.  Needless to say, solutions need to be produced and submitted along with the exercise problems.

Homeworks

A couple of regular homework assignments and possibly a programming assignment will be distributed during the semester.

Grading (tentative)

Course Policies