Networking Preliminary Exam Syllabus

Introductory and Overview Material:

Students are expected to have a working knowledge of the following topics:

• The design and implementation of computer networks and internetworks,
• Network protocol simulation,
• Multicast and lightweight sessions protocols,
• The physical layer,
• Statistics, information theory, source-/channel-coding,
• Queuing theory,
• High-speed communications networks, and
• OS and security.

The following list of reading topics can help students gain a solid working knowledge of these topics.

Historical Papers

Students should review historical papers and be aware of some of the original arguments and underlying concepts behind today's networking protocols and applications. In particular, the 25th Anniversay Issue of SIGCOMM Computer Communication Review (CCR) contains many republished articles of note from earlier volumes and provides an important source of some of the original insights and motivations for important research projects.

• V. Cerf and R. Kahn, A Protocol for Packet Network Interconnection. IEEE Transactions on Communications COM-22, pp. 637-641 , 1974.
• D. Clark, Design Philosophy of the DARPA Internet Protocols, In Proc. SIGCOMM '88.
• B. Metcalfe and D. Boggs, "ETHERNET: Distributed Packet Switching for Local Area Networks," Communications of the ACM, Vol. 39, No. 6, pp. 395-404, 1976.
• P. V. Mockapetris and K. Dunlap, Development of the Domain Name System. In Proceedings of SIGCOMM '88 (Stanford, CA, August, 1988).
• J. Saltzer, D. Reed, and D. Clark, End-to-end Arguments in System Design. ACM Transactions on Computer Systems (TOCS), Vol. 2, No. 4, pp. 195-206, 1984.
• A Smith, The Task of the Referee, IEEE Computer, Vol. 23, No. 4, April 1990, pp. 65-71.
• H. Zimmermann, OSI Reference Model - The ISO Model of Architecture for Open Systems Interconnection , IEEE Transactions on Communications COM-28, No. 4: April 1980.

Measurement, Analysis, and Simulation

These papers discuss measurement, analysis, and simulation techniques for the Internet, MBone, and multi-layer protocol measurements.

• J.-C. Bolot, End-to-End Packet Delay and Loss Behavior in the Internet. In Proceedings of SIGCOMM '93 (San Francisco, CA, August, 1993).
• S. Floyd and V. Jacobson, The Synchronization of Periodic Routing Messages. IEEE/ACM Transactions on Networking, Vol. 2, No. 2, pp. 122-136, April 1994.
• R. Ludwig, B. Rathonyi, A. Konrad, K. Oden, and A. Joseph, Multi-layer Tracing of TCP over a Reliable Wireless Link. In Proceedings of ACM SIGMETRICS 1999 (Atlanta, GA, May 1999).
• M. Yajnik, J. Kurose, and D. Towsley, Packet Loss Correlation in the MBone Multicast Network, In Proceedings of IEEE Global Internet '96 (London, U.K., November, 1996). [On-line datasets]

Reliability and Congestion Control

These papers cover the design and analysis of reliable transmission and network congestion avoidance and control algorithms, including: additive increase and multiplicative decrease analysis and algorithms; congestion control algorithm stability arguments; TCP and DECBit congestion control; ARQ, sliding window, and RTT estimation algorithms; and TCP variants (Tahoe, Reno, Vegas, and SACK).

• L. S. Brakmo and L. L. Peterson, TCP Vegas: End to End Congestion Avoidance on a Global Internet. IEEE Journal of Selected Areas in Communication, Vol. 13, No. 8, pp. 1465-1480, October 1995.
• D.-M. Chiu and R. Jain, Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks. Computer Networks and ISDN Systems, Vol. 17, pp. 1-14, 1989.
• Steve Deering's thesis (part1, part2, part3).
•  K. Fall, and S. Floyd, Simulation-based Comparisons of Tahoe, Reno, and SACK TCP. ACM CCR, Vol. 26, No. 3, July 1996.
• V. Jacobson, Congestion Avoidance and Control, In Proceedings of SIGCOMM '88 (Stanford, CA, August, 1988).
• P. Karn and C. Partridge, Improving Round-Trip Time Estimates in Reliable Transport Protocol. ACM Transactions on Computer Systems (TOCS), Vol. 9, No. 4, pp. 364-373, November 1991.
• K.K. Ramakrishnan and R. Jain, A Binary Feedback Scheme for Congestion Avoidance in Computer Networks , ACM Transactions on Computer Systems (TOCS), Vol. 8, No. 2, pp 158-181, May, 1990.

Router Queue Management

These papers cover router queue management related issues, including: packet scheduling versus queue management; max-min fairness; fair queuing; RED; and End-to-End congestion control.

• A. Demers, S. Keshav, and S. Shenker, Analysis and Simulation of a Fair Queueing Algorithm, Internetworking: Research and Experience, Vol. 1, No. 1, pp. 3-26, 1990.
• S. Floyd and K. Fall, Promoting the Use of End-to-End Congestion Control in the Internet, IEEE/ACM Trans. on Networking, 7(4), August 1999, pp. 458-472.
• S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking, Vol. 1, No. 4, August 1993, pp. 397-413. [Abstract].
• J. Nagle, On Packet Switches with Infinite Storage, IEEE Transactions on Communications ,COM-35, No. 4, pp. 435-438 , April 1987.

Wireless Networking and Mobility

These papers discuss wireless and mobile networking protocols, including: TCP Snoop; MACAW; and MobileIP.

• H. Balakrishnan, S. Seshan, E. Amir, R. Katz, Improving TCP/IP Performance over Wireless Networks, In Proceeding of the 1st ACM Conf. on Mobile Computing and Networking, Berkeley, CA, November 1995.
• V. Bharghavan, A. Demers, S. Shenker, and L. Zhang.  MACAW: A Media Access Protocol for Wireless LANs, In Proceedings of SIGCOMM '94 (University College London, London, U.K., September 1994), pp. 212-225.
• A. Myles, D. B. Johnson, and C. Perkins, A Mobile Host Protocol Supporting Route Optimization and Authentication. IEEE Journal of Selected Areas in Communication, Vol. 13, No. 5, pp. 839-849, June 1995.
• T. Shepard, A Channel Access Scheme for Large Dense Packet Radio Networks. In Proceedings of SIGCOMM '96 (Stanford, CA, August 1996), pp. 219-230.

Multicast Routing

These papers cover the fundamentals of multicast routing, including: the IP Multicast service model; the host groups model; IGMP; scope control; scalability issues; Protocol Independent Multicast (PIM); Core Based Trees (CBT); end-to-end multicast; light-weight sessions; announce/listen protocols; soft state, MASC/BGMP; and PIM-SS.

• T. Ballardie, P. Francis, and J. Crowcroft, Core Based Trees (CBT) An Architecture for Scalable Inter-Domain Multicast Routing. In Proceedings of SIGCOMM '93 (San Francisco, CA, August, 1993).
• S. Deering and D. Cheriton, Multicast Routing in Datagram Internetworks and Extended LANs, ACM Transactions on Computer Systems (TOCS), Vol. 8, No. 2, pp 85-110, May, 1990.
•  S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C.-G. Liu, and L. Wei, An Architecture for Wide-Area Multicast Routing, In Proceedings of SIGCOMM '94 (University College London, London, U.K., September 1994).
• H. Holbrook and D. Cheriton, IP Multicast Channels: EXPRESS Support for Large-scale Single-source Applications, In Proceedings of SIGCOMM'99 (Cambridge, MA, August, 1999).
• S. Kumar, P. Radoslavov, D. Thaler, C. Alaettinoglu, Deborah Estrin, and Mark Handley, The MASC/BGMP Architecture for Inter-domain Multicast Routing, In Proceedings of SIGCOMM '98 (Vancouver, British Columbia, September, 1998).
• S. McCanne, Scalable Multimedia Communication with Internet Multicast, Light-weight Sessions, and the MBone. Under review for publication.

Scalable Reliable Multicast

These papers discuss reliable multicast, including: RMTP; self-configuring hierarchies; local recovery; multiple multicast groups; and multicast deployment. Related links: Reliable Broadcast/Multicast Links (NASA), Multicast Transport Protocols.

• S. Floyd, V. Jacobson, C. Liu, S. McCanne, L. Zhang, A Reliable Multicast Framework for Ligh-Weight Sessions and Application Level Framing. To appear in IEEE/ACM Transactions on Networking, 1997. [Abstract]
• H. Holbrook and D. Cheriton, IP Multicast Channels: EXPRESS Support for Large-scale Single-source Applications, In Proceedings of SIGCOMM'99 (Cambridge, MA, August, 1999).

Adaptive Applications

These papers cover tradeoffs in adaptive applications, including: layering tradeoffs (Application Layer Framing); delay and rate adaptation; source- and receiver-based approaches; scalable feedback with sliding key.

• J.-C. Bolot, T. Turletti, and I. Wakeman, Scalable Feedback Control for Multicast Video Distribution in the Internet, In Proceedings of SIGCOMM '94 (University College London, London, U.K., September 1994).
• D. Clark and D. Tennenhouse, Architectural Consideration for a New Generation of Protocols, In Proceedings of SIGCOMM '90 (Philadelphia, PA, September 1990).
• S. McCanne, V. Jacobson, M. Vetterli, Receiver-driven Layered Multicast. In Proceedings of SIGCOMM '96 (Stanford, CA, August 1996).

Quality of Service and Admission Control

These papers discuss topics related to future service models; utility and (dis)incentives issues; RSVP; admission control; real-time scheduling; token buckets; and predictive service.

• D. Clark S. Shenker, and L. Zhang, Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanisms. In Proceedings of SIGCOMM '92.
• S. Jamin, P. B. Danzig, S. J. Shenker, L. Zhang, A Measurement-based Admission Control Algorithm for Integrated Services Packet Networks.
• S. Shenker, Fundamental Design Issues for the Future Internet, IEEE Journal of Selected Areas in Communication, Vol. 13, No. 7, pp. 1176-1188, September 1995.
• L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, RSVP: A New Resource Reservation Protocol, IEEE Network, Vol. 7, pp. 8-18, September, 1993.

Programmable and Sensor Networks

Students should understand the basics of active networks; dynamic transcoding; and Smart Dust.

• E. Amir, S. McCanne, and R. Katz, An Active Service Framework and its Application to Real Time Multimedia Transcoding, In Proceedings of SIGCOMM '98 (Vancouver, British Columbia, September, 1998).
• J. Kahn, R. Katz, K. Pister, Mobile Networking for "Smart Dust", In Proceedings of ACM MOBICOM'99 (Seattle, WA, August 1999).
• D. Wetherall, Active network vision and reality: lessons from a capsule-based system, In Proceedings of SOSP'99 (Kiawah Island Resort, SC, December, 1999).

HTTP and HTTP/TCP Interactions

These papers discuss the interactions between web (application-level) protocols and transport (TCP/IP) protocols.

• V. Padmanabhan and J. Mogul, Improving HTTP Latency, Computer Networks and ISDN Systems, v. 28, pp. 25-35, December 1995.
• [BPS+98] H. Balakrishnan, V. Padmanabhan, S. Seshan, M. Stemm, and R. Katz, TCP Behavior of a Busy Internet Server: Analysis and Improvements, Proc. IEEE INFOCOM, March 1998.

Useful Networking Texts, Theses, and Papers

General

• Larry Peterson and Bruce Davie, Computer Networks: A Systems Approach.
• S. Keshav, An Engineering Approach to Computer Networking.
• Jean Walrand, Communication Networks: A First Course.
• Andrew Tanenbaum, Computer Networks, 3rd ed. (Search for Tanenbaum on the Prentice Hall site).
• Dmitri Bertsekas and Robert Gallager, Data Networks, 2nd ed. (Search for Bertsekas on the Prentice Hall site).
• Jean Walrand and Pravin Varaiya, High-Performance Communication Networks.
• Craig Partridge, Gigabit Networking.
• Thorsten von Eicken, David E. Culler, Seth Copen Goldstein, and Klaus Erik Schauser, "Active Messages: a Mechanism for integrated Communication and Computation," Proceedings of the International symposium on Computer Architecture, 1992.

Routing, High-Speed Networks

• Christian Huitema, Routing in the Internet. (Search for Huitema on the Prentice Hall site).
• Radia Perlman, Interconnections: Bridges and Routers, Addison Wesley.
• Martha Steenstrup, Routing in Communication Networks. (Search for Steenstrup on the Prentice Hall site).
• BGP4

The TCP/IP Protocol Suite

• W. Richard Stevens, TCP/IP Illustrated, Volume 1: The Protocols.
• W. Richard Stevens, TCP/IP Illustrated, Volume 2: The Implementation.
• W. Richard Stevens, TCP/IP Illustrated, Volume 3: TCP for Transactions, HTTP, NNTP, and the UNIX Datagram Protocols.
• Douglas Comer, Internetworking with TCP/IP, Volume 1: Principles, Protocols and Architecture, 3rd ed. (Search for Comer on the Prentice Hall site).
• Christian Huitema, IPv6: The New Internet Protocol, 2nd ed. (Search for Huitema on the Prentice Hall site).

Multicast

• Stephen Deering, Multicast Routing in a Datagram Internetwork, Part 1 Part 2 Part 3, Ph.D. thesis, Stanford University, 1991.
• Steven McCanne, Scalable Compression and Transmission of Internet Multicast Video, PhD thesis, UC Berkeley, 1996.
• Sanjoy Paul, Multicasting on the Internet and its Applications, Kluwer Academic Publishers, 1998. Search for it on Amazon using the keyword "Sanjoy Paul".

Wireless and Mobility

• J. Solomon, Mobile IP: The Internet Unplugged.
• Charlie Perkins, Mobile IP: Design Principles and Practices.
• Vijay Garg and Joseph Wilkes Wireless and Personal Communication Systems.
• Hari Balakrishnan, Reliable Data Transport over Heterogeneous Wireless Networks, PhD thesis, UC Berkeley, 1998.

Performance, Modeling

• Raj Jain, The Art of Computer Systems Performance Analysis, Wiley, 1991.
• Len Kleinrock, Queueing Theory.

Programmable Networks

• David Wetherall, Service Introduction in an Active Network, PhD thesis, M.I.T., 1999.
• Elan Amir, An Agent-based approach to Multimedia Transmission over Heterogeneous Environments, PhD thesis, U.C. Berkeley, 1998.

Related UCB courses

• Routing, multicast, applications, application-level protocols: covered in CS268,
• The physical layer: covered in EECS122, EE224, EE228A,
• Statistics, information theory, source-/channel-coding: covered in EE229,
• Queuing theory: covered in EE226, EE228B, Stat 205A/B, IEOR263A,
• High-speed communications networks: covered in EE228A,
• OS and security: covered in CS262A/B, CS269.