Home Page for CMSC858S, Algorithms in Networking, Fall 2004

CMSC858S, Algorithms in Networking, Fall 2004

CSIC 3118, Tuesday and Thursday 11-12:15

Instructor: Aravind Srinivasan

Course Outline

The course studies rigorous algorithms that underlie several issues in networking: e.g., peer-to-peer networks, sensor networks, and packet-marking for IP-traceback. (A more detailed syllabus is given below.) Networks and systems require, of course, more than provably-good algorithms: careful engineering, debugging, simulation, performance analysis etc. are critical. However, as demonstrated by recent breakthroughs in areas such as peer-to-peer networks and Web-search, rigorously-developed algorithms can serve as a solid backbone for working, deployable systems. This course aims to present rigorous approaches to such algorithms in networking, and, more importantly, to discuss techniques which could be put to use in future.

Pre-requisites: a strong background in undergraduate algorithms. A high-school-level exposure to probability is sufficient; all required probabilistic ingredients will be developed in the course. The two main additional requirements are: (i) an interest in applying quantitative approaches to system-design, and (ii) enthusiasm to collaborate in small groups of students -- collaborative work will be strongly encouraged in the homeworks and project.

Syllabus

Some of the course will be tailored according to the interests of the class; a broad outline is as follows (and is subject to change).

Probabilistic tools: expectation, moments, tail-bounds, sampling, etc; applications of such tools
Basic distributed algorithms (e.g., backoff protocols, resource allocation)
Overlay and P2P networks
- Consistent Hashing
- Some systems such as Chord and the NICE platform, analyses
- "Know thy neighbor's neighbor", network topologies, insights from social networks
- Unstructured P2P systems
- Minimizing network-distance in lookups
Wireless and Sensor networks: protocols, data-aggregation, robustness, capacity, power-control
Probabilistic Packet-Marking for dealing with DoS Attacks
Robustness to Failure and Attacks
Other topics, as time permits: Web-search, Bloom Filters, Network information theory, Network information flow, Error-correcting codes, Trust in distributed systems.
Guest Lectures: We will also have a few guest-lectures by systems researchers, on the practical aspects of some of the issues we cover.

Coursework and Grading

The course will include a collaborative project. Students will do these projects in small groups, and will be encouraged to come up with their own proposals, which will be evaluated by the instructor; the instructor will also provide a number of possible projects to choose from. In addition, there will be a mid-term, a final, and a few homework assignments. The grading will be: Homework 25%, Project 25%, Mid-Term 20%, and Final Exam 30%. For the final exam, we will stick to the official exam schedule: Monday, December 13, 8-10 AM (note that this is AM, not PM!), in class. The mid-term will be held in mid-to-late October. Further details will be announced soon.

Office Hours

Aravind's office hours will be held in his office AVW 3227, at 2-3PM Tuesdays and Thursdays.

References

The dynamically-updated list of references for the class is here.

Lecture Schedule

Here is the approximate lecture schedule.

Homework

Homework 1, due Sep 30: [pdf]
Homework 2, due Nov 9: [pdf]
Homework 3, due Dec 9: [pdf]

Ungraded Homework

Ungraded Homework 1: [pdf] [ps] [Hint for Problem 5]
Ungraded Homework 2: [pdf]
Ungraded Homework 3: [pdf]

Project

The initial announcement for the writeup-requirement is here. The problem-solving part of the project is here.
The dates 9/23 and 10/10 in the writeup-requirement, have been changed on Sept. 23 to 9/25 and 10/12 respectively.

Exams

Mid-Term (slightly updated): [pdf]

Announcements

[Posted Sept. 1st] We don't have any required textbook for the course, and much of the discussion will be based on papers. For students wishing to study the probabilistic fundamentals from a book, the first three chapters of each of the following two books will be useful: Randomized Algorithms by R. Motwani and P. Raghavan, Cambridge University Press, 1995, and The Probabilistic Method, Second Edition by N. Alon and J. H. Spencer, Wiley, 2000.

[Posted Sept. 2nd] The URL for the lecture schedule has been posted above.

[Posted Sept. 7th] Ungraded HW1 has been posted above.

[Posted Sept. 14th] The announcement for the writeup-requirement of the project has been posted above.

[Posted Sept. 18th] The references (to be continuously updated) and the problem-solving requirement of the project, have been posted above.

[Posted Sept. 22nd] An additional good reference book for randomization is Probability and Computing: Randomized Algorithms and Probabilistic Analysis by M. Mitzenmacher and E. Upfal, to be published soon by the Cambridge University Press.

[Posted Sept. 22nd] Homework 1, due Sept. 30, has been posted above.

[Posted Sept. 22nd] The mid-term exam will be held during class hours on Thursday, October 21; it will cover all material covered in class and in the homeworks, up to and including October 14. You can bring your own notes and homework solutions; other material is not allowed.

[Posted Sept. 23rd] The dates 9/23 and 10/10 in the writeup-requirement for the project, have been changed to 9/25 and 10/12 respectively.

[Posted Sept. 28th] Aravind's office hours for Tuesday, 10/05, are canceled; please email him to set up an alternative time, if you had wanted to meet him then. Also, Prof. Bobby Bhattacharjee will teach a guest lecture on 10/07.

[Posted Sept. 30th] To add to the previous announcement, Aravind's office hours for Thursday, 10/07, are also canceled due to his travel; please email him to set up an alternative time, if you had wanted to meet him then.

[Posted Nov. 9th] We have discussed the role of linear-algebraic and related approaches at various points in the course. See this page for one instance of such research being conducted, here at Maryland.