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


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:

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


Grading Breakdown
2 Midterm Examinations 15% each
Final Project 60%
2 Homework Sets5% 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:

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:

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:

Other Useful References (books):

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 IntroductionChp. 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 LayerChp. 2
Data Compression Techniquesp.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 SublayerChp. 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 Layerp.196-212
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 LecKE 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 Layerp.271-288
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 Algorithmsp.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 Protocolsp.213-253
The Transport LayerChp. 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 Algorithmsp.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 LecV. 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 LecA. 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

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)

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 LecRTP (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 LecCryptographyp.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 WPROJECTS DUE by 5pm