CS590R: Algorithms for Communications Networks - Spring 2003
Professor
Gopal Pandurangan
Office: CS 174
Office hours: Mon, Wed 2-3pm or by appointment
Lectures
Tue, Thu: 1:30-2:45pm;
Room: REC 123
Newsgroup
purdue.class.cs590r
About this course
"We make things that make communications networks work" - Slogan of Lucent Technologies.
"Can you hear me now?" - Slogan of Verizon
1) How do packets avoid collision in a Ethernet link?
2) How do packets get routed in the Internet?
3) How to build reliable networks with guarantees?
4) How to maintain connectivity in peer-to-peer or ad-hoc networks?
5) How to route in a mobile network?
6) Is the "six-degrees of separation" myth really true?
7) Does the World Wide Web have a structure?
In this course we will learn and explore algorithmic and mathematical underpinnings of communications networks and in the process hope to
answer the above questions using a rigorous approach.
We use the term communications networks in a broad sense: they include the Internet and WWW (of course), local area networks, peer-to-peer networks,
wireless networks, adhoc networks, mobile networks, networks of parallel computers, and networks of people! (social networks).
Needless to say that this is an important and exciting area where cutting edge research is happening and a
single brilliant algorithmic idea can have a major impact.
We plan to explore the following topics:
1) Probability theory and models
2) Probabilistic algorithms / Randomized Algorithms
3) Routing protocols
4) Queueing models in Networks
5) Collision resolution protocols
6) Flow Control
7) Peer-to-Peer Networks
8) Wireless Networks
9) Adhoc Networks
10) Mobile Networks
11) Social Networks
12) WWW
The course is aimed towards graduate students (and advanced undergraduate students) in Computer Science, ECE, Mathematics, and Statistics.
There are no real prerequisites, but CS580 (Graduate-level Algorithms course) or equivalent is highly recommended. Background in probability theory
is a plus, but not needed. Talk to me if you have any questions.
Textbook/References
The main source of reference will be the lecture notes and slides.
We will not follow any one textbook, but the following references will be helpful, besides papers from journals/conferences.
1) Data Networks by Bertesekas and Gallager.
2) Queueing Systems by Kleinrock
3) Probability Models for Computer Science by Ross
Grading
Every class one (or two) students will be nominated to take lecture notes.
These should be typeset in Latex and turned in the next week.
There will be a "problem of the week" which will be given in class every week and whose solution
will be discussed the following week (in class). This is collaborative i.e., you can discuss with your friends
but the solution has to be written independently (no copying).
There will be no exams, but there will a final project and presentation.
The project should be a theoretical or experimental analysis of significant scope.
Students are required to discuss with me well in advance of their project interests.
The grading split-up is:
lecture notes: 20%
problems of the week: 30%
final project: 50%