COM 3810: Distributed Network Algorithms

Winter 2002

Reference Books

• Introdution to Algorithms

Cormen, Leiserson, and Rivest, MIT Press, 2001.
• Computer Networks: A Systems Approach

Larry Peterson and Bruce Davie, Morgan Kaufmann, Second edition, 2000.
• Communication Networks: Fundamental Concepts and Key Architectures

Alberto Leon-Garcia and Indra Widjaja, McGraw-Hill, 2000.
• Data Networks

D. Bertsekas and R. Gallager, Prentice-Hall, 1992.

Routing and Network Design

• An Analysis of BGP Convergence Properties

T. Griffin and G. Wilfong, Proceedings of ACM SIGCOMM 1999
• Real-time Model and Convergence Time of BGP

Davor Obradovic, to appear in Proceedings of IEEE Infocom, 2002
• A Minimum Delay Routing Algorithm Using Distributed Computation

R. Gallager, IEEE Transactions on Communications 25:73-85, 1977
• A Simple Approximation to Minimum-Delay Routing

Srinivas Vutukury and J.J. Garcia-Luna-Aceves, Proceedings of ACM SIGCOMM 1999
• Slide: The Key to Polynomial End-to-End Communication

Y. Afek, B. Awerbuch, E. Gafni, Y. Mansour, A. Rosen, and N. Shavit, Journal of the ACM 22:158-186, 1997
• A Simple Local-Control Approximation Algorithm for Multicommodity Flow

B. Awerbuch and T. Leighton, Proceedings of IEEE FOCS, 1993
• Improved Approximation Algorithms for the Multi-commodity Flow Problem and Local Competitive Routing in Dynamic Networks

B. Awerbuch and F. T. Leighton, Proceedings of ACM STOC 1994
• Real-time Model and Convergence Time of BGP

Davor Obradovic, to appear in Proceedings of IEEE Infocom, 2002
• Provisioning a virtual private network : A network design problem for multicommodity flow

A. Gupta , A. Kumar, J. Kleinberg , R. Rastogi , and B. Yener, Proc. 33rd ACM Symposium on Theory of Computing, 2001.
• Algorithms for Provisioning Virtual Private Networks in the Hose Model

Amit Kumar, Rajeev Rastogi, Avi Silberschatz, and Bulent Yener, Proceedings of ACM SIGCOMM, 2001
• Stability of Load Balancing Algorithms in Dynamic Adversarial Systems

E. Anshelevich, D. Kempe, and J. Kleinberg, Proceedings of ACM Symposium on Theory of Computing, 2002

Network Resource Allocation & Scheduling

• Congestion avoidance and control

V. Jacobson, Proceedings of ACM SIGCOMM, 1998.
• Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

D. Chiu and R. Jain, Computer Networks and ISDN Systems
• Optimization Flow Control, I: Basic Algorithm and Convergence

S. Low and D. Lapsley, IEEE/ACM Transactions on Networking, 1999.
• A Duality Model of TCP and Queue Management Algorithms

S. LowITC Specialist Seminar on IP Traffic Measurement, Modeling and Management, 2000, 2002.
• Internet Congestion Control

S. Low, F. Paganini, and J. Doyle IEEE Control Systems Magazine, 2002.
• Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management

S. Kunniyur and R. Srikant.
• Comments on the Performance of Measurement-Based Admission Control Algorithms

L. Breslau, S. Jamin and S. Shenker, Proceedings of IEEE Infocom, 2000.
• Endpoint Admission Control: Architectural Issues and Performance

L. Breslau, E. Knightly, S. Shenker, I. Stoica, and H. Zhang, Proceedings of ACM SIGCOMM, 2000.
• Proportional Differentiated Services: Delay Differentiation and Packet Scheduling

C. Dovrolis, D. Stiliadis, and P. Ramanathan, Proceedings of ACM SIGCOMM, 2000.

Resource Location

• Development of the Domain Name System

P. Mockapetris and K. Dunlap, Proceedings of ACM SIGCOMM, 1988.
• Dynamic DNS, rfcs 2136 and 2137.
• Sparse Partitions

B. Awerbuch and D. Peleg, Proceedings of IEEE Symposium on Foundations of Computer Science, 1990.
• Accessing Nearby Copies of Replicated Objects in a Distributed Environment

C. G. Plaxton, R. Rajaraman, and A. Richa, Theory of Computing Systems, 1999.
• Oceanstore: An architecture for global-scale persistent storage

J. Kubiatowicz, B. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), November 2000.
• Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications

I. Stoica , R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan, Proceedings of ACM SIGCOMM, 2001.
• A Scalable Content-Addressable Network

S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, Proceedings of ACM SIGCOMM, 2001.