CS 591
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.
Prerequisites
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).
-
Each student is expected to take scribe notes for one lecture reflecting the
technical material as well as the class discussion. Click here
for the scribe note
style file
you are to use
and a sample
.tex file (Lecture 1).
-
A semester-long research project, culminating in a presentation to the
class and a writeup in the style of a conference paper. The project and
presentations will constitute 50% of the overall grade. Suggested
project topics and project deadlines will be announced after the first
few weeks of the course. I will expect students in this class to take
the project very seriously and there will be regular interaction with the
instructor outside of class to work on the projects --- ideally, several/many
of the projects in the class will eventually lead to publishable papers.
-
Class participation will constitute 25% of a student's overall grade
-- this grade will be based both on the student's work as a specialist and
contributions to the class discussion throughout the course.
-
For the remaining 25% of the grade, I will pose a few challenging problems
as homework questions, and we will likely have one or two in-class quizzes
testing the main concepts in the papers and class discussions.
Course Presentations
took place on Monday, April 29th, in MCS 135.
The Reading List
Bloom Filters
-
B. Bloom.
"Space/time trade-offs in hash coding with allowable errors,"
Communications of the ACM, 13(7):422-426, 1970. (From the ACM Digital Library,
accessible only from BUCS machines).
-
L. Fan, P. Cao, J. Almeida and A. Z. Broder,
"Summary
Cache: A Scalable Wide-area Cache Sharing Protocol,"
in Proceedings of ACM SIGCOMM '98.
-
M. Mitzenmacher.
"Compressed
Bloom Filters,"
in Proceedings of PODC 2001.
-
A. Snoeren, C. Partridge, L. Sanchez, C. Jones, F. Tchakountio, S. Kent, W. Strayer
"Hash-Based
IP Traceback,"
in Proceedings of ACM SIGCOMM '01.
Consistent Hashing and Retrieval
-
D. Karger, E. Lehman, F. T. Leighton, M. Levine, D. Lewin, and R. Panigrahy.
"Consistent
hashing and random trees: Distributed caching protocols for relieving
hot spots on the World Wide Web,"
in Proceedings of STOC '97.
-
I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan.
"Chord:
A Scalable Peer-To-Peer Lookup Service for Internet Applications,"
in Proceedings of ACM SIGCOMM '01.
-
S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker.
"A
Scalable Content-Addressable Network,"
in Proceedings of ACM SIGCOMM '01.
Information Dispersal and Erasure Codes
-
A. Shamir.
"How to
Share a Secret,"
Communications of the ACM 22(11), pp. 612-613, 1979.
-
M. Rabin.
"Efficient Dispersal of Information for Security, Load Balancing
and Fault Tolerance,"
Journal of the ACM 38, pp. 335-348, 1989.
(copy available as a handout).
-
M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman and V. Stemann
"Efficient
Erasure Codes,"
IEEE Trans. on Information Theory 47(2), 569-584, Feb. 2001.
(Journal version of the STOC '97 paper).
-
J. Byers, M. Luby, M. Mitzenmacher,
"A
Digital Fountain Approach to Asynchronous Reliable Multicast,"
To appear in IEEE Journal on Selected Areas in Communications, 2002.
(Journal version of the ACM SIGCOMM '98 paper.)
-
J. Byers, M. Luby, M. Mitzenmacher,
"Accessing
Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed
Up Downloads,"
in Proceedings of IEEE INFOCOM '99.
Indexing the Web
-
L. Page, S. Brin, R. Motwani and T. Winograd,
"
The PageRank Citation Ranking: Bringing Order to the Web."
-
J. Kleinberg,
"Authoritative
Sources in a Hyperlinked Environment,"
Journal of the ACM 46, 1999. (Version linked is from SODA 1997).
-
K. Bharat and M. Henzinger,
"Improved
Algorithms for Topic Distillation in a Hyperlinked Environment,"
Proceedings of the 21st International ACM SIGIR Conference on Research and Development
in Information Retrieval, 1998, pp. 104-111.
Optimizing Routing Lookups
A Late Entrant (classifiable under several possible categories)
Supplemental Textbooks (both worth owning)