CS 268 Course Description

CS 268: Graduate Computer Networking

History and structure of general computer networks and the Internet.

Note: New class times and locations:

9-11a.m., 310 SODA
2-3p.m., 306 SODA

Instructors:Dr. Kevin Fall and Dr. Mike Luby TA:Elan Amir

Kevin's Office: 665 Soda, Phone: 486-6357 (LBNL), kfall@ee.lbl.gov

Mike's Office: 665 Soda, Phone: 642-4274x138 (ICSI), luby@icsi.berkeley.edu

Elan's Office: 443 Soda, Phone: 642-8248, elan@cs.berkeley.edu

Lectures: SEE NEW TIMES ABOVE

Office Hours: Wed 11-12 (Kevin) and Wed 3-4 (Mike) in 665 Soda,
Tue 2-3 (Elan) at Cafe Nefeli (on Euclid)

Text Book: Andrew S. Tanenbaum, Computer Networks, 2nd ed, Prentice-Hall Publishers, 1989, ISBN 0-13-162959-X

Class Notes are now on-line for the following lectures:

February 21, 1996 (Topics: IP, addressing, DNS, ICMP, IPv6)
February 28, 1996 (Topics: routing, RIP, DV and LS algorithms, multicast)
March 13, 1996 (Topics: flow and congestion control, DECbit, fairness)
March 20, 1996 (Vern Paxson on Internet traffic measurement and modeling)
RED Gateways (Sally Floyd's RED Gateway Slides)

Reader: The reader is now available (in 2 volumes) for $76.24 at:

Grading:

Grading Breakdown

2 Midterm Examinations 15% each

Final Project 60%

2 Homework Sets 5% each

TOTAL 100%

Homework: Homework will be assigned in class and should be turned in on the day indicated. All homework should be your own work.

The Solutions to the First Homework Assignment are now available.

Homework assignment 2 is now available, and is due 4/17/96 (see updated schedule below).

Exams: There will be two exams. The second exam covers material between covered between the first exam and the end of the course and will be given during the final exam period.

Final Exam Information: The final exam period for CS268 is Saturday, May 11th, 8am - 11am in 3107 Etcheverry. The first half of the time (8:10 - 9:30) will be the second exam. After that, groups will present their projects. Presentations should last about 20 minutes each. (The project write-ups are due May 8th at 5pm, as listed below.)

The First Mid-Term: was given Thursday evening, Feb 22nd, 6-8:30pm in 310 Soda. It was open {book,notes,reader}, and contained anything up to and including the switching material given in lecture on 2/14/96. The approximate break-down is as follows:

Score --- Grade
40-42 --- B
43-47 --- B+
48-55 --- A-
56-69 --- A
70+ ----- A+

Project: Most of the grade for the course is based on a project. The project will generally involve research, some form of implementation and measurement, and a final write-up of about 15 pages. The project may be done individually or in groups of 2-3 persons. Ideas for the projects will be presented in class and project proposals must be approved by the instructors prior to undertaking work. A list of past projects is available. Project write-ups are due by 5pm Wednesday, May 8. The numerical score to approximate letter grade mapping is as follows:

Score --- Grade
1 ------ B-
2 ------ B
3 ------ B+
4 ------ A-
5 ------ A

News Group: The news group ucb.class.cs268 is available for discussion of the course, including a forum to find others you may want to do the project with. There are several news readers available. If you don't already have a favorite, you might want to try "tin".

Guest Speakers:

3/20/96 - Vern Paxson (LBNL) on traffic modeling
4/10/96 (10-11am) - Van Jacobson (LBNL) on Implementation
4/10/96 (afternoon) - Chuck Thacker (DEC SRC) - on 'Networks that Work'
4/17/96 - Jeffrey Mogul (DEC WRL) - on receiver livelock avoidance

Other Useful References (books):

W. Richard Stevens, TCP/IP Illustrated, v1: The Protocols
Douglas Comer, Internetworking with TCP/IP, v1, 3rd ed.
Dmitri Bertsekas and Robert Gallager, Data Networks, 2nd ed.
Andrew Tanenbaum, Computer Networks, 3rd ed. (coming 3/96)
Raj Jain, The Art of Computer Systems Performance Analysis
T. Cover and J. Thomas, Elements of Information Theory, Wiley-Interscience Publishers, Wiley Series in Telecommunications

Scope of Course:

Course Schedule: (Also see the full paper listing).

Approximate Date Topics Text Reading

I. Network Architecture and History
Jan 17 W Lec Introduction Chp. 1
Hubert Zimmermann, "OSI Reference Model - The ISO Model of Architecture for Open Systems Interconnection"
A Chapin, "Connections and Connectionless Data Trans"
J Saltzer, D Reed, and D. Clark, "End-to-End Arguments in System Design"
Cerf and Kahn, "A Protocol for Packet Network Interconnection"
D. Clark, "The Design Philosophy of the DARPA Internet Protocols"
Tim Berners-Lee, "The World-Wide Web"
Macedonia, Brutzman, "MBone Provides Audio and Video Across the Internet"
V. Cerf, "Computer Networking: Global Infrastructure Driver for the 21st Century"

II. Statistics, Information Theory, Codes

Jan 24 W Lec The Physical Layer Chp. 2
Data Compression Techniques p.490-495
C. Shannon, "Mathematical Theory of Communication (part 1)"
R. W. Hamming, "Error Detecting and Error Correcting Codes"
David Huffman, "A Method for the Construction of Minimum-Redundancy Codes"

III. Queueing Theory and the MAC Sublayer

Jan 31 W Lec The MAC Sublayer Chp. 3
N. Abramson, "Development of the ALOHANET"
Metcalfe, Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks"
Boggs, Mogul, Kent, "Measured Capacity of an Ethernet: Myths and Reality"
A. Viterbi, "Wireless Digital Communication: a view based on three lessons learned"

IV. Link Layer Protocols

Feb 7 W Lec The Data Link Layer p.196-212
p.253-268
FIRST HOMEWORK ASSIGNMENT DUE
J.W. Conard, "Services and Protocols of the Data Link Layer"
W. Simpson (ed), "The Point-to-Point Protocol (PPP)"

V. Telecommunication Switching and ATM

Feb 14 W Lec KE Batcher, "Sorting networks and their applications"
A Fraser, "Early Experiments with Asynchronous Time Division Networks"
Jonathan Turner, "New Directions in Communications (or which way to the information age?)"
Hamid Ahmadi, Wolfgang Denzel, "A Survey of Modern High-Performance Switching Techniques"
Moe Rahnema, "Frame Relaying and the Fast Packet Switching Concepts and Issues"
Ronald Vetter, "ATM Concepts, Architectures and Protocols"

VI. Network Layer Protocols

Feb 21 W Lec The Network Layer p.271-288
p.316-366
J. Postel, Carl Sunshine, Danny Cohen, "The ARPA Internet Protocol"
Paul Mockapetris, Kevin Dunlap, "Development of the Domain Name System"
S. Bradner, A. Mankin, "The Recommendation for the IP Next Generation Protocol"

VII. Routing and Multicast Delivery

Feb 28 W Lec Routing Algorithms p.289-306
J. McQuillan, I Richer, E. Rosen, "The New Routing Algorithm for the ARPANET"
M. Steenstrup, "An Architecture for Inter-Domain Policy Routing"
S. Deering and D. Cheriton, "Multicast Routing in Datagram Internetworks and Extended LANs"

VIII. Transport Layer Protocols

Mar 6 W Lec Elementary Data Link Protocols p.213-253
The Transport Layer Chp. 6
C A Sunshine, Y K Dalal, "Connection Management in Transport Protocols"
Richard Watson, "Timer-Based Mechanisms in Reliable Transport Protocol Connection Management"
Doeringer, Dykeman, Kaiserswerth, Meister, Rudin, Williamson, "A Survey of Light-Weight Transport Protocols for High-Speed Networks"
Postel, "User Datagram Protocol"
Postel, "Transmission Control Protocol"

IX. Congestion Control

Mar 13 W Lec Congestion Control Algorithms p.309-320
Raj Jain, "Myths About Congestion Management in High Speed Networks"
Van Jacobson, "Congestion Avoidance and Control"
K.K. Ramakrishnan and R. Jain, "A Binary Feedback Scheme for Congestion Avoidance in Computer Networks"
S. Floyd et al, "Random Early Detection Gateways for Congestion Avoidance"

X. Traffic Analysis, Dynamics and Modeling

Mar 20 W Lec V. Frost, B. Melamed, "Traffic Modeling for Telecommunications Networks"
Raj Jain, S. Routhier, "Packet Trains: Measurement and a New Model for Computer Network Traffic"
Rene Cruz, "A Calculus for Network Delay, Part I: Network Elements in Isolation"
Rene Cruz, "A Calculus for Network Delay, Part II"
Leland, Taqqu, Willinger, Wilson, "On the Self-Similar Nature of Ethernet Traffic (Extended Version)"
Vern Paxson, Sally Floyd, "Wide Area Traffic: The Failure of Poisson Modeling"

XI. Admission Control, Integrated Services, Reservations

Apr 3 W Lec A. Demers, S. Keshav, S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm"
D. Ferrari, A. Banerjea and H Zhang, "Network Support for Multimedia: a discussion of the Tenet approach"
A. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control - the Single Node Case"
A. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control - the Multiple Node Case"
David Clark, S. Shenker, L. Zhang, "Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism"
Sally Floyd and Van Jacobson, "Link-Sharing and Resource Management Models for Packet Networks"
Lixia Zhang, S Deering, D Estrin, S. Shenker, D Zappala, "RSVP: A New Resource ReSerVation Protocol"

XII. Implementation Philosophy

Apr 10 W Lec SECOND HOMEWORK ASSIGNMENT HANDED OUT
R. W. Watson and S. A. Mamrak, "Gaining Efficiency in Transport Service by Appropriate Design and Implementation Choices"
D. Clark, "Modularity and Efficiency in Protocol Implementation"
D. Clark and D. Tennenhouse, "Architectural Consideration for a New Generation of Protocols"

XIII. Implementation (systems)

Apr 17 W Lec SECOND HOMEWORK ASSIGNMENT DUE
D. Clark, V. Jacobson, J. Romkey, H. Salwen, "An Analysis of TCP Processing Overhead"
C. Dalton, G. Watson, D. Banks, C. Calamvokis, A. Edwards, J Lumley, "Afterburner"
J. Mogul, R. Rashid, M. Accetta, "The Packet Filter: An Efficient Mechanism for User-Level Network Code"
C. Thekkath, T. Nguyen, E. Moy, E. Lazowska, "Implementing Network Protocols at User Level
T. von Eicken, D. E. Culler, S. C. Goldstein, K. E. Schauser, "Active Messages: a mechanism for integrated communication and computation"

XIV. Special Topics

Apr 24 W Lec RTP (Draft RFC of the IETF AVT Working Group)
K. Birman, A. Schiper, P. Stephenson, "Lightweight causal and atomic group multicast"
S. Floyd, V. Jacobson, C. Liu, S. McCanne, L. Zhang, "A Reliable Multicast Framework for Ligh-Weight Sessions and Application Level Framing"
D. Mills, "Improved Algorithms for Synchronizing Computer Network Clocks"

XV. Security

May 1 W Lec Cryptography p.496-520
V. L. Voydock, S. T. Kent, "Security Mechanisms in High-Level Network Protocols"
R. Rivest, "The MD5 Message-Digest Algorithm"
B. C. Neuman and T. Ts'o, "Kerberos: An Authentication Service for Computer Networks"
B. C. Neuman, "Security, Payment, and Privacy for Network Commerce"
S. Bellovin, W. Cheswick, "Network Firewalls"
R. Atkinson, "Security Architecture for the Internet Protocol"
R. Atkinson, "IP Authentication Header"
R. Atkinson, "IP Encapsulating Security Payload (ESP)"
May 8 W PROJECTS DUE by 5pm

Grading Breakdown
2 Midterm Examinations	15% each
Final Project	60%
2 Homework Sets	5% each
TOTAL	100%

Approximate Date	Topics	Text Reading
I. Network Architecture and History
Jan 17 W Lec	Introduction	Chp. 1
	Hubert Zimmermann, "OSI Reference Model - The ISO Model of Architecture for Open Systems Interconnection"
	A Chapin, "Connections and Connectionless Data Trans"
	J Saltzer, D Reed, and D. Clark, "End-to-End Arguments in System Design"
	Cerf and Kahn, "A Protocol for Packet Network Interconnection"
	D. Clark, "The Design Philosophy of the DARPA Internet Protocols"
	Tim Berners-Lee, "The World-Wide Web"
	Macedonia, Brutzman, "MBone Provides Audio and Video Across the Internet"
	V. Cerf, "Computer Networking: Global Infrastructure Driver for the 21st Century"
II. Statistics, Information Theory, Codes
Jan 24 W Lec	The Physical Layer	Chp. 2
	Data Compression Techniques	p.490-495
	C. Shannon, "Mathematical Theory of Communication (part 1)"
	R. W. Hamming, "Error Detecting and Error Correcting Codes"
	David Huffman, "A Method for the Construction of Minimum-Redundancy Codes"
III. Queueing Theory and the MAC Sublayer
Jan 31 W Lec	The MAC Sublayer	Chp. 3
	N. Abramson, "Development of the ALOHANET"
	Metcalfe, Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks"
	Boggs, Mogul, Kent, "Measured Capacity of an Ethernet: Myths and Reality"
	A. Viterbi, "Wireless Digital Communication: a view based on three lessons learned"
IV. Link Layer Protocols
Feb 7 W Lec	The Data Link Layer	p.196-212
		p.253-268
	FIRST HOMEWORK ASSIGNMENT DUE
	J.W. Conard, "Services and Protocols of the Data Link Layer"
	W. Simpson (ed), "The Point-to-Point Protocol (PPP)"
V. Telecommunication Switching and ATM
Feb 14 W Lec	KE Batcher, "Sorting networks and their applications"
	A Fraser, "Early Experiments with Asynchronous Time Division Networks"
	Jonathan Turner, "New Directions in Communications (or which way to the information age?)"
	Hamid Ahmadi, Wolfgang Denzel, "A Survey of Modern High-Performance Switching Techniques"
	Moe Rahnema, "Frame Relaying and the Fast Packet Switching Concepts and Issues"
	Ronald Vetter, "ATM Concepts, Architectures and Protocols"
VI. Network Layer Protocols
Feb 21 W Lec	The Network Layer	p.271-288
		p.316-366
	J. Postel, Carl Sunshine, Danny Cohen, "The ARPA Internet Protocol"
	Paul Mockapetris, Kevin Dunlap, "Development of the Domain Name System"
	S. Bradner, A. Mankin, "The Recommendation for the IP Next Generation Protocol"
VII. Routing and Multicast Delivery
Feb 28 W Lec	Routing Algorithms	p.289-306
	J. McQuillan, I Richer, E. Rosen, "The New Routing Algorithm for the ARPANET"
	M. Steenstrup, "An Architecture for Inter-Domain Policy Routing"
	S. Deering and D. Cheriton, "Multicast Routing in Datagram Internetworks and Extended LANs"
VIII. Transport Layer Protocols
Mar 6 W Lec	Elementary Data Link Protocols	p.213-253
	The Transport Layer	Chp. 6
	C A Sunshine, Y K Dalal, "Connection Management in Transport Protocols"
	Richard Watson, "Timer-Based Mechanisms in Reliable Transport Protocol Connection Management"
	Doeringer, Dykeman, Kaiserswerth, Meister, Rudin, Williamson, "A Survey of Light-Weight Transport Protocols for High-Speed Networks"
	Postel, "User Datagram Protocol"
	Postel, "Transmission Control Protocol"
IX. Congestion Control
Mar 13 W Lec	Congestion Control Algorithms	p.309-320
	Raj Jain, "Myths About Congestion Management in High Speed Networks"
	Van Jacobson, "Congestion Avoidance and Control"
	K.K. Ramakrishnan and R. Jain, "A Binary Feedback Scheme for Congestion Avoidance in Computer Networks"
	S. Floyd et al, "Random Early Detection Gateways for Congestion Avoidance"
X. Traffic Analysis, Dynamics and Modeling
Mar 20 W Lec	V. Frost, B. Melamed, "Traffic Modeling for Telecommunications Networks"
	Raj Jain, S. Routhier, "Packet Trains: Measurement and a New Model for Computer Network Traffic"
	Rene Cruz, "A Calculus for Network Delay, Part I: Network Elements in Isolation"
	Rene Cruz, "A Calculus for Network Delay, Part II"
	Leland, Taqqu, Willinger, Wilson, "On the Self-Similar Nature of Ethernet Traffic (Extended Version)"
	Vern Paxson, Sally Floyd, "Wide Area Traffic: The Failure of Poisson Modeling"
XI. Admission Control, Integrated Services, Reservations
Apr 3 W Lec	A. Demers, S. Keshav, S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm"
	D. Ferrari, A. Banerjea and H Zhang, "Network Support for Multimedia: a discussion of the Tenet approach"
	A. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control - the Single Node Case"
	A. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control - the Multiple Node Case"
	David Clark, S. Shenker, L. Zhang, "Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism"
	Sally Floyd and Van Jacobson, "Link-Sharing and Resource Management Models for Packet Networks"
	Lixia Zhang, S Deering, D Estrin, S. Shenker, D Zappala, "RSVP: A New Resource ReSerVation Protocol"
XII. Implementation Philosophy
Apr 10 W Lec	SECOND HOMEWORK ASSIGNMENT HANDED OUT
	R. W. Watson and S. A. Mamrak, "Gaining Efficiency in Transport Service by Appropriate Design and Implementation Choices"
	D. Clark, "Modularity and Efficiency in Protocol Implementation"
	D. Clark and D. Tennenhouse, "Architectural Consideration for a New Generation of Protocols"
XIII. Implementation (systems)
Apr 17 W Lec	SECOND HOMEWORK ASSIGNMENT DUE
	D. Clark, V. Jacobson, J. Romkey, H. Salwen, "An Analysis of TCP Processing Overhead"
	C. Dalton, G. Watson, D. Banks, C. Calamvokis, A. Edwards, J Lumley, "Afterburner"
	J. Mogul, R. Rashid, M. Accetta, "The Packet Filter: An Efficient Mechanism for User-Level Network Code"
	C. Thekkath, T. Nguyen, E. Moy, E. Lazowska, "Implementing Network Protocols at User Level
	T. von Eicken, D. E. Culler, S. C. Goldstein, K. E. Schauser, "Active Messages: a mechanism for integrated communication and computation"
XIV. Special Topics
Apr 24 W Lec	RTP (Draft RFC of the IETF AVT Working Group)
	K. Birman, A. Schiper, P. Stephenson, "Lightweight causal and atomic group multicast"
	S. Floyd, V. Jacobson, C. Liu, S. McCanne, L. Zhang, "A Reliable Multicast Framework for Ligh-Weight Sessions and Application Level Framing"
	D. Mills, "Improved Algorithms for Synchronizing Computer Network Clocks"
XV. Security
May 1 W Lec	Cryptography	p.496-520
	V. L. Voydock, S. T. Kent, "Security Mechanisms in High-Level Network Protocols"
	R. Rivest, "The MD5 Message-Digest Algorithm"
	B. C. Neuman and T. Ts'o, "Kerberos: An Authentication Service for Computer Networks"
	B. C. Neuman, "Security, Payment, and Privacy for Network Commerce"
	S. Bellovin, W. Cheswick, "Network Firewalls"
	R. Atkinson, "Security Architecture for the Internet Protocol"
	R. Atkinson, "IP Authentication Header"
	R. Atkinson, "IP Encapsulating Security Payload (ESP)"
May 8 W	PROJECTS DUE by 5pm