CAS CS 559 - Spring 2010
Algorithmic (and Economic) Aspects of Computer Networks

     Instructor:  Prof. John Byers
       Meetings:  TR 11-12:30AM 
 Class Location:  MCS B29
Office Location:  MCS 270 
   Office Hours:  Mon: 9:30-11, Tues: 2:30-4, or by arrangement.
   Office Phone:  3-8925
          Email:  byers_at_cs_dot_bu_dot_edu


Course Overview

Today's complete computer networking researcher must carry a large toolkit. Expertise in network measurement, network modeling, protocol design and systems engineering are perforce. But while many researchers bring these skills to the table, far fewer have deep insight when it comes to questions of algorithms and analysis. This is all the more surprising given the wealth of elegant and essentially algorithmic constructs which have been applied to networking domains in recent years, (including networks arising in biology, physics, and for social networks). This graduate seminar will study 1) fundamental algorithmic principles as relate to networking, 2) how algorithmic methods have been applied to specific networking applications, and 3) the limits of algorithmic practicability, i.e. if and when heuristics should be employed. Increasingly, research in computer networking closely relate to economic considerations: we will therefore also study the interplay between algorithmics, economics, and computer networks.


The course is geared primarily toward graduate students or advanced undergraduates who are interested in pursuing a career in either networking research or algorithms. CS 455/655 or equivalent is a required prerequisite for this course, as is CS 330. Masters students and undergrads who did excellent work in CS 455/655 are encouraged to attend. Most of the papers will delve deeply into algorithmic, statistical or information-theoretic techniques, so a graduate level of mathematical sophistication is expected. Please see the instructor if you are at all uncertain about your level of preparation.

Course Requirements

For class, students will be expected to read and digest approximately two research papers per week (prior to lecture). For the majority of the course, the instructor, along with specialists (see below) will lead discussions on the current set of papers and will lecture on background material needed to understand the next set of papers. For each subsection of the course, a group of students chosen in advance will serve as specialists, i.e. will be experts on the papers we are discussing, and will be expected to help facilitate the discussion, brainstorm about research directions, and help with the presentation of the material (or with supplemental material).

Scribe Notes

The Reading List (subject to change)

Weeks 1-3: Information Dispersal, Erasure Codes, Network Coding

Weeks 4-6: Summarization: Bloom Filters, Sketches, etc.

Weeks 7-8: Consistent Hashing and Applications

Weeks 9-10: Internet Economics. Algorithmic Game Theory.

Weeks 11-13: Network Models vis-a-vis Random Graphs

Weeks 14-15: Potpourri as time allows

Supplemental Textbooks (both worth owning)