CS 591

Computer Science Department
College of Arts and Sciences

Algorithmic Aspects of Computer Networks  

     Instructor:  Prof. John Byers
       Meetings:  Monday: 3-6 PM 
 Class Location:  STH B20 
Office Location:  MCS 280
   Office Hours:  Thu. 9:30 - 12:30, and by appointment.
          Phone:  353-8925
            FAX:  353-6457 
          Email:  byers@cs.bu.edu
            Web:  http://www.cs.bu.edu/fac/byers


Course Overview

Today's complete 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 and Web-related problem domains in recent years. 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.


The course is geared primarily toward PhD students who are interested in pursuing a career in either networking research or algorithms. CS 555 or equivalent is a required prerequisite for this course, as is CS 530 (co-requisite). Masters students and undergrads who did excellent work in CS 555 are also 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 for the class are posted here.

Course Presentations took place on Monday, April 29th, in MCS 135.

The Reading List

Bloom Filters

Consistent Hashing and Retrieval

Information Dispersal and Erasure Codes

Indexing the Web

Optimizing Routing Lookups

A Late Entrant (classifiable under several possible categories)

Supplemental Textbooks (both worth owning)