COM 3810: Distributed Network Algorithms

Winter 2002

Instructor:  Rajmohan Rajaraman

113 Cullinane Hall                                                                      Work: 617-373-2075
College of Computer Science                                                 Email: rraj@ccs.neu.edu
Northeastern University                                                           Home: 617-232-8298
Boston, MA 02115                                                                     Fax:    617-373-5121


Class meeting times/location:     W 6:00-9:00

Office Hours:  M: 4:00-6:00 PM and W: 2:00-4:00 PM

Prerequisites: You can take this course if you have previously taken a course in either algorithms (COM3390 or COM3392, or equivalent) or networks (COM3510 or COM3515, or equivalent). The material covered in class will delve deeply into algorithmic issues in networking; so a graduate level of mathematical sophistication is required. Please see the instructor if you are unsure whether you are adequately prepared for the class.


Course Description

This course will cover algorithmic issues that arise in networking. We will cover both the theory and practice in the area. More specifically, for each topic we discuss, we will present the following: (i) issues, relevant problems, and concrete problem formulations; (ii) what is out there in the ``real-world''; (iii) promising approaches to solving the problem; and (iv) potential lines of new research. We will focus on 3 broad topics: In addition to the above main components, time-permitting and depending on students' interests, we will briefly survey related topics such as modeling of Internet topologies and Internet traffic, ad hoc networks, and grid computing.


Grading

Since this is an advanced course, we will generally avoid stress-inducing activities such as tests. The course grade will be based on two to three problem sets (worth 30\%), class participation (20\%), and a project (50\%). As mentioned above, each student is required to scribe one lecture.


Readings & Web Resources


Tentative Schedule
 
Date Topic Lecture Notes
March  27 Introduction to Internet routing: Protocols and problem formulations Notes
April 3 BGP convergence and optimal routing algorithms Notes
April 10 Local-control algorithms for network flow and multicommodity flow Notes
April 17 Analysis of the local balancing algorithm; intro to network design Notes
April 24 Provisioning Virtual Private Networks Notes
May 1 Flow/congestion control, TCP dynamics, and max-min fairness Notes
May 8 A duality model for congestion control
May 15 Introduction to resource location algorithms
May 22 Data tracking in peer-to-peer systems (same slides as previous lecture)
May 29 Project presentations
June 5 Project presentations


Lectures and lecture notes

We will have a total of 11 meetings. The first 9 lectures will be offered by the instructor. In the remaining 2, students will present their project work. Each student is required to scribe one lecture. We will put together the lecture notes as a manuscript at the end of the course.


Projects

A list of suggested projects is available here.