In this semester, the syllabus will put a major emphasis on so-called network algorithmics (a.k.a.
router/switch architectures and algorithms).
We will study
and protocols used by modern routers/switches to perform data plane
functions including forwarding, address/prefix lookups, switching,
flow classification, flow monitoring and measurement, IP traceback and
other security functions. In other words, we will study almost
everything about a router/switch except routing, which is a control
plane function and out of the scope of this course.
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). This is a reasonably heavy course
because I will cover advanced algorithmic techniques and will NOT have
time to refresh you on undergraduate
algorithms and data
structures. Whenever necessary, students are expected to
the gap on their own.
course includes a group project (see below).
Every student MUST fill in the course survey form and print out
and submit the "receipt page".
IEEE Transacting on Networking, 1993. (We
will talk about
Theorems 1 in class) WF2Q :
Worst-case Fair Weighted Fair Queueing.
J. Bennett, H. Zhang
IEEE Infocom, 1996. (We will talk about the scheduler and its
equivalence to WFQ under certain traffic conditions)
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 protocol) 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.
All work for this class is to be done
individually. You are strongly urged to familiarize yourselves with the
Honor Code rules.
Specifically, the following is not allowed:
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).
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 homework assignments or project reports will be accepted
beyond two lenient days total for the entire semester.