Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Scheideler: Theory of Network Communication

600.348/448: Theory of Network Communication

Fall Term 2003

Christian Scheideler

Course Structure

Lectures: MTW 1, Shaffer 101

Topics

The course covers current state-of-the-art topics in the area of theory of communication in distributed systems. This includes an introduction to various communication models and important routing parameters and networks. Also, strategies for topology control and routing in overlay networks, load balancing strategies, and distributed data management strategies will be presented. Particular emphasis will be on those strategies that support robust and efficient distributed computing over the Internet, and communication and data management in mobile ad hoc networks and peer-to-peer networks. Weekly assignments. Some knowledge of probability theory is helpful. Prerequisite: 600.344/444 or permission. [Analysis] Students receive credit for 600.348 or 600.448, but not both.

Grading

1/3: assignments
1/3: mid-term exam
1/3: software project

Syllabus

The lecture is based on recent research papers. Lecture notes will be posted below.

Sep 8-10: Network flows I: Shortest paths (in ps and pdf)
last updated 09/17/03
Sep 15-17: Network flows II: Single-commodity flows (in ps and pdf)
last updated 09/24/03
Sep 22-24: Network flows III: Multi-commodity flows (in ps and pdf)
last updated 09/24/03
Sep 29 - Oct 1: Network theory (in ps and pdf)
Oct 6-8: Routing (in ps and pdf)
Oct 13: Fall break
Oct 14-15: Scheduling (in ps and pdf)
Oct 20: Midterm exam (in ps and pdf)
Oct 21-22: Hashing (in ps and pdf)
Oct 27-29: Caching (in ps and pdf)
Nov 3-5: Supervised overlay networks (in ps and pdf)
Nov 10-12: Overlay networks for searching (in ps and pdf)
Nov 17-19: Overlay networks for name service (in ps and pdf)
Nov 24-26: Overlay networks for wireless systems (in ps and pdf)
Dec 1-3: Sensor networks (in ps and pdf)
Dec 8: Open discussion
Dec 18: Software project due

Assignments

Assignment 1 (in ps and pdf) and its solution (in ps and pdf)
Assignment 2 (in ps and pdf) and its solution (in ps and pdf)
Assignment 3 (in ps and pdf) and its solution (in ps and pdf)
Assignment 4 (in ps and pdf) and its solution (in ps and pdf)
Assignment 5 (in ps and pdf)
Assignment 6 (in ps and pdf) and its solution (in ps and pdf)
Assignment 7 (in ps and pdf) and its solution (in ps and pdf)
Assignment 8 (in ps and pdf)
Assignment 9 (in ps and pdf)
Assignment 10, due Dec 3 (in ps and pdf)
Further assignments will be posted here...

Assignments will be posted here every Wednesday, and their solutions have to be submitted till the following Wednesday, 1 pm. At most two people are allowed to work together on an assignment, but there has to be a separate submission for each person. Please indicate on your submission with whom you collaborated to solve the assignment (if any). Also, please write your name and the course (348 or 448) for which you registered clearly on your submission. If you have questions about what is allowed and what is not, please read the ethics code of the department or the guide to Academic Ethics for Undergraduates.

Software

Code for the elementary Spheres Simulation Environment:

A simple Ping mechanism using the Spheres Simulation Environment
A simple program for computing the minimum node ID
An example implementation of the Bellman-Ford algorithm
An example implementation of a Synchronization mechanism
An example implementation of the T-balancing algorithm
An example implementation of the Discrete Awerbuch-Leighton algorithm
A program for generating nxn-grids of arbitrary size
A program simulating x-y routing in an nxn-grid
A program simulating consistent hashing on a cycle

Code for the advanced Spheres Simulation Environment:

A simple example creating a line of 10 nodes
Program by Kendall Giles for assignment 7.
Program by Ryan Caudy for assignment 8.
Program by Joshua Kirshtein for assignment 9.

Miscellaneous programs:

Code for the SHA-1 Hash Function
A hash function carved out of the code above useful for Spheres applications

Writing and compiling C++ Code

Linux/Unix/Mac OS: use, for example, the gcc or g++ compiler
Windows: install, for example, the free compiler Dev C++
For information about the C++ language follow this link.

Office Hours

Christian Scheideler: Mon 5-7 pm, Wyman Park 403
Abhishek Chitlangia: Tue 5-6 pm and Fri 10-11 am, NEB 227

Christian Scheideler

Last modified: Mon Aug 18, 2003