All rights reserved by Yang Richard Yang  ©2003-2005. Please do not redistribute.

A Reading List in Computer Networking

Note: this is a list of books and papers that I have collected for students who are interested in doing networking research. These books and papers serve as background and overview. A student should read more in order to become an expert of a special field. For the books, I suggest you eventually collect the books listed here, but I also suggest that you first loan a book from me to see if you like it. As for the papers, you should know the basic papers very well.

Background

• Algorithms and optimization (Networking has a strong algorithmic component. Common algorithms we use are shortest path, minimal spanning tree, facility location, and network flows.)
  • Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. 2001.
  • Approximation Algorithms, by Vijay V. Vazirani.  2001.
  • Randomized Algorithms, by Rajeev Motwani, Prabhakar Raghavan. 1995.
  • Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. 1993.
    The bible on network related algorithms.
• Optimization
  • Nonlinear and convex analysis
    • Nonlinear programming: Theory and Algorithms by M. Bazaraa, H. Sherali, and C. Shetty. 1993.
    • Convex Optimization, S. Boyd and L. Vandenberghe 2003. (the class slides are useful, including contents on Ellipsoid and sub-gradient method which are not covered in the book)
    • Convex Analysis and Optimization by Bertsekas 2003. (slides and solutions can be found at the web site)
    • Nonlinear programming by Bertsekas, 1998. (slides and solutions can be found at the web site)
  • Network Optimization: Continuous and Discrete Models by Bertsekas 1998.
  • Dynamic programming by Bertsekas, 2000 and 2001. (slides can also be found at the web site)
  • Combinatorial Optimization: Algorithms and Complexity by Christos H. Papadimitriou. 1986.
• Distributed and parallel algorithms
  • Distributed Algorithms, by Nancy A. Lynch 1997.
  • Distributed Computing: Fundamentals, Simulations and Advanced Topics, Second Edition, John Wiley & Sons, 2004, by Hagit Attiya and Jennifer Welch.
  • Parallel and Distributed Computation: Numerical Methods by Bertsekas and Tsitsiklis 1997.
• Probability and stochastic processes
  • Probability
    • A Modern Approach to Probability Theory by  Bert Fristedt, Lawrence Gray. 1996.
      If you want to read just one book on probability and stochastic process, I suggest this one.
    • An Introduction to Probability Theory and Its Applications (I and II) by W. Feller. 1971.
  • Stochastic processes, queueing theory, information theory, and control theory
    • A First Course in Stochastic Processes, by Karlin 1975.
    • A Second Course in Stochastic Processes, by Karlin 1981.
  • Queueing theory
    • Fundamentals of Queueing Theory, by Gross and Harris. 1998.
    • Stochastic Networks by  Frank P. Kelly, Ruth J. Williams, 1995.
    • Queueing Systems, Volume 1, by Kleinrock 1975.
    • Queueing Systems, Volume 2, by Kleinrock 1976.
  • Elements of Information Theory, by Thomas M. Cover, Joy A. Thomas. 1991.
    • Shannon's original 1948 paper (html, pdf)
  • Control theory and estimation theory
    • Kalman's original 1960 paper (html, pdf)
• Economics and game theory
  • Classics in Game Theory, edited by Kuhn 1997.
  • A Course in Game Theory, Martin J. Osborne, Ariel Rubinstein. 1994.
  • Microeconomic Theory, by Andreu Mas-Colell, Michael D. Whinston, Jerry R. Green 1995.
• Network security and crypto
  • Applied Cryptography by Schneier 1996.
  • Cryptography and Network Security: Principles and Practice by Stalling, Third Edition, Prentice-Hall, 2003.
  • Cryptography: Theory and Practice by Stinson, 2000.
• Communications
  • Digital communications, by Proakis 2000.
  • Fundamentals of Wireless Communication, by D. Tse and P. Viswanath, Cambridge University Press, May 2005.
  • Wireless Communications: Principles and Practice, by Theodore Rappaport 2001.

Conferences and events

• Conferences to follow
• Conference statistics (acceptance ratio does not say much, but the acceptance ratios of the major networking conferences are just too low.)

Below is a list of important papers in computer networking. Some are review papers but most are papers that proposed important original ideas. When reading a paper below, always ask yourself why the paper made a large impact. Basic papers are in red.

Internet architecture and philosophy [6 basic papers]

• Van Jacobson's list on Internet Protocol Design and Implementation.
• Interesting Papers Related to Network Architecture, maintained by the NewArch project
• [CK74] V. G. Cerf and R. E. Kahn, "A Protocol for Packet Network Interconnection". IEEE Transaction on Communications, 22(5), May 1974, pp. 637-648. (pdf)

Specification of the initial TCP protocol. Notice that TCP and IP had not been separated at the time of writing. How did they separate TCP into IP and TCP? Also, the address was 24 bits instead of the current 32 bits. For the specification of current IP and TCP, see [RFC 791] for current IP, and [RFC 793] for current TCP.

• [Pos81a] J. Postel, "Internet Protocol". RFC 791, Sept 1981. (html)

Protocol specification of IPv4.

• [Pos81b] J. Postel, "Transmission Control Protocol". RFC 793, Sept 1981. (html)

Protocol specification of TCP.

• [Zim80] H. Zimmerman, "OSI Reference Model -- The ISO Model of Architecture for Open Systems Interconnection". IEEE Transactions on Communications, 28(4), April, 1980, pp. 425-432.

Discuss the ISO/OSI seven layers.

• [SRC84] J. Saltzer, D. Reed, and D. Clark, "End-to-end Arguments in System Design". ACM Transactions on Computer Systems (TOCS), Vol. 2, No. 4, 1984, pp. 195-206. (html)

The above paper discusses layered architecture, but a fundamental problem is how to divide functionality among layers. End to end argument is the answer from the Internet community.

End to end arguments is a class of system design principles that organize and guide the placement of function within a system. These arguments and the underlying principles have now been invoked in many contexts, becoming part of the vocabulary of network protocol and operating system designers.

• [Cla88] D. Clark, "The Design Philosophy of the DARPA Internet Protocols". In Proceedings of ACM SIGCOMM '88, 106-114, Palo Alto, CA, Sept 1988. (html)

Discuss the design goals of the Internet.

For more revisions about the above philosophy, please read

• [CT90] D. Clark and D. Tennenhouse, "Architectural Consideration for a New Generation of Protocols". In Proceedings of ACM SIGCOMM '90, Philadelphia, PA, September 1990. (html, pdf)

Consider the design and implementation issues of layered network architecture. Propose Application Level Framing (ALF) and Integrated Layer Processing (ILP).

• [Hin95] R. M. Hinden, "IP Next Generation Overview". CACM 1995. (html, citeseer)

Discuss IPv6.

• [Car96] B. Carpenter, "Architectural Principles of the Internet". RFC 1958, Jun 1996. (html)

A summary of the basic principles of Internet. Very easy to read.

• [Ise97] David Isenberg, "Rise of the Stupid Network". 1997 (html)

An interesting discussion on "stupid" and "intelligent" networks. A strong recommendation to read.

• [RSC98] David P. Reed, Jerome H. Saltzer, and David D. Clark, "Comment on Active Networking and End-to-End Arguments". IEEE Network 12, 3 (May/June 1998) pages 69-71. (html)

Comments active network research, using the end to end arguments.

• [RM99] Suchitra Raman and Steven McCanne, "A Model, Analysis, and Protocol Framework for Soft State-based Communication." In Proceedings of ACM SIGCOMM '99. (html)

Soft state is a fundamental design tool in computer networking.
 

• [Ree00] David Reed, "The End of the End-to-End Argument", April 2000. (html)

"I would argue that we need more than ever to understand [the end-to-end argument] and to apply it as we evolve the network... Future potential is hard to visualize, but our inability to make out the details should not justify locking the doors against new ways to use the network."

• [Cla00] D. Clark. "Rethinking the Design of the Internet: end to end arguments vs. the brave new world". Presented at TPRC 2000, Alexandria, Va., September 23-25th, 2000. (pdf)

Rethinking the end to end arguments. Consider the new requirements for network support.

• [CWSB02] David D. Clark, John Wroclawski, Karen Sollins and Robert Braden, "Tussle in Cyberspace: Defining Tomorrow's Internet." In Proceedings of ACM SIGCOMM 2002. (html, video in Windows Media format)

The traditional Internet is designed for non-commercial usage. This paper introduces new perspectives for next generation Internet.

MAC and link layer [4 basic papers]

• [KT75] Kleinrock, L. and F. Tobagi, "Packet Switching in Radio Channels: Part I--Carrier Sense Multiple-Access Modes and their Throughput-Delay Characteristics", IEEE Transactions on Communications, Vol. COM-23, No. 12, pp. 1400-1416, December 1975. Also, "Multiple Access Communications, Foundations for Emerging Technologies", Norman Abramson (Ed), IEEE Press, 1992, pp. 272-288. PDF

analysis of CDMA protocol
 

• [MB76] 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. (html, pdf)

Specification of the initial Ethernet protocol. Notice that it is different from the current protocol.

• [MBK88] J. Mogul, D. Boggs, S. Kent, "Measured Capacity of an Ethernet: Myths and Reality". In Proceedings of ACM SIGCOMM '88, August 1988 (ACM CCR 18, 4)  (html)

A summary of the theoretical analyses on Ethernet performance. Measure the performance also.

• [BDSZ94] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, ``MACAW: A Media Access Protocol for Wireless LANs.'' ACM Sigcomm '94, London, UK. September 1994. (ps.gz)

Improve the congestion control and message exchange of MACA, which was proposed by Kahn and used RTS/CTS to address the hidden terminal problem.

Routing [7 basic papers]

• [Gal77] Robert G. Gallager, A Minimum Delay Routing Algorithm Using Distributed Computation, IEEE Transactions on Communications, 1, 73-85 (1977).

multiple-path optimal routing

• [Ber82] D. Bertsekas, "Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks," IEEE Transactions on Automatic Control, AC-27, pp. 60-74, February 1982. (pdf)

single path routing; adding bias

• [Seg77] Adrian Segall, The Modeling of Adaptive Routing in Data-Communication Networks, IEEE Transactions on Communications, 25, 85-95 (1977).
   
• [GHS83] R. G. Gallager, P. A. Humblet, and P. M. Spira, "A Distributed Algorithm for Minimum-Weight Spanning Trees," ACM Transactions on Programming Languages and Systems, Vol. 5, No. 1, January ]983, Pages 66-77. (pdf)

a nice distributed spanning tree algorithms

• [KZ89] A. Khanna and J. Zinky, "A Revised ARPANET Routing Metric," ACM SIGCOMM  '89, pp. 45-56, September 1989. (pdf)
  • complexity of Internet routing
     
• [Pax96] V. Paxson, "End-to-End Routing Behavior in the Internet". In Proceedings of ACM SIGCOMM '96, August 1996, Stanford, CA.  (pdf, ps.Z, viewgraph in ps.Z, the author's tutorial on Internet measurement in ps.Z)

Show the pathologies,  stability, and symmetry of Internet routing. Pay attention to the methodology. You may find some other talks by this author also very interesting.

• [LMJ97] C. Labovitz, G. R. Malan, and F. Jahanian, "Internet Routing Instability". In Proceedings of ACM SIGCOMM'97, September 1997. (html, ps.gz)

BGP router send too many BGP packets. Why?

• [GW99] Timothy G. Griffin,  Gordon Wilfong, "An Analysis of BGP Convergence Properties". In Proceedings of ACM SIGCOMM 1999. (html) (here is a link on BGP maintained by Griffin)
   
  • study the problem of persistent route oscillations; propose No Dispute Wheel Theorem
     
• [GR00] Lixin Gao and Jennifer Rexford, "Stable Internet Routing Without Global Coordination". In Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. 2000.
   
  • first application of Internet economy to routing stability

Router--high performance [3 basic papers]

• [McK96] N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick and M. Horowitz, The Tiny Tera: A Packet Switch Core , Proc. Hot Interconnects V, Stanford University, August 1996. (pdf)
   
• [BCDP97] A. Brodnik, S. Carlsson, M. Degermark, and S. Pink, "Small Forwarding Tables for Fast Routing Lookups". In Proceedings of ACM SIGCOMM '97. Pages 3-14. (html)

One of the first papers to discuss how to do fast and scalable forwarding table lookup when we use prefix match.

• [PCBC+98] C. Partridge, P. P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway, P. Herman, A. King, S. Kohalmi, T. Ma, J. McAllen, T. Mendez, W.C. Milliken, R. Pettyjohn, J. Rokosz, J. Seeger, M. Sollins, S. Storch, B. Tober, G.D. Troxel, D. Waitzman, and S. Winterble, "A 50-Gb/s IP router". IEEE/ACM Transactions on Networking, Vol. 6, No. 3 (June 1998), Pages 237-248. (html)

Present MGR, which has five innovations: 1) each forwarding engine has a complete set of the forwarding table (used to have only cache); 2) Use a switched backplane (used to use a shared bus); 3) split forwarding engines from line cards; 4) line cards translate local link layer headers to and from an abstract link layer header format so that forward engines do not need to consider link layer; 5) include QoS; the forwarding engines classify packets, scheduling on the output line cards, in a specialized processor called the QoS processor.

More references

• [SS98] S. Keshav and R. Sharma, "Issues and Trends in Router Design". IEEE Communications Magazine, 35(6):144-151, May 1998. (pdf)

• [BV01] F. Baboescu and G. Varghese, "Scalable Packet Classification", In Proceedings of ACM SIGCOMM 2001, San Diego, CA, August 2001. (html)

Router--more functionality--active networks [1 basic paper]

• [Wet99] David Wetherall, "Active network vision and reality: lessons from a capsule-based system". In Proceedings of ACM SOSP 1999. (ACM DL, ps, pdf, summary in HTML, slides in tar.gz)
   
• [TSSW97] David L. Tennenhouse, Jonathan M. Smith, W. David Sincoskie, David J. Wetherall, and Gary J. Minden, "A Survey of Active Network Research". IEEE Communications Magazine, Vol. 35, No. 1, pp80-86. January 1997. (html)
   

Internet measurements and models  [6 basic papers]

• [Bol93] Jean-Chrysotome Bolot, "End-to-end packet delay and loss behavior in the internet". In Proceedings of ACM SIGCOMM '93. (pdf)

A simple and elegant analysis on packet delay, bandwidth, packet size, and loss.

• [LTWW93] W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson, "On the Self-Similar Nature of Ethernet Traffic". In Proceedings of SIGCOMM '93. IEEE/ACM Transactions on Networking, Vol. 2, No. 1, pp. 1-15, Feb. 1995. (html)

Present that traffic is self-similar in a local area network environment.

• [WPT98] W. Willinger, V. Paxson, and M.S. Taqqu, "Self-similarity and Heavy Tails: Structural Modeling of Network Traffic". In A Practical Guide to Heavy Tails: Statistical Techniques and Applications, 1998. Adler, R. Feldman, R. and Taqqu M.S., editors, Birkhauser.  (html)

Explain LAN and WAN traffic through structral models and show the relationship between self-similarity at the macroscopic level of WANs with the heavy-tailed behavior at the microscopic level of individual sources. 

• [PF95] V. Paxson and S. Floyd, "Wide-area Traffic: The Failure of Poisson Modeling". IEEE/ACM Transactions on Networking, June 1995.  (html)

Present that traffic is self-similar in wide area network environments.

• [FP01] Sally Floyd and Vern Paxson, "Difficulties in Simulating the Internet".  To appear in IEEE/ACM Transactions on Networking. February, 2001. (pdf)

"Modeling and simulating the Internet is not an easy task. The goal of this paper is to discuss some of the issues and difficulties in modeling Internet traffic, topologies, and protocols."

• [Pax96] V. Paxson, "End-to-End Routing Behavior in the Internet". In Proceedings of ACM SIGCOMM '96, August 1996, Stanford, CA.  (pdf, ps.Z, viewgraph in ps.Z, the author's tutorial on Internet measurement in ps.Z)

Show the pathologies, stability, and symmetry of Internet routing. Pay attention to the methodology. You may find some other talks by this author also very interesting.

• [Pax97]  V. Paxson, "End-to-End Internet Packet Dynamics". In Proceedings of SIGCOMM '97, pp. 139-152, Cannes, France, September 1997. (html)
   
• [FFF99] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos, "On Power-Law Relationships of the Internet Topology". In Proceedings of SIGCOMM '99. (html)

  This paper starts the whole process of evaluating power-law in Internet. For a follow up, please read:

• [SMW02] Neil Spring, Ratul Mahajan and David Wetherall, "Measuring ISP Topologies with Rocketfuel." In Proceedings of ACM SIGCOMM 2002. (html, video in Windows Media format)

            Sigcomm 2002 best paper.
   

• [CCLNY03] R. Castro, M. Coates, G. Liang, R. Nowak, and B. Yu (2003). Internet Tomography: Recent Developments Statistical Science. (html)

• [LAWD04] . Lun Li, David Alderson, Walter Willinger, John Doyle. A First-Principles Approach to Understanding the Internet's Router-Level Topology. In SIGCOMM 2004. (html)
   

Traffic management--congestion control, router mechanisms and pricing [14 basic papers]

• [CLZ87] D. D. Clark, M. L. Lambert and L. Zhang, "NETBLT: a high throughput transport protocol", In Proceedings of SIGCOMM '87, August 1987. (html)

Specifies a rate-based, receiver-driven congestion control protocol.

• [CJ89] 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, 1989, pp. 1-14. (html)

  Propose the Additive Increase and Multiplicative Decrease algorithm.

• [RCJ88] K. Ramakrishnan, D. Chiu, and R. Jain, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer". In Proceedings of ACM SIGCOMM '88, Sept. 1988, pp. 303-313. (html) (Note: This is a revised version of the original SIGCOMM'88 paper.)

Specifies both router policies and user policies for congestion avoidance (not congestion control). Routers calculate average queue length at regeneration cycle. Users use AIMD. 

• [RJ90] K.K. Ramakrishnan and R. Jain, "A Binary Feedback Scheme for Congestion Avoidance in Computer Networks". ACM Transactions on Computer Systems, Vol. 8, No. 2, pp 158-181, May, 1990. (pdf).

The first paper on binary feedback congestion control.

• [Jac88] V. Jacobson, "Congestion Avoidance and Control". In Proceedings of ACM SIGCOMM '88, Sept. 1988, pp. 314-329. (html)

The classical paper on TCP congestion control.

A revision after the publication of the paper:

• [Jac90] V. Jacobson, email to end2end-interest mailing list, Apr 30, 1990. (txt)

Revision to [Jac88]. Add fast retransmit and fast recovery.

• [PFTK98] Padhye, J., Firoiu, V., Towsley, D., and Kurose, J., "Modeling TCP Throughput: a Simple Model and its Empirical Validation". In Proceedings of ACM SIGCOMM 1998. (ps.Z)

A model of TCP throughput.

• [FF95] K. Fall and S. Floyd, "Comparisons of Tahoe, Reno, and Sack TCP". LBNL Technical report, December 1995.  (ps.Z)

Simulation comparisons of TCP/Tahoe, TCP/Reno, TCP/SACK. Read the new paper in SIGCOMM 2001 to see how they identify TCP versions.

• [BP95] L. S. Brakmo and L. L. Peterson, "TCP Vegas: End to End Congestion Avoidance on a Global Internet". IEEE Journal on Selected Areas in Communications, Vol. 13, No. 8, October 1995. (html)

An interesting modification to TCP/Reno, as proposed in [Jac88, Jac90].

• [BSK95] H. Balakrishnan, S. Seshan, R. H. Katz, "Improving Reliable Transport and Handoff Performance in Cellular Wireless Networks", ACM Wireless Networks, V 1, N 4, December, 1995. (html)

Modify network-layer software at the base station and mobile host, and preserve the end-to-end semantics of TCP.

• [Ste97] W. Stevens, "TCP congestion control". RFC 2001, Jan 1997. (html)

          A summary of TCP congestion control. Refer to the book by the same author.
 

• [AF99] M. Allman and A. Falk, On the Effective Evaluation of TCP, ACM Computer Communications Review, October 1999. (html)

This paper discusses issues in the evaluation of TCP performance.

• [AAB00] E. Altman, K. Avrachenkov and C. Barakat,  "A Stochastic Model of TCP/IP with Stationary Random Loss". In Proceedings of SIGCOMM 2000. (ps.gz)

An model of TCP/Reno using stochastic equation.

• [BH00] F. Baccelli and D. Hong, "TCP is Max-Plus Linear", In Proceedings of SIGCOMM 2000. (ps.gz)
   

• [SCWA99] S. Savage, N. Cardwell, D. Wetherall, T. Anderson, "TCP Congestion Control with a Misbehaving Receiver". ACM CCR 1999. (pdf)

How to trick TCP?

• [RF99] K. K. Ramakrishnan and S. Floyd, "A Proposal to add Explicit Congestion Notification (ECN) to IP". RFC 2481, Jan. 1999. (txt)
   
• [YKL01] Yang Richard Yang, Min S. Kim, Simon S. Lam, "Transient Behaviors of TCP-Friendly Congestion Control". In Proceedings of IEEE INFOCOM 2001. (html)

Study the aggressiveness, responsiveness, smoothness, and fairness of 4 TCP-friendly congestion control protocols by using step functions.

• [BBFS01] Deepak Bansal, Hari Balakrishnan, Sally Floyd, Scott Shenker, "Dynamic Behavior of Slowly-Responsive Congestion Control Algorithms". In Proceedings of ACM SIGCOMM 2001. (html) 

• [DKS89] A. Demers, S. Keshav, and S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm". In Proceedings of ACM SIGCOMM'89, pp 3-12. (html)

First scheduling paper in computer networks.

• [BZ96] J. C.R. Bennett and H. Zhang, "Hierarchical Packet Fair Queueing Algorithms. IEEE/ACM Transactions on Networking", 5(5):675-689, Oct 1997. Also in Proceedings of SIGCOMM'96, August, 1996. (pdf)
   

• [SCP95] H. Sariowan, R. L. Cruz, and G. C. Polyzos, "Scheduling for Quality of Service Guarantees via Service Curves," Proceedings of the International Conference on Computer Communications and Networks (ICCCN) 1995, Las Vegas, September 20-23, 1995, pp. 512-520. (ps)

Propose service curves. Decouple bandwidth and delay.

• [Kes91] S. Keshav "A Control-Theoretic Approach to Flow Control". In Proceedings of ACM SIGCOMM '91. (html)

Congestion control using control theory. The objective is to control the number of outstanding packets at the bottleneck. Use packet pair to estimate the service rate at the bottleneck. Assume round-robin like service at the bottleneck. A different perspective.

• [CSZ92] D. Clark and S. Shenker and L. Zhang, "Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism". In Proceedings of SIGCOMM '92, Baltimore, Maryland, Aug, 1992, pp 14-26. (html)
   
• [FJ93] S. Floyd and V. Jacobson, "Random Early Detection gateways for Congestion Avoidance". IEEE/ACM Transactions on Networking, 1(4):397-413 August 1993. (html)

Propose and evaluate RED.

• [MGW00] V. Misra, W. Gong and D. Towsley. "A Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED". In Proceedings of ACM SIGCOMM 2000. (ps.gz)

An model of TCP/Reno using renewal theory.

• [SS01] Srisankar Kunniyur, R. Srikant, "Analysis and Design of an Adaptive Virtual Queue (AVQ) Algorithm for Active Queue Management". In Proceedings of ACM SIGCOMM 2001. (html)

An active queue management scheme based on virtual queue. Compare with RED [FJ93]

• [Z+93] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, "RSVP: A New Resource Reservation Protocol". IEEE Communications Magazine, 31(9):8-18, September 1993. (ps.Z)

The signaling protocol for IntServ.

• [BCS94] R. Braden, D. Clark, and S. Shenker. "Integrated Services in the Internet Architecture: an Overview". RFC 1633, June 1994.  (html)

An overview of the architecture of IntServ. See [DiffServ] for comparison.

• [KBC94] H. T. Kung, T. Blackwell, and A. Chapman, "Credit-Based Flow Control for ATM Networks: Credit Update Protocol, Adaptive Credit Allocation, and Statistical Multiplexing". In Proceedings of ACM SIGCOMM '94. (html, pdf)

One of the proposals for ATM congestion control.

• [She95] S. Shenker, "Fundamental Design Issues for the Future Internet". IEEE Journal on Selected Areas in Communications, Vol. 13, No. 7, September 1995, pp. 1176-1188. (html)
   
• [MV95] J. K. MacKie-Mason and H. R. Varian, "Pricing Congestible Network Resources," IEEE Journal of Selected Areas in Communications, vol. 13, no. 7, pp. 1141-149, Sept. 1995.  (pdf)
   
• [SCEH96] S. Shenker, D. Clark, D. Estrin, S. Herzog, Pricing in Computer Networks: Reshaping the Research Agenda, Communications Policy. Vol. 20(1), 1996. (html)

"The more academic literature has largely focused on devising optimal pricing policies; achieving optimal welfare requires charging marginal congestion costs for usage. In this paper we critique this optimality paradigm ... we contend that the research agenda on pricing in computer networks should shift away from the optimality paradigm and focus more on structural and architectural issues." Here is a list  maintained by Richard Gibbens' on Pricing Internet Resources (Last modified in 1998.)

• [Kel97] Frank Kelly, "Charging and rate control for elastic traffic". European Transactions on Telecommunications, volume 8 (1997) pages 33-37. (html)
  
  [LA00] Richard J. La, and Venkat Anantharam, "Charge-Sensitive TCP and Rate Control in the Internet". In Proceedings of IEEE INFOCOM 2000. (html)
   
• [LPW01] Steve Low, Larry Peterson and Liming Wang, Understanding TCP vegas: a duality model. In SIGMETRICS 2001. (html)
•  
• [B+98] S. Blake et al., "An Architecture for Differentiated Services". RFC 2475, December 1998. (txt)

An overview of the architecture of DiffServ. See [IntServ] for comparison.

• [CF98] D.D. Clark and W. Fang, "Explicit Allocation of Best-Effort Packet Delivery Service". IEEE/ACM Transactions on Networking. 6(4):362-373, August 1998. (ps)
• [XCP] Dina Katabi, Mark Handley, and Chalrie Rohrs. Congestion Control for High Bandwidth-Delay Product Networks. In the proceedings on ACM Sigcomm 2002. (html)

Traffic management--adaptive applications  [3 basic papers]

• [PM95] V. Padmanabhan and J. Mogul, "Improving HTTP Latency", Computer Networks and ISDN Systems, v. 28, pp. 25-35, December 1995.  (html)
   
• [BFT99] J. Bolot, S. Fosse-Parisis, D. Towsley, "Adaptive FEC-Based Error Control for Internet Telephony". In Proceedings of IEEE Infocom '99. (html)
   
• [RHE99] R. Rejaie, M. Handley, D. Estrin, "Quality Adaptation for Congestion Controlled Video Playback over the Internet". In Proceedings of ACM SIGCOMM '99, September 1999. (html)

Adaptation by predication.

Network security [3 basic papers]

• [Bel89] S. Bellovin, "Security Problems in the TCP/IP Protocol Suite" Computer Communication Review, Vol. 19, No. 2, April 1989, pp. 32-254. (html)
   
• [BAN90] Burrows and Abadi and Needham. "A Logic of Authentication."  Practical Cryptography for Data Internetworks, IEEE Computer Society Press. 1990. (html)
   
• [APS99] George Apostolopoulos, Vinod Peris, and Debanjan Saha, "Transport Layer Security: How much does it really cost?" In Proceedings IEEE INFOCOM '99, New York, March 1999. (html)

Measure the cost of SSL.

Beyond unicast: multicast and anycast [4 basic papers]

• [Dee88] S. Deering, "Multicast Routing in Internetworks and Extended LANs", SIGCOMM'88, Stanford, CA, Aug 1988, 55-64. (html)

The first model on IP multicast.

• [BFC93] T. Ballardie, P. Fracis, and J. Crowcroft, "An Architecture for Scalable Inter-Domain Multicast Routing", SIGCOM'93. (html)

Propose CBT.

• [DEFJ+94] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C.-G. Liu, and L. Wei, An Architecture for Wide-Area Multicast Routing, In Proeedings of. ACM SIGCOMM '94, London, U.K., September 1994. (ps.Z)

Propose PIM.

• [PMM93] C. Partridge, T. Mendez, W. Milliken, "Host Anycasting Service". IETF RFC 1546, Nov. 1993 (html)

Discuss IP anycast.

• [BTW94] J.-C. Bolot, T. Turletti, and I. Wakeman. "Scalable Feedback Control for Multicast Video Distribution in the Internet". In Proceedings of ACM SIGCOMM, pages 58-67, September 1994. (ps.gz) 

Use a random key to control feedback traffic.

• [FJML+95] S. Floyd, V. Jacobson, S. McCanne, C. G. Liu, and L. Zhang, "A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing", ACM SIGCOMM 95. (html)

Propose SRM and use ALF. Notice how they solve feedback implosion.

• [MJV96] S. McCanne, V. Jacobson, M. Vetterli, "Receiver-driven Layered Multicast". In Proceedings of ACM  SIGCOMM '96, Stanford, CA, August 1996. (ps.gz)

           Layered multicast.
   

• [VRC98] L. Vicisano, L. Rizzo, and J. Crowcroft, ``TCP-like Congestion Control for Layered Multicast Data Transfer'', IEEE Infocom 98, March 1998. (html)

  Emulate TCP behavior in layered multicast.

   

• [BLMR98] John W. Byers, Michael Luby, Michael Mitzenmacher, and Ashu Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data". In Proceedings of ACM SIGCOMM 1998. (html)
   
• [XB01] Zhen Xiao, Ken Birman, "A Randomized Error Recovery Algorithm for Reliable Multicast". In Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, April 2001.
   
• [CRSZ00] Yang-hua Chu, Sanjay G. Rao, Srinivasan Seshan, Hui Zhang, "A Case for End System Multicast". In Proceedings ACM Sigmetrics 2000, Santa Clara, CA, June 2000. (html)

Peer-to-peer networks [3 basic papers]

• [openp2p] O'Reilly's P2P web site
• [CSWH00] I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong, "Freenet: A Distributed Anonymous Information Storage and Retrieval System" ICSI Workshop on Design Issues in Anonymity and Unobservability, July 2000. (ps)

  Describe freenet.

• [SMKK+01] Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, Hari Balakrishnan, "Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications". In Proceedings of ACM SIGCOMM 2001. (html)

  How to search content in a peer-to-peer network?

• [RFHK+01] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, "A Scalable Content-Addressable Network". In Proceedings of ACM SIGCOMM 2001. (html)

  Another approach to search content in peer-to-peer network. Use virtual topology.

Domain Name System [2 basic papers]

• [MD88] P. Mockapetris and K. Dunlap, "Development of the Domain Name System", In Proceedings of ACM SIGCOMM , Stanford , CA, August 1988. (pdf)
   
• [JSBM01] J. Jung, E. Sit, H. Balakrishnan, R. Morris, "DNS Performance and the Effectiveness of Caching", In Proceedings of ACM SIGCOMM Internet Measurement Workshop , San Francisco, CA, November 2001. (html)
   
• [VDAA98] Amin Vahdat, Michael Dahlin, Thomas Anderson, and Amit Aggarwal, "Active Names: Flexible Location and Transport of Wide-Area Resources." In Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS), October 1999.  (ps, pdf)
• [Intentinal naming service]

Some important/influential papers selected by ACM and IEEE. Note that most of these papers are also repeated above under specific categories. Read the papers and think why they are considered to be influential.

• IEEE Communications Magazine 50th Anniversary 10 Landmark Articles (including commentaries)
  • The Viterbi Algorithm Applied to Digital Data Transmission/ Jeremiah F. Hayes
  • Spread Spectrum Communications: Myths and Realities/Andrew J. Viterbi
  • An Overview of Public Key Cryptography/Martin E. Hellman
  • New Directions in Communications (Or Which Way to the Information Age?)/Jonathan S. Turner
  • On Resource Sharing in a Distributed Communication Environment/Leonard Kleinrock
  • Mobile IP/Charles E. Perkins
  • SONET: Now It's the Standard Optical Network/Ralph Ballart and Yau-Chau Ching
  • An Analysis of TCP Processing Overhead/David D. Clark, Van Jacobson, John Romkey, and Howard Salwen
  • Adaptation and Mobility in Wireless Information Systems/Randy H. Katz
  • RSVP: A New Resource ReSerVation Protocol/Lixia Zhang, Stephen Deering, Deborah Estrin, Scott Shenker, and Daniel Zappala
• 25th Anniversary Issue of ACM CCR
  • Research Areas in Computer Communication, L. Kleinrock (Vol. 4, No. 3, July 1974)
  • Nomadic Computing - An Opportunity, L. Kleinrock
  • The ALOHA system, F. F. Kuo (Vol. 4, No. 1, January 1974)
  • Selecting Sequence Numbers, R. S. Tomlinson (Proc. ACM SIGCOMM/SIGOPS Interprocess Communications Workshop, Santa Monica, CA, March 1975)
  • An Overview of the New Routing Algorithm for the ARPANET, J. M. McQuillan, I. Richter, E. C. Rosen (Proc. Sixth Data Comm.Symposium, November 1979)
  • Congestion Control in IP/TCP Internetworks, J. Nagle (Vol. 14, No. 4, October 1984)
  • Improving Round-Trip Time Estimates in Reliable Transport Protocols, P. Karn, C. Partridge (Proc. SIGCOMM `87, Stowe, VT, August 1987, published as CCR Vol. 17, No. 5, October 1987)
  • Fragmentation Considered Harmful, C. A. Kent, J. C. Mogul (Proc. SIGCOMM `87, Stowe, VT, August 1987, published as CCR Vol. 17, No. 5, October 1987)
  • Multicast Routing in Internetworks and Extended LANs, S. Deering (Proc. SIGCOMM `88, Stanford, CA, August 1988, Vol. 18, No. 4)
  • The Design Philosophy of the DARPA Internet Procotols, D. D. Clark (Proc. SIGCOMM `88, Stanford, CA, August 1988, Vol. 18, No. 4)
  • Development of the Domain Name System, P. V. Mockapetris, K. J. Dunlap (Proc. SIGCOMM `88, Stanford, CA, August 1988, Vol. 18, No. 4)
  • Measured Capacity of an Ethernet: Myths and Reality, D. R. Boggs, J. C. Mogul, C. A. Kent (Proc. SIGCOMM `88, Stanford, CA, August 1988, Vol. 18, No. 4)
  • A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer, K. K. Ramakrishnan, R. Jain (Proc. SIGCOMM `88, Stanford, CA, August 1988, Vol. 18, No. 4)
  • Congestion Avoidance and Control, V. Jacobson (Proc. SIGCOMM `88, Stanford, CA, August 1988, Vol. 18, No. 4)
  • Analysis and Simulation of a Fair Queueing Algorithm, A. Demers, S. Keshav, S. Shenker (Proc. SIGCOMM `89, Austin, TX, September 1989, Vol 19. No. 4)
  • A Control-Theoretic Approach to Flow Control, S. Keshav (Proc. SIGCOMM `91, Zurich, Switzerland, September 1991, Vol. 21, No. 4)
  • On the Self-Similar Nature of Ethernet Traffic, W. E. Leland, M. S. Taqqu, W. Willinger, D. V. Wilson (Proc. SIGCOMM `93, San Francisco, CA, September 1993, Vol. 23, No. 4)
• PODC most influential-paper award (Edsger W. Dijkstra Prize in Distributed Computing)
  • 2000:  Leslie Lamport for "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, July 1978, 21(7):558-565.
  • 2001:  Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson for "Impossibility of  Distributed Consensus with One Faulty Process," Journal of the ACM, April 1985, 32(2):374-382.
  • 2002:  Edsger W. Dijkstra for "Self-stabilizing systems in spite of distributed control," Communications of the ACM 17(11):643-644, 1974.
• Recent Infocom best papers
  • 2003: User-Level Performance of Channel-Aware Scheduling Algorithms in Wireless Data Networks Sem Borst.
  • 2002: Priority Service and Max-Min Fairness, Peter Marbach
• Recent Sigcomm best student papers
  • 2004:
  • 2003:
  • 2002: Measuring ISP Topologies with Rocketfuel. Neil Spring, Ratul Mahajan and David Wetherall.
  • 2001: Hash-Based IP Traceback. Alex C. Snoeren, Craig Partridge, Luis A. Sanchez, Christine E. Jones, Fabrice Tchakountio, Stephen T. Kent, W. Timothy Strayer.
• Recent Mobicomm best student papers
  • 2002: Zero-Interaction Authentication. Mark Corner, Brian Noble, University of Michigan, USA.
  • 2001: Exposure In Wireless Ad-hoc Sensor Networks, Seapahn Meguerdichian (University of California, Los Angeles, USA); Farinaz Koushanfar (University of California, Berkeley, USA); Gang Qu (University of Maryland, USA); and Miodrag Potkonjak.
• Future research directions
  • Future Directions in Distributed Computing: Research and Position Papers, LNCS 2584; 2002

Tutorials

• Mostafa Ammar and Don Towsley, "Multicast". Presented at SIGCOMM 1997. (ppt)
• R. Gibbens and Peter kay, "Distributed control and resource pricing". Presented at SIGCOMM 2000. (ppt)
• Jon Crowcroft, "Internet Quality of Service". Presented at Infocom 2000. (ppt)
• Steven Low, "TCP and AQM". Presented at SIGCOMM 2001. (ppt)
• Nitin H. Vaidya "Ad hoc networks". Presented at Mobicom 2001. (ppt)
• Avi Freedman, "BGP 102". (ppt)
• J. Charzinski, "Internet Traffic Measurement and Modelling Tutorial," ACM Sigmetrics 2001, Cambridge, MA, USA, 17.6.2001. (pdf)
• Deborah Estrin, et el. "Sensor networks" at Mobicom 2002. (link)

Books (in reverse chronological order)

• [KR01] J. F. Kurose and W. R. Ross, "Computer Networking: A Top-Down Approach Featuring the Internet", Addison Wesley Logman, Inc., 2001.
• [Gil00] George Gilder, "Telecosm : How Infinite Bandwidth Will Revolutionize Our World". Free Press; ISBN: 0684809303.
• [PD00] L. L. Peterson and B. S. Davie, "Computer Networks: A System Approach", Morgan Kaufman Publishers, 2000.
• [Hui98] C. Huitema, "IPv6: The New Internet Protocol",  Prentice-Hall Second edition Upper Saddle River, NJ 1998 247 pages ISBN 0-13-850505-5
• [Kes97] S. Keshav, "An Engineering Approach to Computer Networking", Addison Wesley Logman, Inc., 1997.
• [Ste97b] W. Richard Stevens, "UNIX Network Programming, Volume 1: Networking APIs - Sockets and XTI", 1009 pages 2 edition, Prentice Hall PTR; ISBN: 013490012X.
• [Tan96] Andrew S. Tanenbaum, "Computer Networks", Prentice Hall, Hardcover, 3rd edition, Published March 1996, 820 pages, ISBN 0133499456.
• [SW96] W. Richard Stevens, Gary R. Wright, "TCP/IP Illustrated, Volume 3: TCP for Transactions, HTTP, NNTP, and the Unix Domain Protocols",  Addison-Wesley, Hardcover, Published January 1996, 325 pages, ISBN 0201634953.
• [KG96] Leonard Kleinrock, Richard Gail (Contributor), "Queueing Systems : Problems and Solutions", Paperback - 227 pages (March 1996) John Wiley & Sons; ISBN: 0471555681.
• [SW95] W. Richard Stevens, Gary R. Wright, "TCP/IP Illustrated, Volume 2: The Implementation",  Addison-Wesley, Hardcover, Published January 1995, 832 pages, ISBN 020163354X.
• [Hui95] C. Huitema, "Routing in the Internet",  Prentice-Hall Englewood Cliffs, NJ 1995 319 pages ISBN 0-13-132192-7
• [Ste94] W. Richard Stevens, "TCP/IP Illustrated, Volume 1: The Protocols", Addison-Wesley, Hardcover, Published January 1994, 600 pages, ISBN 0201633469.
• [Per92] Radia Perlman, "Interconnections: Bridges and Routers", Addison-Wesley, Hardcover, Published May 1992, 400 pages, ISBN 0201563320.
• [Ste92] W. Richard Stevens, "Advanced Programming in the UNIX Environment", 744 pages (June 1992) Addison-Wesley Pub Co; ISBN: 0201563177.
• [BG91] Dimitri P. Bertsekas, Robert Gallager, "Data Networks", Hardcover - 592 pages 2nd edition (December 1991) Prentice Hall; ISBN: 0132009161.
• [Jai91] R. Jain, "The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling", John Wiley & Sons New York, NY 1991 683 pages ISBN 0-471-50336-3.
• [Kle76] Leonard Kleinrock (Editor), "Queueing Systems : Computer Applications", Library Binding - 576 pages Vol 002 (April 1976) John Wiley & Sons; ISBN: 047149111X.
• [Kle75] Leonard Kleinrock, "Queueing Systems : Theory"  Hardcover - 448 pages Vol 001 (January 1975) John Wiley & Sons; ISBN: 0471491101.

All right reserved by Yang Richard Yang  ©2003. Please do not redistribute.