Cover image for An engineering approach to computer networking : ATM networks, the internet, and the telephone network
Title:
An engineering approach to computer networking : ATM networks, the internet, and the telephone network
Personal Author:
Publication Information:
Reading, Mass. : Addison-Wesley, 1997
ISBN:
9780201634426

Available:*

Library
Item Barcode
Call Number
Material Type
Item Category 1
Status
Searching...
30000003660556 TK5105.5 K47 1997 Open Access Book Book
Searching...
Searching...
30000004125336 TK5105.5 K47 1997 Open Access Book Book
Searching...
Searching...
30000004378612 TK5105.5 K47 1997 Open Access Book Book
Searching...

On Order

Summary

Summary

Offers insight into the principles of network design as well as coverage of all essential networking topics: protocol layering, multiple access, switching, scheduling, naming, addressing, routing, error and flow control, and traffic management. The author's engineering approach involves identifying the fundamental constraints on the problem, making reasonable "real world" assumptions, and then examining the pros and cons of several alternative solutions. Annotation copyrighted by Book News, Inc., Portland, OR


Author Notes

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 .



0201634422AB04062001


Excerpts

Excerpts

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 Excerpted from An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network by Srinivasan Keshav All rights reserved by the original copyright owners. Excerpts are provided for display purposes only and may not be reproduced, reprinted or distributed without the written permission of the publisher.

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