MS&E 319: Topics in Network Algorithms, Winter 2005-06, Stanford University

MW 2:15-3:30, Terman 453.


Instructor: Ashish Goel, Terman 311, ashishg @


Essential Class Information


Reading List

Scribed Lecture Notes

Some suggested projects


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


Essential Class Information


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.





  1. Chernoff bounds and the Lovasz Local Lemma – a brief primer.
  2. Brief example demonstrating the instability of FIFO (ppt pdf)
  3. Homework 1



Reading List


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 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.



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.



List of suggested projects


  1. Work-conserving, low buffer packet routing algorithms
  2. Practical low-buffer protocols in the network context
  3. Tamper-proof bloom filters for packet processing
  4. Fair protocols – theory
  5. Fair protocols --  implementation


Project choices are due by Fri 1/27. Please make an appointment if you would like to get additional details.