Instructor: Ashish Goel, Terman 311, ashishg @ stanford.edu
The
list of projects, reading list, and handouts are perpetually under
construction.
There
will be no class on Wed Feb 15th. There will be a make-up class on Thu Feb 23rd
from 9:15-10:30.
Auditors:
Please sign on to the class email list, msande319-win0506-guests using
majordomo. Instructions are at http://lists.stanford.edu/majordomo_basics.html
The course will discuss advanced algorithmic concepts
for the design and analysis of network protocols. Will discuss open problems
and potential applications.
List of topics (subject to change): Packet
routing and scheduling; network coding; bandwidth allocation and flow control;
fairness; adversarial queueing theory; stability of protocols; algorithms for
peer-to-peer systems; gossip style algorithms. Please note that this is not a
comprehensive list but a subjectively chosen subset of important topics in this field.
Grading: There will be four
homework assignments. Limited collaboration will be allowed on the homework
assignments. I would prefer to have everyone enrolled using the P/NC option.
There will be an optional project. If you do the project, you can omit any two
homeworks. All students will have to scribe one lecture.
Prerequisites: Algorithms
at the level of CS 161 (preferably 261). Linear programming at the level of
MS&E 211. Networks at the level of EE 284/CS 244a.
Packet Routing.
Main Paper discussed in class:
Leighton, Maggs, Rao. Packet routing
and job-shop scheduling in O(congestion+dilation) steps, Combinatorica, Vol.
14, No. 2, 1994, pp. 167-180. Since the above version is not very
portable, I have put up a pdf version
here (thanks, Arash!).
Additional recommended reading:
Srinivasan and Teo. A constant-factor approximation algorithm for packet
routing, and balancing local vs. global criteria.
Enachescu, Ganjali, Goel, McKeown, and Roughgarden. Routers with very small buffers.
Adversarial Queueing Theory
Main paper discussed in class:
Andrews, Awerbuch, Fernandez, Leighton, Liu,
Kleinberg. Universal-stability results and
performance bounds for greedy contention-resolution protocols.
Additional recommended reading:
Bramson.
Convergence to Equilibria for Fluid Models of FIFO Queueing Networks.
Queueing Systems, volume 22(1-2), pages 5-45 (1996)
Bhattacharjee, Goel, Lotker. Instability of FIFO at Arbitrarily Low Rates in the
Adversarial Queueing Model.
Gamarnik. On deciding stability of constrained random walks and
queueing systems.
Borodin, Kleinberg, Raghavan, Sudan, and Williamson. Adversarial queuing theory.
Feige. Nonmonotonic phenomena in packet routing.
Randomized Load Balancing
Valiant, A scheme for fast parallel communication,
SIAM Journal on Computing, Vol. 11, No. 2, pp. 350-361, 1982. You can read a
description of this in the text by Raghavan and Motwani, Chapter 4.
Rui Zhang-Shen's slides (pdf ppt) summarizing the
example application. See http://yuba.stanford.edu/~rzhang/VLB/ for more details.
Primal Dual Algorithms
Main papers discussed in class (in varying detail):
Garg and Konemann. Faster and Simpler Algorithms for
Multicommodity Flow and other Fractional Packing Problems.
Kelly, Maulloo, Tan. Rate control in communication networks: shadow prices,
proportional fairness and stability.
Awerbuch, Azar, and Plotkin.Throughput competitive on-line routing.
Additional recommended reading:
Bartal, Byers, and Raz. Global Optimization Using Local
Information with Applications to Flow Control.
Plotkin, Shmoys, and Tardos. Fast approximation algorithms for fractional packing and
covering problems.
Fairness
Main paper discussed in class:
Cho and Goel. Bandwidth allocation in networks: a
single dual-update subroutine for multiple objectives.
Additional recommended reading:
Cho and Goel. Pricing for fairness: distributed
resouorce allocation for multiple objectives..
Kleinberg, Rabani, and Tardos. Fairness in Routing and Load Balancing.
Compact Routing (and Peer-to-peer systems)
Main papers discussed in class (in varying detail):
Stoica, Morris, Karger, Kaashoek, Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet
applications.
Cowen. Compact
Routing with Minimum Stretch.
Arias, Cowen, Laing, Rajaraman, and Taka. Compact routing with name independence.
Additional recommended reading:
Krioukov and Claffy. Toward
Compact Interdomain Routing. If
you have to read one paper on compact routing, read this one first. Also
as an interesting example of how algorithms can contribute to practice.
(thanks, Mei)
Thorup and Zwick. Compact routing schemes.
Plaxton,
Rajaraman, and Richa. Accessing Nearby Copies of Replicated
Objects in a Distributed Environment.
Sensor networks – data aggregation and gossip
Main papers discussed in class (in varying detail)
Kempe,
Kleinberg, Demers. Spatial gossip and resource location protocols.
Nath,
Gibbons, Seshan, and Anderson. Synopsis diffusion for robust aggregation in sensor
networks.
Enachescu,
Goel, Govindan, and Motwani. Scale free aggregation in sensor
networks.
Additional recommended reading:
Boyd,
Ghosh, Prabhakar, and Shah. Randomized gossip algorithms.
Moallemi
and Van Roy. Consensus propagation.
Goel,
Rai, and Krishnamachari. Sharp thresholds for monotone
properties in random geometric graphs.
Note: This is not a network-algorithms
bibliography. Many (most) good papers in this field are omitted since they are
out of the scope of a single quarter class.
Project choices are due by Fri 1/27. Please make an
appointment if you would like to get additional details.