Engineering Approach to Computer Networking, An: ATM Networks, the Internet, and the Telephone Network

About

Features

effective "engineering" approach that not only describes how networks operate but also offers insight into the principles of network design.

An Engineering Approach to Computer Networking simultaneously studies all three major network technologies-Asynchronous Transfer Mode (ATM), Internet, and telephony. You will find clear overviews of these technologies and extensive, up-to-date coverage of all essential networking topics: protocol layering; multiple access; switching; scheduling; naming, addressing, and routing; error and flow control; and traffic management. For each topic, the book identifies fundamental constraints and analyzes the pros and cons of several alternative solutions. Through detailed descriptions of common protocols used in telephone, Internet, and ATM networks-as well as a tour of system design and protocol implementation techniques-this book shows you how these concepts are put to use in real networks.

Practical in focus, An Engineering Approach to Computer Networking features many real-world examples and is supported with on-line material including:

• Microsoft PowerPoint slides covering the material in the book.
• A multithreaded, packet-level network simulator that allows users to simulate arbitrary protocols.
• Simulation exercises covering multiple access, error control, flow control, routing, and scheduling.
• A bibliography with links to Web sites referred to in the text.
• A searchable glossary.
• Solutions to all exercises.

With this deeper understanding of network structure and hands-on experience implementing protocols, you will have an excellent command of the field and be better equipped to design powerful and efficient networks and leading-edge networking software.

S. Keshav, Associate Professor of Computer Science at Cornell University, has employed the engineering approach with great success in networking courses he has taught at the Indian Institute of Technology, Delhi, and Columbia University. Formerly a Member of the Technical Staff at AT&T Bell Laboratories, Dr. Keshav received his Ph.D. in 1991 from the University of California at Berkeley. He can be reached at skeshav@cs.cornell.edu.



Description

• Copyright 1997
• Dimensions: 7-1/2" x 9-1/4"
• Pages: 680
• Edition: 1st

• Book
• ISBN-10: 0-201-63442-2
• ISBN-13: 978-0-201-63442-6

This practical introduction to computer networking takes a unique and highly effective "engineering" approach that not only describes how networks operate but also offers insight into the principles of network design.

An Engineering Approach to Computer Networking simultaneously studies all three major network technologies-Asynchronous Transfer Mode (ATM), Internet, and telephony. You will find clear overviews of these technologies and extensive, up-to-date coverage of all essential networking topics: protocol layering; multiple access; switching; scheduling; naming, addressing, and routing; error and flow control; and traffic management. For each topic, the book identifies fundamental constraints and analyzes the pros and cons of several alternative solutions. Through detailed descriptions of common protocols used in telephone, Internet, and ATM networks-as well as a tour of system design and protocol implementation techniques-this book shows you how these concepts are put to use in real networks.

Practical in focus, An Engineering Approach to Computer Networking features many real-world examples and is supported with on-line material including:

• Microsoft PowerPoint slides covering the material in the book.
• A multithreaded, packet-level network simulator that allows users to simulate arbitrary protocols.
• Simulation exercises covering multiple access, error control, flow control, routing, and scheduling.
• A bibliography with links to Web sites referred to in the text.
• A searchable glossary.
• Solutions to all exercises.

With this deeper understanding of network structure and hands-on experience implementing protocols, you will have an excellent command of the field and be better equipped to design powerful and efficient networks and leading-edge networking software.

S. Keshav, Associate Professor of Computer Science at Cornell University, has employed the engineering approach with great success in networking courses he has taught at the Indian Institute of Technology, Delhi, and Columbia University. Formerly a Member of the Technical Staff at AT&T Bell Laboratories, Dr. Keshav received his Ph.D. in 1991 from the University of California at Berkeley. He can be reached at keshav@ensim.com.



Downloads

Source Code

Click below for Code related to this title:
Solutions



Extras

Web Resources

Click below for Web Resources related to this title:
Simulator
Slides



Sample Content

Table of Contents

(Most chapters contain a Summary.)

Preface xiii.

SECTION II. INTRODUCTION.

1. Atoms, Bits, and Networks.

Introduction.

Common Network Technologies.

Networking Concepts and Techniques.

Engineering Computer Networks.

In Closing.

2. The Telephone Network: Concepts, History, and Challenges.

Concepts.

End-Systems.

Transmission.

Switching.

Signaling.

Cellular Communications.

Historical Sketch.

Challenges.

Summary.

3. The Internet: Concepts, History, and Challenges.

Concepts.

Basic Internet Technology.

Addressing.

Routing.

Endpoint Control.

History.

Challenges.

Summary.

4. Atm Networks: Concepts, History, and Challenges.

Virtual Circuits.

Fixed-Size Packets.

Small Packet Size.

Statistical Multiplexing.

Integrated Service.

History.

Challenges.

Summary.

SECTION II. TOOLS AND TECHNIQUES.

5. Protocol Layering.

Protocols and Protocol Layering.

Importance of Layering.

Problems With Layering.

Iso-Osi Reference Model.

The Seven Layers.

Summary.

6. System Design.

Introduction.

Resource Constraints and Their Metrics.

Common Design Techniques.

Performance Analysis and Tuning.

Summary.

7. Multiple Access.

Introduction.

Choices and Constraints.

Base Technologies.

Centralized Access Schemes.

Distributed Schemes.

Summary.

8. Switching.

Introduction.

Circuit Switching.

Packet Switching.

Switch Fabrics.

Buffering.

Multicasting.

Summary.

9. Scheduling.

Introduction.

Requirements.

Fundamental Choices.

Scheduling Best-Effort Connections.

Scheduling Guaranteed-Service Connections.

Comparison.

Packet Dropping.

Summary.

10. Naming and Addressing.

Introduction.

Naming and Addressing.

Hierarchical Naming.

Addressing.

Addressing in the Telephone Network.

Addressing in the Internet.

Nsaps: Addressing in ATM Networks.

Name Resolution.

Datalink Layer Addressing.

Finding Datalink Layer Addresses.

Summary.

11. Routing.

Introduction.

Routing Protocol Requirements.

Choices.

Routing in the Telephone Network.

Distance-Vector Routing.

Link-State Routing.

Choosing Link Costs.

Hierarchical Routing.

Internet Routing Protocols.

Routing Within a Broadcast Lan.

Multicast Routing.

Routing With Policy Constraints.

Routing for Mobile Hosts.

Summary.

12. Error Control.

Causes of Bit Errors.

Bit-Error Detection and Correction.

Causes of Packet Errors.

Packet-Error Detection and Correction.

Summary.

13. Flow Control.

Model.

Classification.

Open-Loop Flow Control.

Closed-Loop Flow Control.

Hybrid Flow Control.

Summary.

14. Traffic Management.

Introduction.

An Economic Framework for Traffic Management.

Traffic Models.

Traffic Classes.

Time Scales of Traffic Management.

Scheduling.

Renegotiation.

Signaling.

Admission Control.

Peak-Load Pricing.

Capacity Planning.

Summary.

SECTION III. PRACTICE.

15. Common Protocols.

Introduction.

Telephone Network Protocols.

Internet Protocols.

Atm Network Protocols.

Ip Over Atm.

Summary.

16. Protocol Implementation.

Introduction.

Factors Affecting Protocol Stack Performance.

Common Protocol Stack Procedures.

Partitioning Strategies.

Interface Among Protocol Layers.

Protocol Implementation.

Some Rules of Thumb.

Summary.

References.
Glossary.
Answers to Review Questions and Selected Exercises.
Index. 0201634422T04062001

Preface

The world is surging toward a digital revolution where computer networks mediate every aspect of modern life, from paying bills to buying real estate, and from reading a book to watching a film. Computer networks are complex systems that almost magically link tens of millions of computers and more than a billion telephones around the world. A single mouse-click in a Web browser can download text, images, and animations from a computer hundreds or thousands of miles away. With a satellite or cellular telephone, even the most intrepid explorer in the remotest corner of the Earth can call home. How do we build these marvelous webs of interconnection? The goal of this book is to introduce readers to what lies at the basis of computer networks, and why they work the way they do. This book is based on a course that I taught at the Indian Institute of Technology, Delhi, India, in the spring of 1993. My aim was to teach students why networks were built the way they were. I wanted them to question every design decision, and to understand how these decisions would change if we changed the assumptions. I call this an engineering approach to computer networking.

Perhaps it is easiest to appreciate this approach by comparing it with some other approaches. Suppose you wanted to route packets in a computer network. A protocol approach would describe the routing protocols in common use and their packet formats and algorithms, and perhaps compare several routing protocols. An analytical approach would model the network as a graph, assume a traffic distribution from every source to every destination, then compute optimal routing. In my opinion, both these approaches, though important, miss the point. A purely protocol approach tells the reader how routing works, but not why it was designed that way. The success of an analytical approach depends critically on the assumptions it makes. Unfortunately, because of the complexities of the real world, to make the problem tractable, the analyst must make many simplifying assumptions. In my experience, this simplification leads to "toy" models that do not explain what is really important, and what details we can ignore. In contrast, the engineering approach is to begin by identifying the fundamental constraints on the problem, make reasonable "real-world" assumptions, and then examine several alternative solutions, trading off their pros and cons. An engineer recognizes that no solution is perfect, but that every solution represents a particular trade-off between cost and benefit. This book focuses on identifying the fundamental problems and the trade-offs in solving them.

The second aspect of an engineering approach is to learn by doing. This book is meant to be used with implementation exercises on the Internet and on the REAL network simulator. These exercises, which are available on-line at http://www.aw.com/cp/keshav/engcom.html, allow students to learn protocol design and implementation hands-on. Unlike other textbooks in the area, this book simultaneously studies the principles underlying the Internet, the telephone network, and asynchronous transfer mode (ATM) networks. The Internet is the most successful embodiment of a data network, and its study needs no further justification. The global telephone network is arguably the world's largest computer network, though it is specialized to carry voice. Unfortunately, few outside the telephone industry know much about how the telephone network operates, perhaps because of the layers of acronyms and arcana that surround its operations. This book is a small attempt to rectify the situation. Finally, many see ATM networks as the future of computer networking. Although this may not be true, ATM networks are interesting because they draw on experience with the telephone network and the Internet to build an integrated services network that provides end-to-end quality of service. This ambitious goal has led to a unique set of design decisions that have influenced both networking research and commercial networking products. Thus, ATM networks are well worth studying.

Target audience

I assume that readers will have some familiarity with data structures and algorithms, operating systems, elementary algebra, and computer architecture. Deeper material assumes knowledge of calculus and probability. However, most concepts do not require mathematical sophistication beyond a first undergraduate course. In particular, the book almost completely avoids use of queuing theory. Although an appreciation of queuing theory is important in engineering computer networks, I feel queuing theory is best studied as a separate course: to really understand its strengths and its domain of applicability, one needs a deep understanding of the topic that cannot be provided by a book such as this.

The bulk of this book is written at a level suitable for first-year graduate students in computer science or electrical engineering. It is also suitable for advanced undergraduate seniors. Students who intend to work in the area of computer networking or related areas should probably read through the entire text and attempt all the exercises. A number of features make it easy to use for a first undergraduate course. First, every chapter is self-contained, so that instructors can skip entire chapters if necessary. Second, each topic is developed from first principles, with little assumption about the background of the reader, other than some familiarity with mathematics and operating systems. A more sophisticated development that follows from these first principles is marked with vertical sidebars and can be ignored in a first course. Third, most topics are presented at an intuitive level, with little mathematical or algorithmic formalism. Finally, complete solutions are provided to instructors for all numerical exercises.

The book is also targeted at professionals in the field, and at researchers in other areas who want an introduction to the current research frontiers in computer networking. A comprehensive index helps in locating a topic quickly. Moreover, the glossary is keyed to the section or subsection that describes the topic, so that one can rapidly look up the context for a technical term. For those interested in pursuing a topic further, an extensive annotated bibliography references key papers in the field.

Organization

The book has three sections. The first section is an overview of three important networking technologies: telephony (Chapter 2), Internet (Chapter 3), and ATM (Chapter 4). Each introductory chapter describes key elements in the technology, some history, and my perception of the important challenges for the technology.

The second section describes the pieces that come together to form a network. Most chapters in this section begin with an overview of a problem and a taxonomy of possible solutions. We then study a number of representative solutions, concentrating on the set of trade-offs they represent. We can apply most of these solutions to any protocol layer, so we study them independently of protocol layering.

The second section starts with an introductory chapter on protocol layering (Chapter 5) and an overview of the art and science of system design (Chapter 6). These chapters provide a "toolkit" of common system design techniques that we will use in subsequent chapters. Chapter 7 introduces the issue of multiple access, which arises in contexts as diverse as satellite networks, cellular telephony, and local area networks. Chapter 8 describes switching, which is fundamental to the operation of all nontrivial networks. In order to provide end-to-end quality of service, switches (and other multiplexing points) must implement a scheduling algorithm. We study scheduling algorithms in Chapter 9. The next two chapters cover naming, addressing, and routing. At this point, the reader knows enough about how to put together a wide-area network. But, for the network to work efficiently, we need to add two more functionalities: error control and flow control. We study these in Chapters 12 and 13. As we build larger and larger networks, the problem of network control becomes significant. We study this in Chapter 14.

The third section applies the tools and techniques discussed in the preceding chapters to understanding and implementing some common protocols. Chapter 15 presents a detailed description of protocol headers in the telephone network, Internet, and ATM networks, tying together the material in the previous chapters. Finally, Chapter 16 is a survey of protocol implementation techniques.

Style conventions

Textbooks, almost by definition, tend to be boring. A dry assemblage of facts does little to bring out the controversies, the intellectual fights, and the wide-eyed what-if questions that make networking such an interesting and challenging field. I have attempted to capture some of these in what I call engineering boxes. These boxes go off on a tangent from the text, question standard assumptions, and present viewpoints on the fringe of the mainstream. They offer a subjective commentary on the objective and dry material in the text.

I firmly believe in the use of numerical examples to explain concepts. Solved numerical examples throughout the book reinforce the use of back-of-the-envelope calculations in system design, and simultaneously introduce the student to "real-world" constants that engineers use in their calculations. I hope these examples will motivate readers to do their own rough calculations as they embark on a system design.

Advanced material is in smaller font and set off with vertical sidebars as shown in this paragraph. Such material can be ignored in a first reading, or in an undergradute course, with no loss of continuity.

Usage guidelines

In a graduate class, I recommend that the instructor assign Chapters 1-5 as a single reading assignment at the end of the first class. The material here should serve primarily as a review. Subsequent chapters, starting with Chapter 6, can be covered in two or three one-hour lectures per chapter, except Chapter 11, which will require four lectures. In my courses, I used the first hour to cover principles, and the second (and, if necessary, third) to cover specific solutions. I also recommend choosing some exercises for homework and assigning one implementation exercise every two weeks.

In an undergraduate class, the instructor could spend the first several lectures on the first six chapters. The remaining chapters could be covered at the discretion of the instructor, perhaps skipping advanced material. In a first course, Chapters 13, 14, and 16 and advanced topics in Chapters 7, 8, 9, 11, and 12 can be left out entirely.

A reader unfamiliar with the field should probably first read Chapters 1-4. Subseqent chapters may be read as the occasion arises. Much of the material can also be accessed by way of the keyed glossary.

Acknowledgments

I have drawn upon many people in the course of writing this book. During my visit to the Indian Institute of Technology, Delhi, where work on this book began, I had the good fortune to interact with Professors B. N. Jain, S. N. Maheshwari, and Huzur Saran. Detailed class notes by Rajeev Leekha and V. N. Padmanabhan gave me the confidence to start writing this book and formed the core of the first draft. My thanks to them.

I gratefully acknowledge the support and good advice from my friends and colleagues at AT&T Bell Laboratories: Joe Condon, Sandy Fraser, Milan Jukl, Chuck Kalmanek, Hemant Kanakia, Alan Kaplan, Brian Kernighan, Rajiv Laroia, Bill Marshall, Partho Mishra, Sam Morgan, K. K. Ramakrishnan, Bob Restrick, Norm Schryer, Ravi Sethi, David Tse, John Venutolo, and Mihalis Yannakakis. In particular, Alan Kaplan's detailed review of the first two drafts cleared up many errors and inconsistencies, and added an insider's perspective on telephone networking. I also drew upon many colleagues to clear up specific questions. These include Tony Ballardie (UC London), Alan Berenbaum (Bell Labs), Jean Bolot (INRIA), Tony DeSimone (AT&T Research), Bharat Doshi (AT&T Research), Andrew Odlyzsko (AT&T Research), Craig Partridge (BBN), K. K. Ramakrishnan (AT&T Research), Nambi Seshadri (AT&T Research), and Sandeep Sibal (AT&T Research). Special thanks to Pawan Goel at UT Austin for his detailed and perceptive comments on Chapter 9.

I received insightful comments from a number of reviewers on earlier drafts of the book. I received comments on the first draft from Rajeev Agrawal (U Wisconsin, Madison), Cagatay Buyukkoc (AT&T Research), Mark Clement (Brigham Young), Matthias Grossglauser (AT&T Research), Peter Haverlock (Bay Networks), Sugih Jamin (U Michigan, Ann Arbor), Alan Kaplan (AT&T Research), Brian Kernighan (Bell Labs), Doug McIlroy (Bell Labs), Sam Morgan (Bell Labs), Will Morse (BHP Petroleum), Badri Nathan (Andersen Consulting), Craig Partridge (BBN), Vern Paxson (Lawrence Berkeley Lab), Daniel Pitt (HP), Huzur Saran (IIT Delhi), Matthew Scott (Fore Systems), Rosen Sharma (Stanford), Harry Singh (Hitachi), David Tse (UC Berkeley), Roya Ulrich (ICSI), and Hui Zhang (Carnegie Mellon U). I received comments on the second draft from John Gulbenkian (Cerf Net), Alan Kaplan (AT&T Research), Brian Kernighan (Bell Labs), Sugih Jamin (U Michigan, Ann Arbor), Will Morse (BHP Petroleum), Daniel Pitt (HP), Ravi Prakash (FTP Software), Matthew Scott (Fore Systems), Huzur Saran (IIT Delhi), and Hui Zhang (Carnegie Mellon U). My thanks to them all.

0201634422P04062001

Bibliography

References

References for Chapter 1: Atoms, Bits, and Networks

[BK 95] D. Burstein and D. Kline. Road Warriors: Dreams and Nightmares along the Information Highway. Dutton, 1995.

A fascinating introduction to the realities of the digital revolution. The revolution will bring not only technological opportunities, but jarring societal changes that the authors think ought to be the subject of conscious social policy.

[Penzias 89] A. A. Penzias. Ideas and Information: Managing in a High-Tech World. W.W. Norton, 1989.

Penzias, formerly Vice President of Bell Labs, talks informally about the impact of computers and communications on corporations and society. An interesting look at how computers affect the nuts-and-bolts operation of corporations.

[Negroponte 95] N. Negroponte. Being Digital. Alfred A. Knopf, 1995.

A visionary exploration of what it means to live in a digital world. Negroponte is a sage of the digital era, and every page of this book is insightful.

References for Chapter 2: The Telephone Network: Concepts, History, and Challenges

[Bellamy 91] J. Bellamy. Digital Telephony, Second Edition. John Wiley and Sons, 1991.

A lucid description of telephone network design and operation, with details on some recent advances such as SONET.

[Blahut 90] R. E. Blahut. Digital Transmission of Information. Addison-Wesley, 1990.

Standard reference on error coding.

[Boettinger 77] H. M. Boettinger. Telephone Book: Bell, Watson, Vail and American Life, 1876-1976. Riverwood, 1977.

A fascinating coffee-table book with lots of pictures of the telephone network in its early days. A great way to spend a rainy day!

[BS 82] Bell Telephone Laboratories. Engineering and Operations in the Bell System. Bell Telephone Laboratories, 1982.

Prepared in anticipation of divestiture by Members of the Technical Staff of the undivided Bell Laboratories, this is an exhaustive description of everything in the Bell System, as it existed in 1980. It is the ultimate introduction to the telephone system.

[Noll 86] A. M. Noll. Introduction to Telephones and Telephone Systems. Artech House, 1986.

Crisp and clear high-level introduction to telephone networks.

[PN 90] J. R. Pierce and A. M. Noll, Signals: The Science of Telecommunications. Scientific American Library, 1990.

A fascinating introduction to basic concepts in telecommunications, including coding, modulation, switching, and multiplexing.

References for Chapter 3: The Internet: Concepts, History, and Challenges

[BK 95] D. Burstein and D. Kline. Road Warriors: Dreams and Nightmares along the Information Highway. Dutton, 1995.

A fascinating introduction to the realities of the digital revolution. The revolution will bring not only technological opportunities, but jarring societal changes that the authors think ought to be the subject of conscious social policy.

[Clark 88] D. D. Clark. The Design Philosophy of the DARPA Internet Protocols. Proceedings of ACM SIGCOMM '88, August 1988, pp. 106-114.

Describes the reasoning behind the design of TCP and IP. Anecdotes about the early days.

[LR 93] D. C. Lynch and M. T. Rose (eds.). Internet System Handbook. Addison-Wesley, 1993.

Comprehensive, though slightly dated, outline of Internet technology. Excellent surveys on routing, performance tuning, and network management, and an historical overview.

[MV 95] H. MacKie-Mason and H. R. Varian. Pricing Congestible Network Resources. IEEE Journal on Selected Areas in Communication, Vol. 13, No. 7, September 1995, pp. 1141-1149.

Shows the impact of flat-rate and congestion pricing on network behavior.

[SRC 84] J. H. Saltzer, D. P. Reed, and D. D. Clark. End-to-End Arguments in System Design. ACM Transactions on Computer Systems, Vol. 2, No. 4, November 1984, pp. 277-288.

Classic paper describing the need for the "end-to-end principle" and giving examples of its application.

[Zimmerman 80] H. Zimmerman. OSI Reference ModelæThe ISO Model of Architecture for Open Systems Interconnection. IEEE Transactions on Communications, Vol. 28, No. 4, April 1980, pp. 425-432.

Formal introduction to concepts of ISO protocol layering.

References for Chapter 4: ATM Networks: Concepts, History, and Challenges

[Fraser 74] A. G. Fraser. SpideræAn Experimental Data Communications System. Proceedings of IEEE Conference on Communications, June 1974.

Describes an early ATDM system that uses virtual circuits and fixed-size cells.

[Fraser 83] A. G. Fraser. Towards a Universal Data Transport System. IEEE Journal on Selected Areas in Communication, Vol. 1, No. 5, November 1983.

Describes Datakit, a follow-on to Spider that had much better error and flow control.

[Fraser 93] A. G. Fraser. Early Experiments with Asynchronous Time Division Networks. IEEE Network, January 1993, pp. 12-26.

A survey of early work, with historical anecdotes.

[HTK 64] T. Hasegawa, Y. Tezuka, and Y. Kasahara. Digital Data Dynamic Transmission Systems. IEEE Transactions on Communication Technology, 1964.

Early paper on asynchronous time-division multiplexing.

[KTNH 61] Y. Kasahara, Y. Tezuka, S. Nakanishi, and T. Hasegawa. On an Asynchronous Time Multiplexing Communication System. Joint Convention Record Institutes Related with Electrical Engineering, Kansai Branch, Pt. 19, October 1961, pp. 292 (in Japanese).

Early paper describing the concept of packet headers for efficient use of a transmission link.

[Marcus 69] M. G. Marcus. The Design and Analysis of a New Type of Time-Division Switching System. M.Sc. Thesis, MIT, June 1969.

An early ATM switch design.

[Stallings 88] W. Stallings. Data and Computer Communication, Second Edition. Macmillan, 1988.

Standard textbook on computer networking.

References for Chapter 5: Protocol Layering

[Clark 82] D. D. Clark. Modularity and Efficiency in Protocol Implementation. RFC 817, July 1982.

Classic reference on protocol implementation strategies.

[DZ 83] J. Day and H. Zimmerman. The OSI Reference Model. Proceedings of the IEEE, Vol. 71, No. 12, December 1983.

Outline of the OSI reference model.

[EC 83] W. Emmons and H. Chandler. OSI Session Layer Services and Protocols. Proceedings of the IEEE, Vol. 71, No. 12, December 1983.

[Stallings 88] W. Stallings. Data and Computer Communication, Second Edition. Macmillan, 1988.

Standard textbook on computer networking.

[Zimmerman 80] H. Zimmerman. OSI Reference ModelæThe ISO Model of Architecture for Open Systems Interconnection. IEEE Transactions on Communications, Vol. 28, No. 4, April 1980, pp. 425-432.

Formal introduction to concepts of ISO protocol layering.

References for Chapter 6: System Design

[Ferrari 78] D. Ferrari. Computer Systems Performance Evaluation. Prentice Hall, 1978.

Classic text on performance evaluation.

[FJMZL 95] S. Floyd, V. Jacobson, S. McCanne, L. Zhang, and C. Liu. A Reliable Multicast Framework for Lightweight Session and Application Level Framing. Proceedings of ACM SIGCOMM '95, September 1995.

Describes several uses of randomization for scalable reliable multicast.

[Jain 91] R. Jain. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. Wiley, 1991.

[Kaplan 92] A. E. Kaplan. A History of the COSNIX Operating System: Assembly Language Unix 1971 to July 1991. USENIX Winter 1992 Technical Conference, San Francisco, January 1992, pp. 429-434.

A blow-by-blow account of how an early Unix system was tuned to reduce response time for interactive jobs, while allowing access to large disk-resident databases.

[PH 95] D. Patterson and J. Hennesey. Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufman, 1995.

Standard introductory text on computer architecture.

[SG 94] A. Silberschatz and P. Galvin. Operating Systems Concepts, Fourth Edition. Addison-Wesley, 1994.

Standard introductory text on operating systems.

[Tanenbaum 92] A. Tanenbaum. Modern Operating Systems. Prentice Hall, 1992.

Standard introductory text on operating systems.

References for Chapter 7: Multiple Access

[Abramson 70] N. Abramson. The ALOHA SystemæAnother Alternative for Computer Commmunications. Proceedings of Fall Joint Computer Conference, 1970.

The original description of the influential ALOHA protocol.

[Abramson 94] N. Abramson. Multiple Access in Wireless Digital Networks. Proceedings of the IEEE, Vol. 82, No. 9, September 1994.

Argues that CDMA requires only a single code and shows how to extend ALOHA to obtain the same benefits as CDMA.

[AnyLAN FAQ 96] AnyLAN FAQ. HTTP://WWW.IO.COM/~RICHARDR/VG/, 1996.

Introduction to 100VG AnyLAN, with links to products and other related technologies.

[AnyLAN 96] AnyLAN tutorial. HTTP://WWW.IOL.UNH.EDU/TRAINING/VGANYLAN/TEACH/, 1996.

[BDSZ 94] V. Bhargavan, A. Demers, S. Shenker, and L. Zhang. MACAW: A Media Access Protocol for Wireless LANs. Proceedings of ACM SIGCOMM '94, London, September 1994.

Discusses problems with MACA, and some solutions.

[Binder 75] R. Binder. A Dynamic Packet Switching System for Satellite Broadcast Channels. Proceedings of the ICC, 1975.

Describes a variant of R-ALOHA.

[Cox 96] D. Cox. Wireless Communication Networks. Tutorial Notes, IEEE INFOCOM '96, March 1996.

A practitioner's view of wireless communication.

[CRWOH 73] W. Crowther, R. Rettberg, D. Walden, S. Orenstein, and F. Heart. A System for Broadcast Communication: Reservation ALOHA. Proceedings of the Sixth Hawaii International System Science Conference, 1973.

Early description of Reservation ALOHA.

[DN 96] A. DeSimone and S. Nanda. Wireless Data: Systems, Standards, Services. Journal of Wireless Networks, Vol. 1, February 1996, special issue on recent advances in wireless networking technology.

Tutorial on IEEE 802.11, CDPD, and reliable transport over wireless networks.

[Ethernet FAQ 96] Ethernet FAQ. HTTP://TOOLBOX.RUTGERS.EDU/~QMAN/TECHSUPPORT/ETHERNETFAQ.HTML, 1996.

[FAG 95] David D. Falconer, F. Adachi, and B. Gudmundson. Time Division Multiple Access Methods for Wireless Personal Communications. IEEE Communications Magazine, January 1995, pp. 50-57.

Tutorial on TDMA.

[FDDI FAQ 96] FDDI FAQ. HTTP://SHOLEH.NSWC.NAVY.MIL/X3T12/FDDIFAQ.HTML, 1996.

Frequently asked questions about FDDI (and their answers).

[Hayes 84] J. F. Hayes. Modeling and Analysis of Computer Communications Networks. Plenum Publishing Corporation, 1984.

[Jain 94] R. Jain. FDDI Handbook: High-Speed Networking Using Fiber and Other Media. Addison-Wesley, 1994.

[Johnson 96] H.W. Johnson. Fast EthernetæDawn of a New Network. Prentice Hall, 1996.

[Karn 90] P. Karn. MACAæA New Channel Access Method for Packet Radio. Proceedings of ARRL/CRRL Amateur Radio 9th Computer Networking Conference, September 1990.

Insightful description of MACA.

[Kleinrock 75] L. Kleinrock. Queueing Systems, Vol. 1 and Vol. 2. Wiley-Interscience, 1975.

Classic textbook on queueing theory.

[Lam 80] S. S. Lam. Packet Broadcast NetworksæA Performance Analysis of the R-ALOHA Protocol. IEEE Transactions on Computers, July 1980.

[MB 76] R. Metcalfe and D. R. Boggs. Ethernet: Distributed Packet Switching for Local Computer Networks. Communications of the ACM, July 1976.

Classic paper describing Ethernet design and implementation.

[Metricom 96] Metricom Ricochet Home Page. HTTP://WWW.METRICOM.COM/RICOCHET/, 1996.

Describes the Metricom packet-radio product.

[PF 94] V. Paxson and S. Floyd. Wide-Area Traffic: The Failure of Poisson Modeling. Proceedings of ACM SIGCOMM '94, London, September 1994.

Uses measurements to claim that Poisson models do not adequately describe real traffic.

[PGH 95] J. E. Padgett, C. G. Gunther, and T. Hattori. Overview of Wireless Personal Communications. IEEE Communications Magazine, January 1995.

[PL 95] K. Pahlavan and A. H. Levesque. Wireless Information Networks. John Wiley and Sons, New York, 1995.

Textbook devoted to wireless communication networks. Detailed description and a solid mathematical approach.

[Roberts 75] L. Roberts. ALOHA Packet System with and without Slots and Capture. Computer Communication Review, April 1975.

Describes Roberts's scheme for R-ALOHA.

[Sklar 88] B. Sklar. Digital CommunicationsæPrinciples and Applications. Prentice Hall, 1988.

[Stallings 88] W. Stallings. Data and Computer Communications, Second Edition. Macmillan Publishing, 1988.

Textbook on data communications.

[Switched Ethernet FAQ 96] HTTP://WWW.XEDIA.COM/center/resources.html, 1996.

[TK 75] F. A. Tobagi and L. Kleinrock. Packet Switching in Radio Channels, Part II: The Hidden-Terminal Problem in Carrier Sense Multiple Access and the Busy-Tone Solution. IEEE Transactions on Communication, Vol. 23, 1975, pp. 1417-1453.

Describes need for BTMA, the solution, and its analysis.

[Viterbi 95] A. J. Viterbi. CDMA: Principles of Spread Spectrum Communication. Addison-Wesley, 1995.

CDMA, as described by one of its inventors and a practitioner.

References for Chapter 8: Switching

[AD 89] H. Ahmadi and W. E. Denzel. A Survey of Modern High-Performance Switching Techniques. IEEE Journal on Selected Areas in Communication, Vol. 7, No. 9, September 1989, pp. 1091-1103.

An excellent survey of third-generation switching fabrics.

[AOST 93] T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker. High Speed Switch Scheduling for Local Area Networks. ACM Transactions on Computer Systems, Vol. 11, No. 4, November 1993, pp. 319-352.

Describes the Parallel Iterated Match algorithm for arbitration in input-queued switches.

[Batcher 68] K. E. Batcher. Sorting Networks and Their Application. Proceedings of the Spring Joint Computer Conference, AFIPS, 1968, pp. 307-314.

Classic paper on sorting and merging networks.

[Bellamy 91] J. Bellamy. Digital Telephony. John Wiley and Sons, 1991.

Excellent introduction to telephony.

[Clos 53] C. Clos. A Study of Non-Blocking Switching Networks. Bell System Technical Journal, Vol. 32, No. 3, March 1953, pp. 406-424.

Early paper on conditions that a nonblocking circuit switch should satisfy.

[CT 92] F. M. Chiussi and F. A. Tobagi. A Hybrid Shared-Memory/Space-Division Architecture for Large Fast Packet Switches. Proceedings of SUPERCOMM ICC'92, June 1992.

A critique of problems with Banyan switches, and a proposal for a new switch fabric.

[DJ 81] D. M. Dias and J. R. Jump. Analysis and Simulation of Buffered Delta Networks. IEEE Transactions on Computers, Vol. 30, No. 10, October 1981, pp. 273-282.

Proposes and analyzes variants of Banyan networks where switching fabric elements have buffers.

[DLV 89] J. J. Deegan, G. W. R. Luderer, and A. K. Vaidya. Fast Packet Technology for Future Switches. AT&T Technical Journal, March-April 1989, pp. 36-50.

A survey of packet-switching technology.

[Duncanson 95] J. Duncanson. The Technology of Inverse Multiplexing. Available from HTTP://WWW.ASCEND.COM.AU/TECHDOCS/ARTICLES/IMUX/IMUX.HTML, 1995.

[Fraser 83] A. G. Fraser. Towards a Universal Data Transport System. IEEE Journal on Selected Areas in Communication, Vol. 1, No. 5, November 1983, pp. 803-816.

Describes the Datakit network, and in particular, the design of the second-generation Datakit switch.

[GCM 87] I. S. Gopal, I. Cidon, and H. Meleis. Paris: An Approach to Integrated Private Networks. Proceedings of ICC '87, June 1987, pp. 764-773.

Describes the PARIS ring-based second-generation packet switch.

[GHMSL 91] J. N. Giacopelli, J. J. Hickey, W. S. Marcus, W. D. Sincoskie, and M. Littlewood. Sunshine: A High-Performance Self-Routing Broadband Packet Switch Architecture. IEEE Journal on Selected Areas in Communication, Vol. 9, No. 8, October 1991, pp. 1289-1298.

Overview of the Sunshine Batcher-Banyan switch.

[GL 73] L. R. Goke and G. J. Lipovski. Banyan Networks for Partitioning Multiprocessor Systems. Proceedings of the 1st Annual International Symposium on Computer Architecture, December 1973, pp. 21-28.

The paper that first described Banyan switching fabrics.

[HA 87] J. Y. Hui and E. A. Arthurs. A Broadband Packet Switch for Integrated Transport. IEEE Journal on Selected Areas in Communication, Vol. 5, October 1987, pp. 1264-1273.

Proposes a scheme to avoid contention in Banyan switches by preceding a packet by a probe that determines whether a collision is possible.

[HK 84] A. K. Huang and S. Knauer. Starlite: A Wideband Digital Switch. Proceedings of GLOBECOM '84, Atlanta, December 1984, pp. 121-125.

Describes an early Batcher-Banyan switch with recirculation.

[HK 88] M. G. Hluchyj and M. J. Karol. Queueing in Space-Division Packet Switching. Proceedings of IEEE INFOCOM '88, New Orleans, March 1988, pp. 334-343.

A study of buffer-placement strategies in third-generation switches.

[Jacob 90] A. R. Jacob. A Survey of Fast Packet Switches. ACM SIGCOMM Computer Communication Review, Vol. 20, No. 1, January 1990, pp. 54-64.

A survey of third-generation switches.

[Jenq 83] Y. C. Jenq. Performance Analysis of a Packet Switch Based on a Single-Buffered Banyan Network. IEEE Journal on Selected Areas in Communication, Vol. 1, December 1983, pp. 1014-1021.

Analyzes the theoretical limits on the performance of Banyan switches with buffers in switching-fabric elements.

[Kanakia 94] H. Kanakia. Datapath Switch. AT&T Bell Laboratories Internal Technical Memorandum, 1994.

Describes the shared-memory Datapath switch-on-a-chip.

[KHM 87] M. J. Karol, M. G. Hluchyj, and S. P. Morgan. Input versus Output Queueing on a Space-Division Switch, IEEE Transactions on Communications, December 1987, pp. 1347-1356.

Classic paper proving that if traffic is uniformly distributed to all output ports, a single shared queue at the input leads to head-of-line blocking and a maximum achievable throughput of 58%.

[Lee 88] T. T. Lee. Nonblocking Copy Networks for Multicast Packet Switching. IEEE Journal on Selected Areas in Communications, Vol. 9, No. 9, December 1988, pp. 1455-1467.

Describes copy networks used in multicast switches.

[LPR 96] C. Lund, S. Phillips, and N. Reingold. Fair Prioritized Scheduling in an Input-Buffered Switch. Proceedings of Broadband '96, Montreal, April 1996.

Describes a modification to the parallel iterated matching algorithm in input-queued switches that allows an input-queued switch to emulate a multipriority round-robin discipline at an output-queued switch.

[Marcus 69] M. G. Marcus. The Design and Analysis of a New Type of Time-Division Switching System. M.Sc. Thesis, MIT, June 1969.

An early ATM switch design that introduces buffers at crosspoints.

[MAW 96] N. McKeown, V. Anantharam, and J. Walrand. Achieving 100% Throughput in an Input-Queued Switch. Proceedings of IEEE INFOCOM'96, San Francisco, March 1996.

A theoretical analysis of arbitration strategies in input-queued switches.

[McKeown 95] N. McKeown. Scheduling Algorithms for Input-Queued Cell Switches. Ph.D. Thesis, University of California at Berkeley, May 1995.

A survey of techniques for input-queued switches and an analysis of the SLIP approach to arbitration.

[NL 96] P. Newman and T. Lyon. Flow Labeled IP: A Connectionless Approach to ATM. Proceedings of IEEE INFOCOM'96, March 1996.

Describes a second-generation switch where a flow of IP-over-ATM packets automatically sets up a call in an ATM switch.

[OSMKM 90] Y. Oie, T. Suda, M. Murata, D. Kolson, and H. Miyahara. Survey of Switching Techniques in High-Speed Networks and Their Performance. Proceedings of IEEE INFOCOM '90, June 1990, pp. 1242-1251. >

A survey of third-generation switches.

[Perlman 92] R. Perlman. Interconnections: Bridges and Routers. Addison-Wesley, 1992.

An excellent description of an engineering approach to designing and building routers and bridges.

[Scorpio 95] Scorpio Inc. Description of the Scorpio ATM Switch. Available from HTTP://WWW.SCORPIO.COM, 1995.

This site has a detailed description of the Scorpio buffered crossbar switch.

[TKC 91] F. A. Tobagi, T. Kwok, and F. Chiussi. Architecture, Performance, and Implementation of a Tandem Banyan Fast Packet Switch. IEEE Journal on Selected Areas in Communication, Vol. 9, October 1991, pp. 1173-1193.

Proposes and analyzes the Tandem Banyan switch, where several banyan fabrics are linked in tandem to reduce blocking.

[Tobagi 90] F. A. Tobagi. Fast Packet Switching Architectures for Broadband Integrated Services Digital Networks. Proceedings of IEEE, Vol. 78, No. 1, November 1990, pp. 133-167.

A survey of third-generation packet switches.

[Turner 85] J. S. Turner. Design of Integrated Services Packet Network. Proceedings of 9th ACM Data Communication Symposium, September 1985, pp. 124-133.

Describes an early buffered Banyan switch design and its role in providing both voice and data service.

[Turner 88] J. S. Turner. Design of a Broadcast Packet Switched Network. IEEE Transactions on Communications, Vol. 36, June 1988, pp. 734-743.

Describes an early buffered Banyan switch design that allows muticast and broadcast.

[TW 83] J. S. Turner and L. F. Wyatt. A Packet Network Architecture for Integrated Services. Proceedings of GLOBECOMM '83, San Diego, Nov. 1993, pp. 2.1.1-2.1.6.

Early description of a buffered Banyan switch design.

[Vries 90] R. J. F. de Vries. Gauss: A Simple High Performance Switch Architecture for ATM. Proceedings of ACM SIGCOMM '90, September 1990, pp. 126-134.

Describes the Gauss switch, which is based on output queueing and a variation of the knockout principle.

[YHA 87] Y. S. Yeh, M. G. Hluchyj, and A. S. Acampora. The Knockout Switch: A Simple, Modular Architecture for High-Performance Packet Switching. IEEE Journal on Selected Areas in Communication, Vol. 5, October 1987, pp. 1426-1435.

Describes the knockout principle and a switch based on this principle.

References for Chapter 9: Scheduling

[BG 92] D. Bertsekas and R. Gallager. Data Networks, Second Edition. Prentice Hall, 1992.

Classic textbook on computer networking from a formal, algorithmic perspective.

[BK 93] A. Banerjea and S. Keshav. Queueing Delays in Rate-Controlled Networks. Proceedings of IEEE INFOCOM '93, San Francisco, 1993.

Gives an algorithm to compute the worst-case delay over a network of rate-controlled servers, taking internal burstiness into account.

[Brown 88] R. Brown. Calendar Queues: A Fast 0(1) Priority Queue Implementation for the Simulation Event Set Problem. Communications of the ACM, Vol. 31, No. 10, October 1988.

Describes the design and evaluation of a calendar queue.

[BZ 96] J. C. R. Bennet and H. Zhang. WF²Q: Worst-Case Fair Weighted Fair Queueing. Proceedings of IEEE INFOCOM '96, San Francisco, 1996.

Describes WF²Q and proves that the service received under this discipline is no more than one packet ahead or behind GPS.

[CR 96] A. Charny and K. K. Ramakrishnan. Time Scale Analysis of Explicit Rate Allocation in ATM Networks. Proceedings of IEEE INFOCOM '96, March 1996.

Derives a minimum bound on the time taken for a distributed computation of a globally max-min fair allocation. Shows that in order to avoid overloading switches, each source must adapt its rate only after a delay.

[CSZ 92] D. D. Clark, S. Shenker, and L. Zhang. Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism. Proceedings of ACM SIGCOMM '92, Baltimore, August 1992.

Presents a framework for real-time service on the Internet. Describes predictive service, FIFO+, and the concepts of sharing and isolation.

[DH 90] J. Davin and A. Heybey. A Simulation Study of Fair Queueing and Policy Enforcement. Computer Communication Review, Vol. 20, No, 5, October 1990, pp. 23-29.

Studies how WFQ can be used to implement isolation policies. Proposes self-clocking, though without proving that it is a valid emulation of GPS.

[DKS 89] A. Demers, S. Keshav, and S. Shenker. Design and Analysis of a Fair Queueing Algorithm. Proceedings of ACM SIGCOMM '89, Austin, September 1989.

Presents GPS and WFQ. Simulations show that it is effective in protecting well-behaved sources from misbehaving ones.

[FJ 93] S. Floyd and V. Jacobson. Random Early Detection Gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking, August 1993.

Presents the RED policy. Simulations show its effectiveness and compare it with drop-from-tail.

[FV 90] D. Ferrari and D. Verma. A Scheme for Real-Time Channel Establishment in Wide-Area Networks. IEEE Journal on Selected Areas in Communication, Vol. 8, No. 3, April 1990, pp. 368-379.

Proposes Delay-EDD and a framework for providing end-to-end delay and bandwidth bounds using a combination of resource reservation and admission control. Describes deterministic and statistical performance bounds.

[GGPS 96] L. Georgiadis, R. Guerin, V. Peris, and K. N. Sivarajan. Efficient Network QoS Provisioning Based on Per-Node Traffic Shaping. Proceedings of IEEE INFOCOM '96, March 1996.

Shows that with proper choice of regulators, end-to-end delay bounds with rate-controlled disciplines are the same as or better than with GPS emulations.

[GLV 95] P. Goyal, S. Lam, and H. Vin. Determining End-to-End Delay Bounds in Heterogeneous Networks. Proceedings of Fifth International Workshop on Network and Operating System Support for Digital Audio and Video, Durham, NH, April 1995, pp. 287-298.

Proposes a unified framework for determining end-to-end delays over networks of GPS-emulation schedulers.

[GM 92] A. G. Greenberg and A. N. Madras. How Fair Is Fair Queueing? Journal of the ACM, Vol. 3, No. 39, 1992.

Proves a one-sided absolute fairness bound for WFQ.

[Golestani 90a] S. Jamaloddin Golestani. Congestion-Free Transmission of Real-Time Traffic in Packet Networks. Proceedings of IEEE INFOCOM '90, San Francisco, June 1990, pp. 527-542.

Presents the stop-and-go discipline and proves delay and delay-jitter bounds.

[Golestani 90b] S. Jamaloddin Golestani. A Stop-and-Go Queueing Framework for Congestion Management. Proceedings of ACM SIGCOMM '90, Philadelphia, September 1990, pp. 8-18.

Extends stop-and-go to allow multiple frame times.

[Golestani 94] S. Jamaloddin Golestani. A Self-Clocked Fair Queueing Scheme for Broadband Applications. Proceedings of IEEE INFOCOM '94, Toronto, June 1994, pp. 636-646.

Presents and analyzes the SCFQ disciplines. Proposes the relative fairness bound as a metric of how well a discipline emulates GPS.

[GV 95] P. Goyal and H. Vin. Generalized Guaranteed Rate Scheduling Algorithms: A Framework. Technical Report TR-95-30, University of Texas, Austin, September 1995.

Presents a framework for computing end-to-end delay bounds for GPS-emulations and Delay-EDD. Extends the bounds in [GLV 95] for the case when every packet on a connection can be served with a different service rate, and when packets are fragmented and reassembled within the network.

[GVC 96] P. Goyal, H. Vin, and H. Chen. Start-Time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks. Proceedings of ACM SIGCOMM '96, August 1996.

Describes a variant of self-clocked fair queueing called start-time fair queueing. Shows that the discipline is fair, provides throughput and delay bounds, and is easy to implement.

[Hashem 89] E. Hashem. Analysis of Random Drop for Gateway Congestion Control. Technical Report LCS/TR-465, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1989.

Compares early-random-drop, random-drop, and drop-from-tail drop policies.

[HLP 91b] J. Hyman, A. Lazar, and G. Pacifici. Real-time Scheduling with Quality of Service Constraints. IEEE Journal on Selected Areas in Communication, Vol. 9, No. 9, September 1991.

Introduces the notion of a schedulable region and shows its importance in system stability.

[Keshav 91] S. Keshav. On the Efficient Implementation of Fair Queueing. Journal of Internetworking Research and Experience, Vol. 2, No. 3, September 1991.

Presents and compares several techniques for efficiently implementing WFQ.

[KKK 90] C. R. Kalmanek, H. Kanakia, and S. Keshav. Rate Controlled Servers for Very High-Speed Networks. Proceedings of Globecom '90, San Diego, December 1990, pp. 300.3.1-300.3.9.

Describes HRR scheduling and two fast implementations of the discipline. Simulations evaluate its effectiveness.

[Kleinrock 75] L. Kleinrock. Queueing Systems, Volume 2: Computer Applications. Wiley Interscience, 1975.

Classic textbook on queueing theory.

[LNO 95] T. V. Lakshman, A. Neidhardt, and T. J. Ott. The Drop from Front Strategy in TCP and in TCP over ATM. Proceedings of IEEE INFOCOM '96.

Evaluates the performance of drop-from-head drop policy and shows that this reduces the time taken for a source to detect a loss.

[Nagle 87] J. Nagle. On Packet Switches with Infinite Storage. IEEE Transactions on Communications, Vol. 35, No. 4, April 1987, pp. 435-438.

Shows that even with infinite storage, if packets have a time-to-live, there can still be significant packet loss. Proposes round-robin scheduling to give a source an incentive to reduce its flow rate when the network is congested.

[Parekh 92] A. K. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. Ph.D. Dissertation, issued as Technical Report LIDS-TH-2089, Massachusetts Institute of Technology, Cambridge, MA 02139, February 1992.

Analysis of end-to-end delay bounds with networks of WFQ schedulers.

[Partridge 91] C. Partridge. Isochronous Applications Do Not Require Jitter-Controlled Networks. RFC 1257, September 1991.

Lays out the case against the need for delay-jitter control in integrated services networks.

[PG 93] A. K. Parekh and R. G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services NetworksæThe Single Node Case. IEEE/ACM Transactions on Networking, June 1993, pp. 344-357.

Single-hop delay bounds for a WFQ scheduler.

[PG 94] A. K. Parekh and R. G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services NetworksæThe Multiple Node Case. IEEE/ACM Transactions on Networking, April 1994, pp. 137-150.

Analysis of end-to-end delay bounds with networks of WFQ schedulers.

[Restrick 94] R.C. Restrick. Personal communication, 1994.

[RF 94] A. Romanow and S. Floyd. The Dynamics of TCP Traffic over ATM Networks. Proceedings of ACM SIGCOMM '94, September 1994.

Shows that when TCP/IP packets are carried as AAL5 frames, cell losses are multiplied. Shows that this effect is reduced with random early drop.

[Shenker 90] S. Shenker. A Theoretical Analysis of Feedback Flow Control. Proceedings of ACM SIGCOMM '90, Philadelphia, September 1990, pp. 156-165.

Analyzes the fairness, stability, and time-scale invariance of scheduling disciplines when used in conjunction with an ensemble of feedback-flow-controlled sources.

[SV 95b] M. Shreedhar and G. Varghese. Efficient Fair Queueing Using Deficit Round Robin. Proceedings of ACM SIGCOMM '95, Boston, September 1995.

Describes DRR and evaluates its effectiveness.

[SV 96] S. Stiliadis and A. Verma. Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms. Proceedings of IEEE INFOCOM '96, 1996.

Describes latency-rate servers, which emulate GPS, and computes end-to-end delay bounds for networks of LR servers.

[VZF 91] D. Verma, H. Zhang, and D. Ferrari. Guaranteeing Delay Jitter Bounds in Packet Switching Networks. Proceedings of Tricomm '91, Chapel Hill, NC, April 1991.

Describes J-EDD and evaluates its effectiveness.

[ZF 93] H. Zhang and D. Ferrari. Rate-Controlled Static Priority Queueing. Proceedings of IEEE INFOCOM '93, San Francisco, 1993 pp. 227-236.

Proposes RCSP and presents theorems to compute delay and delay-jitter bounds with networks of RCSP servers.

[ZF 94] H. Zhang and D. Ferrari. Rate-Controlled Service Disciplines. Journal of High Speed Networking, Vol. 3, No. 4, 1994, pp. 389-412.

Generalizes RCSP to RC schedulers and proves some theorems about their properties.

[Zhang 89] L. Zhang. A New Architecture for Packet Switching Network Protocols. Technical Report MIT/LCS/TR-455, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge MA, August 1989.

Proposes and analyzes the Virtual Clock discipline. Proposes end-to-end quality of service for flows, which are like connections. Also studies large-scale oscillations with networks of TCP sources.

[Zhang 90] L. Zhang. Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks. Proceedings of ACM SIGCOMM '90, Philadelphia, September 1990.

A shorter description and analysis of the Virtual Clock algorithm.

[Zhang 95] H. Zhang. Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks. Proceedings of IEEE, October 1995.

A survey of scheduling disciplines and their performance bounds.

[ZK 91] H. Zhang and S. Keshav. Comparison of Rate-Based Service Disciplines. Proceedings of ACM SIGCOMM '91, Zurich, 1991.

Compares Delay-EDD, WFQ, Virtual Clock, Jitter-EDD, HRR, and SnG for cell-smooth input traffic.

References for Chapter 10: Naming and Addressing

[DH 96] S. Deering and R. Hinden. IP Version 6 Addressing Architecture. RFC-1884, January 1996.

The authoritative reference for IP version 6 addressing.

[Droms 93] R. Droms. Dynamic Host Configuration Protocol. RFC-1531, October 1993.

Describes the design, features, and details of the DHCP protocol.

[Huitema 94] C. Huitema. The H Ratio for Address Assignment Efficiency. RFC-1715, November 1994.

Computes the number of IPv6 addresses per square meter of the earth's surface.

[ISO 93] ISO/IEC Information Processing SystemsæData Communications: Network Service Definition. International Standard 8348, ISO/IEC JTC 1, Switzerland, 1993.

International standard describing NSAPs.

[ITU-E.164] Recommendation E.164/I.331æNumbering Plan for the ISDN Era. International Teletraffic Union, available from HTTP://WWW.ITU.CH/.

International standard describing telephone numbers.

[Laubach 94] M. Laubach. Classical IP and ARP over ATM. RFC 1577, January 1994.

[LR 95] T. Li and Y. Rekhter. An Architecture for IPv6 Unicast Address Allocation. RFC-1887, December 1995.

A proposed architecture for unicast address allocation that describes how to use additional levels of hierarchy in the address, and how to encode topological hints to reduce routing overheads.

[MD 88] P. Mockapetris and K. J. Dunlap. Development of the Domain Name System. Proceedings of ACM SIGCOMM '88, Stanford, August 1988.

Excellent description of the design and operation of the Domain Name System.

[Mockapetris 87] P. Mockapetris. Domain NamesæImplementation and Specification. RFC-1035, November 1987.

[Partridge 86] C. Partridge. Mail Routing and the Domain System. RFC 794, January 1986.

Describes how MX records work.

[Plummer 82] D. C. Plummer. An Ethernet Address Resolution Protocol. RFC-826, November 1982.

Describes ARP.

References for Chapter 11: Routing

[Akinpelu 84] J. M. Akinpelu. The Overload Performance of Engineered Networks with Non-Hierarchical Routing. AT&T Technical Journal, Vol. 63, No. 7, September 1984, pp. 1261-1281.

Shows the existence of metastability in DNHR and the need for trunk reservation.

[BE 90] L. Breslau and D. Estrin. Design of Inter-Administrative Domain Routing Protocols. Proceedings of ACM SIGCOMM '90, Philadelphia, September 1990.

Overview of issues in designing policy routing protocols between autonomous systems.

[Bellman 57] R. E. Bellman. Dynamic Programming. Princeton University Press, 1957.

Classic text with first description of distance-vector routing.

[BFC 93] A. Ballardie, P. Francis, and J. Crowcroft. Core Based Trees (CBT): An Architecture for Scalable Inter-Domain Multicast Routing. Proceedings of ACM SIGCOMM '93, San Francisco, August 1993.

[Braden 89] R. Braden. Requirements for Internet HostsæCommunication Layers. RFC 1122, 1989.

Exhaustive list of requirements that hosts attached to the Internet ought to obey.

[Clark 89] D. D. Clark. Policy Routing in Internet Protocols. RFC-1102, May 1989.

Early paper on policy routing.

[CRKG 89] C. Cheng, R. Riley, S. Kumar, and J. J. Garcia-Luna-Aceves. A Loop-Free Extended Bellman-Ford Routing Protocol without Bouncing Effect. Proceedings of ACM SIGCOMM '89, Austin, September 1989.

One of the two papers on source tracing.

[Deering 91a] S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D. Thesis, Stanford University, 1991.

Classic Ph.D. thesis that lays out the basic ideas in Internet multicast.

[Deering 91b] S. Deering. ICMP Router Discovery Messages. RFC-1256, September 1991.

[DEFJLW 94] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C.-G. Lue, and L. Wei. An Architecture for Wide-Area Multicast Routing. Proceedings of ACM SIGCOMM '94, London, September 1994.

Describes the PIM approach to IP multicast.

[Dijkstra 59] E. W. Dijkstra. A Note on Two Problems in Connection with Graphs. Numerical Mathematics, October 1959.

Presents the famous algorithm for computing shortest paths in graphs.

[DM 78] Y. Dalal and R. Metcalfe. Reverse Path Forwarding of Broadcast Packets. Communications of the ACM, Vol. 21, December 1978, pp. 1040-1048.

First description of reverse path forwarding for flooding.

[Estrin 89] D. Estrin. Policy Requirements for Inter-Administrative Domain Routing. RFC-1125, November 1989.

[FF 62] L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.

Another classic paper on distance-vector routing.

[Garcia-Luna-Aceves 89] J. J. Garcia-Luna-Aceves. A Unified Approach to Loop-Free Routing Using Distance Vectors or Link States. Proceedings of ACM SIGCOMM '89, Austin, September 1989.

Describes DUAL loop-free distance-vector routing.

[Girard 90] A. Girard. Routing and Dimensioning in Circuit-Switched Networks. Addison-Wesley, 1990.

A good introduction to the area.

[Halpern 96] J. M. Halpern. The Architecture and Status of PNNI. HTTP://WWW.VIVID.NEWBRIDGE.COM/DOCUMENTS/JOEL.HTML, 1996.

A concise and informative description of PNNI routing.

[Hedrick 88] C. Hedrick. Routing Information Protocol. RFC 1058, June 1988.

[Huitema 95] C. Huitema. Routing in the Internet. Prentice Hall, 1995.

Excellent description of Internet routing protocols.

[Kelly 88] F. P. Kelly. Routing in Circuit-Switched Networks: Optimization, Shadow Prices, and Decentralization. Advances in Applied Probability, Vol. 20, 1988.

Describes how to compute and use shadow prices for routing in telephone networks.

[Kelly 91] F. P. Kelly. Loss Networks. The Annals of Applied Probability, 1991, pp. 319-378.

Exhaustive survey of recent research in routing in telephone networks.

[KZ 89] A. Khanna and J. Zinky. The Revised ARPANET Routing Metric. Proceedings of ACM SIGCOMM'89, August 1989.

Describes problems with the older routing metric and the hop-normalized cost used to correct these problems. Introduces the metric map and the network response map to study the dynamics of routing.

[LHH 95] W. C. Lee, M. G. Hluchyj, and P. A. Humblet. Routing Subject to QoS Constraints in Integrated Communication Networks. IEEE Networks Magazine, Vol. 9, No. 4, July/August 1995.

[ME 90] N. Maxemchuk and M. El Zarki. Routing and Flow Control in High-Speed Wide-Area Networks. Proceedings of IEEE, Vol. 78, No. 1, January 1990.

Broad survey of the field.

[Moy 91] J. Moy. OSPF Version 2. RFC-1247, July 1991.

[Moy 94] J. Moy. Multicast Extensions to OSPF. RFC-1584, March 1994.

[Perlman 83] R. Perlman. Fault-Tolerant Broadcast of Routing Information. Computer Networks, Vol. 7, 1983, pp. 395-405.

Classic paper on how to keep LSP databases sane and consistent.

[Perlman 92] R. Perlman. Interconnections: Bridges and Routers. Addison-Wesley, 1992. Introductory text on routing. Covers routing in ISO networks.

[RF 89] B. Rajagopalan and M. Faiman. A New Responsive Distributed Shortest-Path Routing Algorithm. Proceedings of ACM SIGCOMM '89, Austin, September 1989.

One of the two papers on source tracing.

[RL 95] Y. Rekhter and T. Li. A Border Gateway Protocol-4. RFC-1771, March 1995.

[Rosen 82] E. Rosen. Exterior Gateway Protocol. RFC-827, October 1982.

[Tsuchiya 91] P. F. Tsuchiya. Efficient and Robust Policy Routing Using Multiple Hierarchical Addresses. Proceedings of ACM SIGCOMM '91, Zurich, September 1991.

Describes a clever scheme for provider selection.

[WPD 88] D. Waitzman, C. Partridge, and S. Deering. Distance Vector Multicast Routing Protocol. RFC-1075, November 1988.

Standard reference for DVMRP.

References for Chapter 12: Error Control

[AMS 82] D. Anick, D. Mitra, and M. M. Sondhi. Stochastic Theory of Data-Handling System with Multiple Sources. Bell System Technical Journal, Vol. 61, No. 8, 1982, pp. 1871-1894.

This classic paper introduced fluid flow models and asymptotic analysis to study buffer sizing in multiplexors.

[BBP 88] R. Braden, D. A. Borman, and C. Partridge. Computing the Internet Checksum. RFC 1071, September 1988.

Tricks and advice in implementing the IP checksum (this checksum is also used in UDP and TCP).

[BC 92] C. C. Bissell and D. A. Chapman. Digital Signal Transmission. Cambridge University Press, 1992.

A technical introduction to digital transmission at the senior undergraduate level. Excellent treatment of telephone transmission and communication system design.

[BH 90] A. Bhargava and M. Hluchyj. Frame Losses Due to Buffer Overflows in Fast Packet Networks. Proceedings of IEEE INFOCOM '90, June 1990, pp. 132-139.

Models frame loss as a function of cell loss in framed networks.

[Biersack 92] E. Biersack. Performance Evaluation of Forward Error Correction in ATM Networks. Proceedings of ACM SIGCOMM '92, Baltimore, 1992.

Raises questions about the effectiveness of forward error correction, because of the additional load it generates.

[Blahut 90] R. E. Blahut. Digital Transmission of Information. Addison-Wesley, 1990.

[Bolot 93] J.-C. Bolot. End-to-End Delay and Loss Behavior in the Internet. Proceedings of ACM SIGCOMM '93, San Francisco, 1993.

Presents models for packet loss in the Internet based on periodic "ping"s.

[Bolot 95] J.-C. Bolot. Analysis of Audio Packet Loss in the Internet. Proceedings of Workshop on Networks and Operating Systems Support for Digital Audio and Video, April 1995, pp. 163-174.

Presents a model for audio packet loss; shows that FEC is effective for audio on the Internet.

[CKS 93] I. Cidon, A. Khamisy, and M. Sidi. Analysis of Packet Loss Processes in High-Speed Networks. IEEE Trans. On Information Theory, Vol 39, No. 1, January 1993.

Shows that losses are bursty, and that ignoring burstiness causes significant errors in analysis.

[CZL 87] D. D. Clark, L. Zhang, and M. Lambert. NETBLT: A High Throughput Transport Protocol. Proceedings of ACM SIGCOMM '87, 1987.

Overview of the NETBLT protocol, an early rate-based protocol that did selective acks on blocks.

[DJNS 93] B. T. Doshi, P. K. Johri, A. N. Netravali, and K. K. Sabnani. Error and Flow Control Performance of a High Speed Protocol. IEEE Transactions on Communications, Vol. 41, May 1993, pp. 707-720.

Analyzes the periodic state exchange protocol, comparing it with go-back-n and a form of selective ack.

[FKY 81] T. R. Fortesque, L. Kershenbaum, and B. Ydstie. Implementation of Self-Tuning Regulators with Variable Forgetting Factors. Automatica, Vol. 17, No. 6, 1981, pp. 831-835.

Describes exponential averagers with dynamically varying decay factors.

[Henderson 95] T. R Henderson. Design Principles and Performance Analysis of SSCOP: A New ATM Adaptation Layer Protocol. ACM Computer Communication Review, Vol. 25, No. 2, April 1995.

Describes Service Specific Connection-Oriented Protocol, a transport protocol used in ATM signaling.

[Jacobson 88] V. Jacobson. Congestion Avoidance and Control. Proceedings of ACM SIGCOMM '88, Stanford, 1988.

Classic paper on congestion-avoidance strategies in TCP.

[Jacobson 90] V. Jacobson. Modified TCP Congestion Avoidance Algorithm. End-to-end mailing list, April 1990. Available from FTP://FTP.ISI.EDU/END2END/END2END-INTEREST-1990.MAIL.

Describes the fast-retransmit algorithm in TCP.

[Jakes 93] W. C. Jakes (ed.). Microwave Mobile Communications. IEEE Press, 1993.

A classic text and standard reference on all aspects of cellular communications.

[KK 92] P. S. Khedkar and S. Keshav. Fuzzy Prediction of Timeseries. Proceedings of IEEE Conference on Fuzzy Systems, FUZZ-IEEE, March 1992.

Uses fuzzy logic to identify a system and decide an appropriate exponential decay factor.

[KM 97] S. Keshav and S. P. Morgan. SMART: Performance with Overload and Random Losses. Proceedings of IEEE INFOCOM '97, April 1997.

Describes SMART retransmission, and how it works with packet-pair.

[KP 87] P. Karn and C. Partridge. Improving Round-Trip Time Estimate in Reliable Transport Protocols. Proceedings of ACM SIGCOMM '87, 1987.

Details of Karn's algorithm to deal with estimating the round-trip time when packets have been retransmitted.

[Maxemchuk 75] N. F. Maxemchuck. Dispersity Routing in Store and Forward Networks. Ph.D. Thesis, University of Pennsylvania, May 1975.

Proposes the idea that a source can increase throughput and decrease loss probability by distributing data over several alternative paths simultaneously.

[Mukherjee 94] A. Mukherjee. On the Dynamics and Significance of Low Frequency Components of Internet Load. Journal of Internetworking: Research and Experience, Vol. 5, 1994, pp. 163-205.

An exhaustive measurement and modeling of Internet delay, loss, and reordering over long time periods.

[NRS 90] A. Netravali, W. D. Roome, and K. K. Sabnani. Design and Implementation of a High Speed Protocol. IEEE Transactions on Communications, Vol. 38, 1990, pp. 2010-2024.

Describes a transport protocol that introduces the idea of explicit periodic state exchange.

[PHS 95] C. Partridge, J. Hughes, and J. Stone. Performance of Checksums and CRCs over Real Data. Proceedings of ACM SIGCOMM '95, Cambridge, 1995.

[PW 72] W. W. Peterson and E. J. Welden. Error Correcting Codes. John Wiley and Sons, 1972.

Standard reference on error-correcting codes.

[RF 94] A. Romanow and S. Floyd. Dynamics of TCP Traffic over ATM Networks. Proceedings of ACM SIGCOMM '94, London, 1994.

Studies the effect of error multiplication on TCP throughput in ATM networks.

[Sarwate 88] D. Sarwate. Computation of Cyclic Redundancy Checks via Table Look-up. Communications of the ACM, August 1988, pp. 1008-1013.

Presents a simple algorithm for fast CRC computation.

[SD 78] C. Sunshine and Y. Dalal. Connection Management in Transport Protocols. Computer Networks, Vol. 2, No. 6, 1978, pp. 454-473.

Classic reference on connection management, with analysis of connection establishment and termination in connectionless networks.

[Stallings 88] W. Stallings. Data and Computer Communication, Second Edition. Macmillan, 1988.

Standard textbook on computer networking.

[Watson 81] R. Watson. Timer-Based Mechanisms in Reliable Transport Protocol Connection Management. Computer Networks 5, North-Holland, Amsterdam, 1981, pp. 47-56.

Describes implicit relationships that must hold in connection management protocols for reliable connection establishment and termination.

[Zhang 87] L. Zhang. Why TCP Timers Don't Work Well. Proceedings of ACM SIGCOMM '87, 1987.

A critique of timer mechanisms in general, with conclusions about why timers are needed, and when they should be used.

References for Chapter 13: Flow Control

[ABB 93] E. Altman, F. Baccelli, and J.-C Bolot. Discrete-Time Analysis of Adaptive Rate Control Algorithms. Proceedings of 5th International Conference on Data Communications, Raleigh, NC, October 1993, pp. 121-140.

Analyzes the one-step-ahead predictive control scheme used in the MK and packet-pair schemes and shows that they are stable even when taking the nonlinearity at the endpoints of the control into account. Also proves that flow-control schemes that ignore the queue length are unstable.

[ADLY 95] J. S. Ahn, P. B. Danzig, Z. Liu, and L. Yan. Experience with TCP Vegas: Emulation and Experiment. Proceedings of ACM SIGCOMM '95, Boston, August 1995.

An emulation and simulation study of TCP-Vegas, which confirms its effectiveness both in simulations and over the Internet.

[BF 95] F. Bonomi and K. Fendick. The Rate-Based Flow Control Framework for the Available Bit Rate ATM Service. IEEE Network Magazine, March/April 1995, pp. 25-39.

An overview of the process leading to the ATM Forum's decision to adopt rate-based flow control, and a detailed description of the adopted scheme.

[BP 95] L. S. Brakmo and L. L. Peterson. TCP Vegas: End to End Congestion Avoidance on a Global Internet. IEEE Journal on Selected Areas in Communication, Vol. 13, No. 8, October 1995, pp. 1465-1480.

Describes the TCP-Vegas scheme and evaluates its performance.

[BW 92] A. W. Berger and W. Whitt. The Impact of a Job Buffer in a Token-Bank Rate-Control Throttle. Stochastic Models, Vol. 8, 1992, pp. 685-717.

Proves that the parameter important in a leaky bucket is the sum of the data buffer and the token bucket.

[CJ 89] D.-M Chiu and R. Jain, Analysis of Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks. Computer Networks and ISDN Systems, Vol. 17, 1989, pp. 1-14.

A control-theoretic analysis that shows that additive-increase-multiplicative-decrease is the only stable control algorithm for dynamic window flow control.

[CLZ 88] D. D. Clark, M. L. Lambert, and L. Zhang. NETBLT: A High Throughput Transport Protocol. Proceedings of ACM SIGCOMM '88, Stanford, August 1988.

Describes the insights that went into the design of NETBLT and gives an overview of its operation.

[Cruz 87] R. L. Cruz. A Calculus for Network Delay and a Note on Topologies of Interconnection Networks. Ph.D. Thesis, University of Illinois, issued as Report UILU-ENG-87-2246, July 1987.

The first analysis of the worst-case end-to-end delay suffered by a leaky-bucket controlled source. Introduces LBAP-constrained sources.

[DKS 89] A. Demers, S. Keshav, and S. Shenker. Analysis and Simulation of a Fair Queueing Algorithm. Proceedings of ACM SIGCOMM '89, Austin, August 1989.

Describes the fair queueing algorithm and evaluates its effectiveness in many simulated scenarios. Early comparison of DECbit and JK algorithms.

[Floyd 91] S. Floyd. Connections with Multiple Congested Gateways in Packet-Switched Networks, Part 1: One-Way Traffic. ACM Computer Communications Review, Vol. 21, No. 5, October 1991, pp. 30-47.

A detailed simulation study of TCP performance in a multihop congested network.

[Fraser 83] A. G. Fraser. Towards a Universal Data Transport System. IEEE Journal on Selected Areas in Communication, Vol. 1, No. 5, November 1983, pp. 803-816.

Describes the motivations for, and design of, the Datakit network.

[Fraser 91] A. G. Fraser. Designing a Public Data Network. IEEE Communications Magazine, October 1991, pp. 31-35.

Describes technology trends and requirements for building a public data network.

[FV 90] D. Ferrari and D. C. Verma. A Scheme for Real-Time Channel Establishment in Wide-Area Networks. IEEE Journal on Selected Areas in Communications, Vol. 8, No. 3, April 1990, pp. 368-379.

Classic paper describing a scheme for providing real-time performance guarantees to connections by using a combination of resource reservation, admission control, and intelligent packet scheduling.

[GF 95] A. Gupta and D. Ferrari. Resource Partitioning for Multi-Party Real-Time Communication. IEEE/ACM Transactions on Networking, October 1995.

Describes issues and algorithms in partitioning a resource among services such as real-time and best-effort communication.

[GKT 95] M. Grossglauser, S. Keshav, and D. Tse. RCBR: A Simple and Efficient Service for Multiple Time-Scale Traffic, Proceedings of ACM SIGCOMM '95, Boston, September 1995.

Proposes renegotiated constant-bit-rate service as a viable alternative for providing service to video streams that show slow-time-scale variations in the traffic rate.

[Golestani 90] S. J. Golestani. A Stop-and-Go Queueing Framework for Congestion Management. Proceedings of ACM SIGCOMM '90, Philadephia, September 1990.

Proposes the (r,T) moving-average descriptor for traffic, as part of the stop-and-go congestion management framework.

[GVSS 96] P. Goyal, H. Vin, C. Shen, and P. Shenoy. A Reliable, Adaptive Network Protocol for Video Transport. Proceedings of INFOCOM '96, San Francisco, 1996.

Improves on Kung and Chapman's buffer and delay bounds by a detailed analysis of the credit update protocol and by estimating the future bandwidth requirements of each connection.

[HKM 91] E. L. Hahne, C. R. Kalmanek, and S. P. Morgan. Fairness and Congestion Control on a Large ATM Data Network with Dynamically Adjustable Windows. 13th International Teletraffic Congress, Copenhagen, June 1991.

Description and evaluation of the DAWM scheme.

[Hoe 96] J. C. Hoe. Improving the Start-up Behavior of a Congestion Control Scheme for TCP. Proceedings of ACM SIGCOMM '96, Stanford, August 1996.

Improves TCP performance by better estimating initial parameters and dealing better with multiple losses.

[Jacobson 88] V. Jacobson. Congestion Avoidance and Control. Proceedings of ACM SIGCOMM '88, Stanford, August 1988.

Classic paper describing the modifications to TCP subsequently called TCP-Tahoe.

[KBC 94] H. T. Kung, T. Blackwell, and A. Chapman. Credit-Based Flow Control for ATM Networks: Credit Update Protocol, Adaptive Credit Allocation, and Statistical Multiplexing. Proceedings of ACM SIGCOMM '94, London, September 1994, pp. 101-114.

Studies the credit update protocol's behavior in many scenarios. Proposes overbooking of buffers at the downstream switch to cut down on buffer requirements.

[KC 93], H. T. Kung and A. Chapman. The Flow-Controlled Virtual Channels Proposal for ATM Networks. Proceedings of 1993 International Conference on Network Protocols, San Francisco, 1993, pp. 116-127.

The first description of the hop-by-hop credit-based scheme.

[Keshav 91] S. Keshav. A Control-Theoretic Approach to Flow Control. Proceedings of ACM SIGCOMM '91, Zurich, September 1991.

Proposes packet-pair flow control and uses control theory to analyze its performance.

[Keshav 97] S. Keshav. Packet-pair Flow Control. IEEE/ACM Transactions on Networking, to appear, 1997.

A detailed description and performance analysis of packet-pair flow control.

[KK 92] P. S. Khedkar and S. Keshav. Fuzzy Prediction of Timeseries. Proceedings of IEEE Conference on Fuzzy Systems, FUZZ-IEEE, March 1992.

Uses fuzzy logic to identify a system and decide an appropriate exponential decay factor.

[KKM 93] H. R. Kanakia, S. Keshav, and P. P. Mishra. A Comparision of Congestion Control Schemes. Proceedings of Fourth Annual Workshop on Very High Speed Networks, Baltimore, Maryland, March 1993.

Compares the performance of several popular closed-loop flow control schemes on a benchmark of ten test scenarios.

[KM 95] H. T. Kung and R. Morris. Credit-Based Flow Control for ATM Networks. IEEE Network Magazine, March/April 1995, pp. 40-48.

An overview of the credit-based scheme.

[KM 97] S. Keshav and S. P. Morgan. SMART: Performance with Overload and Random Losses. Proceedings of IEEE INFOCOM '97, April 1997.

Describes SMART retransmission, and how it works with packet-pair.

[LM 95] T. V. Lakshman and U. Madhow. Performance Analysis of Window-Based Flow Control Using TCP/IP: the Effect of High Bandwidth-Delay Products and Random Loss. IFIP Transactions C-26, High Performance Networking V, North-Holland, 1994, pp. 135-150.

Detailed analysis of TCP-Tahoe and TCP-Reno behavior with and without random losses.

[Low 92] S. Low. Traffic Management of ATM Networks: Service Provisioning, Routing, and Traffic Shaping, Ph.D. Thesis, U.C. Berkeley, 1992.

Proves the basic theorems on bottleneck behavior and flow control.

[MK 92] P. P. Mishra and H. R. Kanakia. A Hop-by-Hop Rate-based Congestion Control Scheme. Proceedings of ACM SIGCOMM '92, Baltimore, August 1992.

Describes the MK scheme.

[Mogul 93] J. C. Mogul. IP Network Performance. In Internet System Handbook (D. C. Lynch and M. T. Rose, eds.). Addison-Wesley, 1993, pp. 575-675.

Hints in improving TCP/IP performance for Internet administrators.

[Ogata 90] K. Ogata. Modern Control Engineering. Prentice Hall, 1990.

Standard text on control theory for engineers.

[OSV 94] C. Ozveren, R. Simcoe, and G. Varghese. Reliable and Efficient Hop-by-Hop Control. Proceedings of ACM SIGCOMM '94, London, September 1994, pp. 89-100.

Improves on the credit-based scheme by efficient sharing of downstream buffers while still avoiding loss.

[Rathgeb 91] E. Rathgeb. Modeling and Performance Comparison of Policing Mechanisms for ATM Networks. IEEE Journal on Selected Areas in Communications, Vol. 9, No. 3, April 1991, pp. 325-334.

Compares several traffic-policing schemes.

[RJ 88] K. K. Ramakrishnan and R. Jain. A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer. Proceedings of ACM SIGCOMM '88, Stanford, August 1988, pp. 303-313.

First description of the DECbit scheme.

[RJ 90] 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, 1990, pp. 158-181.

Detailed description of the DECbit scheme and its performance.

[RN 95] K. K. Ramakrishnan and P. Newman. Integration of Rate and Credit Schemes for ATM Flow Control. IEEE Network Magazine, March/April 1995, pp. 49-56.

Compares the relative merits of credit- and rate-based flow control, and proposes three ways in which we might combine them.

[Stevens 94] W. R. Stevens. TCP/IP Illustrated, Vol. 1. Addison-Wesley, 1994.

Comprehensive description of Internet protocols and TCP/IP as implemented in 4.4 BSD Unix.

[SZC 90] S. Shenker, L. Zhang, and D. D. Clark. Some Observations on the Dynamics of a Congestion Control Algorithm. ACM Computer Communication Review, 20(4), October 1990, pp. 30-39.

Simulation study of TCP's behavior with elementary analysis.

[Turner 86] J. Turner. New Directions in Communications (or Which Way to the Information Age?). IEEE Communications Magazine, Vol. 25, No. 10, pp. 8-15, October 1986.

A road map for research in high-speed networks. This paper is famous mostly for introducing the concept of a leaky bucket.

[Verma 91] D. Verma. Guaranteed Performance Communication in High Speed Networks. Ph.D. Thesis, U.C. Berkeley, issued as Technical Report UCB/CSD 91/663.

A thorough study of issues in open-loop flow control. Proposes jitter-control schemes with traffic reshapers and separation of rate control from delay management.

[ZSC 91] L. Zhang, S. Shenker, and D. D. Clark. Observations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic. ACM SIGCOMM '91, Zurich, 1991.

Simulation study of TCP in the presence of two-way traffic. Describes the ACK-compression phenomenon.

References for Chapter 14: Traffic Management

[BCS 94] R. Braden, D. Clark, and S. Shenker. Integrated Services in the Internet Architecture: An Overview. RFC 1633, available from FTP://DS.INTERNIC.NET, 1994.

Reviews the IETF service model.

[Bellamy 91] J. Bellamy. Digital Telephony, Second Edition. John Wiley and Sons, 1991.

A detailed introduction to telephone networking.

[BF 77] P. R. Boorstyn and H. Frank. Large-Scale Network Topological Optimization. IEEE Transactions on Communications, January 1977, pp. 29-47.

Studies how to optimize topology given a traffic matrix and call blocking requirement.

[Billingsley 95] P. Billingsley. Probability and Measure. Third Edition. John Wiley & Sons, 1995.

Advanced textbook on probability.

[BL 76] E. Bailey and E. Lindenberg. Peak Load Pricing Principles: Past and Present. In New Dimensions in Public Utility Pricing, MSU Public Utilities Studies, 1976.

Introduction to peak-load pricing.

[BT 92] P. E. Boyer and D. P. Tranchier. A Reservation Principle with Applications to ATM Traffic. Computer Networks and ISDN Systems, Vol. 24, 1992, pp. 321-334.

Discusses the fast-reservation procotol for BE traffic.

[Bulmer 79] M. G. Bulmer. Principles of Statistics. Dover Publications, 1979.

An elementary introduction to statistics, with historical anecdotes.

[BZ 96] J. C. R. Bennett and H. Zhang. Hierarchical Packet Fair Queueing Algorithms. Proceedings of ACM SIGCOMM '96, Stanford, August 1996.

Describe practical algorithms that simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link sharing.

[CLG 95] S. Chong, S. Q. Li, and J. Ghosh. Predictive Dynamic Bandwidth Allocation for Efficient Transport of Real-Time Video over ATM. IEEE Journal on Selected Areas in Communication, Vol. 13, No. 1, January 1995, pp. 12-23.

Describes techniques to predict compressed video traffic online to allow renegotiation.

[CWSA 95] J. Crowcroft, Z. Wang, A. Smith, and J. Adams. A Rough Comparison of the IETF and ATM Service Models. IEEE Network Magazine, Vol. 9, No, 6, November/December 1995.

[DB 95] L. Delgrossi and L. Berger (eds.). Internet Stream Protocol Version 2 (ST2) Protocol SpecificationæVersion ST2+, RFC 1819, August 1995.

[DJCME 92] P. Danzig, S. Jamin, R. Caceres, D. Mitzel, and D. Estrin. An Empirical Workload Model for Driving Wide-Area TCP/IP Network Simulations. Journal on Internetworking: Research and Experience, Vol. 3, No. 1, 1992, pp. 1-26.

[DMRW 94] D. Duffy, A. McIntosh, M. Rosenstein, and W. Willinger. Statistical Analysis of CCSN/SSN Traffic Data from Working CCS Subnetworks. IEEE Journal on Selected Areas in Communication, Vol. 12, No, 3, April 1994, pp. 544-551.

[EMW 95] A. Elwalid, D. Mitra, and R. H. Wentworth. A New Approach for Allocating Buffers and Bandwidth to Heterogeneous, Regulated Traffic in an ATM Node. IEEE Journal on Selected Areas in Communication, Vol. 13, No. 6, August 1995, pp. 1115-1127.

Extends the notion of equivalent bandwidth and shows that some sources are more multiplexable than others.

[Feldmann 95] A. Feldmann. On-line Call Admission for High-Speed Networks. Ph.D. Thesis, issued by School of Computer Science, Carnegie Mellon University as Technical Report CMU-CS-95-20, Pittsburgh, PA 15213, 1995.

A theoretical study of call-admission strategies, backed up by empirical studies of traffic behavior.

[FJ 95] S. Floyd and V. Jacobson. Link-Sharing and Resource Management Models for Packet Networks. IEEE Transactions on Networking, Vol. 3, No. 4., August 1995.

Describes link sharing.

[GAN 91] R. Guerin, H. Ahmadi, and M. Nagshineh. Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks. IEEE Journal on Selected Areas in Communication, Vol. 9, No. 7, September 1991, pp. 968-981.

Seminal paper on using equivalent bandwidth for admission control.

[Garrett 94] M. W. Garrett. ATM Service Architecture: From Applications to Scheduling, ATM Forum Contribution 94-0846 TM SWG, September 1994, available from FTP://THUMPER.BELLCORE.COM/PUB/MWG/ATM-FORUM.QOS.MWG.

Overview of the ATM Forum service model.

[GB 96] M. Grossglauser and J. Bolot. On the Relevance of Long-Range Dependence in Network Traffic. Proceedings of ACM SIGCOMM '96, September 1996.

Argues that with finite buffers and phenomena involving short time scales, long-range dependence may not affect performance.

[GG 92] R. Guerin and L. Gun. A Unified Approach to Bandwidth Allocation and Access Control in Fast Packet-Switched Networks. Proceedings of IEEE INFOCOM '92.

Shows how to estimate the burst parameters for a source, and the corresponding leaky-bucket regulator.

[GH 91] R. J. Gibbens and P. J Hunt. Effective Bandwidths for Multi-Type UAS Channel. Queueing Systems, Vol. 29, No. 10, October 1991, pp. 17-28.

Computes equivalent bandwidth for a call when sharing a buffer with other calls.

[GKT 95] M. Grossglauser, S. Keshav, and D. Tse. RCBR: A Simple and Efficient Service for Multiple Time-Scale Traffic. Proceedings of ACM SIGCOMM '95, Boston, September 1995.

Proposes renegotiated constant-bit-rate service as a viable alternative to provide service to video streams that show slow-time-scale variations in the traffic rate.

[Grossman 90] J. W. Grossman. Discrete Mathematics: An Introduction to Concepts, Methods, and Applications. Macmillan, 1990.

Introductory textbook.

[GW 94] M. Garrett and W. Willinger. Analysis, Modeling, and Generation of Self-Similar VBR Video Traffic. Proceedings of ACM SIGCOMM '94, London, September 1994.

[Henderson 95] T. R. Henderson. Design Principles and Performance Analysis of SSCOP: A New ATM Adaptation Layer Protocol. ACM Computer Communication Review, Vol. 25, No. 2, April 1995.

Describes Service Specific Connection-Oriented Protocol, a transport protocol used in ATM signaling.

[HL 96] D. P. Heyman and T. V. Lakshman. What Are the Implications of Long-Range Dependence for VBR Video Traffic Engineering? IEEE/ACM Transactions on Networking, Vol. 4, June 1996.

[JDSZ 95] S. Jamin, P. B. Danzig, S. Shenker, and L. Zhang. A Measurement-Based Admission Control Algorithm for Integrated Services Packet Networks. Proceedings of ACM SIGCOMM '95, Boston, September 1995.

Proposes measurement-based admission control for predictive service.

[Kalmanek 95] C.R. Kalmanek. Why Is Signaling Hard? Proceedings of Workshop on Open Signaling, Columbia University, October 1995.

[Kelly 91] F. P. Kelly. Loss Networks. The Annals of Applied Probability, 1991, pp. 319-378.

Exhaustive survey of recent research in routing in telephone networks.

[Keshav 91] S. Keshav. Congestion Control in Computer Networks. Ph.D. Thesis, U.C. Berkeley, issued as UCB Technical Report 91/469, August 1991.

[MS 90] A. Modarressi and R. A. Skoog. Signaling System No. 7: A Tutorial. IEEE Communications Magazine, July 1990, pp. 19-34.

A crisp summary of the SS7 protocol stack.

[Mukherjee 94] A. Mukherjee. On the Dynamics and Significance of Low Frequency Components of Internet Load. Journal of Internetworking: Research and Experience, Vol. 5, 1994, pp. 163-205.

A detailed examination of Internet behavior on the time scale of a day.

[MV 95] H. MacKie-Mason and H. R. Varian. Pricing Congestible Network Resources. IEEE Journal on Selected Areas in Communication, Vol. 13, No. 7, September 1995, pp. 1141-1149.

Shows the impact of flat-rate and congestion pricing on network behavior.

[PF 94] V. Paxson and S. Floyd. Wide-Area Traffic: The Failure of Poisson Modeling. Proceedings of ACM SIGCOMM '94, London, September 1994.

Uses measurements to claim that Poisson models do not adequately describe real traffic.

[Pressman 70] I. Pressman. A Mathematical Formulation of the Peak Load Pricing Problem. Bell Journal of Economics and Management Science, Vol. 1, Autumn 1970, pp. 304-326.

[RE 96] B. K. Ryu and A. Elwalid. The Importance of Long-Range Dependence of VBR Video Traffic in ATM Traffic Engineering: Myths and Realities. Proceedings of ACM SIGCOMM'96, September 1996.

[Roberts 92] J. W. Roberts, ed. Performance Evaluation and Design of Multiservice Networks. COST 224 Final Report, Commission of the European Communities, Brussels, 1992.

An analytical view of integrated services network design.

[SCZ 93] S. Shenker, D. Clark, and L. Zhang. A Scheduling Service Model and a Scheduling Architecture for an Integrated Services Packet Network. Working Paper, Xerox PARC, August 1993.

An early description of the service architecture that is being adopted by the IETF.

[Shenker 95] S. Shenker. Service Models and Pricing Policies for an Integrated Services Internet. In Public Access to the Internet (Brian Kahin and James Keller, Eds.). Prentice-Hall, 1995.

Uses simple economic models to formulate economic principles for traffic management.

[Shiryaev 96] A. N. Shiryaev. Probability, Springer Verlag, 1996.

Graduate textbook on probability.

[SW 95] A. Shwartz and A. Weiss. Large Deviations for Performance Analysis: Queues, Communications, and Computing. Chapman & Hall, New York, 1995.

A textbook that describes this powerful technique for queueing analysis.

[VPV 88] W. Verbiest, L. Pinnoo, and B. Voeten. The Impact of the ATM Concept on Video Coding. IEEE Journal on Selected Areas in Communication, December 1988, pp. 1623-1632.

Describes how to carry variable-bit-rate compressed traffic with ATM services.

[WTSW 95] W. Willinger, M.S. Taqqu, R. Sherman, and D.V. Wilson. Self-Similarity through High-Variability: Statistical Analysis and Ethernet LAN Traffic at the Source Level. Proceedings of ACM SIGCOMM'95, Boston, September 1995.

Proposes the superposition of heavy-tailed arrival processes as the mechanism giving rise to long-range dependence and self-similarity in aggregated traffic.

[ZDEZ 93] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. RSVP: A New Resource ReSerVation Protocol. IEEE Network Magazine, Vol. 7, No. 5, September 1993, pp. 8-19.

A description of the first version of the RSVP protocol. A formal description of the latest version is available online.

References for Chapter 15: Common Protocols

[AKS 96] R. Ahuja, S. Keshav, and H. Saran. Design, Implementation and Performance Measurement of a Native-Mode ATM Transport Protocol. IEEE/ACM Transactions on Networking, August 1996.

Describes the design and implementation of a task-based in-kernel transport layer that exploits AAL5 functionality in hardware to deliver high performance on cheap personal computers.

[ANSI 88] American National Standards Institute. ANSI T1.105-1988 American National Standard for Telecommunications, Digital Hierarchy-Optical Interface Rates and Formats Specifications, 1988.

SONET standard.

[Armitage 95a] G. J. Armitage. Multicast and Multiprotocol Support for ATM-based Internets, ACM SIGCOMM Computer Communication Review, Vol. 25, No. 2, April 1995.

Excellent tutorial on several approaches for carrying IP traffic over ATM networks.

[Armitage 95b] G. J. Armitage. Support for Multicast over UNI3.1-based ATM Networks, Internet Draft ·draft-ietf-ipatm-ipmc-04.txtÒ, February 1995.

Describes the MARS approach to IP multicast support in ATM LANs.

[BBP 88] R. Braden, D. A. Borman, and C. Partridge. Computing the Internet Checksum. RFC 1071, September 1988.

Tricks and advice in implementing the IP checksum (this checksum is also used in UDP and TCP).

[BC 92] C. C. Bissell and D. A. Chapman. Digital Signal Transmission. Cambridge University Press, 1992.

Excellent reference on the physical and datalink layers in telecommunication networks.

[Bellamy 91] J. Bellamy. Digital Telephony. John Wiley and Sons, New York, 1991.

A good introduction to telephone network engineering.

[Berners-Lee 94] T. Berners-Lee. Universal Resource Identifiers in WWW: A Unifying Syntax for the Expression of Names and Addresses of Objects on the Network as Used in the World Wide Web. RFC 1630, June 1994.

Formal definition of URIs and URLs.

[BFF 95] T. Berners-Lee, Roy T. Fielding, and H. Frystyk Nielsen. Hypertext Transfer Protocol, Version 1.0, Draft 5. HTTP://WWW.W3.ORG/HYPERTEXT/WWW/PROTOCOLS/OVERVIEW.HTML, 1995.

[BMM 94] T. Berners-Lee, L. Masinter, and M. McCahill. Uniform Resource Locators (URL), RFC 1738, December 1994.

[Brim 96] S. Brim (Ed.). Cells in Frames, Version 1.0: Specification, Analysis, and Discussion. HTTP://WWW.CIF.CORNELL.EDU, October 1996.

Rationale and specification of the Cells in Frame proposal.

[BZBHJ 96] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin. Resource ReSerVation Protocol (RSVP)æVersion 1, Functional Specification. Internet draft available from ftp://ietf.org/internet-drafts/draft-ietf-rsvp-spec-14.txt, March 1996.

Work in progress that describes the RSVP signaling protocol.

[EWLBCD 94] A. Edwards, G. Watson, J. Lumley, D. Banks, C. Calamvokis, and C. Dalton. User-Space Protocols Deliver High Performance to Applications on a Low-Cost Gb/s LAN. Proceedings of ACM SIGCOMM'94, London, September 1994.

[FFBGM 96] R. T. Fielding, H. Frystyk Nielsen, T. Berners-Lee, J. Gettys, and J. Mogul. Hypertext Transfer Protocol, Version 1.1, Draft 2. HTTP://WWW.W3.ORG/HYPERTEXT/WWW/PROTOCOLS/OVERVIEW. HTML, April 1996.

[GR 96] M. Grossglauser and K. K. Ramakrishnan. SEAM: Scalable and Efficient ATM Multipoint-to-Multipoint Multicasting. Proceedings of NOSSDAV '96, April 1996.

Describes a technique for efficient multipoint-to-multipoint multicast of AAL5 frames.

[Heinanen 93] J. Heinanen. Multiprotocol Encapsulation over ATM Adaptation Layer 5. RFC 1483, July 1993.

Describes how to encapsulate layer-3 protocols over AAL5, including IP.

[Henderson 95] T. R. Henderson. Design Principles and Performance Analysis of SSCOP: A New ATM Adaptation Layer Protocol. ACM Computer Communication Review, Vol. 25, No. 2, April 1995.

Describes the SSCOP transport protocol used in ATM signaling.

[HHS 94] R. Handel, M. N. Huber, and S. Schroder. ATM Networks: Concepts, Protocols and Applications. Addison-Wesley, 1994.

Introduction to ATM standards.

[Kent 91] S. T. Kent. U.S. Department of Defense Security Options for the Internet Protocol. RFC 1108, November 1991.

[KLPRS 95] S. Keshav, C. Lund, S. Phillips, N. Reingold, and H. Saran. An Empirical Evaluation of Virtual Circuit Holding Time Policies for IP-over-ATM Networks. IEEE Journal on Selected Areas in Communication, October 1995.

A description, analysis, and experimental study of several holding-time heuristics.

[KPCL 96] D. Katz, D. Piscitello, Bruce Cole, and James V. Luciani. NBMA Next Hop Resolution Protocol (NHRP). Internet Draft <draft-ietf-rolc-nhrp-07.txt,> January 96.

[Laubach 94] M. Laubach. Classical IP and ARP over ATM. RFC 1577, January 1994.

[LMKQ 89] S. J. Leffler, M. K. McKusick, M. J. Karels, and J. S. Quarterman. The Design and Implementation of the 4.3BSD UNIX Operating System. Addison-Wesley, 1989.

[MK 87] C. A. Kent and J. C. Mogul. Fragmentation Considered Harmful. Proceedings of ACM SIGCOMM '87, 1987.

An influential and insightful criticism of IP fragmentation.

[MK 90] T. Mallory and A. Kullberg. Incremental Updating of the Internet Checksum. RFC 1141, January 1990.

A trick that allows IP routers to recompute the header checksum (required because the TTL changes) without touching every byte of the header.

[MS 90] A. R. Modarressi and R. A. Skoog. Signaling System No. 7: A Tutorial. IEEE Communications Magazine, July 1990.

A crisp summary of the SS7 protocol stack.

[Pendarakis 96] D. Pendarakis. On the Tradeoff between Transport and Signaling in Broadband Network. Ph.D. thesis, Columbia University, April 1996.

Analyzes the trade-offs between signaling overhead and resource wastage in ATM networks with virtual paths.

[Postel 81] J. B. Postel. Internet Protocol. RFC 791, September 1981.

[Postel 81a] J. B. Postel. Internet Control Message Protocol. RFC 792, September 1981.

[Postel 81b] J. B. Postel. Transmission Control Protocol. RFC 793, September 1981.

[Rijsinghani 94] A. Rijsinghani. Computation of the Internet Checksum via Incremental Update. RFC 1624, 1994.

[Ritchie 84] D. Ritchie. A Stream Input-Output System. AT&T Bell Laboratories Technical Journal, Vol. 63, No. 8, 1984, pp. 1897-1910.

Classic reference on streams.

[RP 94] J. Reynolds and J. Postel. Assigned Numbers. RFC 1700, October 1994.

The standard set of protocol numbers, and port numbers assigned to services, in the Internet.

[SJ 95] K.-Y. Siu and R. Jain. A Brief Overview of ATM: Protocol Layers, LAN Emulation, and Traffic Management. ACM SIGCOMM Computer Communication Review, Vol. 25, No. 2, April 1995.

[Stevens 94] W. R. Stevens. TCP/IP Illustrated, Vol. 1. Addison-Wesley, 1994.

Comprehensive description of Internet protocols and TCP/IP as implemented in 4.4 BSD Unix.

[TELMP 95] H. Truong, W. Ellington, J. Le Boudec, A. Meier, and J. Pace. LAN Emulation on an ATM Network. IEEE Communications Magazine, Vol. 33, No. 5, May 1995, pp. 70-85.

Overview of LANE.

[ZDEZ 93] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. RSVP: A New Resource ReSerVation Protocol. IEEE Network Magazine, Vol. 7, No. 5, September 1993, pp. 8-19.

A tutorial on RSVP.

References for Chapter 16: Protocol Implementation

[AKS 96] R. Ahuja, S. Keshav, and H. Saran. Design, Implementation and Performance Measurement of a Native-Mode ATM Transport Protocol. IEEE/ACM Transactions on Networking, August 1996.

Describes the design and implementation of a task-based in-kernel transport layer that exploits AAL5 functionality in hardware to deliver high performance on cheap personal computers.

[CJRS 89] D. D. Clark, V. Jacobson, J. Romkey, and H. Salwen. An Analysis of TCP Processing Overhead. IEEE Communications Magazine, June 1989, pp 23-29.

Insightful analysis into why TCP processing can be slow, and how to make it fast.

[Clark 82] D. D. Clark. Modularity and Efficiency in Procotocol Implementation. RFC 817, July 1982.

Classic reference on protocol implementation strategies.

[Clark 85] D. D. Clark. The Structuring of Systems Using Upcalls. Proceedings of 10th ACM Symposium on Operating Systems Principles, December 1985, pp. 171-180.

Describes upcall architecture.

[CT 90] D. D. Clark and D. L. Tennenhouse. Architectural Considerations for a New Generation of Protocols. Proceedings of ACM SIGCOMM'90, Philadelphia, September 1990, p. 200-208.

Proposes controlled coalescing of protocol layers to improve performance.

[CV 95] A. M. Costello and G. Varghese. Redesigning the BSD Callout and Timer Facilities. Techical Report WUCS-95-23, Washington University, November 1995, available from HTTP://SIESTA.CS.WUSTL.EDU/~AMC/RESEARCH/TIMER/.

Details of implementing timing wheels in the BSD operating system

.

[DPD 94] P. Druschel, L. L. Peterson, and B. S. Davie. Experiences with a High-Speed Network Adaptor: A Software Perspective. Proceedings of ACM SIGCOMM'94, London, September 1994.

Describes performance tuning for high-performance host adaptors and application device channels.

[EM 95] A. Edwards and S. Muir. Experiences Implementing a High-Performance TCP in User-Space. Proceedings of ACM SIGCOMM '95, Cambridge, September 1995, pp. 196-205.

[EWLBCD 94] A. Edwards, G. Watson, J. Lumley, D. Banks, C. Calamvokis, and C. Dalton. User-Space Protocols Deliver High Performance to Applications on a Low-Cost Gb/s LAN. Proceedings of ACM SIGCOMM'94, London, September 1994.

[HP 91] N. Hutchinson and L. Peterson. The x-Kernel: An Architecture for Implementing Network Protocols. IEEE Transactions on Software Engineering, Vol. 17, No. 1, January 1991, pp. 64-76.

Describes a threads-based approach to protocol implementation.

[KP 93] J. Kay and J. Pasquale. The Importance of Non-Data-Touching Processing Overheads in TCP/IP. Proceedings of ACM SIGCOMM'93, San Francisco, September 1993, pp. 259-269.

[Mogul 93] J. Mogul. IP Network Performance. In Internet System Handbook (D. C. Lynch and M. T. Rose, Eds.). Addison-Wesley, 1993.

An exhaustive survey of techniques for measuring and improving IP performance.

[Mogul 95] J. Mogul. The Case for Persistent-Connection HTTP. Proceedings of ACM SIGCOMM'95, Cambridge, September 1995, pp. 299-313.

An analysis to show how HTTP wastes resources by opening a TCP connection per embedded object, and how to fix it.

[MRA 87] J. Mogul, R. F. Rashid, and M. J. Acetta. The Packet Filter: An Efficient Mechanism for User-Level Network Code. Proceedings of 11th ACM Symposium on Operating Systems Principles, November 1987, pp. 39-51.

Describes the packet-filter approach, where packets are demultiplexed in the kernel and handed directly to applications.

[PH 95] D. Patterson and J. Hennesey. Computer Organization and Design: The Hardware/Software Interface. Morgan Kaufman, 1995.

Standard introductory text on computer architecture.

[TNML 93] C. A. Thekkath, T. D. Nguyen, E. Moy, and E. D. Lazowska. Implementing Network Protocols at User Level. Proceedings of ACM SIGCOMM'93, San Francisco, September 1993.

Pioneering work on user-level protocol implementation.

[VBBV 95] T. von Eicken, A. Basu, V. Buch, and W. Vogels. U-Net: A User-Level Network Interface for Parallel and Distributed Computing. Proceedings of ACM Symposium on Operating Systems Principles, December 1995.

A high-performance user-level protocol implementation that emphasizes low-latency communication.

[VL 87] G. Varghese and T. Lauck. Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility. Proceedings of 11th ACM Symposium on Operating Systems Principles, November 1987, pp. 25-38.

[WM 87] R. Watson and S. Mamrak. Gaining Efficiency in Transport Services by Appropriate Design and Implementation Choices. ACM Transactions on Computer Systems, Vol. 5, No. 2, 1987, pp. 97-120.

Classic reference on protocol implementation techniques.



Updates

Errata

Click below for Errata related to this title:
Errata

Submit Errata

