CS856 - Advanced Topics in Distributed Systems:

Internet Transport Performance

Please remember to frequently use the reload button for these pages.

Course Outline, Presentation Slides, and Reading List

We will rotate through a number of topics and cover each topic twice. During the first round, there will be a lecture and we will discuss historical and background material. During the second round, we will discuss selected papers presenting recent research proposals.

Those papers marked with an asterisk (*) are the minimum required reading material for in-class discussion. Material will be added to this list during the term. Papers in bold are the ones to write summaries of. All papers from ACM's and IEEE's Digital Libraries can be downloaded when logged in on UW machines.

Lecture 05.05. - Organization, Introduction (slides: PS/PDF)

RFC 1958 - Architectural Principles of the Internet. B. Carpenter, Ed. June 1996.
RFC 2235 - Hobbes' Internet Timeline. R. Zakon. November 1997
RFC 2990 - Next Steps for the IP QoS Architecture. G. Huston. November 2000.
RFC 3426 - General Architectural and Policy Considerations. S. Floyd. November 2002.
RFC 3714 - IAB Concerns Regarding Congestion Control for Voice Traffic in the Internet. S. Floyd, J. Kempf, Eds. March 2004.
RFC 3724 - The Rise of the Middle and the Future of End-to-End: Reflections on the Evolution of the Internet Architecture. J. Kempf, R. Austein, Eds., IAB. March 2004.

Lecture 12.05. - Packet Scheduling (slides: PS/PDF)

Analysis and simulation of a fair queueing algorithm. A. Demers, S. Keshav, S. Shenker. SIGCOMM 1989.
A generalized processor sharing approach to flow control in integrated services networks: the single-node case. A. K. Parekh, R. G. Gallager. IEEE/ACM Transactions on Networking 1(3), June 1993
A generalized processor sharing approach to flow control in integrated services networks: the multiple node case. A. K. Parekh, R. G. Gallager. IEEE/ACM Transactions on Networking 2(2), April 1994
Virtual clock: a new traffic control algorithm for packet switching networks. L. Zhang. SIGCOMM 1990.
Efficient fair queueing using deficit round robin. M. Shreedhar, G. Varghese. SIGCOMM 1995.
Worst-case fair weighted fair queueing. J.C.R. Bennett, H. Zhang. INFOCOM 1996
Hierarchical packet fair queueing algorithms. J.C.R. Bennett, H. Zhang. SIGCOMM 1996.
Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks. P. Goyal, H. M. Vin, H. Chen. SIGCOMM 1996
Latency-rate servers: a general model for analysis of traffic scheduling algorithms. D. Stiliadis, A. Varma. IEEE/ACM Transactions on Networking 6(5), June 1998

Lecture & Discussion 19.05. - Network Control: Routing & Signalling (slides: PS/PDF)

RFC 3221 - Commentary on Inter-Domain Routing in the Internet. G. Huston. December 2001.
Internet Draft - Analysis of IDR Requirements and History. A. Doria, E. Davies, Eds. February 2002.
Internet Draft - Requirements for Inter Domain Routing. A. Doria, E. Davies, F. Kastenholz. December 2003.
(*) RSVP: A New Resource ReSerVation Protocol. L. Zhang, S. Deering, D. Estrin, S. Shenker, D. Zappala. IEEE Network Magazine. September 1993.
(*) BGRP: A Tree-Based Aggregation Protocol for Inter-domain Reservations. P. Pan, E, Hahne, H. Schulzrinne. Journal of Communications and Networks 2(2), June 2000
Internet Draft - Analysis of Existing Quality of Service Signaling Protocols. J. Manner, X. Fu, P. Pan, Eds. October 2003.
(*) RFC 3031 - Multiprotocol Label Switching Architecture. E. Rosen, A. Viswanathan, R. Callon. January 2001.

Lecture & Discussion 26.05. - Congestion Control: TCP, ECN, and Variants (slides: PS/PDF)

Congestion Avoidance and Control. V. Jacobson, M.J. Karels. SIGCOMM 1988.
Note: Formulas are sometimes not shown correctly in this version. Alternative download.
Random Early Detection Gateways for Congestion Avoidance. S. Floyd, V. Jacobson. IEEE/ACM Transactions on Networking 1(4), August 1993.
RFC 2581 - TCP Congestion Control. M. Allman, V. Paxson, W. Stevens. April 1999.
RFC 3782 - The NewReno Modification to TCP's Fast Recovery Algorithm. S. Floyd, T. Henderson, A. Gurtov.
(*) RFC 3168 - The Addition of Explicit Congestion Notification (ECN) to IP. K.K. Ramakrishnan, S. Floyd, D. Black. September 2001
Resource pricing and the evolution of congestion control. R.J. Gibbens, F.P. Kelly. Automatica 35 (1999).
(*) Service differentiation in ECN networks using weighted window-based congestion control. V. Siris, C. Courcoubetis, G. Margetis. Springer LNCS 2156, September 2001.
(*) Distributed Connection Acceptance Control for a Connectionless Network. R.J Gibbens, F.P. Kelly. ITC 16, June 1999.

Lecture & Discussion 02.06. - Network Architecture: Mobility, Multicast and Overlays (slides: PS/PDF)

RFC 2002 - IP Mobility Support. C. Perkins, Ed. October 1996.
Comparison of IP micromobility protocols. A.T. Campbell, J. Gomez, S. Kim, C.-Y. Wan, Z.R. Turanyi, A.G. Valko. IEEE Wireless Communications 9(1), February 2002.
(*) IP micro-mobility protocols. P. Reinbold and O. Bonaventure. IEEE Communications Surveys and Tutorials, 2003.
Distance Vector Multicast Routing Protocol. T. Pusateri. October 2003. Internet Draft.
RFC 2362 - Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. D. Estrin et al. June 1998.
RFC 3569 - An Overview of Source-Specific Multicast (SSM). S. Bhattacharyya, Ed. July 2003.
(*) Routing in Overlay Multicast Networks. S. Shi, J. Turner. INFOCOM 2002

Seminar 09.06. - Project Proposal Presentations

no reading

Discussion 16.06. - Packet Scheduling

Fair and efficient packet scheduling using Elastic Round Robin. S.S. Kanhere, H. Sethu, A.B. Parekh. IEEE Transactions on Parallel and Distributed Systems 13(3), March 2002.
(*) Stratified Round Robin: A Low Complexity Packet Scheduler with Bandwidth Fairness and Bounded Delay. S. Ramabhadran, J. Pasquale. SIGCOMM 2003.
IP Router Architectures: An Overview. J. Aweya. published as: On the design of IP routers Part 1: Router architectures. J. Aweya. Journal of Systems Architecture 46(6), April 2000.
(*) A highly flexible, distributed multiprocessor architecture for network processing. M. Venkatachalam, P. Chandra, R. Yavatkar. Computer Networks 41(5), April 2003.

Discussion 23.06. - Network Control

(*) BANANAS: An Framework for Explicit, Multipath Routing in the Internet. H.T. Kaur, S. Kalyanaraman, A. Weiss, S. Kanwar, A. Gandhi. Submitted to Computer Networks, 2004. earlier version in FDNA 2003.
(*) An Investigation of Inter-Domain Control Aggregation Procedures. R. Sofia, R. Guerin, P. Veiga. ICNP 2002.
(*) SICAP, a Shared-segment based Inter-domain Control Aggregation Protocol. R. Sofia, R. Guerin, P. Veiga. HPSR 2003.

Discussion 30.06. - Congestion Control

(*) Congestion Control for High Bandwidth-Delay Product Networks. D. Katabi, M. Handley, C. Rohrs. SIGCOMM 2002.
(*) Binary Increase Congestion Control (BIC) for Fast Long-Distance Networks. L. Xu, K. Harfoush, I. Rhee. INFOCOM 2004.
HSTCP, STCP, FAST, etc., see Sally Floyd's page on TCP for Long, High-Bandwidth Paths

Discussion 07.07. - Mobility, Multicast and Overlay Networks

(*) Internet Indirection Infrastructure. I. Stoica, D. Adkins, S. Zhuang, S. Shenker, S. Surana. SIGCOMM 2002.
(*) Resilient Overlay Networks. D.G. Andersen, H. Balakrishnan, M.F. Kaashoek, R. Morris. SOSP 2001.
Topologically-Aware Overlay Construction and Server Selection. S. Ratnasamy, M. Handley, R. Karp, S. Shenker. Infocom 2002.
An Evaluation of Scalable Application-level Multicast Built Using Peer-to-peer Overlays. M. Castro, M. B. Jones, A.-M. Kermarrec, A. Rowstron, M. Theimer, H. Wang, A. Wolman. Infocom 2003.

Discussion 14.07. - Network Architecture

(*) TRIAD: A New Next-Generation Internet Architecture. D.R. Cheriton, M. Gritter. Technical Report, March 2000.
(*) A Delay-Tolerant Network Architecture for Challenged Internets. K. Fall. Technical Report, Intel Research Berkeley, February 2001.
Design guidelines for robust Internet protocols. T. Anderson, S. Shenker, I. Stoica, D. Wetherall. ACM SIGCOMM Computer Communication Review 33(1), January 2003.

Flexible Slot 21.07. - TBA

Seminar 28.07. - Final Project Presentations

no reading

Disclaimer: The above is not intended to be an exhaustive list of existing research in those areas. You are encouraged to search for additional literature.

Other Useful Information

Network Simulation

The Network Simulator - ns-2
On the effective evaluation of TCP. M. Allman, A. Falk. ACM SIGCOMM Computer Communication Review 29(5), October 1999.
Difficulties in simulating the internet. S. Floyd, V. Paxson. IEEE/ACM Transactions on Networking 9(4), August 2001.

Efficient Programming

The Aggregate Magic Algorithms
Bentley's Rules (from Writing Efficient Programs)

Research and Writing

Advice on Research and Writing

CS856 main page

Last updated: May 26, 2004