CS 7260: Internetworking Architectures and Protocols

Spring 2003

Course Objectives

Understand in depth the major network, routing, and transport protocols and mechanisms used in the Internet today
Become familiar with the networking research tools of simulation, traffic analysis, and active measurements
Appreciate some open research issues related to Internet routers, routing, congestion control, traffic characteristics, naming & addressing

Prerequisites

CS6250 (Computer Networks) or an equivalent graduate-level networking course.

Instructor: Constantinos Dovrolis

dovrolis@cc.gatech.edu

Teaching assistant: Hao Jiang

hjiang@cc.gatech.edu

Course Information

Class meeting times: MW 17:05-18:25
Classroom: 17 CCB
Midterm exam: March 10 (in class)
Final exam: April 28, 5:00-7:50pm (in Physics L5)

`What's New' and Important Dates

Have a nice summer!

Syllabus - Schedule

Please note that the following schedule is somewhat tentative.

Mon Jan-6, Class #1: Course objectives and overview

Internet routers: hardware architecture and packet processing algorithms

Wed Jan-8, Class #2: Router hardware architectures
Mon Jan-13, Class #3: Crossbar switch scheduling algorithms
Wed Jan-15, Class #4: Longest-match prefix algorithms and IP lookups
Mon Jan-20: Holiday
Wed Jan-22, Class #5: Flow classification algorithms
Mon Jan-27, Class #6: Packet scheduling algorithms
Wed Jan-29, Class #7: Traffic limiting/shaping algorithms
Mon Feb-3, Class #8: Quality-of-Service mechanisms

Wed Feb-5, Class #9: Network Simulator (NS) seminar (Slides)

Internet routing protocols and their evaluation

Mon Feb-10, Class #10: Intradomain routing and OSPF
Wed Feb-12, Class #11: Intradomain routing and traffic engineering
Mon Feb-17, Class #12: Interdomain routing and BGP
Wed Feb-19, Class #13: BGP and policy-based routing
Mon Feb-24: Class #14 End-to-end routing performance
Wed Feb-26, Class #15: Overlay networks

Mon Mar-3: Spring break
Wed Mar-5: Spring break
Mon Mar-10: Midterm

End-to-end congestion control in the Internet

Wed Mar-12, Class #17: Review of TCP congestion control algorithms
Mon Mar-17, Class #18: Fundamentals of end-to-end congestion control
Wed Mar-19, Class #19: TCP throughput modeling and TCP-friendlyness
Mon Mar-24, Class #20: Active Queue Management (AQM) and RED
Wed Mar-26, Class #21: TCP as the WWW transport protocol
Mon Mar-31, Class #22: Recent extensions and open issues in TCP

Traffic measurement methodologies and objectives

Wed Apr-2, Class #23: Network traffic statistical characteristics
Mon Apr-7, Class #24: Scaling effects in network traffic
Wed Apr-9, Class #25: Bandwidth estimation (part I)
Mon Apr-14, Class #26: Bandwidth estimation (part II)

Naming and Addressing

Wed Apr-16, Class #27: DNS and its usage in Content Distribution Networks
Mon Apr-21, Class #28: Network Address Translation (NAT) boxes

Summary and architectural trends

Wed Apr-23, Class #29: The end-to-end principle revisited
Mon Apr-28: Final exam

Reading list

Each class will be based on a recent research paper. The reading list for each class will be posted at this web page before the corresponding class.

The Design Philosophy of the DARPA Internet Protocols, by D. D. Clark, ACM SIGCOMM 1988.
Jan 6 class.
IP Router Architectures: An Overview, by James Aweya (Nortel Networks).
Jan 8 class.
iSLIP: A Scheduling Algorithm for Input-Queued Switches, by Nick McKeown. IEEE Transactions on Networking, Vol 7, No.2, April 1999.
Jan 13, 15 classes.
Survey and Taxonomy of IP Address Lookup Algorithms, by M. A. Ruiz-Sanchez, Ernst W. Biersack, and Walid Dabbous. IEEE Network Magazine, 15(2):8--23, March/April 2001.
Jan 22, 27 classes.
Algorithms for Packet Classification, by Pankaj Gupta and Nick McKeown. IEEE Network, March 2001.
Jan 27, 29 classes.
WF2Q: Worst-Case Fair Weighted Fair Queueing, by J. Bennett and H. Zhang. IEEE INFOCOM 1996.
Feb 3 class.
Theories and Models for Internet Quality of Service, by Victor Firoiu, Jean-Yves Le Boudec, Don Towsley, Zhi-Li Zhang. In Proceedings of IEEE, special issue on Internet Technology, August 2002.
Optional reading.
Difficulties in Simulating the Internet, by S. Floyd and V. Paxson. IEEE/ACM Transactions on Networking, August 2001.
Feb 5 class.
OSPF Version 2 , by J. Moy. IETF RFC 1583, 1994.
Feb 10 class (read only the parts of the RFC that will be discussed in class).
Internet Traffic Engineering by Optimizing OSPF Weights, by Bernard Fortz, Mikkel Thorup. In IEEE INFOCOM 2000.
Feb 12 class.
A Border Gateway Protocol 4 (BGP-4), by Y. Rekhter and T. Li. IETF RFC 1771, 1995.
Feb 17 class. (lecture slides by Ola Nordstrom)
The Impact of Internet Policy and Topology on Delayed Routing Convergence, by C. Labovitz, R. Wattenhofer, S. Venkatachary, A. Ahuja. In IEEE INCOCOM 2001.
Feb 19, 24 classes.
The End-to-end Effects of Internet Path Selection, by Stefan Savage, Andy Collins, Eric Hoffman, John Snell and Tom Anderson. Proceedings of the 1999 ACM SIGCOMM Conference, 1999.
Feb 26 class.
A Case for End System Multicast, by Yang-hua Chu, Sanjay G. Rao, Srinivasan Seshan and Hui Zhang. In IEEE Journal on Selected Areas in Communication (JSAC).
Optional reading.
Congestion Avoidance and Control, by V. Jacobson and M. Karels. ACM SIGCOMM 1988.
Mar 12 class.
TCP Congestion Control, by Mark Allman, Vern Paxson, W. Richard Stevens. IETF RFC 2581.
Mar 12 class.
Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks, by D. Chiu and R. Jain. Journal of Computer Networks and ISDN, Vol. 17, No. 1, June 1989, pp. 1-14.
Mar 17 class.
Random Early Detection (RED) gateways for Congestion Avoidance, by Floyd, S., and Jacobson, V. IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413.
Mar 19 class.
Modeling TCP Throughput: A Simple Model and its Empirical Validation, by J. Padhye, V. Firoiu, D. Towsley and J. Kurose. ACM SIGCOMM 1998.
Mar 24 class.
A Web Server's View of the Transport Layer, by Mark Allman. ACM Computer Communication Review, 30(5), October 2000.
Mar 26 class.
Promoting the Use of End-to-End Congestion Control in the Internet, by S.Floyd and K.Fall. IEEE/ACM Transactions on Networking, Aug 1999.
Mar 31 class.
Bandwidth estimation: metrics, measurement techniques and tools, by R.S.Prasad, M.Murray, C.Dovrolis, and K.Claffy To appear in IEEE Network Magazine, 2003
Apr 2 class.
End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation with TCP throughput, by Manish Jain and Constantinos Dovrolis. IEEE/ACM Transactions on Networking, August 2003.
Apr 7 class.
On the Self-Similar Nature of Ethernet Traffic (Extended Version), by W.Leland, M.Taqqu, W.Willinger, D.Wilson. IEEE/ACM Transactions on Networking, February 1994.
Apr 9,14 classes.
Experimental Queueing Analysis with Long-Range Dependent Packet Traffic by A.Erramilli, O.Narayan, W.Willinger. IEEE/ACM Transactions on Networking, 1996.
Optional reading.
On the Effectiveness of DNS-based Server Selection, by Anees Shaikh (IBM Research), Renu Tewari (IBM Research), Mukesh Agrawal (University of Michigan). In IEEE Infocom 2001.
Apr 16 class.
The IP Network Address Translator (NAT), by K.Egevang and P.Francis. IETF RFC 2631.
Apr 21 class.
Rethinking the Design of the Internet: end to end arguments vs. the brave new world, by D.D. Clark and M.S.Blumenthal. In ACM Transactions on Internet Technology (2000).
Apr 23 class.

Other references

The following books may be useful for refreshing your background, and for going deeper on specific topics.

L.L.Petterson and B.S.Davie, Computer Networks: A Systems Approach (second edition) , 1999
J.Kurose and K.Ross, Computer Networking, A top down approach featuring the Internet , 2000
S.Keshav, An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network , 1997
J.Walrand and P.Varaiya, High-Performance Communication Networks (second edition) , 1999
R. Perlman, Interconnections: Bridges, Routers, Switches, and Internetworking Protocols , 2000
J.T.Moy, OSPF: Anatomy of an Internet Routing Protocol , 1998
C.Murphy, R.White, V.Bollapragada, Inside Cisco IOS Software Architecture , 2000
S. Halabi and D.McPherson, Internet Routing Architectures (second edition) , 2000
B.S.Davie and Y.Rekhter, MPLS: Technology and Applications , May 2000

There will be four assignments. The assignments will cover active delay/loss and routing measurements, simulation experiments using NS, traffic analysis from network traces, and the thorough review of a research paper. You will have roughly three weeks for each assignment. A short description for each assignment follows.

The following due dates are tentative.

First assignment: Due Feb 3
In this assignment, you will perform a number of measurements over the `real Internet' using tools such as traceroute, ping, and wget. You will use these measurements to study the characteristics of routing, losses, delays, and throughput in the Internet.
Second assignment: Due Feb 28
In this assignment, you will study a research paper that you will have to carefully evaluate, and then write a thorough review answering specific questions.
Third assignment: Due Apr 7
In this assignment, you will simulate a simple network of Drop-Tail and RED routers with different types of TCP and UDP flows. You will experiment with various settings of network and traffic parameters.
Fourth assignment: Due Apr 23
In this assignment, you will be given a traffic trace from a backbone Internet link. You will process the trace and perform measurements regarding the packet size distribution, the application usage, the number and size of flows, the interarrivals distribution, etc.

Grading

Class participation: 20%
Assignments: 40% (10% for each assignment)
Midterm: 20%
Final: 20%