3810Distributed Network AlgorithmsSpring 200227 March 20023

Reference List

This is a tentative reference list. It will be updated as we go along. For an up-to-date list, please consult the course homepage.

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, by D. Bertsekas and R. Gallager, Prentice-Hall, 1992.

Routing and Network Design

• ``A Simple Approximation to Minimum-Delay Routing'', by Srinivas Vutukury and J.J. Garcia-Luna-Aceves, SIGCOMM 1999.

• ``Improved Approximation Algorithms for the Multi-commodity Flow Problem and Local Competitive Routing in Dynamic Networks'', by B. Awerbuch and F. T. Leighton, STOC 1994.

• ``Real-time Model and Convergence Time of BGP'', by Davor Obradovic, to appear in Proceedings of IEEE Infocom, 2002.

• ``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'', by 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'', by S. Low and D. Lapsley, IEEE/ACM Transactions on Networking, 1999.

• ``Optimization Flow Control, II: Implementation'', by S. Athuraliya, and S. Low.

• ``Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management'', by 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'', by S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, Proceedings of ACM SIGCOMM, 2001.